Wilmott Forums - two heads

Streambase

Forum Navigation:

login

FORUMS > Brainteaser Forum

Topic Title: two heads
Created On Wed May 05, 04 03:47 PM

Topic View:

View thread in raw text format

MikeM
Senior Member

Posts: 276
Joined: Mar 2003

Wed May 05, 04 03:47 PM

User is offline

...Apparently this was an interview question. It's more complicated than it looks. Best of all, standard quant tricks tend to lead you in the wrong direction:

When flipping an unbiased coin, how long do you have to wait on average before you get two heads in a row.

zerdna
Senior Member

Posts: 1890
Joined: Jul 2002

Wed May 05, 04 04:58 PM

User is offline

Suppose all path die when conseq HH is encountered. Call P(n, H) number of paths that end in H and survive until step n, P(n, T) that end in T and survive until n.
P(n, H) = P(n-1,T)
P(n, T) = P(n-1,T)+P(n-1,H)=P(n-1,T)+P(n-2,T)
Clearly P(n,H) = F(n), P(n,T) = F(n+1), total paths surviving until n P(n)=P(n,H)+P(n,T)=F(n+2),
cumulative prob of surving Pr(n)=F(n+2)/2^n,
where F is fibonacci seq
Prob of dying on step n is
d(n)=Pr(n-1)-Pr(n)=(F(n+1)-F(n+2)/2)/2^(n-1)
Then time to death is
sum(n*d(n))
Might be a way to sum it up using explicit formula for fibonacci, or generating function tricks, have no time to think. I have a feeling there is a neat cool way of dealing with this problem, but this is just old man straight calculation that is also ok sometimes. Maybe MikeM will reveal the deal.

-------------------------
"Doubt everything. Find your own light." -- Gautama Buddha

Athletico
Senior Member

Posts: 846
Joined: Jan 2002

Wed May 05, 04 05:15 PM

User is offline

Let tau be the stopping time: tau = # of flips before two consec heads.

Mike is right, the initial condition does complicate things:

Let x = E[tau], the desired uncondtional expectation.

Let h = E[tau | first flip is Heads] = 1 + 1/2(x + 2)

Let t = E[Tau | first flip is Tails] = 1 + x

x = E[tau] = E[tau | first flip is Heads]P[Heads] + E[tau | first flip is Tails] P[Tails]

x = 1/2(t + h) = 1/2(1 + 1/2(x + 2) + 1 + x) = 3/2 + 3x/4

x = 6 flips

zerdna
Senior Member

Posts: 1890
Joined: Jul 2002

Wed May 05, 04 05:58 PM

User is offline

Athletico seems right, i wonder how to sum my fibonacci stuff

-------------------------
"Doubt everything. Find your own light." -- Gautama Buddha

adannenberg
Senior Member

Posts: 280
Joined: Jul 2002

Wed May 05, 04 06:40 PM

User is offline

2 heads in a row is easy. How about 5 heads in a row? Ans = 62. See it?

MikeM
Senior Member

Posts: 276
Joined: Mar 2003

Wed May 05, 04 07:34 PM

User is offline

Athletico is right (and very nicely explained).

As Zerdna pointed out, the Fibonacci sequence does rear its head in this problem, but I don't think there is any simple way to turn this into an answer.

The natural quant thing to do would be to try a binomial tree, but that turns out to be a big mistake for this problem.

...will have to think about 5 heads.

kr
Senior Member

Posts: 1887
Joined: Sep 2002

Wed May 05, 04 11:13 PM

User is offline

the fibanocci thing is pretty straightforward... if you write

state space = {X, Y, Z}
X = no heads yet
Y = one head
Z = two heads

then P(X->X) = P(X->Y) = P(Y->X) = P(Y->Z) = 1/2, P(Z->Z) = 1. This gives you a simple 3x3 transition matrix whose characteristic polynomial is (1 - X).(X^2 - X/2 - 1/4), and just like in fib you have nontrivial eigenvalues coming from the golden section - in this case 1/2 . ((1 +/- sqrt(5)) / 2)... and as usual, the sqrt goes away when these roots are powered up and added or subtracted, just like e^ix / sin / cos... this addition/subtraction comes from the eigenvectors etc...

plain old pad o paper problem

-------------------------
Fools!
I'm Nonius!!!!

karakfa
Member

Posts: 135
Joined: May 2002

Thu May 06, 04 04:05 AM

User is offline

The general solution for the expected value of number of flips (T) for N heads in a row is:
E{T(N)} = 2^(N+1) - 2

for N=2 => E{T2} = 6
for N=5 => E{T5} = 62

S P O I L E R

Define the states for 0, 1, 2, 3,..., N-1 # contiguous heads so far.
Define the expected value of flips from given state as e0, e1, ... e(N-1), which satisfy the following
e0 = 1/2e0 + 1/2e1 + 1 (1/2 prob tails stay at 0. 1/2 prob move to 1, increase flips by one)
e1 = 1/2e2 + 1/2e0 + 1 (1/2 prob move to state 2, 1/2 back to state 0, increase flips by one)
....
e(N-1) = 1/2.1 + 1/2(e0+1) (1/2 prob done, 1/2 prob back to e0, increase flips by one for that case only)
==============
since starting from 0 #heads, we're looking for the value of e0.

straighforward algebra gives the recursive formula for the solution of e0
g(n) = 2g(n-1) + 2
with g0 = 0

Therefore:

E{T(N)} = g(N) = 2^(N+1) - 2.

-------------------------
karakfa.

Edited: Thu May 06, 04 at 04:11 AM by karakfa

Aaron
Senior Member

Posts: 6371
Joined: Jul 2001

Thu May 06, 04 04:06 AM

User is offline

Come on guys, doesn't 2^(n+1) - 2 jump out at you as the formula for the expected number of flips before n heads in a row?

Sorry, my post crossed with the last one.

-------------------------
Aaron Brown

Edited: Thu May 06, 04 at 04:07 AM by Aaron

Aaron
Senior Member

Posts: 6371
Joined: Jul 2001

Thu May 06, 04 04:30 AM

User is offline

My reasoning is different.

Suppose someone has already flipped n-1 times, but we don't know what came up. The probability that the first flip completes n heads is 2^-n. The probability is the same for the second and all subsequent flips. The probabilities are not independent, but that doesn't matter for expected waiting time. It's 2^n flips, 1 over the (constant) probablility of completion.

Our expected waiting time is longer because we get cheated out of any success in the first n-1 flips. If the first flip is a head, we get cheated 2^(1-n) of the time. If the first k flips are heads, we get cheated 2^(k - n) of the time. Reversing the order, this is the sum 2^-1, 2^-2, . . .2^(1-n) which of course equals 1 - 2^(1-n).

Multiplying 2^n times 2 times 1 - 2^(1-n) gives 2^(n+1) - 2.

-------------------------
Aaron Brown

Posts: 94
Joined: Dec 2003

Thu May 13, 04 01:08 PM

User is offline

A nice way to do this question is to use martingale theory. Proceeding like the "Abracadabra" question in David William's "Probability with Martingales" let's turn this into a gambling question.

Suppose just before each coin toss a gambler arrives and bets 1 on the outcome being heads.
If he wins he receives double his stake and bets on the next coin toss. If the outcome is tails the gambler leaves.
Let \tau be the stopping time the number of tosses at the first occurence of n heads and M_t be the winnings of the house.

We can use Doobs optional sampling theorem if we suppose E(\tau)<\infinity.
So E(M_\tau)=0.

Hence 0=-( 2+2^2+2^3+...+2^n)+\tau.
\tau=2(2^n-1).

Ayone know an easy way to show E(\tau)<\infinity?

Aaron
Senior Member

Posts: 6371
Joined: Jul 2001

Thu May 13, 04 04:04 PM

User is offline

The gambler gives another easy way to do the problem.

A gambler bets $1 on every flip that the result will be heads at even odds. She quits after she wins n times in a row. We know that any strategy must have an expected value of zero. Let K be the expected number of flips. We know that she won $n on the last n flips and, if K>n, that she lost $1 on the flip before that. So she must have an expected loss of $n - 1 on the first K - n - 1 flips.

So the question is, how many times must I flip a coin such that I expect to lose $n - 1 if I know that there is no run of n heads?

For n = 1 the answer is clearly 0, meaning K = 2. Knowing there is no run of 1 head means there are no heads, so I will lose $1 per flip. I only lose $0 at zero flips. So for n = 1 I throw 0 times and expect 0 heads and 0 tails. Let H(n) be the expected number of heads I throw before the string of n and T(n) be the expected number of tails. H(1) = T(1) = 0.

We have the recursive relation: H(n+1) = H(n) + T(n) + 1 and T(n) - H(n) = n - 1 to keep the total expectation zero. Substituting gives H(n+1) = 2*H(n) + n. With the initial condition H(1) = 0, that means H(n) = 2^n - n - 1. T(n) = 2^n - 2. K(n) = H(n) + T(n) + n + 1 = 2^(n+1) - 2.

-------------------------
Aaron Brown

mj
Senior Member

Posts: 3006
Joined: Dec 2001

Thu May 13, 04 09:04 PM

User is offline

Quote
Originally posted by: FV
A nice way to do this question is to use martingale theory. Proceeding like the "Abracadabra" question in David William's "Probability with Martingales" let's turn this into a gambling question.

Suppose just before each coin toss a gambler arrives and bets 1 on the outcome being heads.
If he wins he receives double his stake and bets on the next coin toss. If the outcome is tails the gambler leaves.
Let \tau be the stopping time the number of tosses at the first occurence of n heads and M_t be the winnings of the house.

We can use Doobs optional sampling theorem if we suppose E(\tau)<\infinity.
So E(M_\tau)=0.

Hence 0=-( 2+2^2+2^3+...+2^n)+\tau.
\tau=2(2^n-1).

Ayone know an easy way to show E(\tau)<\infinity?

can't you use the same argument as in the abracabradra question to get E(\tau) < \infty ?

-------------------------
Quant Job Interview Questions and Answers now available on lulu.com and amazon.com

Posts: 94
Joined: Dec 2003

Thu May 13, 04 09:54 PM

User is offline

Quote
Originally posted by: mj
can't you use the same argument as in the abracabradra question to get E(\tau) < \infty ?

Off the top of my head I can't remember what the argument was!

scholar
Senior Member

Posts: 821
Joined: Oct 2001

Wed Jun 23, 04 04:37 PM

User is offline

The same result 2^{K+1} -2 can be obtained in two lines using recursion. Let N_k is the number of trials needed to get k heads in the row. It satisfies the recursion

N_{k} = 0.5*(N_{k-1} + 1) + 0.5*( N_{k-1} + 1 + N_{k})

meaning that with prob 1/2 we need only one more flip, and we probability 1/2 we get a tail and will have to start the whole thing anew. Therefore we obtain

N_{k} = 2 N_{k-1} + 2

whose solution is

N_{k} = 2^{k+1} - 2

View thread in raw text format

FORUMS > Brainteaser Forum

Forum Navigation:

© All material, including contents and design, copyright Wilmott Electronic Media Limited - FuseTalk 4.01 © 1999-2010 FuseTalk Inc.