Expected number of times a random walk of n steps starting from origin and ending at x passes a point

Question

I wonder what is the expected number of times a random walk of n steps starting from origin and ending at x passes a point m located between 0 and x or after x? I just found the occupancy equation and probability of return to the origin and no similar question.

Answer 1

I think it will be a sum of scalar products on the power series of the random walks Markov matrix. $$(p_{x|x-1} {\bf \delta_{x-1}} ^T + p_{x|x+1} {\bf \delta_{x+1}} ^T) \sum_{k=0}^\infty {\bf P}^k [1,0,0,\cdots]^T$$

Where the Dirac delta vectors are $(\delta _i)_j = \cases{1 , i=j\\0, i \neq j}$

and the $p_{x|x-1},p_{x|x+1}$ can be extracted from the matrix.

Answer 2

Let $W(x,n)$ be the number of walks of $n$ steps producing a net displacement of $x$ (equivalently, starting at $0$ and ending at $x$).

$$W(x,n)={n \choose \frac{x+n}{2}} \quad [x=n \pmod 2]\,[-n \le x \le n]$$

Let $Z_t$ be the indicator variable of the event "a random walk of $n$ steps starting at $0$ and ending at $x$ is found at position $m$ at step $t$". Then $$ P(Z_t=1)=E(Z_t)=\frac{W(m,t)W(x-m,n-t)}{W(x,n)}$$

Then, by linearty of expectations, the desired result is

$$ E(\sum_{t=0}^{n-1} Z_t) =\sum_{t=0}^{n-1} \frac{W(m,t)W(x-m,n-t)}{W(x,n)} $$