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

Question

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.

Answer 1

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}

Answer 2

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.: \begin{equation} N((0,0)\to(2n,0) : S_k\neq0,\; 0<k<2n)=2N((1,1)\to(2n-1,1) : S_k>0,\; 1\leq k \leq 2n). \end{equation} 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: \begin{equation} N((0,0)\to(2n,0) : S_k\neq0,\; 0<k<2n)=2\left[N((1,1)\to(2n-1,1)-N((1,1)\to(2n-1,-1))\right]=2\left[\binom{2n-2}{n-1}-\binom{2n-2}{n-2}\right]. \end{equation} The probability of the first return can then be easily computed multiplying the result by $2^{-2n}$.