Computing the expected number of steps of a random walk

Question

I have a Markov chain with probability $p_{ij}$ to transition from state $i$ to state $j\, (p_{01} = 1)$. How can I calculate the expected number of steps it takes to go from one state to another?

Answer 1

Let $A$ be a subset of the state space $E$, $\tau(x)=\inf \{ t : X_t \in A \mid X_0=x \}$. Let $t(x)=E[\tau(x)]$. For $x \not \in A$, by conditioning on the first step you get

$$t(x)=\sum_{y \in E} p_{xy} (1+t(y)) = 1+\sum_{y \in E} p_{xy} t(y).$$

For $x \in A$, $t(x)=0$. These equations can be written in matrix form as

$$(Lt)(x) = -1 \quad x \not \in A \\ t(x) = 0 \quad x \in A$$

where $P$ is the transition probability matrix and $L=P-I$ is called the generator matrix. This is a system of $|E|$ linear equations in $|E|$ unknowns, so generically it has a unique solution.