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.
Best Answer
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}