|
||
|
Title: Return to Origin (probability) Post by Radiohead_man on Dec 8th, 2004, 8:07am 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 |
||
|
Title: Re: Probability Post by Eigenray on Dec 8th, 2004, 8:46pm I'd have said [hide]2*min(p,1-p)[/hide]. Since the case p=1/2 is easy, assume p != 1/2:[hide] 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[/hide]. [Edit] Handwavy alternative argument: Let r be the probability of ever getting more heads than tails. [hide]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[/hide]. [/Edit] Now let p>1/2, and suppose we start at 0. [hide]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)[/hide]. Similarly if p<1/2 the probability of return is [hide]2p[/hide]. |
||
|
Title: Re: Return to Origin (probability) Post by william wu on Dec 19th, 2004, 8:38pm 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 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). |
||
|
Title: Re: Return to Origin (probability) Post by Eigenray on Dec 20th, 2004, 1:08pm 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. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |