Introduction to Probability · Problem 11.2.10
Markov Chains — Grinstead & Snell
Mathematics — Probability · absorbing-markov-chains
Problem
Using the result of Exercise 9, make a conjecture for the form of the fundamental matrix if the process moves as in that exercise, except that it now moves on the integers from 1 to . Test your conjecture for several different values of . Can you conjecture an estimate for the expected number of steps to reach state , for large ? (See Exercise 11 for a method of determining this expected number of steps.)Intuitive explanation
This problem asks you to spot a pattern in the fundamental matrix for a random walk on states to , then use that pattern to estimate how long it takes to reach the absorbing state . The key insight is that the fundamental matrix entries encode "expected visits" to transient states—and for a simple random walk, these visits follow a predictable structure that scales with . By computing the matrix for small values of and comparing their forms, you'll uncover a formula, then sum the relevant entries to estimate total expected time, which typically grows polynomially with .
Intuitive explanation
This problem asks you to spot a pattern in the fundamental matrix for a random walk on states to , then use that pattern to estimate how long it takes to reach the absorbing state . The key insight is that the fundamental matrix entries encode "expected visits" to transient states—and for a simple random walk, these visits follow a predictable structure that scales with . By computing the matrix for small values of and comparing their forms, you'll uncover a formula, then sum the relevant entries to estimate total expected time, which typically grows polynomially with .