3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Oct 17, 2019 at 8:35
  • $\begingroup$ I got this formula from the book? $\endgroup$ Commented Oct 17, 2019 at 9:06

2 Answers 2

1
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ How did you get the second equality? Where is the 1/2 that get multiplied by? $\endgroup$ Commented Oct 17, 2019 at 16:47
  • $\begingroup$ @user42493 $\mathsf{P}_0(T_0=2n\mid X_1=1)=\mathsf{P}_0(T_0=2n\mid X_1=-1)$. $\endgroup$
    – user140541
    Commented Oct 17, 2019 at 18:18
  • $\begingroup$ @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. $\endgroup$
    – gbi1977
    Commented Dec 15, 2019 at 21:31
  • 1
    $\begingroup$ @gbi1977 A simple proof of this result is given here. $\endgroup$
    – user140541
    Commented Dec 15, 2019 at 22:02
  • $\begingroup$ I have actually found an even simpler explanation for the problem here $\endgroup$
    – gbi1977
    Commented Dec 15, 2019 at 22:10
0
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – apelle
    Commented Jun 12, 2023 at 9:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .