Simple Random Walk: Hitting time of 1 is a.s. finite

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.?

• Do you know how to calculate $P(T_1=n)$ (for odd $n$)? – Arthur Dec 24 '15 at 8:35
• 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$. – A.S. Dec 24 '15 at 8:47
• 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? – user136457 Dec 24 '15 at 9:01
• Reflection principle suffices as you don't need CLT/Catalan numbers to see that $P(S_n\in\{0,1\})\to 0$. – A.S. Dec 24 '15 at 9:08
• 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. – 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$$.

• $\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. – Dingo13 Jan 31 at 9:43
• @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. – Sangchul Lee Jan 31 at 14:39
• I think you missed the even terms, i.e. $T_1=2k+2$, ... Otherwise I do not understand the answer. – Dingo13 Jan 31 at 14:42
• @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). – Sangchul Lee Jan 31 at 14:43
• 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. – Dingo13 Jan 31 at 14:45