Alice and Bob play a game using fair $n$-sided dice, with $n>1$. Alice rolls two dice and takes the maximum as her score. Bob rolls one die for his score. If the players score the same, they restart the game, otherwise the highest score wins. What is the probability that Bob eventually wins?

$\textit{Hint:}$ The following may be useful: $\sum_{x=1}^n x^2=\frac{n(n+1)(2n+1)}{6}$

1. What is the probability of getting the sequence $HTHTHT$ in six coin flips?

2. Calculate $\sum_{n=7}^{17}n.$

3. Evaluate $\sum_{n=1}^{10}(n+1)^2 - 2 \cdot \sum_{n=0}^{10}n.$

What are the probabilities of Bob and Alice each scoring $x?$

Have you tried finding the probability that Alice scores less than $x$?

Could you use the probability that Alice scores less than $x$ to calculate the proabability that Alice scores $x?$

What is the probability of a draw in a single round?

Try calculating the probability of Bob winning the game after $i$ rounds.

How could you use this to find the probability that Bob eventually wins?

As Alice and Bob restart the game in the event of a draw, the probabilities of each outcome don’t change as the game goes on.

Let $A$ be the highest number Alice rolls, $B$ be the number Bob rolls, and $k=1,2,\ldots,n.$ We have:\begin{aligned} P(A \leq k) &= \big(\frac{k}{n}\big)^2\\ P(A = k) &= P(A \leq k) - P(A \leq k-1) = \big(\frac{k}{n}\big)^2 - \big(\frac{k-1}{n}\big)^2 = \frac{2k-1}{n^2}\\ P(B \leq k) &= \frac{k}{n}\\ P(B = k) &= \frac{1}{n}. \end{aligned}

We find the probability, $p,$ that Bob wins in a round, by summing the probability that Bob’s score is higher over all possible scores: $p = \sum\limits_{i=1}^{n}\big(P(B=i) \cdot P(A \leq i-1)\big).$ Substituting and simplifying gives us $p = \frac{1}{n^3} \cdot \sum\limits_{i=1}^{n}(i-1)^2,$ at which point we can change the bounds of the summation and apply the hint given in the question $p = \frac{1}{n^3} \cdot \sum\limits_{i=0}^{n-1}i^2=\frac{n(n-1)(2n-1)}{6n^3}.$

Similarly, we can find the probability $q$ that a round ends in a draw: $q = \sum\limits_{i=1}^n \big(P(A=i) \cdot P(B = i)\big).$ Again substituting and simplifying, we get that $q = \frac{1}{n}.$

The probability $r_i$ of Bob winning the game after $i$ rounds is the probability of Bob winning that round and drawing all the ones before it: $r_i=pq^{i-1}.$ To get the overall probability of Bob winning, we sum this geometric progression over all possible $i,$ which gives us $\sum\limits_{i=1}^{\infty} pq^{i-1} = \frac{p}{1-q}= \frac{1}{3} - \frac{1}{6n}.$