MathCastle
Linear AlgebraSuperchallengeMarkov Chains & Long-Run Behavior

Markov Chains & Long-Run Behavior · Superchallenge problem

A robot does a random walk on a 3×33 \times 3 grid of squares, each step moving to a uniformly chosen square that shares a side with its current square. It starts in a corner square. Let qnq_n be the probability that it is on the centre square after exactly nn steps. What is lim⁡n→∞q2n\displaystyle\lim_{n \to \infty} q_{2n}? Express your answer as a common fraction.