# Conditional return time of simple random walk

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, \, S_t =k \}$, the hitting time of $k \in \mathbb{N}$. Call $\tau^* = \min\{t >0\, : \, \, S_t =0 \}$, the return time to the origin. Let $c<1$ be a positive constant.

Is there a way to compute the next formula explicitly?

$$\sum_{k=1}^{\infty} \sum\limits_{j=1}^{\infty} P ( \tau_k = j \, | \, \tau_k < \tau^*) \cdot c^{j-1}$$

• For starters can you compute $P(\tau_k\lt\tau^*)$?
– Did
Aug 7, 2014 at 10:05
• Yes, let's say we know that…. Aug 7, 2014 at 10:54
• Perhaps a bound could be $\frac{P(\tau^* > j)}{P(\tau_j < \tau^*)}$, just using the bound $P(\tau_k < \tau^*) > P(\tau_j < \tau^*)$. But is $P(\tau^* > j)$ know exactly? Aug 7, 2014 at 10:58
• No, how do YOU compute THE EXACT VALUE of $P(\tau_k\lt\tau^*)$?
– Did
Aug 7, 2014 at 11:01
• The first step must be right. Thus $P(\tau_k < \tau^*) =$p P(SRW starting from 1 reaches k before 0)$and it comes from the gambler ruin problem. Aug 7, 2014 at 11:07 ## 1 Answer To have$\tau_k < \tau^*$, the first step of the walk must be in the positive direction. So, we may as well start the walk at position$1$: let$X_1$,$X_2$,$X_3$,$\ldots$be i.i.d. with$\mathbb{P}(X_i=1)=\mathbb{P}(X_i=-1)={1\over 2}$, let$T_n:=1+\sum_{1\le i\le n} X_i\ \ (n\in\mathbb{Z}_{\ge 0})$, and let$\mu_k:=\min \{n\in\mathbb{Z}_{\ge 0}\mid T_n=k\}$. We then want to compute $$\sum_{k\ge 1} \mathbb{E}[c^{\mu_k}\mid \mu_k<\mu_0],$$ where the$-1$in the exponent has disappeared because we started the walk at what was formerly time$1$. Fix some$A>0$and let$M_n:=c^n A^{T_n}$; if$A+A^{-1}=2/c$,$M_n$will be a martingale. Then, by the optional stopping theorem, \begin{eqnarray*} A=M_0&=& \mathbb{E}[M_{\min(\mu_k, \mu_0)}]\\ &=& \mathbb{P}(\mu_k<\mu_0) \mathbb{E}[c^{\mu_k}\mid \mu_k < \mu_0] A^k+ \mathbb{P}(\mu_k>\mu_0) \mathbb{E}[c^{\mu_0}\mid \mu_k > \mu_0]. \ \ (*) \end{eqnarray*} The equation$A+A^{-1}=2/c$has two positive roots. Let$A_0$be the one greater than$1$; the other will then be$A_0^{-1}$. Setting$A:=A_0$and$A:=A_0^{-1}$in$(*)$then gives two linear equations. Subtracting one from the other and solving gives $$\mathbb{P}(\mu_k<\mu_0) \mathbb{E}[c^{\mu_k}\mid \mu_k < \mu_0] = {A_0-A_0^{-1}\over A_0^k-A_0^{-k}}= {1\over A_0^{k-1}+A_0^{k-3}+\cdots+A_0^{-(k-3)}+A_0^{-(k-1)}}.\ \ (**)$$ Letting$c\to 1$,$A_0\to 1$as well. In this case$(**)$becomes $$\mathbb{P}(\mu_k<\mu_0) = \frac{1}{k},$$ which can also be found by using the optional stopping theorem with the martingale$T_n$. Dividing this into$(**)$gives $$\mathbb{E}[c^{\mu_k}\mid \mu_k < \mu_0] = k {A_0-A_0^{-1}\over A_0^k-A_0^{-k}},$$ so the answer is $$\sum_{k\ge 1} k {A_0-A_0^{-1}\over A_0^k-A_0^{-k}}.$$ • Nice the idea of using the optional stopping theorem! However, in (*), shouldn't the second term in the right hand side contain$c^{μ_0}$instead of$c^{μ_k}\$? Mar 20, 2015 at 11:17
• Yes, it should. I corrected this mistake. Mar 20, 2015 at 22:25