The conditional expectation in Gambler’s ruin

Question

Consider the random walk $X_0, X_1, X_2, \ldots$ on state space $S=\{0,1,\ldots,N\}$ with absorbing states $A=\{0,N\}$, and with $P(i,i+1)=p$ and $P(i,i-1)=q$ for all $i \in S \setminus A$, where $p+q=1$ and $p,q>0$.

Let $T:=\inf \left\{n\in\mathbb{N}:X_{n}\in \left\{0,N \right\}\right\}$ denote the number of steps until the walk is absorbed in either $0$ or $N$.

I don't know why $\mathbb{E}\left\{T\mid X_{1}=k+1\right\}=\mathbb{E} \mathbb\{T | X_0 = k+1\}+1$ for any $k \in S \setminus A$.

---

I can only provide a strict proof that $$\begin{align} \mathbb{E}\left\{T\mid X_{1}=k\right\}=\mathbb{E} \mathbb\{T | X_0 = k\}+1,\forall k\in \left\{1,\cdots,N-1 \right\} \tag{1} \end{align} $$

But I feel the following equation $(2)$ is not true:

$$\begin{align} &\mathbb{E}\left\{T\mid X_{1}=N\right\}=\mathbb{E} \mathbb\{T | X_0 = N\}+1\tag{2} \\\text{since} \quad &\mathbb{E}\left\{T\mid X_{1}=N\right\}=\frac{p\cdot\mathbf{P}(X_0=N-1)}{p\cdot\mathbf{P}(X_0=N-1)+1\cdot\mathbf{P}(X_0=N)}\tag{3}\\\text{and}\quad &\mathbb{E} \mathbb\{T | X_0 = N\}=0\tag{4} \end{align} $$

Answer 1

I think the equality in $(2)$ does not hold. The expectation on the left has to be $1$, because $\{X_1 = N\} \subset\{T = 1\}$, thus $$\mathbb{E}[T|X_1 = N] = \sum_{k=1}^\infty k \mathbb{P}(T=k|X_1 = N) = \mathbb{P}(T=1|X_1 = N) = 1.$$ The sum on the right is at least $2$ (it actually is $2$), since $T\geq 1$.

Edit: Even if $T$ takes values in $\mathbb{Z}_{\geq 0}$, I still do not see why $$\mathbb{E}[T|X_1 = N] = \mathbb{E}[T|X_0 = N]+1.$$ The right side is now $1$ by definition. Then the left side is $$\mathbb{E}[T|X_1 = N] = \mathbb{P}(T=1|X_1 = N)$$ which is strictly less than one, because $T$ is not Markov, and on the event $\{X_0 = N\}$, $T = 0$.

Answer 2

To make sense of any of this you have to spell out whether $X_0 \in A$ means $T=0$ or not. Based on your very last line, it sounds like you mean to have $T=0$ in this case, but unfortunately the symbol $\mathbb{N}$ is sometimes used for $\{ 1,2,\dots \}$ and other times for $\{ 0,1,\dots \}$. So from your initial writeup alone, I cannot tell which is intended.

The nice thing is that you can handle one in terms of the other. Specifically, everything is simpler if you are looking at the case where $X_0 \in A$ means $T=0$. In this setting, you can write

$$E[T \mid X_0=i]=\sum_j p_{ij} E[T \mid X_0=i,X_1=j]$$

regardless of what $i$ is. But you can only simplify further to get

$$E[T \mid X_0=i,X_1=j]=1+\sum_k p_{jk} E[T \mid X_0=j]$$

when $i \not \in A$. Intuitively that is because you can't just "forget" that you hit $A$ earlier on. Again it doesn't matter whether $j \in A$ in this setting; if $i \not \in A$ and $j \in A$ then this last equation reads $1=1$.

To make the conversion to the other case, you do the first step "by hand" and then work with the case we discussed above. That is, you define $T=\inf \{ n \geq 1 : X_n \in A \}$ and $S=\inf \{ n \geq 0 : X_n \in A \}$ and then

$$E[T \mid X_0=i]=1+\sum_j p_{ij} E[S \mid X_0=j].$$