Fog Creek Software
Discussion Board




pennies - problem with solution

I would argue that the odds would be 50-50 because the game is not on a fixed turn basis.

In a 3 turn game:

O needs HH, X needs HT
HHH OO  *added O
HHT OX
HTH X
HTT X
THH O
THT X
TTH
TTT

After realizing that HHH would actually produce 2 winning combinations, the counts turn out to be 4X and 4O.

Taking it to a 4 round game:
HHHH OOO
HHHT OOX
HHTH OX
HHTT OX
HTHH OX
HTHT XX
HTTH X
HTTT X
THHH OO
THHT OX
THTH X
THTT X
TTHH O
TTHT X
TTTH
TTTT

The result are 12X and 12O - an even 50-50 split

Jacob
Thursday, February 07, 2002

I think this has already been covered:

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=144&ixReplies=22

Michael H. Pryor
Thursday, February 07, 2002

The above thread refers to the "Painfully Easy" problem, not to this, the "Pennies" problem.

Joseph, it looks like you're assuming the game continues indefinitely, with each player accumulating wins.  That makes the game fair.  However, the problem said the game wasn't fair, so I think the game ends once one or both people win on the same flip.

I will attempt to demonstrate who wins
Player Y needs HH to win
Player M needs HT to win

Let G(n) be the probability that the game lasts at least n flips.

Let P(n,Y) be the probability that Y wins on flip n, given that that many flips occur, let P(n,M) be the probability the M wins under the same circumstances.

P(1,Y) = P(1,M) = 0 
must have 2 flips for anyone to win

P(2,Y) = P(2,M) = 1/4
HH equally likely as HT

for x > 2

P(x,Y) = 1/3 * 1/2 = 1/6
since Y did not win on flip x-1, flips x-2 and x-1 were HT, TH, and TT with equal probability.  So flip x-1 was
H with probability 1/3

P(x,M) = 2/3 * 1/2 = 1/3
flips x-2 and x-1 were HH, TH, TT with equal probability, so flip x-1 was H with probability 2/3

This, by the way, is a rough proof already that M will win more often, since on any given flip he is at least as likely
to win.  In an interview, I'm guessing it would stop here

But let's finish it.
G(2) = 1  ; must reach two flips
G(3) = 1 - 1/4 - 1/4 + 1/16 = 9/16

for x > 3
G(x) is the odds that the game gets to x-1 flips and does not stop there

G(x) = G(x-1) * C(x-1)

where C(y) is the odds that it does not stop at y-1 flips given that it has gotten there

C(y) = 1 - P(y,Y) - P(y,M) + P(y,Y)*P(y,M)
C(y) = 1 - 1/6 - 1/3 + 1/18 = 10/18
since both can win at once, don't double count

G(x) = G(x-1) * 10/18 for x > 3


So the probability of Y winning is
1/4 + 1/6*9/16 + 1/6*9/16*10/18 +          1/6*9/16*10/18*10/18 + ...

The probability of M winning is
1/4 + 1/3*9/16 + 1/3*9/16*10/18 + 1/3*9/16*10/18*10/18 + ...

solving the infinite seires using:
1+10/18+10/18*10/18 + ... = 18/8

gives:

Probability of Y winning
1/4 + 1/6*9/16*18/8 = 192/768 + 162/768 = 354/768 ~= .46

Probability of M winning
1/4 + 1/3*9/16*18/8 = 192/768 + 384/768 = 576/768 = .75

Note that since both can win at once, the sum of the probabilities is > 1.

I believe I managed to get all the math right, but it's kinda early in the morning/late at night so please point out any errors.

Roy Pollock
Friday, February 08, 2002

Yes it has, but since this topic no longer appears on the message board, I am going to reply here. To make sure, I am responding to post 39 - pennies - posted May 14, 2001.

After reading the entire archive, it seems as though the posters are not solving the problem being asked.  The problem does not state 'If I told you that one of the pennies was a head, what is the probability that the second is also came up heads'.

The problem was stated as a game in which player 1 (p1) needed to get HT is order to win and p2 needed to get HH to win.  After someone had hit their expected target, the game would end and no more tosses would take place.  so after 2 tosses, the results are as follows.

HH p2 wins
HT p1 wins
TH continue
TT continue

After 3 tosses, then results are

HHH p2 wins
HHT p1 & p2 wins
HTH p2 wins
HTT p2 wins
THH p1 wins
THT p2 wins
TTH continue
TTT continue

After looking at this, it seems as though p1 would have the advantage as demonstrated in the answer given.  But what is not accounted for is the fact that HHH would result in p2 winning twice (which would not be allowed since the game would end after the second flip). 

The fact that I have had 3 straight heads on coin flips does not mean that the next flip of the coin will result in a tails.  Granted, the odds of 4 straight heads is 1/16 but the odds that the next flip will be heads is 1/2.

Unless you are using a two-headed coin :)

Jacob
Friday, February 08, 2002

*  Recent Topics

*  Fog Creek Home