Dominion Strategy Forum
Miscellaneous => General Discussion => Topic started by: WanderingWinder on January 30, 2015, 09:38:48 am
-
I feel like this should be simple, but having spent 15 minutes, I haven't cracked it yet. You guys are who I've come to.
Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?
Probably I need to explain this better. If the first trial is success, obviously we hit (1 of 1 is a majority). If after 3, we have 2+ out of 3, then we hit success, but these would already have been counted by the first one hitting, except for the case 011. etc etc. Probably there's a better way of going about this, but I haven't come up with it yet.
-
I'm not an expert in statistics by any means. But is it possible this analysis could apply?
http://www2.math.uu.se/~sea/kurser/stokprocmn1/slumpvandring_eng.pdf
In particular, section 2 ("The monkey at the cliff"). If the monkey falls off the cliff, that means the majority of steps have been towards the cliff, which is analogous to a majority of trials being successful. If I'm understanding correctly, the odds approach 1 if the odds of success are greater than or equal to the odds of failure. Otherwise, the odds are p/q.
-
I would look at this using stopping times ( http://en.wikipedia.org/wiki/Stopping_time ). I'll try it this afternoon or tonight if I have some time :-)
Edit : Should've taken the time to read the PDF first, my post is redundant.
-
ThAt's basically what the pdf does
-
I think WalrusMcFishSr's post is better, but here's an argument I thought up. (PPE: I think it's actually the same as the argument in the link, now that I've read the pdf more closely)
Think of it as a random walk, where we either travel +1 or -1 with equal probability. The question becomes P(visit +1 at any point, starting from state 0)
Let that be p. If the first trial is +1, then we've obviously made it, so
P(visit +1 at any point, starting from state 0) = 1/2 + 1/2 * P(visit +1 at any time, starting from -1)
To visit +1 starting from -1, we must first pass through 0, so
P(visit +1 at any time starting at 0) = 1/2 + 1/2 * P(visit 0 at any time starting from -1) * P(visit +1 at any time starting from 0)
The probabilities are the same under translation (we only care about walking right by 1, not where we start from), so this turns into
p = 1/2 + 1/2 * p^2
which has a solution at only p = 1
Edit: yep it for sure is the same argument. I also only solved it for when the random walk chance is 1/2, so you should just look at the pdf instead because that solves it generally.
-
Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?
If I understand the question right ("given an infinite number of trials, what is the probability that at any point the number of successes outnumber the number of failures"), the probability is 1 for any p > 0.
-
Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?
If I understand the question right ("given an infinite number of trials, what is the probability that at any point the number of successes outnumber the number of failures"), the probability is 1 for any p > 0.
A good rule of thumb is that whenever infinity is involved, you need to be very careful on your intuition. From the linked PDF, it turns out that the probability is 1 for p >= 1/2, and p / (1-p) for p < 1/2.
This sounds weird because if we do something an infinite number of times, surely we must have every possibility eventually happen. However, it turns out this isn't generally true. For example, a random walk in 2 dimensions returns to the origin with probability 1, but a random walk in 3 dimensions returns to the origin only around a third of the time. Usually, this comes down to the rate of growth for the two - for example, if the probability of getting a majority at time t+1 is 1/4 the probability of a majority at time t, then the probabilities decrease fast enough to make the sum across all times t not equal to 1.
-
Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?
If I understand the question right ("given an infinite number of trials, what is the probability that at any point the number of successes outnumber the number of failures"), the probability is 1 for any p > 0.
A good rule of thumb is that whenever infinity is involved, you need to be very careful on your intuition. From the linked PDF, it turns out that the probability is 1 for p >= 1/2, and p / (1-p) for p < 1/2.
This sounds weird because if we do something an infinite number of times, surely we must have every possibility eventually happen. However, it turns out this isn't generally true. For example, a random walk in 2 dimensions returns to the origin with probability 1, but a random walk in 3 dimensions returns to the origin only around a third of the time. Usually, this comes down to the rate of growth for the two - for example, if the probability of getting a majority at time t+1 is 1/4 the probability of a majority at time t, then the probabilities decrease fast enough to make the sum across all times t not equal to 1.
Yup, I misread the question as asking about an infinite number of random walks, rather than an infinite number of steps in a single random walk.
-
I consider myself an interested amateur with regards to statistics and probabilities, meaning I understand the simple problems but struggle with harder and counterintuitive ones.
So don't shoot if I'm way off base.
But my question is this: does this have something to do with entropy? I understand that when you keep shuffling a deck of cards, you don't automatically get back to the original order because you're introducing entropy.
But given an infinite number of shuffles don't we just get every ordering as much as any other?
So with the walking in 3d analogy, does taking a step introduce entropy?
-
But given an infinite number of shuffles don't we just get every ordering as much as any other?
You'll get each ordering in proportion to how probable that ordering is. If you flip two coins a single time, the probabilities look like: 25% two heads, 50% one heads, one tails, 25% two tails. So if you flip two coins X times, you'll have on average .25*X instances of two heads,.5*X instances of one heads one tails, and 25*X instances of two tails.
But you can't assign the value "infinity" to X. You can look at things as X approaches infinity. So no matter what the real value of X is, you'll always have twice as many instances of one-heads-one-tails as you will two-heads.
-
But given an infinite number of shuffles don't we just get every ordering as much as any other?
You'll get each ordering in proportion to how probable that ordering is. If you flip two coins a single time, the probabilities look like: 25% two heads, 50% one heads, one tails, 25% two tails. So if you flip two coins X times, you'll have on average .25*X instances of two heads,.5*X instances of one heads one tails, and 25*X instances of two tails.
But you can't assign the value "infinity" to X. You can look at things as X approaches infinity. So no matter what the real value of X is, you'll always have twice as many instances of one-heads-one-tails as you will two-heads.
If you consider each card to be unique in a deck of cards, each ordering (of the 52 cards) has the same probability, right? The .5*X instance of one heads one tails comes because you're considering the orderings HT and TH to be the same.
-
If you consider each card to be unique in a deck of cards, each ordering (of the 52 cards) has the same probability, right? The .5*X instance of one heads one tails comes because you're considering the orderings HT and TH to be the same.
If we're talking about a deck of unique cards, yes.
-
That I understand.
But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.
I think amateurs like me often make the mistake of treating infinity as a really big number.
If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.
-
That I understand.
But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.
I think amateurs like me often make the mistake of treating infinity as a really big number.
If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.
Well a physical shuffle is not a complete random permutation on the deck order. In fact, when we shuffle we try to shuffle perfectly (a faro shuffle), which is completely deterministic. So, uh.. actually it's not the easiest problem I guess. For perfect shuffles it is, but for slight random perturbation of a perfect shuffle, I'm not sure.
-
If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.
I like when this play is relevant:
https://www.youtube.com/watch?v=CQ_Ocor3MEA
-
"It was the best of times, it was the BLURST of times? You stupid monkey!" (https://www.youtube.com/watch?v=no_elVGGgW8)
-
That I understand.
But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.
I think amateurs like me often make the mistake of treating infinity as a really big number.
If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.
Well a physical shuffle is not a complete random permutation on the deck order. In fact, when we shuffle we try to shuffle perfectly (a faro shuffle), which is completely deterministic. So, uh.. actually it's not the easiest problem I guess. For perfect shuffles it is, but for slight random perturbation of a perfect shuffle, I'm not sure.
But actually, after enough* shuffles, the distribution function of the imperfectly shuffled deck is well approximated by the uniform distribution. And if we assume a uniform selection of a deck ordering, you can calculate how long you can expect to wait to get back to the original ordering. So take that number and tack on "enough" extra shuffles at the beginning. I imagine the extra shuffles up front shouldn't matter at all. I also imagine your hands will get tired.
*Rule of thumb: 7. I think it's more formally treated in http://projecteuclid.org/download/pdf_1/euclid.aoap/1177005705, though I haven't read through that.. this is just from a few minutes of Googling.
-
That I understand.
But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.
I think amateurs like me often make the mistake of treating infinity as a really big number.
If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.
Well a physical shuffle is not a complete random permutation on the deck order. In fact, when we shuffle we try to shuffle perfectly (a faro shuffle), which is completely deterministic. So, uh.. actually it's not the easiest problem I guess. For perfect shuffles it is, but for slight random perturbation of a perfect shuffle, I'm not sure.
But actually, after enough* shuffles, the distribution function of the imperfectly shuffled deck is well approximated by the uniform distribution. And if we assume a uniform selection of a deck ordering, you can calculate how long you can expect to wait to get back to the original ordering. So take that number and tack on "enough" extra shuffles at the beginning. I imagine the extra shuffles up front shouldn't matter at all. I also imagine your hands will get tired.
*Rule of thumb: 7. I think it's more formally treated in http://projecteuclid.org/download/pdf_1/euclid.aoap/1177005705, though I haven't read through that.. this is just from a few minutes of Googling.
It really depends on how you shuffle.
-
Yeah, this is assuming imperfect riffle shuffling.
-
Yeah, this is assuming imperfect riffle shuffling.
Yes, but also a particular version of imperfect riffle. Bobby might shuffle that way, but Suzie probably won't, even if she does an imperfect riffle shuffle as well.
Lightning edit: i.e. they will have different measures of 'how imperfect' of a riffle shuffle you are looking at.
-
I was assuming the truffle shuffle.
-
Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics
-
Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics
Sorry to derail the maths discussion, but am I the only one bothered by the fact that riffle shuffling damages cards?
Dominion isn't blackjack, just give the cards a quick overhand shuffle and get on with your turn!
-
Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics
Sorry to derail the maths discussion...
Really, this is a forum for derailing Dominion discussion with maths topics, not the other way round!
-
Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics
Sorry to derail the maths discussion, but am I the only one bothered by the fact that riffle shuffling damages cards?
Dominion isn't blackjack, just give the cards a quick overhand shuffle and get on with your turn!
Just come up with a model that measures the degradation of cards as a result of riffle shuffling, the consequence of which can be the extent of your botherment. That way you're not derailing the math thread.
-
Yeah, this is assuming imperfect riffle shuffling.
But don't you make your own shuffle luck?