Assume that we have a random walk on the integers $\{0, \ldots, n\}$ where 0 is absorbing and $n$ is reflecting and that we start at state $n$. I want to find the expected number of visits to each state given that we start in state $n$.
The number of visits $N_i$ to each state $i$ is geometric with parameter $\gamma_i$, where $\gamma_i$ is the probability of never returning.
I have computed the first few probabilities by hand:
The first two are obvious
$$
\begin{aligned}
N_1 &\sim \operatorname{Geom}(1/2)\\
N_2 &\sim \operatorname{Geom}(1/4)
\end{aligned}$$
For the other cases:
$$
\gamma_3 = \frac{1}{2} \sum_{i = 0}^\infty \left(\frac{1}{4}\right)^i = \frac{1}{6}
$$
$$
\gamma_4 = \frac{1}{2^4} \sum_{i = 0}^\infty 2^i \left(\frac{1}{4}\right)^i = \frac{1}{8}
$$
where the $2^i$ comes from the number of ways that we can loop (either going to 3 or to 1).
So
$$
\begin{aligned}
N_3 &\sim \operatorname{Geom}(1/6)\\
N_4 &\sim \operatorname{Geom}(1/8)
\end{aligned}
$$
In general, I solved it numerically using the canonical form $I + R + R^2 + \cdots = (I – R)^{-1}$ where
$$
(I – R) = \begin{bmatrix}
1 & -1 & 0 & \cdots & & & 0\\
-1/2 & 1 & -1/2 & 0 & \cdots & & 0\\
0 & -1/2 & 1 & -1/2 & 0 & \cdots & 0\\
& & \vdots\\
0 & 0 & \cdots & & & -1/2 & 1
\end{bmatrix}
$$
and the first row of the inverse corresponds to the expected number of visits when starting at state $n$.
$$
(I – R)^{-1} = \begin{bmatrix}
n & 2(n – 1) & 2(n – 2) & \cdots & & 4 & 2\\
n – 1 & \cdots & & & & & 2\\
n – 2 & \cdots & & & & & 2\\
& & \vdots\\
\end{bmatrix}
$$
Thus,
$$
E[N_i] = \begin{cases}
2i & 0 < i < n\\
n & i = n
\end{cases}
$$
My question is how I would solve this algebraically. My thought was
- Either solve the matrix inversion algebraically
- Solve the rest of the cases by hand without the use of the canonical form
I would like to generalize this to a random walk with probability $p$ rather than $1/2$ but am currently unsure of how to proceed.
Best Answer
When the walk tries to go to the right from state $i$, it succeeds with probability $\frac12$, so the expected number of visits is twice the number of times it goes right.
When it goes right, there is then a simple symmetric random walk between $0$ and $i$, starting from $i-1$, and in such a walk the probability to reach either boundary first is linear. Thus the probability to reach $0$ before reaching $i$ again is $\frac1i$, so the walk is expected to need $i$ attempts to reach $0$ from $i$. Thus the expected number of visits to state $i$ is $2i$.