A stopping time problem for a random walk with transition probabilities dependent on states

Question

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

Answer 1

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.