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.

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).

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:**215**Joined:**

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:**

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:**215**Joined:**

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:**

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:**215**Joined:**

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

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.

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.

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.

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.

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.

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

GZIP: On