• 1
• 2 ooff
Topic Author
Posts: 7
Joined: May 26th, 2010, 1:17 am

### Coint toss game

Hi,This teaser is from a quant interview prepare book. The original question states as below:Two players, A and B, alternatively toss a fair coin (A tosses the coin first, then B tosses the coin, then A, then B...) If there is a head followed by a tail, the game ends and the person who tosses the tail wins. What's the probability that A wins the game?The answer given uses law of total probability. Prob of A win the game = P(A) = 1/2 P(A|H) + 1/2 P(A|T) where P(A|H), P(A|T) are probs of A wins the game given his first toss is H or T respectively.It further says P(A|H) = 1/2 * 0 + 1/2 * (1- P(A|H)), where 1/2 *0 is due to B tosses a T after A's H. So far I understand. The part I don't understand is about the 1/2 * (1 - P(A|H)) part. If after A's first H, B tosses a H as well, why/how do we get the prob of (1-P(A|H))? Also, it says P(A|T) = P(B) where P(B) is the prob of B wining. I understand if A's first toss is a T, the game essentially starts again with B is the first one to toss. But why do we have the prob P(A|T) = P(B), i.e. given A's first toss of T, A's prob of wining is the same as B's wining? I don't quite understand this equation here...Thanks for some insights. Costeanu
Posts: 189
Joined: December 29th, 2008, 5:33 pm

### Coint toss game

If A gets tails, basically the game starts afresh, only that A is the second player now. The probability that the second player wins is P(B). So P(A|T) = P(B). Vanubis1
Posts: 152
Joined: February 21st, 2011, 7:41 am

### Coint toss game

You have 2 distincts equations:One on P(A) and one on P(A/H).P(A)=1/2*P(A/T)+1/2*P(A/H)As you notice, P(A/T)=P(B)=1-P(A)P(A/H)=1/2*0+1/2*(1-P(A/H))Because after A tossed a H, if B tosses a T, it's over for A and if B tosses a H, it's 1-P(B/H) and P(B/H)=P(A/H)You find easily P(A/H)=1/3 and P(A)=4/9
Last edited by Vanubis1 on August 26th, 2014, 10:00 pm, edited 1 time in total. CommodityQuant
Posts: 218
Joined: July 5th, 2007, 6:16 am

### Coint toss game

QuoteThis teaser is from a quant interview prepare book.What is the name of this book?(Since it's not one of Smullyan's books on mathematical logic, the name of the book is probably not "What is the name of this book?".)CommodityQuant reaverprog
Posts: 194
Joined: October 28th, 2009, 8:53 am

### Coint toss game

Quick question :I still don't see why P(A|T) = P(B), because this assumes that the probability of B winning when A tosses first = probability of B winning when B tosses first, which is clearly wrong. In theory, we should say P(A|T) = P(B|B starts first), which makes sense to me. Can someone please explain then why P(A|T) = P(B) ? Same question applies to P(A|HH) = P(B|H).Thanks CommodityQuant
Posts: 218
Joined: July 5th, 2007, 6:16 am

### Coint toss game

reaverprog,We are assuming that A tosses first. If A tosses a tail on the very first throw, that tail becomes totally irrelevant. It has no bearing on any Heads-Tail sequence. So we may as well pretend A's first tail never happened and let B have her turn. This puts A into the position of "second player". Note that since B tosses second, P(B) simply means the probability of a second player win. If A tosses a tail, A gets a win if the second player wins. (Remember to assume the tail never happened). That is why P(A|T) = P(B).The condition "given that B starts first" is confusing because the question stipulates that A starts first. A and B simply denote the first and second player respectively.If we begin with HH then A's first H becomes totally irrelevant and we may as well pretend it never happened but keep A as the player tossing next. If we pretend the first H never happened and let A toss next, then A is acting as the second player after an initial H. That is why P(A|HH) = P(B|H).CommodityQuant reaverprog
Posts: 194
Joined: October 28th, 2009, 8:53 am

### Coint toss game

CommodityQuant >> thanks for your response. Im still a bit confused about the first equation, P(A|T) = P(B). If you start from the whole beginning of the game (ie before the player A tosses), P(A) is the proba of A winning and P(B) proba of B winning, but this is conditional on the fact that A starts tossing (so P(A) = P(A |A starts tossing), P(B) = P(B|A starts tossing). Now when A tosses T, I understand that this swaps the roles of players A and B, in the sense where A becomes the second player ... but saying that P(A|T) = P(B) doesn't look right, because if we draw a tree we see that P(A|T) excludes the path which represents getting HT from the first two tosses. So isn't right to say : P(A|T) = P(B|B starts) <> P(B|A starts) ? CommodityQuant
Posts: 218
Joined: July 5th, 2007, 6:16 am

### Coint toss game

reaverprog,You're using a messy notation and terminology and it's preventing you understanding me. Please think of A as simply being shorthand for the first player. Please think of B as simply being shorthand for the second player.If you use that notation/terminology, it makes no sense to add conditions like "given that B tosses first".Once you've got that convention settled, then please reread my response. Then please either confirm that you now understand, or ask further questions.CommodityQuant MattF
Posts: 925
Joined: March 14th, 2003, 7:15 pm

### Coint toss game

QuoteOriginally posted by: reaverprogCommodityQuant >> thanks for your response. Im still a bit confused about the first equation, P(A|T) = P(B). If you start from the whole beginning of the game (ie before the player A tosses), P(A) is the proba of A winning and P(B) proba of B winning, but this is conditional on the fact that A starts tossing (so P(A) = P(A |A starts tossing), P(B) = P(B|A starts tossing).By definition, A starts tossing so these simplify to P(A) and P(B).QuoteNow when A tosses T, I understand that this swaps the roles of players A and B, in the sense where A becomes the second player ... but saying that P(A|T) = P(B) doesn't look right, because if we draw a tree we see that P(A|T) excludes the path which represents getting HT from the first two tosses. So isn't right to say : P(A|T) = P(B|B starts) <> P(B|A starts) ?If the first toss is a tail then all of A's subsequent wins are going to be identical to B's wins from the starting position except for an initial tail so P(A|T) = P(B)P(A|T) certainly excludes HT but it doesn't exclude THT which is the corresponding A win after a tail. reaverprog
Posts: 194
Joined: October 28th, 2009, 8:53 am

### Coint toss game

thanks for the explanations, much clearer now wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

### Coint toss game

instead of the 2-player game, suppose there are N people participate the tossing (e.g., with three players, the turns are A,B,C,A,B,C...).same stopping criteria: whoever gets a tail after a head wins.one can prove that the 2nd player has the highest probability of winning while the 1st player has the least. the probability of n-th player winning is actually monotonic: P(2)>P(3)>... >P(N)>P(1). the question is how large the edge: P(2)-P(1) is?(we have seen that N=2 results 1/9 and it's easy to see when N->infty, the edge is 1/4)
Last edited by wileysw on September 4th, 2014, 10:00 pm, edited 1 time in total. Vanubis1
Posts: 152
Joined: February 21st, 2011, 7:41 am

### Coint toss game

If N->infinity, it's quite easy to calculate P(inf)(i): P(inf)(i)=(i-1)/2^iSo, if N is finite, we can obtain P(i)=sum k P(inf)(i+kN)=sum k (i+kN-1)/2^(i+kN)After some calculation:P(i)-P(i-1)=1/2^(i-1)*2^N/(2^N-1)-P(i)Let's note X=2^N/(2^N-1)P(i)=P(i-1)/2+X/2^iP(i)=P(1)/2^(i-1)+X*(i-1)/2^iP(1)=P(N+1)=P(1)/2^N+X*N/2^(N+1)P(1)=N*X^2/2^(N+1)P(2)=N*X^2/2^(N+2)+X/4P(2)-P(1)=X/4-N*X^2/2^(N+2)P(2)-P(1)=2^(N-2)*(2^N-N-1)/(2^N-1)^2
Last edited by Vanubis1 on September 4th, 2014, 10:00 pm, edited 1 time in total. emmy
Posts: 17
Joined: February 8th, 2005, 11:21 pm

### Coint toss game

Hi Vanubis1,In the 2nd equation of two players, you said thatP(A/H)=1/2*0+1/2*(1-P(A/H))Because after A tossed a H, if B tosses a T, it's over for A and if B tosses a H, it's 1-P(B/H) and P(B/H)=P(A/H)Should P(A/H)=1/2*0+1/2*P(A/HH)=1/2*0+1/2*P(B/H)=1/2*0+(1-P(A/H)), where P(B/H)=1-P(A/H)? Thanks. Vanubis1
Posts: 152
Joined: February 21st, 2011, 7:41 am

### Coint toss game

No.P(A/HH)=1-P(B/H)=1-P(A/H)Because the proba he wins with H followed by B/H is 1-the proba that B wins with an H : 1-P(B/H)The notation used is P(A/...) is the proba that A wins and P(B/...) is the proba that B wins.
Last edited by Vanubis1 on September 18th, 2014, 10:00 pm, edited 1 time in total. ghlian
Posts: 5
Joined: March 27th, 2007, 1:21 pm

### Coint toss game

using Markov Chain state transition graph is easy to understand and solve it.  