Question

A total of \(m\) white and \(m\) black balls are distributed among two urns, with each urn containing \(m\) balls. At each stage, a ball is randomly selected from each urn and the two selected balls are interchanged. Let \(X_{n}\) denote the number of black balls in urn 1 after the \(n\) th interchange. (a) Give the transition probabilities of the Markov chain \(X_{n}, n \geqslant 0\). (b) Without any computations, what do you think are the limiting probabilities of this chain? (c) Find the limiting probabilities and show that the stationary chain is time reversible.

Short answer

The transition probabilities for the Markov chain \(X_n\) are given by: \(p_{i,j} = \begin{cases} \frac{i}{m} \cdot \frac{m-j}{m}, & j=i-1 \\ \frac{m-i}{m} \cdot \frac{j}{m}, & j=i+1 \\ 0, & \text{otherwise} \end{cases}\) The limiting probabilities of the Markov chain tend to a uniform distribution over all its possible states, with \(\pi_i = \frac{1}{m+1}\), for \(i = 0,1,2,...,m\). The stationary chain is time reversible, as the reversibility condition \(\pi_i p_{ij} = \pi_j p_{ji}\) holds true for every pair of states.

Step-by-step solution

Analyzing the Problem and Variables

We are given a Markov chain \(X_{n}\), where each state of the chain represents the number of black balls in urn 1 after \(n\) interchanges. For each interchange, a ball is selected randomly from each urn and interchanged. Since there are m black balls and m white balls, the number of black balls in urn 1 can take values between 0 and m, inclusive (i.e., 0, 1, 2, ..., m).

Identifying Transition Probabilities

We will now calculate the transition probabilities for the Markov chain \(X_{n}\). Let \(p_{ij}\) denote the probability of transitioning from state \(i\) to state \(j\). 1. If we have \(i\) black balls in urn 1 and \(m-i\) white balls in urn 2, there is a probability of \(\frac{i}{m} \cdot \frac{m-j}{m}\) of choosing a black ball from urn 1 and a white ball from urn 2 (such that \(j=i-1\)) and a probability of \(\frac{m-i}{m} \cdot \frac{j}{m}\) of choosing a white ball from urn 1 and a black ball from urn 2 (such that \(j=i+1\)). Hence, the general transition probabilities are: \(p_{i,j} = \begin{cases} \frac{i}{m} \cdot \frac{m-j}{m}, & j=i-1 \\ \frac{m-i}{m} \cdot \frac{j}{m}, & j=i+1 \\ 0, & \text{otherwise} \end{cases}\)

Limiting Probabilities Prediction

Without any computations, we can predict that the limiting probabilities will tend towards a uniform distribution over all possible states, as interchanging balls many times leads to an equal likelihood of any given arrangement of black and white balls.

Calculating Limiting Probabilities

To calculate the limiting probabilities, we start to calculate the stationary distribution of this Markov chain also known by the stationary distribution vector \(\pi\). The stationary distribution satisfies \(\pi P = \pi\). However, we note that since the total number of balls in each urn remains constant, the system will reach a uniform distribution of balls in the urns as this process continues. Thus, the stationary distribution \(\pi\) will be uniform between each of the reachable states of the urns: \(\pi_i = \frac{1}{m+1}, \quad i = 0,1,2,...,m\)

Verifying Time Reversibility

A stationary Markov chain is time reversible if the following condition is satisfied: \(\pi_i p_{ij} = \pi_j p_{ji}\). As this condition holds true for every pair of states, we can say that the stationary chain is time reversible. Since the stationary distribution is uniform, we can check the reversibility using the given transition probabilities: \(\frac{1}{m+1} \cdot \left(\frac{i}{m} \cdot \frac{m-(i-1)}{m}\right) = \frac{1}{m+1} \cdot \left(\frac{i-1}{m} \cdot \frac{m-i+1}{m}\right)\) As we can see, the reversibility condition holds, proving that the stationary chain is time reversible.