wu :: forums
wu :: forums - Return to Origin (probability)

Welcome, Guest. Please Login or Register.
Jan 24th, 2022, 8:59pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: towr, Icarus, william wu, Grimbal, SMQ, Eigenray)
   Return to Origin (probability)
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Return to Origin (probability)  (Read 1900 times)
Radiohead_man
Junior Member
**





   


Gender: male
Posts: 74
Return to Origin (probability)  
« on: Dec 8th, 2004, 8:07am »
Quote Quote Modify 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: male
Posts: 1948
Re: Probability  
« Reply #1 on: Dec 8th, 2004, 8:46pm »
Quote Quote Modify 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
*****





   
WWW

Gender: male
Posts: 1291
Re: Return to Origin (probability)  
« Reply #2 on: Dec 19th, 2004, 8:38pm »
Quote Quote Modify Modify

Nice job Eigenray -- Martingales are neat Smiley
 
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: male
Posts: 1948
Re: Return to Origin (probability)  
« Reply #3 on: Dec 20th, 2004, 1:08pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board