I'm reading Durrett's book on Probability and in the example of the asymmetric 1D random walk with $P(X_1=1)=p>1/2$, when trying to compute the expectation of the hitting time $T_{b}:=\inf\{n: S_n=b\}$ using optional stopping, in order to use the dominated convergence theorem to prove that $E[S_{T_b\wedge n}]\to E[S_{T_b}]$ he makes the following statement: $$E[\min_{n} S_n]>-\infty.$$

First of all, I think the $\min$ should be replaced by $\inf$ and intuitively I agree with the result, but I can't seem to be able to prove it.

I know that my random walk $S_n$ converges almost surely to $\infty$ by the law of large numbers and the fact that $p>1/2$ and I was thinking that this should imply that there are finitely many negative $S_n$, but this finite number is $\omega$-dependent (i.e. random). My idea was then to say that $$E[\inf_{n}S_n]\geq \sum_{k\in\mathbb{N}} (-k)P(\inf_{n}S_n=-k)$$ and then to use the fact the the above probabilities should be zero for all but finitely many $k$, but I don't know how to get rid of the $\omega$-dependance.

Any hints or (other) ideas?


Let $q$ be the probability that starting from $0$ the walk ever reaches $-1$. Then the probability $a_n$ that starting from $0$ the walk ever reaches $-n$ satisfies

$$ a_{n+1}=qa_n\;, $$

since the walk reaches $-(n+1)$ if and only if it first reaches $-n$ and then with probability $q$ reaches $-(n+1)$. Thus $a_n=q^n$. We have $q\ne1$, so the desired expectation can be computed as a finite expression in terms of $q$.

  • $\begingroup$ Thank you for your answer, but I don't unserstand how I can proceed from there. You are saying that $P(\exists j: S_j=-n)=q^n$. How does this say anything about $P(\inf_j S_j=-n)$? $\endgroup$ – DCPC Jul 13 '16 at 12:56
  • $\begingroup$ @DCPC: $P(\inf_jS_j=-n)=P(\exists j: S_j=-n)-P(\exists j: S_j=-(n+1))$. But more directly, $E[\inf_jS_j]=-\sum_{n=1}^\infty P(\exists j: S_j=-n)$. $\endgroup$ – joriki Jul 13 '16 at 13:50
  • $\begingroup$ Thank you. I agree with your reasoning except one thing. Your initial claim. If you consider $P(\exists j: S_j=-1)$, this is equal to $P(\cup_{j} \{S_j=-1\}) = \sum_{j} P( T_{-1}=j)=P(T_{-1}<\infty)\geq q$, where $T_{-1}$ is the hitting time of $-1$. Then, by the same reasoning, $P(\exists j: S_j=-n)= P(T_{-1}<\infty)^n$. $\endgroup$ – DCPC Jul 14 '16 at 8:15
  • $\begingroup$ @DCPC: I don't quite understand that comment. Why do you write $\ge q$ and not $=q$? And I'm not sure what you're getting at -- are you saying that the conclusion you reach in the end is wrong, and hence my argument must be wrong? If so, why is the conclusion wrong? $\endgroup$ – joriki Jul 14 '16 at 10:24
  • $\begingroup$ I'm saying it's greater than $q$ because $q=P(S_1=-1)$, but $P(S_3=-1, S_1>-1, S_2>-1)=P(T_{-1}=3)>0$ and similarly $P(T_{-1}=2k+1)= c_k p^{k}q^{k+1}>0$, where $c_k$ is the k-th Catalan number. $\endgroup$ – DCPC Jul 14 '16 at 13:23

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.