# Symmetric random walk and the distribution of the visits of some state

I need help with this problem:

Let $(S_n)_n$ a symmetric random walk in $\mathbb{Z}$ i.e $S_n=X_1 + \cdots + X_n$ with $(X_n)$ iid $\mathbb{P}(X_n=1)=\mathbb{P}(X_n=-1)=\frac{1}{2}$. Let $m \in \mathbb{Z}\setminus\{0\}$ and consider the random variable

$$V_m= \text{number of visits to } m \text{ in a excursion of X starting at 0 and ending at 0}$$

Prove that $\mathbb{P}(V_m \geq k)=\frac{1}{2|m|}\left(1-\frac{1}{2|m|}\right)^{k-1}$

My approach:

I consider the stopping times $T_0 = \inf\{n > 0 \colon \ X_n=0\}$ and $$T_m(1)=\inf\{n > 0 \colon \ X_n=m\}, \dots,T_m(k+1)=\inf\{n > T_m(k) \colon \ X_n=m\}$$ Then we have that the probability that we are seeking is $\mathbb{P}_0(T_m(k)<T_0)$.

I try to use that $X$ is martingale and $\min\{T_0,T_m(k)\}$ is stopping time but $X_{\min\{T,n\} }$ is not bounded and I fail. Then I try to use a similar approach but only with the stopping time $T_m(1)$ and I failed. And finally I try to prove by induction (and the strong Markov property) that $$\mathbb{P}_0(T_m(k)<T_0)=\frac{1}{2|m|}\left(1-\frac{1}{2|m|}\right)^{k-1}$$
(assuming $\mathbb{P}_0(T_m(1)<T_0)=\mathbb{P}_0(T_m(k)<T_0)=\frac{1}{2|m|}$ which is something that I haven't prove yet) And I failed.

Any help will be appreciated

• Got something from the answer? – Did Jul 15 '14 at 17:45

One can decompose the final formula, this shows how the proof works. Assume wlog that $m\gt0$.
• $\frac12=P(S_1=1)$ (if $S_1=-1$, then $V_m=0$)
• $\frac1m=P_1(T_m\lt T_0)$ (means that one gets at least one visit to $m$)
• $\frac1{2m}=P_m(T_0\lt T_m)$ (means that the number of visits does not increase anymore)
• $1-\frac1{2m}=P(V_m\geqslant k+1\mid V_m\geqslant k)$ for every $k\geqslant1$ (follows from the preceding item)
Thus, martingales are off topic in the sense that the only necessary tool, applied several times in conjunction with the strong Markov property, is that, for every integers $a\lt b\lt c$, $$P_b(T_c\lt T_a)=\frac{b-a}{c-a}.$$ But to show this, martingales are useful since, considering $T=T_a\wedge T_c$, the martingale $(S_{T\wedge n})$ starting from $S_0=b$ is bounded hence $E_b(S_T)=b$, that is, $$aP_b(T_a\lt T_c)+cP_b(T_c\lt T_a)=b=a(1-P_b(T_c\lt T_a))+cP_b(T_c\lt T_a),$$ which yields $P_b(T_c\lt T_a)$.