I was trying to solve this problem (Strategic Practice Week 3, Homework problem 4 in Harvard's Stat 110 class), by framing it as a gambler's ruin problem:

Calvin and Hobbes play a match consisting of a series of games, where Calvin has probability $p$ of winning each game (independently) and $q = 1-p$. They play with a “win by two” rule: the first player to win two games more than his opponent wins the match. Find the probability that Calvin wins the match (in terms of $p$), by interpreting the problem as a gambler's ruin problem.

Here's how I approached the problem:


$W:$ Calvin wins the match;

$D_i:$ (Wins by Calvin) $-$ (Wins by Hobbes) $= i$

$p_i:$ $\Pr($W | $D_i$$)$

Now, by conditioning on the first game, and using the law of total probability, we get:

$p_i = p p_{i+1} + qp_{i-1}$, with $p_2 = 1$ (Calvin wins with certainty if the difference is $2$) and $p_{-2} = 0$ (Calvin loses with certainty if the difference is $-2$).

Solving this recurrence relation (which I omit here, since it's mostly algebra gymnastics), we get:

$p_i = \dfrac{p^6}{p^8 - q^4}p^i - \dfrac{p^2q^2}{p^8-q^4}(\dfrac{q}{p})^i$

Since both Calvin and Hobbes start with a $0$ difference in wins, what we need to find is $p_0 = \dfrac{p^2(p^4-q^2)}{p^8-q^4}$.

However, the answer turns out to be $\dfrac{p^2}{p^2+q^2}$, which can be easily obtained by using the law of total probability and conditioning on the number of wins in the first 2 matches (0 win, 1 win or 2 wins, with the number of wins $X \sim $ Bin($2,p$)).

Where am I going wrong with my interpretation of the problem as a gambler's ruin problem?


Your formulation is correct. Your solution to the recurrence relation (the part you omitted) is not. You should find

$$\lambda=\frac{1 \pm \sqrt{1-4pq}}{2p}=\frac{1 \pm (2p-1)}{2p}=1,\frac{q}{p}.$$

Thus if $0<p<1$ then the basis of solutions is given by $\{ 1,(q/p)^i \}$, except when $p=q$ in which case the basis of solutions is given by $\{ 1,i \}$. So in particular the inclusion of $p^i$ in the basis of solutions was not correct.

  • $\begingroup$ Ah, yes! I somehow wrote $p$ instead of $1$ for the first root. And to think I was checking and rechecking the subsequent calculations, without so much as a glance back! Lesson learnt, thank you! :) $\endgroup$ – Train Heartnet Feb 5 '18 at 14:47
  • $\begingroup$ But even then, with the now correct $p_i = \dfrac{p^2-q^2}{p^2} + \dfrac{q^4-p^2q^2}{p^4}(\dfrac{q}{p})^i$ (assuming $p \neq q$), I'm getting $p_0 = \dfrac{p^4+q^4}{p^4}$, which is incorrect. $\endgroup$ – Train Heartnet Feb 5 '18 at 15:19
  • $\begingroup$ @Heartnet You made a sign error in simplifying. $\endgroup$ – Ian Feb 5 '18 at 15:22
  • $\begingroup$ Ah, darn it. Okay, assuming the $p_i$ I wrote is correct, now I have $p_0 = \dfrac{(p^2-q^2)^2}{p^4}$, which still is incorrect. Or did you mean I made a sign error elsewhere, while obtaining $p_i$? I'm really sorry to be a bother, but I just want to nail this problem. $\endgroup$ – Train Heartnet Feb 5 '18 at 15:34
  • $\begingroup$ @TrainHeartnet There was definitely a sign error there but I think there was also a mistake further back. I usually prefer to do this with linear algebra, which in this case means solving the system $a_1+(q/p)^2a_2=1,a_1+(q/p)^{-2}a_2=0$. This solution to that is not all that complicated; the only ugly thing is the division by the determinant. $\endgroup$ – Ian Feb 5 '18 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.