wu :: forums
« wu :: forums - More heads than tails »

Welcome, Guest. Please Login or Register.
Feb 23rd, 2024, 5:54am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
(Moderators: SMQ, Grimbal, Eigenray, Icarus, towr, ThudnBlunder, william wu)
   More heads than tails
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: More heads than tails  (Read 18236 times)
wu::riddles Moderator

The dewdrop slides into the shining Sea


Gender: male
Posts: 4489
More heads than tails  
« on: Nov 11th, 2003, 8:40pm »
Quote Quote Modify Modify

You flip a fair two-sided 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
« Last Edit: Jul 27th, 2004, 4:44am by william wu » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
wu::riddles Moderator

Some people are average, some are just mean.


Gender: male
Posts: 13730
Re: More Coin Tossing  
« Reply #1 on: Nov 12th, 2003, 1:54pm »
Quote Quote Modify Modify

::I might be mistaken, but is this a very difficult way to do a very simple operation??::
[e]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(n-1, m+1) + e(n+1, m-1)) +1  (when n>0, m>0)
« Last Edit: Nov 12th, 2003, 2:17pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu
wu::riddles Administrator


Gender: male
Posts: 1291
Re: More Coin Tossing  
« Reply #2 on: Jul 27th, 2004, 4:41am »
Quote Quote Modify Modify

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 Xi is generated, equally likely to be either +1 or -1. Then our random walk corresponds to the cumulative sum of these variables:

Sn = S0 + [sum]i=1 to n Xi

where S0 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 S0 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 | S0 = k). Then, finishing what towr started, we have the recursion

h(k) = 0.5 h(k-1) + 0.5 h(k+1) + 1

with boundary conditions

0 = h(n) = h(-m).

To solve this recurrence quickly, consider the discrete forward difference operator

[smiley=cdelta.gif]h(k-1) = h(k) - h(k-1)

Invoking the operator twice on h(k-1) then yields

[smiley=cdelta.gif]2 h(k-1) = h(k+1) - 2h(k) + h(k-1)

Note that is highly resemblant of our original recurrence equation. In fact we can now express the recurrence as

-1 = (1/2) [smiley=cdelta.gif]2 h(k-1)

Thus the function h has a constant second difference.  This suggests a quadratic expression for h, with the highest-order coefficient scaled by [smiley=cdelta.gif]2 h(k-1) / 2 = -1. By also considering the boundary conditions 0 = h(n) = h(-m), we make the educated guess

h(k) = -(k - n)(k + m)

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:

h(0) = -(0 - n)(0 + m) = nm.  (SWEET!)

« Last Edit: Aug 3rd, 2004, 6:17pm by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
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