| Re .3:
Could you expand on this a little more? I honestly can't follow
this.
Re .2:
Boy, this is just like being back in college! "Show your work!
Show your work!" Thats all I ever heard. Ok, here goes:
1) Since we have flipped once, we musthave a difference of exactly
one (+1, or -1). Signs don't really matter here so I'm just going
to ignore them.
2) The greatest multiple of 3 less than 1 is 0.
The least multiple of 3 greater than 1 is 3.
3) The difference will change by exactly 1 after every new flip.
:. 4) By (2) and (3) the only multiples of 3 that we can stop on are
0, and 3. Also, the only numbers that we can stop are 0 and
3.
:. 5) By (4) and (3) the only non-terminal differences will be 1 and
2. That is to say, if we have not yet stopped then we must be
either at 1 or 2.
6) If our current difference is 1, then 50% of the time we will
go out on the next flip (diff = 0), and 50% of the time we will
not (diff = 2). Likewise if the difference is currently 2, (50%
= 3, 50% = 1).
:. 7) By (6) we can see that the chances of going out are:
at 1 = 0
at 2 = 1/2
at 3 = 1/4
at 4 = 1/8
at 5 = 1/16
... etc.
We can generalize this as:
(n-1)
Chances of going out at (n) = 2
8) We can now formulate the expected number of flips as:
(oo) (i-1) (oo) i
Sigma ( i / 2 ) ==> Sigma ((i+1) / 2 )
i=2 i=1
Now this can be changed to:
(oo) (oo) j (oo) i
Sigma ( Sigma (1 / 2 ) + Sigma (1 / 2 )
i=1 j=i i=1
As we all know:
(oo) j (n-1)
Sigma (1 / 2 ) = 1 / 2
j=n
:. Substituting:
(oo) (i-1)
Expected = Sigma (1 / 2 ) + 1
i=1
Substituting again:
Expected = 2 + 1 = 3
-- Barry
|
| An attempt to generalize from .3 (M = 3, only) to a legitimate cookie-winner
(many M's at once) follows. It relies on manipulation of determinants which
may not survive scrutiny.
John
** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
Let E(k) = expected # of flips, starting with k more heads than tails, or
with (M-k) more tails than heads.
Let p = probability of heads on any flip.
E(0) = 1 + p * E(1) + q * E(M-1), because you have to flip once, and it's
p that you go from (no flips) to (H), and
q that you go from (no flips) to (T), and
(T) is equivalent to (M-1 * H).
E(1) = 1 + p * E(2) + q * 0, because you have to flip once, and it's
p that you go from (H) to (HH), and
q that you go from (H) to (HT: stop).
E(2) = 1 + p * E(3) + q * E(1), because you have to flip once, and it's
p that you go from (HH) to (HHH), and
q that you go from (HH) to (HHT), and (HHT)
is equivalent to (H).
E(j) = 1 + p * E(j+1) + q * E(j-1), similarly, for j = 3,4,5,...,M-2.
E(M-1) = 1 + p * 0 + q * E(M-2), similar to E(1).
Reordering: E(0) - p * E(1) - q * E(M-1) = 1
E(1) - p * E(2) = 1
E(2) - p * E(3) - q * E(1) = 1
.
E(j) -p * E(j+1) - q * E(j-1) = 1
.
E(M-1) - q * E(M-2) = 1
Use determinants to solve for E(0). Denominator determinant is
| 1 -p 0 0 0 0 ..... 0 0 0 q |
| 0 1 -p 0 0 0 ..... 0 0 0 0 |
| 0 -q 1 -p 0 0 ..... 0 0 0 0 |
| 0 0 -q 1 -p 0 ..... 0 0 0 0 |
.
.
| 0 0 0 0 0 0 ..... 0 -q 1 -p |
| 0 0 0 0 0 0 ..... 0 0 -q 1 |
and there are few enough diagonals that this is equal to the determinant
if the top row's -p and -q are discarded, yielding:
| 1 0 0 0 0 0 ..... 0 0 0 0 |
| 0 1 -p 0 0 0 ..... 0 0 0 0 |
| 0 -q 1 -p 0 0 ..... 0 0 0 0 |
| 0 0 -q 1 -p 0 ..... 0 0 0 0 |
{D} .
.
| 0 0 0 0 0 0 ..... 0 -q 1 -p |
| 0 0 0 0 0 0 ..... 0 0 -q 1 |
Numerator determinant is
| 1 -p 0 0 0 0 ..... 0 0 0 q |
| 1 1 -p 0 0 0 ..... 0 0 0 0 |
| 1 -q 1 -p 0 0 ..... 0 0 0 0 |
| 1 0 -q 1 -p 0 ..... 0 0 0 0 |
.
.
| 1 0 0 0 0 0 .....-q 1 -p 0 |
| 1 0 0 0 0 0 ..... 0 -q 1 -p |
| 1 0 0 0 0 0 ..... 0 0 -q 1 |
Replace the top row with the sum of all the rows (I sure hope this doesn't
change the value of the determinant), yielding:
| M 0 0 0 0 0 ..... 0 0 0 0 |
| 1 1 -p 0 0 0 ..... 0 0 0 0 |
| 1 -q 1 -p 0 0 ..... 0 0 0 0 |
| 1 0 -q 1 -p 0 ..... 0 0 0 0 |
{N} .
.
| 1 0 0 0 0 0 .....-q 1 -p 0 |
| 1 0 0 0 0 0 ..... 0 -q 1 -p |
| 1 0 0 0 0 0 ..... 0 0 -q 1 |
Note that (1-p-q = 0) was used in every column but the first.
Finally,
{N} / {D} = M
|
| Let X(m,t) be the probability that, after t flips, the number of heads less
the number of tails modulo M is m. Let p be the probability of a head and
let q = 1-p be the probability of a tail.
We have the following recurrence relations:
X(M-1,1) = q
X( m ,1) = 0 m = 0, 2..M-2
X( 1 ,1) = p
X(M-1,t) = p X(M-2,t-1) t >= 2
X( m ,t) = p X(m-1,t-1) + q X(m+1,t-1) m = 2..M-2, t >= 2
X( 1 ,t) = q X( 2 ,t-1) t >= 2
X( 0 ,t) = p X(M-1,t-1) + q X( 1 ,t-1) t >= 2
Let
inf inf
--- ---
S(m) = > X(m,t) and E(m) = > t X(m,t)
--- ---
t=1 t=1
and assume that the sums S(m) and E(0) exist. We want to evaluate E(0).
Now
S(M-1) = X(M-1,1) + p S(M-2)
S( m ) = X( m ,1) + p S(m-1) + q S(m+1) m = 2..M-2
S( 1 ) = X( 1 ,1) + q S( 2 )
S( 0 ) = X( 0 ,1) + p S(M-1) + q S( 1 )
We remark that S(0) = 1, since we must eventually reach a multiple of M with
probability 1. We can also show this directly by summing the above equations:
M-1 M-1 M-1 M-1 M-1
--- --- --- --- ---
> S(m) = > X(m,1) + p > S(m) + q > S(m) = 1 + > S(m)
--- --- --- --- ---
m=0 m=0 m=1 m=1 m=1
So that S(0) = 1, as stated.
Rewriting the equations, we have the pretty set of equations:
S(M-1) = p S(M-2) + q S( 0 )
S( m ) = p S(m-1) + q S(m+1) m = 1..M-2
S( 0 ) = p S(M-1) + q S( 1 ) = 1
Now we note that
M-1 t-1
--- ---
> X(m,t) + > X(0,s) = 1 (*)
--- ---
m=0 s=1
(this is easily proved by induction on t). The interpretation of this equation
is that we either reach t flips, or we reach a multiple of M before that.
Manipulating this equation gives
M-1 inf inf
--- --- ---
> X(m,t) = > X(0,s), since > X(0,t) = S(0) = 1
--- --- ---
m=0 s=t t=1
Summing both sides
inf M-1 inf inf
--- --- --- ---
> > X(m,t) = > > X(0,s)
--- --- --- ---
t=1 m=0 t=1 s=t
and interchanging the order of summation gives
M-1 inf
--- ---
> S(m) = > t X(0,t) = E(0)
--- ---
m=0 t=1
which is just what we want to evaluate.
Returning to the equations for S(m), the astute reader will have noticed
that the following set of M+1 linear equations in M unknowns:
S(M-1) = p S(M-2) + q S( 0 )
S( m ) = p S(m-1) + q S(m+1) m = 1..M-2
S( 0 ) = p S(M-1) + q S( 1 ) = 1
has a solution: S(i) = 1. Thus,
M-1
---
E(0) = > S(m) = M
---
m=0
and so the expected number of flips is M.
- Gilbert
P.S. How'd I lark onto the problem? I tried to make E.Osman's problem a bit
harder by going for a multiple of 2. But this was too trivial (even if the
coin was unfair), so I decided to try a multiple of 3. The fact that E(0)=M
for M <= 4 (and a fair coin) was a little curious, and the longhand evaluation
for M=3 and an unfair coin was quite surprising. A computer program (for a
fair coin) showed the pattern, which was also trivially true (as R.Lary noted)
for a completely unfair coin. Figuring that it was probably true of any unfair
coin, I posted .0 as a teaser (supposing that someone else would try M=4 and
beyond), and started working on the problem myself, but getting absolutely
nowhere until I saw J.Munzer's approach. Suspecting something amiss when they
didn't easily generalize (!), I set to developing them from the X(m,t).
I started 'correcting' the equations, and tried to solve for the S(m), since
they also occurred in the similar equations for E(m). This was going slowly,
and I had the inkling that the S(m) should be treated as a group. Then I
wrote the text explanation of the X(m,t), and realized that the equation (*)
would be needed to clarify the definition. Thinking of each of these equations
graphically, I saw the 'overlap' of the X(0,t), and found that with a little
persuasion (using the fact that S(0)=1), the overlap could be turned around to
form E(0). An embarassment later, I realized that all the S(m) must equal 1.
|