MathCastle
Linear AlgebraSuperchallengeMarkov Chains & Long-Run Behavior

Markov Chains & Long-Run Behavior · Superchallenge problem

The Petersen graph has 1010 vertices: the 22-element subsets of {1,2,3,4,5}\{1, 2, 3, 4, 5\}, with two subsets joined by an edge when they are disjoint. Each vertex has degree 33. A walker moves each step to a uniformly random neighbour. Starting at {1,2}\{1, 2\}, what is the expected number of steps until it first reaches {1,3}\{1, 3\}?