wu :: forums « wu :: forums - Return to Origin (probability) » Welcome, Guest. Please Login or Register. Jan 24th, 2022, 8:59pm RIDDLES SITE WRITE MATH! Home Help Search Members Login 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 Notify of replies Send Topic Print
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
.

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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

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