Author |
Topic: HARD: Infinite Coin Flips (Read 5081 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
HARD: Infinite Coin Flips
« on: Oct 29th, 2002, 7:37pm » |
 Quote  Modify
|
Quote:| Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips? |
|
Was there really no thread on this one yet? Or is it just that my eyes glaze over by the time I get to the back pages when looking for one?
Anyway, this is what I have:
For each number n, there are (2n choose n) sequences of heads and tails with n each. Each sequence has probability
pn(1-p)n.
The sequences are independent, so the total probability of getting any of them is
(2n choose n)pn(1-p)n.
Thus, the probability that you WON'T have equal numbers of heads and tails on the 2nth flip is
1-(2n choose n)pn(1-p)n.
The probability of not getting equal numbers of heads and tails at any time in the first 2M flips is then
PRODn=1M(1-(2n choose n)pn(1-p)n).
The probability of ever getting equal numbers of heads and tails is therefore:
1 - PRODn=1oo(1-(2n choose n)pn(1-p)n).
Next I hang my head and start crying as the nightmares resurface in my memories. How do you find closed forms for infinite products? Wasn't there some trick involving holomorphic functions? I brace myself and pull out my complex analysis textbook. But no! The products have a different form than this! Maybe diffentiating? Yikes! that logarithmic derivative is UGLY! Is there no help for this? 
|
|
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: Infinite Coin Flips
« Reply #1 on: Oct 31st, 2002, 9:29am » |
Quote Modify
|
on Oct 29th, 2002, 7:37pm, Icarus wrote:
The probability of not getting equal numbers of heads and tails at any time in the first 2M flips is then
PRODn=1M(1-(2n choose n)pn(1-p)n).
|
|
I'm not sure I agree with this part. The analysis for a single sequence seems correct, but the first M+1 flips aren't independent of the first M flips, so I don't think you can multiply like this.
Let's say you have 7 heads and 3 tails. It's actually impossible to reach equality in 1, 2, or 3 flips. It will take at least 4 flips, with a probability of 1/16, to reach even.
Intuitively, the answer is 1, but it is not immediately clear how to prove it.
No, wait, it's easy! You start with 0 of each, so QED!
Here's a possible spreadsheet simulation (apologies to spreadsheet-haters!). You can simulate the regular distribution of results in coin flips by forming Pascal's triangle. Now simulate the distribution of results in this problem, by simulating just half of Pascal's triangle. When a coin flip path crosses over into the other half, it no longer satisfies the "never-equal" criterion. You'll see that the growth of the number of different paths grows exponentially in both triangles, but it grows faster in the regular Pascal's triangle.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: HARD: Infinite Coin Flips
« Reply #2 on: Oct 31st, 2002, 9:48am » |
Quote Modify
|
Maybe its helpfull to consider that if they're never equal, one has to be perpetually higher than the other..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: HARD: Infinite Coin Flips
« Reply #3 on: Oct 31st, 2002, 9:52am » |
Quote Modify
|
on Oct 29th, 2002, 7:37pm, Icarus wrote:
The probability of ever getting equal numbers of heads and tails is therefore:
1 - PRODn=1oo(1-(2n choose n)pn(1-p)n).
Next I hang my head and start crying as the nightmares resurface in my memories. How do you find closed forms for infinite products? |
|
Well.. putting aside the issue of if the reasoning is correct (I can't really follow it)
Then since 1-(2n choose n)pn(1-p)n is always smaller than 1 and larger than 0, an infinite product of it must be 0, and 1 -0 = 1.. So that'd be your proof right there..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: Infinite Coin Flips
« Reply #4 on: Oct 31st, 2002, 9:54am » |
Quote Modify
|
Icarus,
That spreadsheet is very interesting. I simulated the entire triangle, and then I simulated the two halves (you can do this at the same time, by making a Pascal's triangle and zeroing out the middle items).
Next, I subtracted this simulation triangle from the original Pascal's triangle. The result is intruiging: It is Pascal's triangle, shifted down by one row, multiplied by 2, and missing one column in the middle. This means that the exact proportion, as a function of n, is:
2 * (2n-1 - nchoosek(n, floor(n/2))) / 2n
This is equal to 1 - nchoosek(n, floor(n/2)) / 2n-1, which goes to 1 as n grows.
However, I don't have a good explanation for why the numbers take that form...
Of course, this doesn't take into account p ... I think if p<>0.5, then the answer isn't equal to 1.
|
| « Last Edit: Oct 31st, 2002, 9:55am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: HARD: Infinite Coin Flips
« Reply #5 on: Oct 31st, 2002, 11:25am » |
Quote Modify
|
Isn't it true that any event with a nonzero chance of occurring will eventually occur, given an infitite number of said events?
Actually, I'm fairly confident that's true; what I should be asking is whether it applies here. (after typing the rest of the problem, I think it doesn't because the probability of the "eventual win" event is continuously decreasing as the event continues to fail)
If it doesn't apply, I think the problem could be approached as summing an infinite series, where An represents the probability of eventually equalizing from a point where you are n flips in the hole. So, assuming WLOG p<0.5, p is the minority flip, and (1-p) is the majority flip:
A1 = p + (1-p)A2
An = pAn-1 + (1-p)An+1
Gut instinct tells me that this has a closed form, assuming Ainf => 0. But pen-and-paper tells me that it's ugly, at least trying to calculate A3 by hand.
Oh! Inspiration! Let's sum up all the intermediate Ai outright.
SUMi=1inf Ai = p + pA1 + A2 + A3 + ...
The infinitude of terms drops out and we get A1 = p + pA1, or A1 = p/(1-p).
So there's a p/(1-p) chance we'll eventually equalize given that we're 1 flip on the majority side. (in retrospect, we don't really need to sum all the An given that we know A1.) But we could get lucky, with probability p, and have the first flip put us on the minority side, in which case destiny will cross us back over the line easily. So
ans = p(1) + (1-p) * (p/(1-p)) = 2p.
Cool problem!
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Infinite Coin Flips
« Reply #6 on: Oct 31st, 2002, 9:03pm » |
Quote Modify
|
on Oct 31st, 2002, 9:29am, James Fingas wrote:
I'm not sure I agree with this part. The analysis for a single sequence seems correct, but the first M+1 flips aren't independent of the first M flips, so I don't think you can multiply like this.
|
|
Yeah - it looks like I goofed  . Your spreadsheet sounds interesting, but I haven't had time to play with it yet.
on Oct 31st, 2002, 9:52am, towr wrote:
Then since 1-(2n choose n)pn(1-p)n is always smaller than 1 and larger than 0, an infinite product of it must be 0, and 1 -0 = 1.. So that'd be your proof right there..
|
|
Not quite: the handy-dandy convergence theorem for products is this - Given a sequence {un}, the product
PRODi=1oo(1 + ui)
converges to a non-zero result if and only if the series
SUMi=1oo ui
converges.
In this case that is the sum
-SUMn=1oo (2n choose n)(p(1-p))n
which is a power series inside its radius of convergence (except when p=.5 - then we are at the radius, and I don't know if it converges). So for p != .5, we are guaranteed that the product does not converge to zero. It does however fail to represent what I claimed it did, so it's value is moot.
on Oct 31st, 2002, 11:25am, Garzahd wrote:| Isn't it true that any event with a nonzero chance of occurring will eventually occur, given an infitite number of said events? |
|
I want to make clear what you intimated in the next paragraph: If the probability of an event over time is bounded away from zero, then the probablity of it ever occuring given an infinite number of chances is 1. But it does not apply here because the per-chance probability of this particular event converges to zero.
You analysis looks good, though I haven't had the chance to work through the logic yet. But I wanted to comment on on this:
Quote:
A1 = p + (1-p)A2
An = pAn-1 + (1-p)An+1
Gut instinct tells me that this has a closed form, assuming Ainf => 0. But pen-and-paper tells me that it's ugly, at least trying to calculate A3 by hand. |
|
Though your final solution method is beautiful, I am curious: Am I really the only one on these boards who knows the general method for finding closed forms for linear recursions? This one is particularly nice:
An = X + Y(p/(1-p))n
where X and Y are constants that can be evaluated from A1 and A2
I described the method in the Ladder Rungs thread (Medium):
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1028840376;start=0
Its a useful trick to know, given how often these linear recursions keep turning up.
|
| « Last Edit: Oct 31st, 2002, 9:04pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: HARD: Infinite Coin Flips
« Reply #7 on: Nov 1st, 2002, 12:14am » |
Quote Modify
|
on Oct 31st, 2002, 9:03pm, Icarus wrote:
Not quite: the handy-dandy convergence theorem for products is this - Given a sequence {un}, the product
PRODi=1oo(1 + ui)
converges to a non-zero result if and only if the series
SUMi=1oo ui
converges. |
|
Let's take ui=-0.5 for every i,
SUMi=1oo ui does not converge, PRODi=1oo(1 + ui) however certainly does..
So I can't really agree here..
|
| « Last Edit: Nov 1st, 2002, 12:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: HARD: Infinite Coin Flips
« Reply #8 on: Nov 1st, 2002, 12:50pm » |
Quote Modify
|
Quoth Garzahd: Quote:| ans = p(1) + (1-p) * (p/(1-p)) = 2p. |
|
Houston, we have a problem. What if p > .5?
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: Infinite Coin Flips
« Reply #9 on: Nov 1st, 2002, 2:13pm » |
Quote Modify
|
on Oct 31st, 2002, 11:25am, Garzahd wrote:... assuming WLOG p<0.5, p is the minority flip, and (1-p) is the majority flip ...
... ans = p(1) + (1-p) * (p/(1-p)) = 2p. |
|
I think it's the non-linear nature of the problem that makes it so the equation doesn't work for p > 0.5, but you can see Garzahd has his bases covered!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Infinite Coin Flips
« Reply #10 on: Nov 1st, 2002, 3:37pm » |
Quote Modify
|
on Nov 1st, 2002, 12:14am, towr wrote:
Let's take ui=-0.5 for every i,
SUMi=1oo ui does not converge, PRODi=1oo(1 + ui) however certainly does..
So I can't really agree here..
|
|
If you read a little more carefully, you will see that I said it converges to non-zero result. Convergence for infinite products is usually examined for non-zero limits, since convergence to zero corresponds very nicely to series that diverge to -infinity. The theorem is a standard one you can find in any Real Analysis textbook.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Infinite Coin Flips
« Reply #11 on: Nov 2nd, 2002, 10:28am » |
Quote Modify
|
When p > .5, the recursions still hold, but Garzahd's summation of the An diverges, so his calculation that A1=p/(1-p) would no longer hold.
The closed form expression for An that I gave
An = X + Y(p/(1-p))n
is a little more robust, holding for all p, though it is not as easy as I indicated to evaluate the constants X and Y (which are constant with respect to n, not p). From A0=1 we find that X = 1-Y. If p<.5, then it is clear that the limit of An as n --> oo is zero, so X=0, Y=1 and we get
A(p)n = (p/(1-p))n p < .5
where I have written A as A(p) to emphasize it's dependence on p.
If p = .5, then the equation is just An=1. If p>.5, then the only way that An can be kept < 1, which it must be as a probability, is if Y=0, and we get
A(p)n = 1 p > .5
Since after the first flip we have a 1 flip advantage for one side or the other, the total probability of getting back to equal heads and tails is
p*A(1-p)1 +(1-p)A(p)1
if p < .5, this reduces to 2p. If p > .5, it reduces 2(1-p). If p=.5, it reduces to 1. So the answer for general p is
Prob of equality = 2*min(p, 1-p)
Which is in essence what Garzahd said. Cool deduction Garzahd - give youself a star!
|
| « Last Edit: Nov 2nd, 2002, 10:30am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: HARD: Infinite Coin Flips
« Reply #12 on: Nov 3rd, 2002, 10:12pm » |
Quote Modify
|
Yeah, I figured that my p<0.5 assumption would imply that p>0.5 just requires a translation to 1-p. Hence the use of the words "minority event" and "majority event".
Give myself a star? But that would involve posting to some thread about fifty times! 
Thanks.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Infinite Coin Flips
« Reply #13 on: Nov 4th, 2002, 5:57pm » |
Quote Modify
|
I know I wasn't actually adding anything major to your solution. But since some confusion on the matter of p > .5 had come up, I thought I would a give a long-winded explanation of what happens.
The one thing I did add to the proof is an actual mathematical explanation (though not a very satisfying one I think) as to why the probability of returning to even after a minority flip is 1. Appeals to destiny always leave me a little queasy! 
As for giving yourself a star, just do what I do and make myriads of junk posts all over the place! 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
harvestar
Newbie
Posts: 5
|
|
Re: HARD: Infinite Coin Flips
« Reply #14 on: May 14th, 2003, 4:47am » |
Quote Modify
|
o wow. i just saw the riddle and thought it was a simple lil riddle. had no idea what i was gettin into here, lol. all your formulas look real purty and all, but... well, i'll just go ahead and tell ya what i Thought the answer was anywayz... you brainiacs will probly get a chuckle out of it at least.
>>Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips? <<
my answer: the probability is infinite.
see, told ya you'd laugh. *sigh* i really didnt know this was a math place. and i suck at math. but, it just seemed obvious to me, that any problem where you got an infinite Anything, well then, anything ya stick in there in the problem has Got to be infinite. i mean, hey, INFINITE, right?
sheesh, i probly sound like a moron, but o well, thats what i thought
|
|
IP Logged |
|
|
|
harvestar
Newbie
Posts: 5
|
|
Re: HARD: Infinite Coin Flips
« Reply #15 on: May 14th, 2003, 4:50am » |
Quote Modify
|
p.s. ...
and in my own defense, i Do know what probabilities are, but i never could understand em, becuz i think i just dont Believe in the whole thing. i mean, to me, every probability is just 50/50. it either Is, or it Isn't.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: Infinite Coin Flips
« Reply #16 on: May 14th, 2003, 12:51pm » |
Quote Modify
|
Thud,
I thought that too, until I noticed a certain line in the problem statement: the coin does not have a 50/50 probability. Obviously, a coin with a 100% probability of getting tails will never flip an equal number of heads and tails.
If p=0.5, or you flip the less likely side first, then you will eventually break even. Otherwise, you won't necessarily.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: Infinite Coin Flips
« Reply #17 on: May 14th, 2003, 1:45pm » |
Quote Modify
|
To me, it looks like the paper says it will only return to the beginning necessarily if p=1/2. I'm looking at this part:
Quote:
These results suggest that when the walk is asymmetric, it is far less likely for the particle to return to the origin (the p(2n)s follow an exponential decay as opposed to a O(1/sqrt(n)) fall-off). This statement agrees with intuition that when the walk is biased in one direction, the particle is likely to wander off far away after many steps.
|
|
So if p is not 1/2, then the particle has a good chance of wandering farther and farther afield as time goes on, never to return. The distribution in the limit is a normal curve, with a mean of p*n (n is the number of steps), and a variance proportional to sqrt(n). As time goes on, you can see that the mean will eventually overtake the standard deviation, leading to a rapidly diminishing probability of returning to zero.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
harvestar
Newbie
Posts: 5
|
|
Re: HARD: Infinite Coin Flips
« Reply #18 on: May 14th, 2003, 6:49pm » |
Quote Modify
|
>>'What is the probability of a 1-dimensional random walk ever returning to its starting point?' <<
heehee, this is fun. i think im Glad i dont know math 
and please don't take offense to this, consider my ignorance, ok? but...
don't you guys get the word INFINITY LOL
if by 'ever', you mean 'in an infinite amount of time' (sorta oxymoronic in itself, eh?), then the walker will return to its starting point an infinite number of times, AND it will NOT return to its starting point - Ever!
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: HARD: Infinite Coin Flips
« Reply #19 on: May 16th, 2003, 12:37pm » |
Quote Modify
|
on May 14th, 2003, 6:49pm, harvestar wrote:don't you guys get the word INFINITY LOL
|
|
Let's just not get into a discussion of infinity here - enough to say that it has been/is being discussed intensively elsewhere.
Purely intuitively (since the maths has already been done by other people) there are two distinct types of behaviour you'd expect to be possible for a time-invariant one-dimensional random walk: it generally hangs around where it started; or it drifts off towards infinity (plus or minus). If it's a symmetrical walk, then it will tend to stay put at 0 (actually it tends to gradually drift away, but keeps coming back), otherwise it will tend to drift. The question in the asymmetric case is whether the expected error in its location grows faster than its expected distance from 0. Turns out the expected distance goes up as O(n) while expected error is O(root(n)) (If memory serves) so for large enough n, the chance of being far enough away from the expected location to be at 0 decays rapidly
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Infinite Coin Flips
« Reply #20 on: May 17th, 2003, 10:35am » |
Quote Modify
|
on May 14th, 2003, 4:47am, harvestar wrote:
my answer: the probability is infinite.
see, told ya you'd laugh. *sigh* i really didnt know this was a math place. and i suck at math. but, it just seemed obvious to me, that any problem where you got an infinite Anything, well then, anything ya stick in there in the problem has Got to be infinite. i mean, hey, INFINITE, right? |
|
Welcome to Wu's Wonderland! There is nothing wrong with being bad at math (there is something wrong with being PROUD about being bad at math, like some people are, but that's another matter). Nor should you refrain from expressing your point of view or berate yourself for it: Quote:| sheesh, i probly sound like a moron, but o well, thats what i thought |
|
Just be ready for people who are good at math to point out where you went wrong. If they do it courteously, you can learn from it (and so can they).
The answer couldn't be "infinite", because probability is trapped between 0 (completely improbable) and 1 (completely probable). (I stated it this way because when there are infinitely many possibilities, saying it has probability zero is not the same as saying it will not happen.)
Quote:| i Do know what probabilities are, but i never could understand em, becuz i think i just dont Believe in the whole thing. i mean, to me, every probability is just 50/50. it either Is, or it Isn't. |
|
But surely you've noticed that some things "are" far more often than they "aren't", and vice versa. For instance, if you play the lottery, your are not the winner far more often than you are! And if you roll a die repeatedly, the number that comes up "is not a 6" about five times more often than it "is a 6".
Quote:| don't you guys get the word INFINITY |
|
Umm... Isn't this rather like the inner city dweller saying to the farmer "don't you know anything about growing plants?"
Concerning the random walk bit, you are misinterpreting what was said. I will try to state it more clearly:
Linear Random walk: A man starting at position O moves either right or left on a straight line. Each minute he flips a fair coin and moves 1 meter to the right if the result is heads, or 1 meter to the left if the result is tails. How likely is it he will return to the point O at some time in the future (assuming he keeps going as long as he needs to)?
The answer that Polya, and Garzhad, found is: 100%. What this means is that it is effectively certain that at some FINITE time after he starts, he will return to point O. In fact, he has a 50% chance of being back at point O after only 2 minutes.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
harvestar
Newbie
Posts: 5
|
|
Re: HARD: Infinite Coin Flips
« Reply #21 on: Jun 3rd, 2003, 4:36am » |
Quote Modify
|
hey Icarus!
thank you muchly for your kind words, and your patient explanations.
first of all, i wanna take a lil trip back in time, so i can take back the words, >don't you guys get the word INFINITY<. as you said, >Isn't this rather like the inner city dweller saying to the farmer "don't you know anything about growing plants?"<
yes, you're right, icarus, it was way lame of me to say that, and the particular words you used got to me becuz i used to live in the woods, and we had all the city-folk trying to tell us about conservation, lol. anywayz, i do apologize not only for saying it, but for the attitude behind it. *humbled head bowed*
secondly, thank you for explaining the aspect of probability -
>>probability is trapped between 0 (completely improbable) and 1 (completely probable).<<
in that case i think i would say, as far as the infinite coin-toss, the probability would be 1.
my reasoning is based on the semantic logic of infinity, rather than the mathmatical one, though (since i haven't yet learned anything about the mathmatical aspects of infinity).. in that an infinite number of coin tosses would not just be portrayed by a coin being flipped up and Then landing, over and over and over, in a straight line of unending time.. but that there would also exist an infinite number of time-lines simultaneously repeating the coin toss. in which case, every possible result would be effected. (all the IMpossible ones, too, lol).
now, the random walk question, i obviously got all kinds of wrong. thank you, icarus, for explaining a linear random walk to me. (i'm remembering a great book i read, called 'number of the beast', by some sci-fi writer, i disremember who, and one bit of it i would have gotten more out of had i understood the random walk before).
>>Linear Random walk: A man starting at position O moves either right or left on a straight line. Each minute he flips a fair coin and moves 1 meter to the right if the result is heads, or 1 meter to the left if the result is tails. How likely is it he will return to the point O at some time in the future (assuming he keeps going as long as he needs to)?<<
this one i would now say the probability is .5 - but remember, i Still see everything as 50/50, hehe. if im Ever going to really understand probability theory, i know i have to get over that. but i dont know how i can. when you said about the lottery and the die.. well, i still see that one lottery ticket is either the winning ticket or / it is not.. and the die will either land on 6 or / not. *sigh* i Do wish someone could help me see it otherwise.
>>The answer that Polya, and Garzhad, found is: 100%. What this means is that it is effectively certain that at some FINITE time after he starts, he will return to point O. In fact, he has a 50% chance of being back at point O after only 2 minutes.<<
i'll do a search and see if that polya and garzhad stuff is published online anyplace so i can read it. it does make sense tho, that the walker wouldn't ever get very far away from the starting point.
thanks again, icarus
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Infinite Coin Flips
« Reply #22 on: Jun 3rd, 2003, 6:00pm » |
Quote Modify
|
Polya was a mathematician who examined the random walk question. The link that THUDandBLUNDER gave:
http://mathworld.wolfram.com/PolyasRandomWalkConstants.html
Gives a brief description of his work. I don't know if a more complete explanation is available anywhere. It would likely be very technical if it is.
You're in better luck with Garzahd. He is a member of this forum (or was - he hasn't posted since January). The result I was refering to was his solution to the coin flips puzzle, which is the 6th post in this thread.
As for the probability bit. If you feel that the probability of rolling a 6 is 50%, maybe we could get together some time for a game of craps!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Infinite Coin Flips
« Reply #23 on: Jun 4th, 2003, 5:45pm » |
Quote Modify
|
It has nothing to do with this problem, but since Harvestar and I have had a little discussion on die probabilities, and since at 40 years, I am about ripe to start giving long rambling pointless stories at the drop of a hat, I thought I'd tell this one, that happened 2 or 3 years ago:
Some friends and I were playing an Avalon Hill game called "Naval War". In the game you have the option of drawing a card on your turn, or if you have aircraft carriers, rolling a die for each of them, successfully sinking someone's ship if you roll a one. At the end of a game that I was losing, I decided drastic action was necessary and started rolling the die for my two aircraft carriers. No luck - I could not roll a one. Having no hope at all, I kept rolling just to see what would happen. I did not keep track, but I must of rolled at least 12+ times without a single one.
When the game ended, I picked up the die, made a sarcastic remark about "is there a one on this thing" and rolled it again. It came up 1. "Now it can roll ones!" I said disgustedly and rolled again. Another 1. Again - 1, and 1, and 1, and 1, and 1, and 1, and 1,... Amazed at this progression I kept rolling (I wish now that I had also kept count). But being conservative, I must have rolled at least 15 ones in a row before it came up another number. I kept rolling, and even though other numbers started showing up, at least 2/3 of the rolls were still 1. This went on for another 12 rolls at least.
The probability of this event was less than
1 in 29 quadrillion, and this does not account for the change from "no ones" to "all ones" falling at such a portentious time - exactly when rolling the ones no longer did me any good.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: HARD: Infinite Coin Flips
« Reply #24 on: Jun 4th, 2003, 11:32pm » |
Quote Modify
|
of course you realize an equally long sequence of any other sides would be exactly equally (un)likely.. be it 11111 or 34251
There are ways to bias your throwing though.. it is after all just newtonian physics you're dealing with..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print