First let us get clear about the process that we are aiming to build a probabilistic model for, leaning a little on what we bring from programming, especially how we took computation to be a succession of states.

To help with mental consolidation of the process, think of two jars \(W\) and \(B\), each containing initially \(n\) white and black balls, respectively. In the swap game, our states can be represented as tuples \((i,d)\), where \(i\) is the number of exchanges that have been performed (or turns in the game), and \(d\) is the number of black balls in \(W\) or white balls in \(B\), which will always be equal.

Second, let’s agree on some terminology to make our discussion easier. Let’s distinguish draws as self and other, where the former designates drawing a \(c\) color ball from a \(c\) color jar, and the latter designates drawing a \(c\) color ball from an opposite color jar. We have a representation for the states and a representation for the moves. Here is a characterization of how state transitions proceed:

  1. Given a state \((i,0)\), the next state is always \((i+1,1)\), reached by a necessarily self-self move.
  2. Therefore, all games start as \((1,1)\).
  3. Given a state \((i,d)\), with \(d>0\), the three possible next states are:
    • \((i+1,d+1)\): reached by a self-self move.
    • \((i+1,d-1)\): reached by an other-other move.
    • \((i+1,d)\): reached by either a self-other or an other-self move.

With this representation, the probability of transiting from \(s_i\) to \(s_{i+1}\) will be the sum of the probabilities of the moves that take us from \(s_i\) to \(s_{i+1}\). We will use the following denotational conventions. Given a state \((i,d)\) and \(r,s\in \lbrace\text{self},\text{other}\rbrace\),

  1. \(p_i(r\text{-}s)\) is the probability of making an \(r\text{-}s\) move from the base state \((i,d)\).
  2. \(p_i(d)\) is the probability of ending up at the state \((i,d)\) after \((i-1)\) successive moves from the initial state \((1,1)\).

When in a state \((i,d_i)\) the probabilities of the moves afforded by that state are:

\[\begin{align*} p_i(\text{self-self}) & = \frac{(n-d_i)^2}{n^2}\\ p_i(\text{other-other}) & = \frac{d_i^2}{n^2}\\ p_i(\text{self-other}) & = p_i(\text{other-self}) = \frac{d_i(n-d_i)}{n^2} \end{align*}\]

Workbench set, knives sharpened, let’s get to work.

The question asks the probability of reaching the state \((4,0)\), namely \(p_4(0)\). Given the nature of our system, this state can only be reached from \((3,1)\). Therefore,

\[p_4(0) = p_3(1) \cdot p_3(\text{other-other}) = p_3(1)\cdot\frac{1}{n^2}\]

Now, what is \(p_3(1)\)? The states that have any chance to be preceding \((3,1)\) are \((2,0)\), \((2,2)\), and \((2,1)\).

Therefore,

\[\begin{align} p_3(1) & = p_2(0) \cdot p_2(\text{self-self}) & \\ \nonumber & + p_2(1) \cdot (p_2(\text{self-other}) + p_2(\text{other-self})) & \\ \nonumber & + p_2(2)\cdot p_2(\text{other-other}) & \\ \nonumber & = p_2(0) \cdot 1 + p_2(1) \cdot \frac{2\cdot(n-1)}{n^2} + p_2(2)\cdot \frac{4}{n^2} & \end{align}\]

As the game starts at \((1,1)\),

\[p_2(0) = p_1(\text{other-other}) = \frac{1}{n^2}\]

and

\[p_2(1) = p_1(\text{other-self}) + p_1(\text{self-other})= \frac{2\cdot(n -1)}{n^2}\]

and

\[p_2(2) = p_1(\text{self-self}) = \frac{(n-1)^2}{n^2}\]

Putting everything together,

\[\begin{align} p_4(0) &= \big(\frac{1}{n^2} + \frac{8\cdot (n-1)^2}{n^4}\big) \cdot \frac{1}{n^2}\\ \nonumber &= \frac{1}{n^4} + \frac{8\cdot (n-1)^2}{n^6}\\ \nonumber &= \frac{n^2 + 8\cdot (n-1)^2}{n^6}\\ \nonumber &= \frac{9n^2 - 16n + 8}{n^6} \end{align}\]