Let $X_i, i \geq 0$ be i.i.d. random variables with $P[X_i=1]=P[X_i=-1]=1/2$ and consider $S_n = X_1 + \dotsc + X_n$ for $n \geq 1$, $S_0=0$, the symmetric simple random walk on $\mathbb{Z}$.

Let $T_1:=\inf{\{n \geq 0 \,\colon \, S_n = 1\}}$ be the hitting time of $1$.

How can one see that $T_1 < \infty$ a.s.?

  • $\begingroup$ Do you know how to calculate $P(T_1=n)$ (for odd $n$)? $\endgroup$
    – Arthur
    Dec 24 '15 at 8:35
  • 2
    $\begingroup$ By reflection principle, $P(T\le n)=P(S_n\ge 1)+P(S_n\ge 2)=1-P(S_n=0,1)\to 1$. From CLT we get $P(T>n)=P(S_n=0,1)\sim \frac 2{\sqrt {2\pi n}}$ which yields $E(T)=\infty$. $\endgroup$
    – A.S.
    Dec 24 '15 at 8:47
  • $\begingroup$ Thanks a lot for your answers. Is there some easier approach not relying on CLT or very specific knowledge about Catalan numbers? Is there maybe an approach using Borel-Cantelli? $\endgroup$
    – user136457
    Dec 24 '15 at 9:01
  • 1
    $\begingroup$ Reflection principle suffices as you don't need CLT/Catalan numbers to see that $P(S_n\in\{0,1\})\to 0$. $\endgroup$
    – A.S.
    Dec 24 '15 at 9:08
  • 1
    $\begingroup$ 1. Since this is the application of the reflection principle, I wonder as to where you've seen it used. 2. $P(S_n\ge 1)=P(S_n\le -1)$. 3. Informally, distribution of $S_n$ flattens more and more it's support grows linearly - so occupation probability of each site goes to zero. Formally, you express $P(S_n=0,1)$ through a binomial coefficient and apply Stirling's approximation. $\endgroup$
    – A.S.
    Dec 24 '15 at 9:26

In this case, we can give an easy estimate on the tail probability of $T_1$. Notice that

$$ \{T_1 = 2n+1\} = \{S_1 \leq 0, \cdots, S_{2n-1} \leq 0, S_{2n} = 0, S_{2n+1} = 1\}. $$

Using one of the equivalent characterization of Catalan number, we can explicitly compute the probability of this event as

$$ \Bbb{P}(T_1 = 2n+1) = \frac{1}{2^{2n+1}}C_n = \frac{1}{2^{2n+1}(n+1)} \binom{2n}{n}. $$

From this, we explicitly compute the probability generating function of $T_1$ by

$$ |z| < 1 \quad \Rightarrow \quad \mathbb{E}[z^{T_1}] = \sum_{n=0}^{\infty} z^n \mathbb{P}(T_1 = n) = \sum_{n=0}^{\infty} \frac{C_n}{2^{2n+1}} z^{2n+1} = \frac{1-\sqrt{1-z^2}}{z}. $$

Letting $z \to 1^-$ shows that, by the monotone convergence theorem,

$$ \mathbb{P}(T_1 < \infty) = \lim_{z \to 1^-} \mathbb{E}[z^{T_1}] = \lim_{z \to 1^-} \frac{1-\sqrt{1-z^2}}{z} = 1. $$

Therefore $\Bbb{P}(T_1 = \infty) = 0$.

Addendum. Using this, we can also show that

$$ \mathbb{E}[T_1 z^{T_1}] = \frac{1-\sqrt{1-z^2}}{z\sqrt{1-z^2}}, $$

and so, $T_1$ infinite expectation $\Bbb{E}[T_1] = \infty$.

  • $\begingroup$ $\Bbb{P}(T_1 > 2n) = \sum_{k=n}^{\infty} \Bbb{P}(T_1 = 2k+1)$ is it true? It seems you have missed a lot of terms. $\endgroup$
    – Dingo13
    Jan 31 '19 at 9:43
  • $\begingroup$ @Dingo13, It does not misses a lot of terms, but you are right in that I am missing a term. More precisely, the alleged equality is actually missing the single term $\mathbb{P}(T = \infty)$, which is crucial for the argument. I will fix it later. $\endgroup$ Jan 31 '19 at 14:39
  • $\begingroup$ I think you missed the even terms, i.e. $T_1=2k+2$, ... Otherwise I do not understand the answer. $\endgroup$
    – Dingo13
    Jan 31 '19 at 14:42
  • $\begingroup$ @Dingo13, Notice that $S_{2n}$ takes only even integers and $S_{2n+1}$ takes only odd integers. Since $T_1$ is the hitting time for the value $1$, $T_1$ can take only odd-integer values (or infinity). $\endgroup$ Jan 31 '19 at 14:43
  • $\begingroup$ Isn't it possible to give a formula for $P(T_1=n)$ instead of $P(T_1=2n+1)$ ? Thank you. I make these comments because I am interested by this theory that I do not know. If you can improve you answer, I will be happy. $\endgroup$
    – Dingo13
    Jan 31 '19 at 14:45

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.