# What is the probability that a random walk hit $0$ for the first time?

Let $$S_n$$ be a symmetric random walk with $$S_0=0$$. Denote by $$T_0$$ the time of the first return of the walk to the origin. Show that $$P(T_0=2k)=\frac{1}{2k-1}\binom{2k}{k}2^{-2k},k=1,2...$$?

I know that starting at $$0$$, the random walk first hit $$b$$ at step $$n$$ is probability $$\frac{|b|}{n}P(S_n=b)$$. How can we use this to solve the problem?

OK so Catalan number $$C_{k}=\frac{1}{n+1}\binom{2n}{n}$$. is the number of path that visite origin starting at the origin? ok then answer should be $$\frac{1}{n+1}\binom{2n}{n}(\frac{1}{2})^{2n}$$ which is still different from what we want.

• The statement "the random walk frst hit $b$ at step $n$ is $\frac bn P(S_n = b)$" has a problem in it, please check. Also, read up Dyck paths. Commented Oct 17, 2019 at 8:35
• I got this formula from the book? Commented Oct 17, 2019 at 9:06

Let $$\mathsf{P}_k$$ denote the law of a random walk started at $$k$$ and let $$X_i=S_i-S_{i-1}$$. Then for $$n\ge 1$$, \begin{align} \mathsf{P}_0(T_0=2n)&=\frac{1}{2}\mathsf{P}_0(T_0=2n\mid X_1=1)+\frac{1}{2}\mathsf{P}_0(T_0=2n\mid X_1=-1) \\ &=\mathsf{P}_1(T_0=2n-1)=\frac{1}{2n-1}\mathsf{P}_1(S_{2n-1}=0) \\ &=\frac{1}{2n-1}\mathsf{P_0}(S_{2n-1}=-1)=\frac{1}{2n-1}\binom{2n-1}{n}2^{-(2n-1)} \\ &=\frac{1}{2n-1}\binom{2n}{n}2^{-2n}. \end{align}

• How did you get the second equality? Where is the 1/2 that get multiplied by? Commented Oct 17, 2019 at 16:47
• @user42493 $\mathsf{P}_0(T_0=2n\mid X_1=1)=\mathsf{P}_0(T_0=2n\mid X_1=-1)$.
– user140541
Commented Oct 17, 2019 at 18:18
• @d.k.o. can you please explain the transition $P_{1}(T_{0}=2n−1)=\frac{1}{2n−1}P_{1}(S_{2n−1}=0)$? I'm struggling to have intuition for it. Commented Dec 15, 2019 at 21:31
• @gbi1977 A simple proof of this result is given here.
– user140541
Commented Dec 15, 2019 at 22:02
• I have actually found an even simpler explanation for the problem here Commented Dec 15, 2019 at 22:10

The problem can be solved using the reflection principle. The number of paths that do not touch $$0$$ between $$0$$ and $$2n$$ are given by the sum of the number of paths from $$(1,1)$$ to $$(2n-1,1)$$ always larger that $$0$$ and the number of paths from $$(1,-1)$$ to $$(2n-1,-1)$$, these two numbers are obviously equal by symmetry. I.e.: $$$$N((0,0)\to(2n,0) : S_k\neq0,\; 00,\; 1\leq k \leq 2n).$$$$ This number can be computed subtracting from the total number of paths between $$(1,1)$$ and $$(2n-1,1)$$ the number of paths touching $$0$$ between these two point. This last number can be computed using the reflection principle, therefore the total number of paths that do not touch $$0$$ between $$0$$ and $$2n$$ is: $$$$N((0,0)\to(2n,0) : S_k\neq0,\; 0 The probability of the first return can then be easily computed multiplying the result by $$2^{-2n}$$.

• I know that the question is old and has been answered. I just did not find the solution written is this form and I wanted to write it somewhere. This method of derivation may be interesting for someone looking to answer this or a similar question. Commented Jun 12, 2023 at 9:33