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

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.

• The infamous Ehrenfest Urn, only the name is missing Jul 17, 2019 at 8:18
• As soon as you get a solution for $\pi_i P_{i,i+1}=\pi_{i+1} P_{i+1,i}$, you KNOW $P$ is reversible with respect to $\pi$ (a definition !) and you get for free that $\pi$ a stationary measure for $P$ (a one line general fact : $\sum_i \pi_i P(i,j) = \sum_i \pi_j P(j,i)=\pi_j$). So that (b) is not an issue. Also, the result you mention in (c) does not require reversibility, only irreducibility (again this is plain in your case). Jul 17, 2019 at 9:50
• So for (c), is the answer $(\frac{20!}{10!10!}2^{-20})^{-1}$? Jul 18, 2019 at 1:10
• Is it true that for all irreducible Markov chains are time reversible? Jul 18, 2019 at 1:26
• It is not true. Jul 18, 2019 at 7:16

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$$

• What is the related formula or theorem related to $\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}$? I could prove it by hand but it took me nasty and long calculation to do it. Is there any easier way to prove that than expanding everything? Jul 19, 2019 at 16:53
• @soobster The left hand side is $\frac12 2^{-M}\left( {M-1 \choose i-1} + {M \choose i} + {M-1 \choose i}\right)$ and, since ${M-1 \choose i-1} + {M-1 \choose i}={M \choose i}$ (think Pascal's triangle), this is equal to $2^{-M} {M \choose i}$ i.e. the right hand side Jul 21, 2019 at 17:11
• 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$$.

• Wouldn't $p_0$ be $\frac{1}{2} p_0 + \frac{1}{2M}p_1$ instead? Jul 18, 2019 at 1:14
• Thanks, good catch. Jul 18, 2019 at 2:17