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

Solution 1:

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