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.
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$.