Random walk on a square to the opposite corner

Question

Four corners of a square are labeled A, B, C, D in order around the edge, so the neighbors of A are B and D, and C is the corner diagonally opposite A. A token sits at A. Each step it moves to one of the two adjacent corners, each with probability 	frac12. It stops on reaching C. What is the expected number of steps for the token to reach C?

Accepted Answer

Let a be the expected steps from A to reach C, and b the expected steps from B. By the mirror symmetry swapping B and D, corner D has the same value b. From A, both neighbors (B and D) have value b: a = 1 + b. From B, neighbors are C (done, value 0) and A (value a): b = 1 + 	frac12 (0) + 	frac12 a. Substitute a = 1 + b: b = 1 + 	frac12(1 + b) = 	frac32 + 	frac12 b, so 	frac12 b = 	frac32, b = 3, and a = 1 + 3 = 4. Takeaway. Symmetry collapses four unknowns to two, and first-step analysis finishes it: reaching the opposite corner of a square averages 4 steps. (For a cycle of n vertices,…

Random walk on a square to the opposite corner

Your answer

Discussion

Learn the concepts

Related questions