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.


Solution

Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 215 / 4 / a / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-215/4/a/solution