A stopping time problem for a random walk with transition probabilities dependent on states The Problem: In a one-dimensional random walk, at position $n > 0$, the probability of moving to $(n-1)$ is $\frac{n+2}{2n+2}$, and the probability of moving to $(n+1)$ is $\frac{n}{2n+2}$. Starting at position $n$, what is the average time to reach position $0$?
Question 1:
Let $v(n)$ be the expected time of moving from $n$ to $0$. Then we have the following recursive equation:
$$v(n) = 1 + \frac{n+2}{2n+2} v(n-1) + \frac{n}{2n+2} v(n+1)$$
And obviously $v(0) = 0$, but to solve the equation we also need to know $v(1)$, which I cannot compute.
So my first question is: How to compute $v(1)$?
p.s. Using random simulation on a computer, I have estimated that $v(1) = 3$. Then the recursive equation can be solved to obtain $v(n) = n(n+2)$. But I do not know how to compute $v(1)$ theoretically.
Question 2:
Another way to solve this problem is to use martingale.
Let $X_t$ be the random position at time $t$, and $X_0 = n$.
Let
$$Y_t = (X_t+1)^2 + t$$
then $\{Y_t, t \ge 0\}$ is a martingale with respect to $\{X_t, t \ge 0\}$.
Let $T$ be the first visit time from $n$ to $0$ (stopping time).
If the optional stopping theorem is applicable, then
$$E(Y_T)= (0+1)^2+E(T) = E(Y_0) = (n+1)^2 + 0$$
So we have
$$E(T) = n(n+2)$$
However, for the optional stopping theorem to be applicable, I have to firstly prove $E(T) < \infty$.
So my second question is: How to prove the expected stopping time $E(T) < \infty$?
Thanks

You can introduce stopping times $T_N=\inf \{ t : X_t \in \{ 0,N \} \}$. Then using optional stopping you have $(n+1)^2=P(X_{T_N}=0)+(N+1)^2 P(X_{T_N}=N) + E[T_N]$. Now you can proceed in one of two ways:

*

*Calculate $L:=\lim_{N \to \infty} (N+1)^2 P(X_{T_N}=N)$, in which case you get $E[T]=(n+1)^2-P(X_T=0)-L=n(n+2)-L$. It turns out that this $L$ is actually zero, but the fact that $P(X_{T_N}=N)=o(N^{-2})$, which is required to prove this, is not immediately obvious.

*Note that by taking $N \to \infty$, the above equation implies $E[T]<\infty$, because the LHS is finite and the RHS consists only of nonnegative terms. Therefore you can use the optional stopping argument that you set up.

