Author |
Topic: Return to Origin (probability) (Read 1951 times) |
|
Radiohead_man
Junior Member
Gender: 
Posts: 74
|
 |
Return to Origin (probability)
« on: Dec 8th, 2004, 8:07am » |
 Quote  Modify
|
Suppose we have a coin that, when tossed, has probability P to obtain tails, and probability 1-P to obtain heads. Suppose we toss it again and again, until an equal number of heads and tails is obtained, and then the process ends. Compute the probability that this process would end eventually.
// thread title modified by wwu 8:07 PM 12/19/2004
|
| « Last Edit: Dec 19th, 2004, 8:08pm by william wu » |
 IP Logged |
I'm a reasonable man
get off my case, get off my case.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Probability
« Reply #1 on: Dec 8th, 2004, 8:46pm » |
Quote Modify
|
I'd have said 2*min(p,1-p).
Since the case p=1/2 is easy, assume p != 1/2:
Let Sn = 1+X1+...+Xn
be a random walk starting at 1, the Xi i.i.d. with P(Xi=1) = 1-P(Xi=-1) = p.
If r = (1-p)/p, one checks that Mn = rSn is a martingale.
If T=TN = min { j : Sj =0 or N},
then Mmin(n,T) is a bounded martingale, so the optional stopping/sampling theorem applies, and
r = EM0 = EMT = 1P(ST=0) + rN P(ST=N).
Solving, P(ST=0) = (r-rN)/(1-rN)
is the probability of returning to 0 before hitting N.
Letting N go to infinity, the probability of ever returning to 0, given that we start at 1, is r for p>1/2, and 1 for p<1/2.
[Edit]
Handwavy alternative argument: Let r be the probability of ever getting more heads than tails. This happens if we first flip a head, or if we first flip a tail and then "go negative" twice, i.e.,
r = (1-p) + pr2.
Solving, r is either 1 or (1-p)/p.
If you wave your hands fast enough it's clear that r=1 when p<1/2, and (1-p)/p for p>1/2.
[/Edit]
Now let p>1/2, and suppose we start at 0. If our first step is up (with probability p), then we return with probability r=(1-p)/p. By a symmetric argument to the one above, if our first step is down we return with probability 1. Thus the probability of returning to 0 is 2(1-p).
Similarly if p<1/2 the probability of return is 2p.
|
| « Last Edit: Dec 8th, 2004, 9:25pm by Eigenray » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Return to Origin (probability)
« Reply #2 on: Dec 19th, 2004, 8:38pm » |
Quote Modify
|
Nice job Eigenray -- Martingales are neat 
We can also solve it with rudimentary difference equations -- although there are a few steps here I'm shaky about, which I've highlighted in pink.
Let Zk = probability of returning to zero, given that the random walk starts at location k.
Assume the walk starts at +1, and k is non-negative.
Then Zk = p Zk-1 + q Zk+1. Assume a solution of the form Zk = C rk, for some constants C and r. Then solving the quadratic reveals
r = 1 or p/q
Our boundary condition is Z0 = 1 = Cr0 [bigto] C = 1.
So Zk = rk = probability of returning to origin, starting at location k.
Now consider when p/q < 1. We should then have an extra boundary condition lim k[to][infty] Zk = 0. (*Why? I'm not sure but it makes intuitive sense.) Then only the r = (p/q) solution satisfies this, and we thus have Z1 = (p/q).
If p/q = 1, then we only have one solution, r = 1. So Z1 = 1. (*For some reason, the aforementioned boundary condition in the previous case disappears.)
If p/q > 1, then Z1 = r = p/q makes no sense since Z1 is a probability. So we must use the other solution, r = 1. (*Again, boundary condition not present.)
Symmetric results can be obtained in the case where the random walk starts at -1. Finally, conditioning on the first step we get the answer of 2*min(p,1-p).
|
| « Last Edit: Dec 19th, 2004, 8:39pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Return to Origin (probability)
« Reply #3 on: Dec 20th, 2004, 1:08pm » |
Quote Modify
|
I believe this justifies the boundary condition:
For Sn starting at S0 = 2k (going down with probability p),
P(S2n=0) = (2nCn+k)pn+kqn-k
Note that
2nCn+k [le] (1+1)2n = 4n,
and if r = p/q < 1, then a=pq < 1/4, and we have
Z2k [le] [sum]n=0[infty] P(S2n=0) [le] [sum] 4n an rk = rk / (1-4a) [to] 0
as k[to][infty].
This is more or less the same as the handwavy argument I gave above: by the Markov property Zk+1 = Z1Zk, and the preceeding justifies solving for Z1 to be strictly less than 1, i.e., Z1 = r = p/q, in the case p < 1/2.
|
| « Last Edit: Dec 20th, 2004, 1:41pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print