I have taken to the habit of giving my posts subtitles. Sometimes you just need a bit of extra description to capture the journey of the problem. We bashed our heads against this problem for roughly two weeks, but in the end, beautiful things resulted.

Q:

Each of the integers from $1$ to $n$ is written on a separate card, and then the cards are combined into a deck and shuffled. Three players, $A$, $B$, and $C$, take turns in the order $A$, $B$, $C$, $A$, $\dots$ choosing one card at random from the deck. (Each card in the deck is equally likely to be chosen.) After a card is chosen, that card and all higher-numbered cards are removed from the deck, and the remaining cards are reshuffled before the next turn. Play continues until one of the three players wins the game by drawing the card numbered $1$.

Show that for each of the three players, there are arbitrarily large values of $n$ for which that player has the highest probability among the three players of winning the game.

A:

This problem, as with most problems regarding games and probability, lends itself immediately to formulating some kind of recursive relationship between the probabilities involved. Define $A(n), B(n), C(n)$ to be the probabilities that $A, B, C$ win the game, respectively, when they begin the game with $n$ cards in the deck.

We observe, courtesy of the singular Franklin Lu, that if we just consider the first player $A$ in a game of $n+1$ cards, $A$ has a $\frac{1}{n+1}$ probability of picking the $n+1$ card, in which case the players rotate turns, and essentially $A$ becomes the new $C$. The other $\frac{n}{n+1}$ of the time, $A$ picks a card smaller than $n+1$, which is equivalent to $A$ playing the game with a deck of $n$ cards, since any card $A$ picks will automatically remove $n+1$ as well. This gives us the recurrence:

\[ A(n+1) = \frac{1}{n+1}C(n) + \left(1-\frac{1}{n+1}\right)A(n) \]

Applying similar logic to $B$ and $C$, we obtain the following system of recurrences:

\[ A(n+1) = \frac{1}{n+1}C(n) + \left(1-\frac{1}{n+1}\right) A(n) \] \[ B(n+1) = \frac{1}{n+1}A(n) + \left(1-\frac{1}{n+1}\right) B(n) \] \[ C(n+1) = \frac{1}{n+1}B(n) + \left(1-\frac{1}{n+1}\right) C(n) \]

Here, there are a plethora of algebraic manipulations we could make, limits we could construct, vector spaces we could spot, circles we could run around, etc. Instead, let us take a step back and interpret what we see. We see that $A(n+1)$ is a weighted average of $A(n)$ and $C(n)$; $B(n+1)$ is a weighted average of $B(n)$ and $A(n)$; and $C(n+1)$ is a weighted of $C(n)$ and $B(n)$.

In other words, we see that with each additional card added to the deck, $A(n+1)$ gets pulled slightly towards $C(n)$, $B(n+1)$ gets pulled slightly towards $A(n)$, and $C(n+1)$ gets pulled slightly towards $B(n)$.

There’s something rotate-y going on… perhaps something… complex?

Define the sequences of complex numbers $z_A$, $z_B$, $z_C$ by

\[ z_A(1) = \frac{1}{3} + \frac{2}{3} e^{0 \cdot i} \] \[ z_B(1) = \frac{1}{3} + \frac{2}{3} e^{\frac{2\pi i}{3}} \] \[ z_C(1) = \frac{1}{3} + \frac{2}{3} e^{\frac{4\pi i}{3}} \]

and for all natural numbers $n$,

\[ z_A(n+1) = \frac{1}{n+1} z_C(n) + \left(1-\frac{1}{n+1}\right) z_A(n) \] \[ z_B(n+1) = \frac{1}{n+1} z_A(n) + \left(1-\frac{1}{n+1}\right) z_B(n) \] \[ z_C(n+1) = \frac{1}{n+1} z_B(n) + \left(1-\frac{1}{n+1}\right) z_C(n) \]

We note that

\[ Re(z_A(1)) = 1 = A(1) \] \[ Re(z_B(1)) = 0 = B(1) \] \[ Re(z_C(1)) = 0 = C(1) \]

and thus by induction and the fact that taking averages of complex numbers simply averages the numbers’ corresponding real and imaginary components, we have that for all $n$

\[ Re(z_A(n)) = A(n) \] \[ Re(z_B(n)) = B(n) \] \[ Re(z_C(n)) = C(n) \]

Thus we have translated a rotate-y problem into an actual rotating problem. We note that $z_A(1), z_B(1), z_C(1)$ are equally spaced $120^{\circ}$ on a circle of radius $2/3$ centered at the point $1/3$.

We can prove, in fact, that for all $n$, the complex numbers $z_A(n), z_B(n), z_C(n)$ are equally spaced $120^{\circ}$ apart on a circle centered at $1/3$.

This can be seen geometrically, since if $z_A(n), z_B(n), z_C(n)$ are equally spaced around a circle centered at $1/3$, they form an equilateral triangle. By our recurrences relations, $z_A(n+1)$ lies on the line connecting $z_A(n)$ and $z_C(n)$, $\frac{1}{n+1}$ of the way from $z_A(n)$.

$z_B(n+1)$ and $z_C(n+1)$ lie in similar fashion on the line segments $z_B(n)$ to $z_C(n)$ and $z_C(n)$ to $z_B(n)$, respectively. Thus the points $z_A(n+1)$, $z_B(n+1)$, $z_C(n+1)$ also form an equilateral triangle centered at $1/3$.

Algebraically, $z_A(n), z_B(n), z_C(n)$ being equally spaced on a circle centered at $1/3$ implies that there exists a radius $r$ and angle $\theta$ such that we can write

\[ z_A(n) = \frac{1}{3} + r e^{\theta i} \] \[ z_B(n) = \frac{1}{3} + r e^{(\theta + \frac{2\pi}{3}) i} \] \[ z_C(n) = \frac{1}{3} + r e^{(\theta + \frac{4\pi}{3}) i} \]

Then we have

\[ z_A(n+1) = \frac{1}{n+1}z_C(n) + \left (1-\frac{1}{n+1} \right)z_A(n) \] \[ = \frac{1}{n+1}\left (\frac{1}{3} + r e^{(\theta + \frac{4\pi}{3}) i} \right) + \left (1-\frac{1}{n+1}\right )\left (\frac{1}{3} + r e^{\theta i} \right ) \] \[ = \frac{1}{3} + \frac{1}{n+1} r e^{(\theta + \frac{4\pi}{3}) i} + \left (1-\frac{1}{n+1} \right ) r e^{\theta i} \] \[ = \frac{1}{3} + r e^{\theta i} \left (1 - \frac{1}{n+1} + \frac{1}{n+1} e^{\frac{4\pi i}{3}}\right ) \] \[ = \frac{1}{3} + r e^{\theta i} \left (1 - \frac{1}{n+1} + \frac{1}{n+1} (-\frac{1}{2} - \frac{\sqrt{3}}{2}i) \right ) \] \[ = \frac{1}{3} + r e^{\theta i} \left ( 1 - \frac{3}{2(n+1)} + \frac{\sqrt{3}}{2(n+1)}i \right ) \]

and similarly, by rotational symmetry,

\[ z_B(n+1) = \frac{1}{3} + r e^{(\theta + \frac{2\pi}{3} i )} \left ( 1 - \frac{3}{2(n+1)} + \frac{\sqrt{3}}{2(n+1)}i \right ) \] \[ z_C(n+1) = \frac{1}{3} + r e^{(\theta + \frac{4\pi}{3} i )} \left ( 1 - \frac{3}{2(n+1)} + \frac{\sqrt{3}}{2(n+1)}i \right ) \]

Define

\[ \phi(n) = \left( 1 - \frac{3}{2(n+1)} + \frac{\sqrt{3}}{2(n+1)}i \right) \]

We can rewrite the above result:

\[ z_A(n+1) = \frac{1}{3} + r e^{\theta i} \cdot \phi(n) \] \[ z_B(n+1) = \frac{1}{3} + r e^{(\theta + \frac{2\pi}{3} i )} \cdot \phi(n) \] \[ z_C(n+1) = \frac{1}{3} + r e^{(\theta + \frac{4\pi}{3} i )} \cdot \phi(n) \]

Multiplying by a complex number simply multiplies the magnitudes and adds the angles, so we see that $z_A(n+1), z_B(n+1), z_C(n+1)$ are still centered about $1/3$; their distances relative to $1/3$ have been scaled down by $\left\lVert \phi(n) \right\lVert$, and they have been rotated about $1/3$ by an angle of

\[ \arg(\phi(n)) = \arctan \left ( \frac{\frac{\sqrt{3}}{2(n+1)}}{1 - \frac{3}{2(n+1)}}\right ) = \arctan \left ( \frac{\sqrt{3}}{2(n+1) - 3} \right ) = \arctan \left ( \frac{\sqrt{3}}{2n - 1} \right ) \]

Thus $z_A(n+1), z_B(n+1), z_C(n+1)$ remain evenly spaced on a circle centered at $1/3$, which completes the induction.

To complete the solution to the problem, we note that the Taylor Series of $\arctan$ is

\[ x - \frac{x^3}{3} + \frac{x^5}{5} - \cdots = x + o(x^3) \]

which implies that for $n$ very large,

\[ \arctan \left ( \frac{\sqrt{3}}{2n-1} \right ) \approx \frac{\sqrt{3}}{2n-1} \]

which means that as we increase $n$, the angle increases proportionally to the harmonic series.

Since the harmonic series diverges, we conclude that $z_A, z_B, z_C$ will rotate infinitely many times around $1/3$. Since this series is decreasing and infinitesimal, there will be infinitely many instances where each of $z_A, z_B, z_C$ is rotated to be the rightmost point (i.e. having greatest real part), i.e. each of $A, B, C$ will have highest probability of winning for infinitely many values of $n$. $\square$