Author 
Topic: Return to Origin (probability) (Read 1900 times) 

Radiohead_man
Junior Member
Gender:
Posts: 74


Return to Origin (probability)
« on: Dec 8^{th}, 2004, 8:07am » 
Quote Modify

Suppose we have a coin that, when tossed, has probability P to obtain tails, and probability 1P 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 19^{th}, 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 8^{th}, 2004, 8:46pm » 
Quote Modify

I'd have said 2*min(p,1p). Since the case p=1/2 is easy, assume p != 1/2: Let S_{n} = 1+X_{1}+...+X_{n} be a random walk starting at 1, the X_{i} i.i.d. with P(X_{i}=1) = 1P(X_{i}=1) = p. If r = (1p)/p, one checks that M_{n} = r^{Sn} is a martingale. If T=T_{N} = min { j : S_{j} =0 or N}, then M_{min(n,T)} is a bounded martingale, so the optional stopping/sampling theorem applies, and r = EM_{0} = EM_{T} = 1P(S_{T}=0) + r^{N} P(S_{T}=N). Solving, P(S_{T}=0) = (rr^{N})/(1r^{N}) 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 = (1p) + pr^{2}. Solving, r is either 1 or (1p)/p. If you wave your hands fast enough it's clear that r=1 when p<1/2, and (1p)/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=(1p)/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(1p). Similarly if p<1/2 the probability of return is 2p.

« Last Edit: Dec 8^{th}, 2004, 9:25pm by Eigenray » 
IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Return to Origin (probability)
« Reply #2 on: Dec 19^{th}, 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 Z_{k} = probability of returning to zero, given that the random walk starts at location k. Assume the walk starts at +1, and k is nonnegative. Then Z_{k} = p Z_{k1} + q Z_{k+1}. Assume a solution of the form Z_{k} = C r^{k}, for some constants C and r. Then solving the quadratic reveals r = 1 or p/q Our boundary condition is Z_{0} = 1 = Cr^{0} [bigto] C = 1. So Z_{k} = r^{k} = 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] Z_{k} = 0. (*Why? I'm not sure but it makes intuitive sense.) Then only the r = (p/q) solution satisfies this, and we thus have Z_{1} = (p/q). If p/q = 1, then we only have one solution, r = 1. So Z_{1} = 1. (*For some reason, the aforementioned boundary condition in the previous case disappears.) If p/q > 1, then Z_{1} = r = p/q makes no sense since Z_{1} 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,1p).

« Last Edit: Dec 19^{th}, 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 20^{th}, 2004, 1:08pm » 
Quote Modify

I believe this justifies the boundary condition: For S_{n} starting at S_{0} = 2k (going down with probability p), P(S_{2n}=0) = (^{2n}C_{n+k})p^{n+k}q^{nk} Note that ^{2n}C_{n+k} [le] (1+1)^{2n} = 4^{n}, and if r = p/q < 1, then a=pq < 1/4, and we have Z_{2k} [le] [sum]_{n=0}^{[infty]} P(S_{2n}=0) [le] [sum] 4^{n} a^{n} r^{k} = r^{k} / (14a) [to] 0 as k[to][infty]. This is more or less the same as the handwavy argument I gave above: by the Markov property Z_{k+1} = Z_{1}Z_{k}, and the preceeding justifies solving for Z_{1} to be strictly less than 1, i.e., Z_{1} = r = p/q, in the case p < 1/2.

« Last Edit: Dec 20^{th}, 2004, 1:41pm by Eigenray » 
IP Logged 



