5

Question A and B play until one has 2 more points than the other. Assuming that each point is independently won by A with probability p, what is the probability they will play a total of 2n points? What is the probability that A will win?

My attempt for the solution:

what is the probability they will play a total of 2n points?

For the first question, A and B will be "exchanging wins" until $|A-B| = 2$, if one wins twice in a row then its terminal state. Also, winning guarantees even total points,

$A = B + 2\\ A+B=B+B+2=2B+2$

A win always means even points then, making the job simpler. Probability prior to double winning streak shown in the following,

Let $E_{i}$ be a set of game from start till achieving $2*i$ points.

$P(E_{1}, E_{2}, \cdots, E_{n-1}) = P(E_{1}) + P(E_{2}) + \cdots + P(E_{n-1})\\ P(E_{1}, E_{2}, \cdots, E_{n-1}) = 1 + p*(p-1) + \cdots + (p*(p-1))^{2i-2}\\ P(E_{1}, E_{2}, \cdots, E_{n-1}) = \frac{1}{1-(p*(p-1))^{2}} - (p*(p-1))^{2i-1} - (p*(p-1))^{2i}$

*Note that $P(E_{1}) = P(\emptyset)$ since this is not the two winning streak.

The winning streaks can be a union of either $A$ wins twice in a row or $B$ wins twice in a row:

Let $S$ be the probability of 2n final points.

$P(S) = P(E_{1}, E_{2}, \cdots, E_{n-1})*p^{2} + P(E_{1}, E_{2}, \cdots, E_{n-1})*(p-1)^{2}$


What is the probability that A will win? I didn't really understand this question, does it mean from a tie points to a double winning streak of A? Anyway, in that case, I just use the result from first question,

$P(A_{win}) = P(E_{1}, E_{2}, \cdots, E_{n-1})*p^{2}$

JoeyAndres
  • 1,269

2 Answers2

7

The probability $a$ that A (ultimately) wins is easy to compute. She wins if she wins the first two games, or if the players are tied after $2$ games, but A ultimately wins. Thus, conditioning on the outcome of the first two games, we have $$a=p^2+2p(1-p)a.$$ Solve this linear equation for $a$.

For the probability the game lasts for a total of $2n$ points, we need that there is a tie at $2n-2$ points, and no one has won by then, and then one of the two players gets $2$ in a row.

For tie at $2n-2$ points, with no one having won, we need $n-1$ occurrences of the pattern AB or BA (we can "mix" these). This sort of pattern has probability $2p(1-p)$, so the required probability is $$[2p(1-p)]^{n-1}(p^2+(1-p)^2).$$

Remark: We can alternately use the formula for winning in $2n$ games to find A's probability of winning. Her probability of winning in $2$ is $p^2$. Her probability of winning in $4$ is $(2p-2p^2)p^2$. Her probability of winning in $6$ is $(2p-2p^2)^2p^2$. And so on. So her probability of winning is $$p^2+p^2(2p-2p^2)+p^2(2p-2p^2)^2+p^2(2p-2p^2)^3+\cdots.$$ This is an infinite geometric series, first term $p^2$, common ratio $2p-2p^2$. Now use the formula for the sum of such a series.

More complicated for sure than the simple linear equation approach we gave in the answer!

André Nicolas
  • 507,029
  • I'll digest this for a minute or 2, I just hope your still online then so I can clarify stuff. – JoeyAndres Jun 28 '14 at 05:21
  • I will be around for a while, I have made the argument somewhat compact. – André Nicolas Jun 28 '14 at 05:23
  • I got your answer for the first question, may I ask for clarification on the answer on the second question? What is "She wins if she wins first two games, or if the players are tied after 2 games". – JoeyAndres Jun 28 '14 at 05:29
  • Player A wins if she wins the first two games. Clear. She also wins if the first two games end AB or BA, but A ultimately manages to win. Given they are tied after the first two games, A's probability of winning is exactly the same as her initial probability of winning, hence the result. I can make an explicit conditional probability calculation if you wish. I will also add a remark giving a different way of solving the A wins problem. – André Nicolas Jun 28 '14 at 05:37
  • I have difficulty with the 2nd question, I get that $p_{2}$ if the player wins the first two games. I get that $2p(1-p)$ is to account for the pattern AB or BA, but why $2p(1-p)a$? How do you literally translate $2p(1-p)a$ in words? – JoeyAndres Jun 28 '14 at 05:37
  • Here it is with lots of symbols. Let $W$ be the event A wins, let $I$ be the event "instant win" ($2$ games) and let $T$ be the event "tie after $2$." Then $W=I\cup (T\cap W)$. So $\Pr(W)=\Pr(I)+\Pr(T\cap W)$. And $\Pr(T\cap W)=\Pr(T)\Pr(W|T)$. But $\Pr(W|T)=\Pr(W)=a$. But the point is that if there is a tie after $2$, A has just the same chance of ultimately winning as she had at the beginning. – André Nicolas Jun 28 '14 at 05:51
  • Thanks, that Remark cleared it up more. Although M.Vinay gave a simple explaination of breaking cases, I prefer this one since it is more rigorous. Before I stop bothering you, do you know any websites or book that have lots of examples of these kind of problem (suitable for someone beginning with probabilities)? – JoeyAndres Jun 28 '14 at 05:51
  • MSE has an enormous number of such problems, just hard to find. I have heard good things about the Khan Academy. – André Nicolas Jun 28 '14 at 05:53
  • @JoeyAndres Usually, I too prefer a recursive approach. You might enjoy this problem: A bacteria population starts out with one bacterium. The bacterium either divides into two bacteria with probability $p = 3/4$, or dies. The same applies for every bacterium in successive generations. What is the probability that the population never dies out? Calculate the probability for an unknown (constant) value $p$. Advanced version: http://bayesianthink.blogspot.in/2012/08/bacteria-puzzle.html#.U65ZxLG8TSE – M. Vinay Jun 28 '14 at 06:10
2

If the players are currently tied, and then one wins twice in a row, that player wins and the game ends. If one player is currently leading, then the other player has to win the next game to reach a tie. Therefore, in order for the result of the first $2n - 2$ games to be a tie, the wins have to be in the form of $n - 1$ pairs, each of the form $AB$ or $BA$ (for example: $ABBABAAB$). Thus, the wins are in the pattern $\underbrace{(P_1)(P_2)\ldots(P_n)}_{n-1}$, where each pair $P_i$ is either $AB$ or $BA$ (independently of the other pairs). If $q = 1 - p$, each of the pairs $AB$ and $BA$ has probability $pq$ (for $qp = pq$). As there are two possibilities for each of the $n - 1$ pairs $P_i$, there are $2^{n-1}$ possible configurations. Thus the probability of a tie after $2n - 2$ games is $2^{n-1}(pq)^{n-1}$.

Now, the last two wins can be either $AA$ with probability $p^2$, or $BB$ with probability $q^2$. So the probability of there being exactly $n$ games is $\boxed{2^{n-1}(pq)^{n-1}(p^2 + q^2)}$.

If $A$ wins, then the only possibility for the last two wins is $AA$, so the probability that $A$ wins in $2n$ games is $2^{n-1}(pq)^{n-1}p^2$.

The probability that $A$ wins after an indefinite number of games can be obtained by summing the probabilities for $n = 1, 2, \ldots$

$\displaystyle\sum\limits_{n=1}^{\infty}(2pq)^{n-1}p^2 = \boxed{\dfrac{p^2}{1 - 2pq}}$.

M. Vinay
  • 9,004
  • @AndréNicolas Now we agree! Thanks for pointing out the mistake. – M. Vinay Jun 28 '14 at 05:55
  • 1
    @JoeyAndres Note that the probability that $B$ wins is, by symmetry, $\dfrac{q^2}{1 - 2pq}$. And either $A$ or $B$ must ultimately win (the probability of a tie approaches $0$ as the number of games approaches infinity - note that $2pq < 1$). So the total $\dfrac{p^2 + q^2}{1 - 2pq}$ should be $1$. Check whether it is so. – M. Vinay Jun 28 '14 at 06:16