I would appreciate a further hint for this question:

Let $S_n$ a random walk on $\mathbb Z$, with $S_0=0$. Let $\tau_0 = \inf\{n>0:S_n=0\}$, the hitting time of $0$. Show that $$ 1 = \sum_{m=0}^n P_0(S_{n-m}=0) P_0(\tau_0>m).$$ (Hint: Condition according to the last time, that the chain will visit $0$, before time $n$.)

I cannot seem to work out what I should be conditioning.


For fixed $n \in \mathbb{N}$ set

$$\sigma := \sup\{k \leq n; S_k = 0\}.$$

Since $$\mathbb{P}(0<\tau_0 \leq n) = \mathbb{P}(0<\sigma \leq n) = \sum_{k=1}^n \mathbb{P}(\sigma=k)$$

we have

\begin{align*} \mathbb{P}(0<\tau_0 \leq n) &= \sum_{k=1}^n \mathbb{P}(S_k=0,S_{k+1} \neq 0, \ldots,S_n\neq 0) \\ &= \sum_{k=1}^n \mathbb{P}(S_k=0,S_{k+1}-S_k \neq 0, \ldots,S_n-S_k \neq 0). \end{align*}

By the independence of the increments of the random walk this implies

$$\mathbb{P}(0<\tau_0 \leq n) = \sum_{k=1}^n \mathbb{P}(S_k=0) \underbrace{\mathbb{P}(S_{k+1}-S_k \neq 0,\ldots,S_{n}-S_k \neq 0)}_{=\mathbb{P}(\tau_0>n-k)}. \tag{1}$$

On the other hand, we clearly have

$$\mathbb{P}(\tau_0>n) = \mathbb{P}(S_0=0) \mathbb{P}(\tau_0>n-0). \tag{2}$$

Adding $(1)$ and $(2)$ we conclude that

$$\underbrace{\mathbb{P}(\tau_0>0)}_{=1} = \sum_{k=0}^n \mathbb{P}(S_k=0) \mathbb{P}(\tau_0>n-k),$$


$$1 = \sum_{m=0}^n \mathbb{P}(S_{n-m}=0) \mathbb{P}(\tau_0>m).$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.