Question

\(M\) balls are initially distributed among \(m\) urns. At each stage one of the balls is selected at random, taken from whichever urn it is in, and then placed, at random, in one of the other \(M-1\) urns. Consider the Markov chain whose state at any time is the vector \(\left(n_{1}, \ldots, n_{m}\right)\) where \(n_{i}\) denotes the number of balls in urn \(i\). Guess at the limiting probabilities for this Markov chain and then verify your guess and show at the same time that the Markov chain is time reversible.

Short answer

The limiting probabilities for the Markov chain with states \((n_1, n_2, \ldots, n_m)\) representing the number of balls in each urn are uniform, with each state having a probability of \(\frac{1}{\binom{M+m-1}{m-1}}\). The Markov chain is also time-reversible, as we have shown that for all states \(i\) and \(j\), \(P_{ij} = P_{ji}\).

Step-by-step solution

Understand the Markov chain and states

The Markov chain consists of states \((n_1, n_2, \ldots, n_m)\), with \(n_i\) representing the number of balls in urn \(i\). The initial state will be given, and then at each stage, one ball is selected randomly, taken from its original urn, and placed randomly in one of the other \(M-1\) urns.

Identifying the Transition Probabilities

Define the transition probability \(P_{ij}\) as the probability of going from state \(i\) to state \(j\). In this case, the transition probabilities are: 1. If a ball is taken from urn \(i\) and placed in urn \(j\), then the transition probability is given by \(\frac{n_i}{M} \cdot \frac{1}{M-1}\) (probability of selecting a ball from urn \(i\) times the probability of placing the ball in urn \(j\)). 2. If there is no change in the state, the transition probability is given by \(1-\sum_{i\neq j} P_{ij}\).

Guessing the Limiting Probabilities

Let's assume the limiting probability for state \((n_1, n_2, \ldots, n_m)\) is given by \(\pi\left(n_1, n_2, \ldots, n_m\right)\). We can guess that the limiting probabilities are uniform (equal) because each urn has equal chances of gaining and losing balls in the long run. Therefore, each state has a limiting probability of \(\frac{1}{\binom{M+m-1}{m-1}}\).

Show Time Reversibility

A Markov chain is time-reversible if \(\pi_i P_{ij} = \pi_j P_{ji}\) for all states \(i\) and \(j\). If the limiting probabilities are uniform, then \(\pi_i = \pi_j = \frac{1}{\binom{M+m-1}{m-1}}\), and hence, this condition simplifies to: \[P_{ij} = P_{ji}\] Using the transition probabilities we identified earlier in Step 2: \[\frac{n_i}{M} \cdot \frac{1}{M-1} = \frac{n_j}{M} \cdot \frac{1}{M-1}\] Since the denominator is equal on both sides, we can rearrange for \(n_i\) and \(n_j\): \[n_i = n_j\] The time reversibility condition holds for all states \(i\) and \(j\), which confirms that the Markov chain is time-reversible.

Conclusion

The limiting probabilities for the given Markov chain are uniform, with each state having a probability of \(\frac{1}{\binom{M+m-1}{m-1}}\). Additionally, the Markov chain is time-reversible, as we have shown that the time reversibility condition holds for all states.