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

  • $\begingroup$ For starters can you compute $P(\tau_k\lt\tau^*)$? $\endgroup$
    – Did
    Aug 7, 2014 at 10:05
  • $\begingroup$ Yes, let's say we know that…. $\endgroup$ Aug 7, 2014 at 10:54
  • $\begingroup$ 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? $\endgroup$ Aug 7, 2014 at 10:58
  • $\begingroup$ No, how do YOU compute THE EXACT VALUE of $P(\tau_k\lt\tau^*)$? $\endgroup$
    – Did
    Aug 7, 2014 at 11:01
  • $\begingroup$ 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. $\endgroup$ Aug 7, 2014 at 11:07

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

  • 1
    $\begingroup$ 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}$? $\endgroup$ Mar 20, 2015 at 11:17
  • $\begingroup$ Yes, it should. I corrected this mistake. $\endgroup$ Mar 20, 2015 at 22:25

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.