A Markov Chain - Let X ~ the heads of M coins

Question

A Markov chain is defined as follows. There are $M$ coins $(M ∈ \mathbb N)$, each showing Heads or Tails. At each step, a coin is selected uniformly at random and flipped. The state of the system is the number of Heads.

(a) Determine the transition matrix of the Markov chain.

(b) Using any method, determine the stationary distribution (your solution should prove that the distribution you find is in fact the stationary distribution).

(c) Suppose $M = 20$ and the initial state is $X_0 = 10$. How long, on average, will it take until the next time the state is $10$?

My question

I am not sure for (b), how to prove its time reversibility.

---

My attempt so far

(a) $P_{i,i+1} = \frac{M-i}{2M}$, $P_{i,i-1} = \frac{i}{2M}$, $P_{i,i} = \frac{1}{2}$

(b) Using the property of time reversible Markov chain (without proving), I could get $\pi_0 = 2^{-M}, \pi_i = {M \choose i}2^{-M}$.

(c) I'm guessing that the average time to return to state $10$ is $\frac{1}{\pi_{10}}$. Still, I need to prove the time reversibility to be able to use it.

Answer 1

To prove (b) is correct you want to show that the probbabilities remain the same after one step, so here that $\forall i$ $$P_{i-1,i}\pi_{i-1}+P_{i,i}\pi_{i}+P_{i+1,i}\pi_{i+1} =\pi_{i}$$ i.e. $$\frac{M-(i-1)}{2M}{M \choose i-1}2^{-M} + \frac12 {M \choose i}2^{-M} +\frac{i+1}{2M}{M \choose i+1}2^{-M} = {M \choose i}2^{-M}$$ remembering that ${M \choose -1}= {M \choose M+1}=0$

Answer 2

• We can represent this situation as a Markov chain with $M+1$ states, corresponding to the possible number $k\in \{0,\ldots,M\}$ of heads-up coins.

• Given the state with $k$ heads-up coins, a transition occurs by choosing one of the coins and flipping it. We can consider two cases: half the time, the coin we pick lands same-side-up; hence we transition into the same state again. The other half of the time, the coin lands opposite-side-up, and we either gain or lose a head.

  Hence the transition probability is a $\frac{1}{2}$ chance of transitioning to the same state again, a $\frac{k}{2M}$ chance of picking (and toggling) a heads-up coin $k\mapsto (k-1)$, and a $\frac{M-k}{2M}$ chance of picking (and toggling) a tails-up coin $k\mapsto (k+1)$. Note that the probabilities sum to 1, and that these formulas work even for the extreme cases of $k=0$ or $k=M$.

• A steady-state probability distribution is a distribution over all states $k\in\{0,\ldots,M\}$ which remains the same after a single transition step is applied.

  Denoting the probability of each state by $p_0 \ldots p_M$, the transition probabilities give us certain equations that must hold. For example, if the probability on state $0$ is the same before and after transitioning, then $$p_0 = \frac{1}{2} p_0 + \frac{1}{2M}p_1$$

  And similarly for the other states. We also have the law of total probability $\sum_i p_i = 1$. These constraints are enough to uniquely determine the stationary distribution for this ergodic system; you can use a matrix representation to make the calculation smoother.

• There is a theorem which states that if a finite Markov chain has a stationary distribution, then the expected time of return to state $x$ is, as you say, $1/p_x$.