
pennies  problem with solution
I would argue that the odds would be 5050 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 5050 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 x1, flips x2 and x1 were HT, TH, and TT with equal probability. So flip x1 was
H with probability 1/3
P(x,M) = 2/3 * 1/2 = 1/3
flips x2 and x1 were HH, TH, TT with equal probability, so flip x1 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 x1 flips and does not stop there
G(x) = G(x1) * C(x1)
where C(y) is the odds that it does not stop at y1 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(x1) * 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 twoheaded coin :)
Jacob
Friday, February 08, 2002
Recent Topics
Fog Creek Home
