Players A and B take turns in answering trivia questions, starting with player A answering the first question. Each time A answers, she has a probability p1 of getting it right. Each time B plays, he has probability p2 of getting it right. Suppose that first player to answer correctly wins the game. What is the probability that A wins?
Attempt 1: I approached it with Markov chains with states $(A, B, win)$ representing A playing, B playing, and A winning the game respectively. If (pA, pB) denote the probability that A and B wins the game respectively, then I have the set of equations
$$pA = p1 + (1-p1)pB$$ $$pB = (1-p2)pA + p2 $$
The first equation says that if player A plays, she has a probability $p1$ of winning the game and $(1-p1)$ of getting the answer wrong, in which case it is player B's turn. The second equation says that player B has $p2$ chance of winning the game and with probability $(1-p2)$ it is player A's turn. However, the set of equations give the answer $pA=1$ which doesn't make sense.
Attempt 2: I augmented the states with $(A,B, Awins, Bwins)$, giving me the set of equations
$$pA = p1 + (1-p1)pB $$
$$pB = (1-p2)pA + p2*0 $$
The solution to this system is $pA = \frac{p1}{1-(1-p1)(1-p2)}$, which makes sense.
My questions are as follows:
- Where is the flaw in attempt1?
- How do we set up the states in such Markov chain type problems?
- How do we solve this problem in recursive fashion without the knowledge of Markov chains?
Thanks a ton!
Best Answer
I can think of two reasons why Attempt $1$ fails. 1) By setting up this mutually recursive relationship you're making the assumption that $pA$ and $pB$ aren't influenced by the choice of starting player. 2) We must have $pB=1-pA$ since the probability this game continues indefinitely is $0$. Therefore $pB$ can only depend on $p_1$ since $pA$ does not depend on $p_2$. But clearly we know from the problem statement that $pB$ should depend on $p_2$.
Here is how to solve this problem without Markov chains. Assuming player $A$ goes first, the probability $A$ wins within the first $n$ guess is given by $P(A_n)$. Then, $$P(A_n)=p_1+(1-p_1)(1-p_2)p_1+\cdots+(1-p_1)^{n-1}(1-p_2)^{n-1}p_1$$ E.g. to win on the second guess $A$ must mess up the first guess, have $B$ mess up their guess, and then guess it correctly. $$P(A)=\lim_{n\rightarrow \infty}P(A_n)=\dfrac{p_1}{1-(1-p_1)(1-p_2)}$$ by convergence of the geometric series since $(1-p_1)(1-p_2)<1$.