

Title: More heads than tails Post by THUDandBLUNDER on Nov 11^{th}, 2003, 8:40pm You flip a fair twosided coin until you have either n more heads than tails or m more tails than heads. What is the expected average number of flips that you willl need? // title modified by wwu july 27 2004 

Title: Re: More Coin Tossing Post by towr on Nov 12^{th}, 2003, 1:54pm ::[hide]I might be mistaken, but is this a very difficult way to do a very simple operation??[/hide]:: [e][hide]the following recursion holds, and conveniently fits with the solution I was thinking of. e(n,0) = 0 e(0,m) = 0 e(n,m) = 1/2 (e(n1, m+1) + e(n+1, m1)) +1 (when n>0, m>0)[/hide][/e] 

Title: Re: More Coin Tossing Post by william wu on Jul 27^{th}, 2004, 4:41am You can think of this as simply a random walk on the integers, with increments of +1 and 1. Let heads correspond to +1 and tails correspond to 1. At each time step 1,2,.... a random variable X_{i} is generated, equally likely to be either +1 or 1. Then our random walk corresponds to the cumulative sum of these variables: where S_{0} is the initial position. We then want to know the expected time till this walk hits either n or m. To do this, we can set up a recursion. The underlying principle is that after you have moved somewhere, the problem of computing the remaining expected hitting time is just like the problem you started with, except that the initial position S_{0} has changed. Let T be the random variable denoting the time till either level n or level m is hit. Then we want to find E[T]. Let h(k) = E(T  S_{0} = k). Then, finishing what towr started, we have the recursion with boundary conditions To solve this recurrence quickly, consider the discrete forward difference operator Invoking the operator twice on h(k1) then yields Note that is highly resemblant of our original recurrence equation. In fact we can now express the recurrence as Thus the function h has a constant second difference. This suggests a quadratic expression for h, with the highestorder coefficient scaled by [smiley=cdelta.gif]^{2} h(k1) / 2 = 1. By also considering the boundary conditions 0 = h(n) = h(m), we make the educated guess whose correctness can be verified by substitution into the original recurrence. Now recall that h(k) = expected hitting time given that the initial position is k. Thus our final answer is very, very elegant: 

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