Probability Bertsekas Question

Question

Question:

We have two jars each containing an equal number of balls. We perform four successive ball exchanges. In each exchange, we pick simultaneously and at random a ball from each jar and move it to the other jar. What is the probability that at the end of the four exchanges all the balls will be in the jar where they started?

Resource (Bertsekas)

Correct Answer: $$ \frac{1}{n^2}\left( \frac{1}{n^2} + \frac{8(n-1)^2}{n^4} \right) $$

My Approach:

• There are $4$ exchanges in total
• $1^{st}$ swap definitely results in disturbing configuration
• $2^{nd}$ swap can disturb configuration or can set things right
• $3^{rd}$ swap can set things right or can disturb configuration based on $2^{nd}$ swap

• $4^{th}$ swap has to set things right

• Ground rule is one can set things right only if there is a disturbance created before

• $1$ swap you do to create disturbance, $1$ swap you need to do revert that
  disturbance. Hence maximum $2$ swaps causing a disturbance allowed. But just making $1$ swap which causes a disturbance cannot just happen by ground rule

I will represent swap causing disturbance by $1$ and swap reverting back balls by $-1$

\begin{align} P(\text{same configuration after $4$ exchanges}) &= P(1, -1, 1, -1) + P(1, 1, -1, -1) \\ &= 1 \cdot \frac{1}{n^2} \cdot 1 \cdot \frac{1}{n^2} + 1 \cdot \frac{(n-1)^2}{n^2} \cdot \frac{4}{n^2} \cdot \frac{1}{n^2} \\ &= {\bf \frac{1}{n^2}\left(\frac{1}{n^2} + \frac{4(n-1)^2}{n^4} \right) } \end{align}

Why I am getting the wrong answer?

Answer 1

Answer:

$A_i$ is the number of balls in Jar A and belonged to Jar A and $B_i$ is the number of balls in Jar B and belonged to Jar B. Given this notation, I have solved with raw reasoning. Could be helpful in your answer.

Answer 2

I can tell you that probability, $\frac{1 + 8(n-1)^2}{n^4}$, is wrong for sure as I wrote a quick simulation to check it and it does not agree (by orders of magnitude). Are you sure you copied it down correctly?

There are essentially two ways in which the jars can have the same configuration after $4$ steps:

1. The exchange of step $1$ is reversed on step $2$ (e.g. $3 \leftrightarrow 8$ is followed by $8 \leftrightarrow 3$) with the same thing happening on steps $3$ and $4$, with possibly different balls;
2. The exchanges of step $1$ and $2$ are not inverses, say $n_1 \leftrightarrow m_1$ followed by $n_2 \leftrightarrow m_2$ with either $n_2 \neq m_1$ or $m_2 \neq n_1$. The sub-possibilities here are
   • a): $n_2 \neq m_1$, $m_2 \neq n_1$
   • b): $n_2 = m_1$, $m_2 \neq n_1$
   • c): $n_2 \neq m_1$, $m_2 = n_1$

Now, there are $n^2$ possible exchanges on any step, all equally likely; let $\cal{P}_i$ be the set of all possible exchanges on step $i$. Thus possibility $1$ has probability $$ \sum_{p_1 \in \cal{P}_1}\left(\frac{1}{n^2}\cdot \frac{1}{n^2}\right) \sum_{p_3 \in \cal{P}_3}\left(\frac{1}{n^2}\cdot \frac{1}{n^2}\right) = \frac{1}{n^4}. $$ For case $2$ a), the possible (ordered) exchanges on steps $3$ and $4$ are $$ \begin{array}{cc} (m_1 \leftrightarrow n_1, m_2 \leftrightarrow n_2), & (m_1 \leftrightarrow n_2, m_2 \leftrightarrow n_1) \\ (m_2 \leftrightarrow n_2, m_1 \leftrightarrow n_1), & (m_2 \leftrightarrow n_1, m_1 \leftrightarrow n_2) \\ \end{array}; $$ i.e. there are only $4$ exchanges out of a possible $n^4$, thus possibility $2$ a) has probability $$ \sum_{p_1 \in \cal{P}_1}\left(\frac{1}{n^2}\cdot\left(1- \frac{1}{n}\right)^2\right) \frac{4}{n^4} = \frac{4(n-1)^2}{n^6}. $$ For case $2$ b), the configuration after step $2$ is as follows (ellipses denote unexchanged balls): $$ \begin{array}{ccc} m_2, \ldots & \left.\frac{}{}\right| & m_1, n_1 \ldots \\ \end{array} $$ note that $m_2 \leftrightarrow n_1$ is not a valid exchange since on step $3$ it would restore the original configuration (leaving a perturbed configuration for step $4$), and by symmetry it cannot work on step $4$. The possible (ordered) exchanges on steps $3$ and $4$ are therefore $$ \begin{array}{cc} (m_2 \leftrightarrow m_3, m_3 \leftrightarrow n_1), & (n_3 \leftrightarrow n_1, m_2 \leftrightarrow n_3) \\ \end{array} $$ for some $m_3 \neq n_1$ and some $n_3 \neq m_2$; so there are $2(n-1)$ possible exchanges. Since the probability of exchange $2$ not being the inverse of exchange $1$ because $n_2=m_1,m_2\neq n_1$ is $\frac{n-1}{n^2}$ (there are $n-1$ choices for $m_2$ and $1$ for $n_2$) the probability of possibility $2$ b) is $$ \sum_{p_1 \in \cal{P}_1} \frac{1}{n^2} \frac{n-1}{n^2} \frac{2(n-1)}{n^4} = \frac{2(n-1)^2}{n^6} $$ and by symmetry this is also the probability of possibility $2$ c). Therefore, the total probability is (since these possibilities form a partition of the desired event) \begin{align} \frac{1}{n^4} + \frac{4(n-1)^2}{n^6} + \frac{4(n-1)^2}{n^6} &= \frac{1}{n^2}\left(\frac{1}{n^2} + \frac{8(n-1)^2}{n^4}\right), \end{align} and this agrees with simulation.

Answer 3

There are two answers that derive the result, but as far as I can tell they don't answer your question why you're getting the wrong answer. The reason is that you disregarded the possibility that the second swap hits one of the previously swapped balls but not the other, leaving one pair of balls swapped. Then the third swap must do the same, and the fourth swap must hit the pair of swapped balls. The probability for this is

$$ \frac{2\cdot1\cdot(n-1)}{n^2}\cdot\frac{2\cdot1\cdot(n-1)}{n^2}\cdot\frac1{n^2}=\frac{4(n-1)^2}{n^6}\;, $$

which is exactly the term that you were missing.