Stochastic Processes – Problem 16: Find the stationary distribution of this Markov chain

Let $\mathcal{M}=\{(a_{1},\ldots,a_{n})\in\{0,1\}^{n}:a_{i}a_{i+1}=0\;\forall\, i=1,\ldots,n-1\}$. Consider the following Markov chain with state space $\mathcal{M}$: at each step, a coordinate $i$ is chosen uniformly at random; if all of its neighbors (if $i=1$ or $i=n$, there is only one neighbor) have value 0, then $a_i$ is updated to 0 with probability $1/2$ and to 1 with probability $1/2$; otherwise the state remains unchanged.

(a) Find the stationary distribution of this Markov chain.

(b) As $t\to\infty$, given that the state contains exactly $\ell$ ones (assume $\ell\leq n/3$), find the limiting conditional probability that the state is $a_{2i}=1$ for all $i=1,\ldots,\ell$ (and these are all the positions equal to 1).

(a) Finding the stationary distribution.

We check whether the chain is reversible. For any two states $x, y \in \mathcal{M}$: If $x$ and $y$ differ in more than one coordinate, then $P(x,y) = P(y,x) = 0$, so detailed balance holds trivially.

If $x$ and $y$ differ only in coordinate $i$, say $x$ has $a_i=0$ and $y$ has $a_i=1$, then for both $x,y$ to lie in $\mathcal{M}$, the neighbors of $i$ must all be 0. In state $x$, selecting coordinate $i$ is allowed (neighbors are 0), and the update probability is $1/(2n)$. Similarly, in state $y$, selecting coordinate $i$ is also allowed (neighbors are still 0), giving $P(y,x) = 1/(2n)$.

Since $P(x,y) = P(y,x)$ for all $x,y$, the transition matrix is symmetric. By detailed balance with a uniform candidate $\pi(a) = 1/|\mathcal{M}|$, we verify $\pi(x)P(x,y) = \pi(y)P(y,x)$.

The chain is irreducible (any state can reach any other by flipping coordinates one at a time through the all-zeros state). Since the state space is finite and the chain is irreducible, the stationary distribution is unique: $\pi(a) = \frac{1}{|\mathcal{M}|}$ for all $a \in \mathcal{M}$.

(b) Finding the limiting conditional probability.

The chain is irreducible and aperiodic (since $P(a,a)>0$), so as $t\to\infty$ the distribution converges to $\pi$.

Let $A$ be the specific state with $a_{2i}=1$ for $i=1,\ldots,\ell$ and all other entries 0, and let $C_\ell$ be the set of all states in $\mathcal{M}$ with exactly $\ell$ ones. Since $\pi$ is uniform: $P(A | C_\ell) = \frac{1}{|C_\ell|}$.

To count $|C_\ell|$: we need to place $\ell$ ones among $n$ positions with no two adjacent. Using the stars-and-bars method (placing $n-2\ell+1$ remaining zeros into $\ell+1$ gaps), we get: $|C_\ell| = \binom{n-\ell+1}{\ell}$.

Therefore the limiting conditional probability is $\frac{1}{\binom{n-\ell+1}{\ell}}$.

(a) $\frac{1}{|\mathcal{M}|}$ (b) $\frac{1}{\binom{n-\ell+1}{\ell}}$