Solution
= Solution
For each fixed output state $y$, the right-shift part has exactly two predecessors, each contributing $1/3$, and the left-shift part also has exactly two predecessors, each contributing $1/6$. Thus every column sum is
$$
2\left(\frac13\right)+2\left(\frac16\right)=1.
$$
The transition matrix is doubly stochastic, so the uniform law
$$
\pi(y)=2^{-n}
$$
is invariant.