The Mean First Passage Time of a Markov Chain with Infinite Number of States

All of the following arguments are based around the recursive formula that comes from conditioning on the first step:

---

Suppose i>j$i>j$:

Let's simplify notation by recognizing that shifting i$i$ and j$j$ equally has no effect:

If p≥.5$p\ge .5$, then the expectation is infinite. (This will follow from our solution to the p<.5$p<.5$ case.)

If p<.5$p<.5$, then:

⇒m^(k)−m^(k−1)=1+p⋅(m^(k+1)−m^(k−1))$$\Rightarrow \hat{m}(k)-\hat{m}(k-1)=1+p\cdot (\hat{m}(k+1)-\hat{m}(k-1))$$

We can guess and verify that m^(k)=βk$\hat{m}(k)=\beta k$ is linear.

⇒βk−β(k−1)=1+p(β(k+1)−β(k−1))$$\Rightarrow \beta k-\beta (k-1)=1+p(\beta (k+1)-\beta (k-1))$$

⇒β=1+2pβ$$\Rightarrow \beta =1+2p\beta$$

⇒β=11−2p$$\Rightarrow \beta =\frac{1}{1-2p}$$

Note that β$\beta$ does not depend on k$k$, so we guessed correctly. Our equation is satisfied for any k$k$ by:

⇒m^(k)=k1−2p$$\Rightarrow \hat{m}(k)=\frac{k}{1-2p}$$

In particular, we can see for k=1$k=1$:

Note that our expression for m^(k)$\hat{m}(k)$ has the correct boundary values: when p=0$p=0$ it deterministically takes k$k$ steps, and the expression gets arbitrarily large as p$p$ goes to .5$.5$ from the left. In fact, this proves the expectation is infinite for the p≥.5$p\ge .5$ case since m^$\hat{m}$ is monotonically increasing in p$p$.

---

Suppose i<j$i<j$:

For any fixed j$j$, there are finitely many states to consider and an equal number of equations.

⇒p⋅m(0,j)=1+p⋅m(1,j)$$\Rightarrow p\cdot m(0,j)=1+p\cdot m(1,j)$$

⇒m(0,j)=1/p+m(1,j)$$\Rightarrow m(0,j)=1/p+m(1,j)$$

Now let's compute the next one:

⇒p⋅m(1,j)=1+(1−p)/p+p⋅m(2,j)$$\Rightarrow p\cdot m(1,j)=1+(1-p)/p+p\cdot m(2,j)$$

⇒m(1,j)=(1+(1−p)/p)/p+m(2,j)$$\Rightarrow m(1,j)=(1+(1-p)/p)/p+m(2,j)$$

There is a pattern:

Where:

Ai=(1+(1−p)Ai−1)/p$$A_i=(1+(1-p)A_{i-1})/p$$

A0=1/p$$A_0=1/p$$

Thus:

Ai=∑k=0i(1−p)kpk+1$$A_i=\sum _{k=0}^i\frac{(1-p{)}^k}{p^{k+1}}$$

Recursing forward until j−1$j-1$, we get:

⇒m(j−1,j)=Aj−1$$\Rightarrow m(j-1,j)=A_{j-1}$$

Now, we can recurse backwards:

m(i,j)=∑n=ij−1An$$m(i,j)=\sum _{n=i}^{j-1}{A}_n$$

⇒m(i,j)=∑n=ij−1∑k=0n(1−p)kpk+1$$\Rightarrow m(i,j)=\sum _{n=i}^{j-1}\sum _{k=0}^n\frac{(1-p{)}^k}{p^{k+1}}$$

This can be simplified further by noticing An$A_n$ is the sum of a finite geometric series. There are three cases to consider depending on the value of r=(1−p)/p$r=(1-p)/p$.

---

If (1−p)/p=1$(1-p)/p=1$, then p=.5$p=.5$ and An=2(n+1)$A_n=2(n+1)$, thus:

---

If (1−p)/p<1$(1-p)/p<1$, then p>.5$p>.5$ and An$A_n$ is a finite geometric series with r=(1−p)/p$r=(1-p)/p$, thus:

Their summation is then:

---

If (1−p)/p>1$(1-p)/p>1$, then p<.5$p<.5$ and An$A_n$ is a finite geometric series.

We can do exactly as in the previous case but by reversing the finite geometric series and using r=p/(1−p)$r=p/(1-p)$.

(I'll write this up at some point, but it's not mathematically harder than the previous case, just a bit messier notationally.)