Fall 2011 Homework 11: Question 5
In the Ehrenfest chain, there are two containers with a total of M (distinguishable) particles, and transitions are done by choosing a random particle and moving it from its current container into the other container. Initially (at time n = 0), all of the particles are in the second container. Let $X_{n}$ be the number of particles in the first container at time n (so $X_{0}$ = 0 and the transition from $X_{n}$ to $X_{n+1}$ is done as described above). This is a Markov chain with state space {0, 1,..., M}.
(a) Why is $q_{ii}^{(n)}$ (i.e., the probability of being in state i after n steps, starting from state i) always 0 if n is odd?
(b) Show that $(s_{0},s_{1},. . .,s_{M})$ with $s_{i}=\binom{M}{i}(\frac{1}{2})^{M}$ is the stationary distribution. Why does this, which is a Binomial distribution, seem reasonable intuitively? Hint: First show that $s_{i}q_{ij}=s_{j}q_{ji}$.
Solution: (a) Note that the parity of Xn (whether it is even or odd) changes after each step of the chain. So after an odd number of steps, the parity is different from the initial parity. (b) The Binomial distribution makes sense here since after running the Markov chain for a long time, each particle is about equally likely to be in either container, approximately independently. To show that the stationary distribution is Binomial(M, 1/2), we will check the reversibility condition. We see that s is stationary.
"Mathematics is the logic of certainty, but statistics is the logic of uncertainty."