Fog Creek Software
Discussion Board




Pennies

So what am I missing here?  The solution to "Pennies":

===============================
i challenge you to a game. we each get one penny and we flip them at the same time. (so on turn 1, we each flip our respective pennies - turn 2, we flip them again, and so on until someone wins). i am looking to get heads then tails. you are looking to get heads then heads. so if you flip heads on any flip and then heads on the next flip, you win. if i flip heads on any flip and then tails on the next flip, i win. (its not a speed race, we both flip at the same time, except i'm only concerned with what appears on my coin, and you are only concerned with whats on your coin). are the odds fair? (obviously not, otherwise this wouldn't be a question). who has the advantage and why?
===============================

is posted below:

===============================     
Solved by blah

solution: pennies

(ummm,, I don't right too good. ;) )

In a 3 turn game:

O needs HH, X needs HT

HHH O

HHT OX

HTH X

HTT X

THH O

THT X

TTH

TTT

X wins 4 times out of 8, O wins 3 times out of 8

Its because in the event X loses there is a 50% chance of starting out on another H where O has to start on a T 75% of the time. (or something like that...)
===============================

In the "HHT" case, O wins on the second flip, X doesn't "win" until the 3rd flip.  But there is no 3rd flip, because the game's over.  So X doesn't win.

And if you're going to count 3 flips, no matter if the game's won already, then wouldn't you have to count "HHH" as *two* wins for O?

Seems pretty simple mathematically:  there are 4 different ways to flip a coin twice, 1 wins for O, 1 wins for X.  If you've already flipped once, then either it's an H or T - if it's an H, then they both have an equal chance of winning on the next toss (1 wins for X, the other wins for O).  If the first flip is a T, they both have zero chance of winning on the next toss...

But I've been wrong before - anything I'm missing here?

Joe Fordham
Wednesday, March 02, 2005

Which part of "we each get one penny" didn't you understand?

Skeptic
Saturday, March 05, 2005

So X is me, wanting heads-then-tails.  O is you, wanting heads-then-heads.  For shorthand, (H|T) means a simultaneous flip where I flipped heads and you flipped tails.

There are four "starting" states, such as after the very first flip where no one could possibly have won:
(H|H), (H|T), (T|H), (T|T).

Next, find values for the second flip which would satisfy my win condition or yours, or both:
Both: (H|H) --> (T|H)
X wins: (H|H) --> (T|T)
X wins: (H|T) --> (T|T)
O wins: (T|H) --> (H|H)

Since the "both" condition counts as a tie, X is twice as likely to win as O on a single roll (one-in-six versus one-in-twelve).  Since all rolls have the same set of initial states and the same probabilities, X is more likely to win.

Assuming ties are stopping points, I have a 50% chance to win and you have a 25% chance to win.  If ties just mean we flip again, I have a 2/3 chance to win and you have a 1/3 chance to win.

I'm pretty sure that's right.

Tail of the "g"
Monday, March 07, 2005

These can happen where O wins.

O wins: (H|H) --> (H|H)
O wins: (T|H) --> (T|H)

JHY
Monday, March 07, 2005

Yep, definitely jinxed it.  I completely forgot to draw the edges from each node to itself on my state diagram.  Grumble.

Good catch, JHY.

Tail of the "g"
Monday, March 07, 2005

O looks for HH
X looks for HT

Turn 1: X and O have zero chance of winning here
Turn 2: X and O have 1/4 chance of winning here

Turn 3: O has a 1/6 chance of winning here, but X has a 2/6 chance of winning here.

The reason for the asymmetry is that when O flips HT, O cannot win on the next turn but when X flips HH, X can win on the next turn. Thus, the chance of a win on turn 3 given that there is no win on turn 2 differs.

WanFactory
Tuesday, March 08, 2005

I calculated the average number of rounds before each person won: the result was 4 for the heads then tails person and 6 for the two heads in a row person.

John
Tuesday, March 08, 2005

Ok, I think I found a full solution: probability of the heads-then-tails person (call that X, the other O) winning is 5/8 (assuming that they start over replay on a tie).

Let P = probability of X winning, then
4P = Phh + Pht + Pth + Ptt

where
Phh = probability of X winning if X gets heads on first toss and O gets heads on first toss, etc...

A little analysis reveals:
P = Ptt (if both flip tails becomes like the original problem before the first flip)

4Phh = 0+ Pht + Ptt + 1 (if both flip heads on first, then either no one wins and it is as if we are on 2nd toss and first toss was X=h, O=t, or both win/tie and it is like original problem, or just X wins or just O wins)

4Pht = Phh + Pht + 1 + 1 (if X flips heads and O flips tails, then either X wins or it is as if both flipped heads or we are in the same scenario again)

4Pth = 0 + Pht + 0 + Ptt (if X flips tails and O flips tails, then either X loses or it is as if X flipped heads and O flipped tails or as if both flipped tails)

Solving a 4x4 linear system of equations (thank you microsoft excel) gives:
P = Ptt = Phh =5/8
Pht = 7/8
Ptt = 3/8

So after the first flip, probability of winning either stays the same at 5/8, jumps up to 7/8 or jumps down to 3/8.

Cant think of something simpler than the 4x4 linear system of equations though...

WanFactory
Wednesday, March 09, 2005

All the above "answers" miss a key point. The game continues till someone wins. That means you can't enumerate all the outcomes. Te guy who wants HH can flip an arbitrarily large number of tails. The other guy simultaneously flips the same arbitrarily large number of heads. Then one of them gets lucky.

Alex. McLellan
Wednesday, April 06, 2005

Making the same point, but more specifically...

There is an example above where the winning outcomes after 3 flips are analysed to check outcomes favourable to the two players.
This isn't enough to work out the overall probability of winning/losing.
You have also to continue with ALL the BOTH LOSING outcomes, since they will continue playing.
e.g.,
(T:H), (H:H), (T:H) - No winner - CONTINUE
(T:H), (H:H), (T:T) - X wins
(T:H), (H:H), (H:T) - Draw - both win
(T:H), (H:H), (H:H) - O wins

(H:H), (T:H), (H:H) - No winner - CONTINUE
(H:H), (T:H), (H:T)  - X wins
(H:H), (T:H), (T:H) - No winner - CONTINUE
(H:H), (T:H), (T:T) - X  wins

and so on ad nauseam.

There may be closed expressions for how many ways there are of getting to a particular number of throws without a winner, but I'm not smart enough to figure it out.

Alex. McLellan
Wednesday, April 06, 2005

I believe my answer takes into the account the "continue" situations.

WanFactory
Wednesday, April 06, 2005

          H:H  H:T  T:H  T:T
===================
H:H      X      --      <>  O
H:T      --      --      O    O
T:H      X      --      X    --
T:T      --      --      --    --

<> = draw
This table covers ALL scenarios in two sequential tosses.
I do not believe anyone has an advantage.

Mike
Wednesday, April 06, 2005

Great, let's play for even money. I'm looking for heads-then-tails. You look for heads-then-heads.

Either you'll realize that the situations you mark with a -- are not  all equivalent and that I have a slight advantage or I will make some money.

For example, if we both flip heads on first, and then I flip heads and you flip tails on second neither of us win so you mark it with a --.

Notice, however, that I now have an advantage because I may win on the 3rd toss but you may not win on the 3rd toss.

In other words, there are two states: unable to succeed next flip, able to succeed next flip (there is a tie if we both succeed, also we both start out unable to succeed next flip). Once I become "able to succeed" I can either succeed or remain "able to succeed" but I will never fall back to "unable to succeed". You, on the other hand, may become unable to succeed after being able to succed.

Imagine an archery contest in which you had to hit the target twice in a row, but I only needed to hit it twice but we had similar skills at archery.

WanFactory
Wednesday, April 06, 2005

No, I mark H:H --> H:T as  a draw.  You are confusing conditional probability with  a  joint probability of two  independent events.  Each cell in the table has an equal probabolity of 1/16.

Mike
Thursday, April 07, 2005

In the position when X and O  both have tails, none of them has a chance to win at the next toss, but when both have heads - a probability to win for both is 1/4  ( not 1/2 'cause the draw is also a possibility).  The rest is symmetric.

Mike
Thursday, April 07, 2005

Lets play for money

WanFactory
Thursday, April 07, 2005

Let me try this again:

Suppose on
Flip1: we both flip heads
Flip2: I flip heads and you flip tails.

This is not a draw that resets the game to its original state. Notice that on Flip 3, I could win the game by flipping tails but no matter what you get on flip 3, you will not win on flip 3 though you may win eventually.

In the case we both flip heads on flip 1, there is no corresponding flip 2 that gives you a similar advantage over me. The four possibilities are: you win, I win, both win, I have an advantage. You win cancels with I win. A draw we can ignore. Then we are left with an unmatched advantage for me.

Let's play for money.

WanFactory
Thursday, April 07, 2005

Now I got it.  The game is not reset.  The "DROW" still contains a possibility for you and no chance for me.  This is where I am being bobbed.  Simple simulation confirms you are right .  Thanks.

Mike
Thursday, April 07, 2005

Unfortunately, I'm not sure if my 5/8 solution is correct. I simply do not see any flaws in my reasoning  - which does not mean very much.

WanFactory
Thursday, April 07, 2005

Here's a little clearer an argument for those who are still having trouble following (like I was a moment ago).  I'm pretty sure my math is right.

Say X is going for HT and O is going for HH, and define "adv" as a 50% chance of winning on the next flip.  An outcome for a round is given by (X:O).

1. First round is H:H - possibilities are X wins (T:T), O wins (H:H), both wins (T:H), or adv X (H:T).  This one slightly goes to X (67.5%) vs O (50%).

2. First round is H:T - possibilities are X wins (T:T), adv both (H:H), X wins (T:H), or adv X (H:T).  This one's all X (75%) vs O (12.5%).

3. First round is T:H - possibilities are nothing (T:T), O wins (H:H), O wins (T:H), or adv X (H:T).  This one's for O (50%) vs X (12.5%)

4. First round is T:T - possibilities are nothing (T:T), adv both (H:H), adv O (T:H), or adv X (H:T).  This one's even at 25%.

So, the probability of X winning (or having already won) by the third round is 45%, while for O it's only 34.375%, or roughly 57:43 in favour of X.

If you bet $100 on X with even odds, you'd probably be up about $14.

Krease
Thursday, April 14, 2005

With each flip of the penny the number of head/tail combinations doubles. There are only 4 combinations after 2 flips, but 8 after 3. In general after n flips, there are 2^n combinations. Many of these combinations will not be applicable because there was a previous match (HT for player X, and HH for player O) in its history. The question then is: how many of these combinations are new matches?

Let q(A,m) be the number of new matches for player A at flip m. So you can see that, q(X,2) = 3 because only the combos, HHT and THT, are new matches (both HTH and HTT were new matches at flip 2, but now they're historical). Likewise, q(O,4) = 2 (HTHH and TTHH but all four HHxx and both THHx combos had already matched in flips 2 and 3, respectively).

In general at flip n, there were 2*q(A,n-1) combinations which were taken out of play because they were matches for player A in the previous flip. And 2*2*q(A, n-2) combinations were taken out by matching at step n-2. And so on. In general there were,

S(A,n) = sum (i = 1 to n-1) of (2^(n-i))*q(A,i)

previously matching combinations. So of the 2^n combinations at flip n, S(A,n) are out of play because of previous matches. So there are only 2^n - S(A,n) contending combinations. Half of these end in a H and half in T. There are q(A,n) matching combinations in flip n, but for a given A, they must all end in the same coin side.

For player O, q(O,n) matches end in H. So there are (2^n - S(O,n)) / 2 T-ending and (2^n - S(O,n) - 2*q(O,n))/2 H-ending non-matching combinations left after flip n (q(O,n) H-ending combinations matched). These will carry over into flip n+1.

At flip n+1, there are 2^n - S(O,n) - 2*q(O,n) Hx-ending combinations. Half of these end in HH and so are matching for the current flip.

So q(O,n+1) = ( 2^n - S(O,n) - 2*q(O,n) ) /2

But we also know that, 2^(n+1) - S(O,n+1) is the number of contending combinations for flip n+1 (by definition), so

2^(n+1) - S(O,n+1) = 2^n - S(O,n) + 2*q(O,n+1)

S(O,n+1) - S(O,n) + 2*q(O,n+1) = 2^(n+1) - 2^n = 2^n

and with the definition of S(O,n),

q(O,n+1) = q(O,n) + 1 !

The same induction works for player X and

q(X,n+1) = q(X,n) + 1

Seeding these equations, we get,

q(X,n) = n -1 and q(O,n) = n - 2, for n>2 and q(X,2) = q(O,2) = 1/4.

So the probability of player A having a match at or before flip n, is

P(A,n) = sum ( i = 2 to n) of q(A,n) / 2^n

And the difference between player X and player O having a match at or before flip n, is

P(X,n) - P(O,n) = sum (i=2 to n) of ( q(X,n) - q(O,n) )/ 2^n

(=) sum (i=3 to n) of (n-1 - (n-2) ) / 2^n
(=) sum (i=3 to n) of 1 / 2^n

As n approaches infinity this sum approaches 1/4. So the difference between player X winning and player O winning is 1/4. So player X has 5/8 probability of winning and player O has 3/8.

Just like WanFactory said.

slava
Friday, April 22, 2005

*  Recent Topics

*  Fog Creek Home