Random walk on the integers

Question

A particle initially stands at $0$ in $\mathbb{N}$. Every second, it jumps one unit towards $-\infty$ or $+\infty$ with probability $\frac{1}{2}$ each.

What is the probability that it reaches $+1$?

Answer 1

if you are allowed to wait forever: 1.

There are lots of ways to do this. Suppose we ask the question hit 1 or -n first and stop when this happens.

Then since hitting time is a finite stopping time, the value of the random walk stopped at the hitting is still a martingale and so has expectation 0. So probability of hitting $1$ is $n$ times that of hitting $-n.$ So the probability of hitting $1$, is $n/(n+1).$

The probability you want must be bigger than this for any $n$ so it must be $1.$

Answer 2

The probability to hit $1$ after $1$ step is $\frac{1}{2}$, encoded by the string $+$; the probability to hit $1$ after $3$ steps is $\frac{1}{8}$, encoded by the string $-++$; the probability to hit $1$ after $5$ steps is $\frac{1}{16}$, encoded by the strings $-+-++$ and $--+++$. To compute the probability to hit $1$ after $2k+1$ steps, we just have to count how many binary strings of length $2k$, with $k$ zeroes and $k$ ones, have more zeroes than ones in every prefix. This is a well-known problem: the solution is given by the Catalan numbers: $$ C_k = \frac{1}{k+1}\binom{2k}{k}. $$ The probability to hit $1$ in the first $2N+1$ steps is so: $$ \sum_{k=0}^{N}\frac{1}{2^{2k+1}(k+1)}\binom{2k}{k}=\sum_{k=0}^{N}\left(\frac{1}{4^k}\binom{2k}{k}-\frac{1}{4^{k+1}}\binom{2k+2}{k+1}\right)\\=1-\frac{1}{4^{N+1}}\binom{2N+2}{N+1}=1-\frac{1}{\sqrt{\pi(N+5/4)}}+O\left(\frac{1}{N^{5/2}}\right).$$

Answer 3

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$

$\ds{\, P_{\sigma} = \half}$ is the probability of taking a jump of length $\ds{\sigma\ =\ \pm 1}$. So, the desired answer is given by:

\begin{align}&\color{#66f}{\large% \sum_{\sigma_{1}\ =\ \pm}\sum_{\sigma_{2}\ =\ \pm}\ldots\sum_{\sigma_{N}\ =\ \pm} \, P_{\sigma_{1}}\, P_{\sigma_{2}}\ldots \, P_{\sigma_{N}} \delta_{\sigma_{1} + \sigma_{2}+\cdots+\sigma_{N},1}} \\[5mm]&=\sum_{\sigma_{1}\ =\ \pm}\sum_{\sigma_{2}\ =\ \pm}\ldots\sum_{\sigma_{N}\ =\ \pm} \, P_{\sigma_{1}}\, P_{\sigma_{2}}\ldots \, P_{\sigma_{N}} \oint_{\verts{z}\ =\ 1} {1 \over z^{\sigma_{1} + \sigma_{2} + \cdots + \sigma_{N}}} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1} \pars{\sum_{\sigma\ =\ \pm}P_{\sigma}z^{-\sigma}}^{N}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1} \pars{\half\, z + \half\,{1 \over z}}^{N}\,{\dd z \over 2\pi\ic} \\[5mm]&={1 \over 2^{N}}\oint_{\verts{z}\ =\ 1}{\pars{1 + z^{2}}^{N} \over z^{N}} \,{\dd z \over 2\pi\ic} ={1 \over 2^{N}}\sum_{\ell\ =\ 0}^{N}{N \choose \ell}\oint_{\verts{z}\ =\ 1} {1 \over z^{N - 2\ell}}\,{\dd z \over 2\pi\ic} \\[5mm]&={1 \over 2^{N}}\sum_{\ell\ =\ 0}^{N}{N \choose \ell}\delta_{2\ell,N - 1} =\color{#66f}{\large{1 \over 2^{N}}\,{N \choose \bracks{N - 1}/2}} \quad\dsc{{\tt\mbox{if}}\ N\ {\tt\mbox{is odd and}}\ N \geq 1}. \\&\dsc{\mbox{Otherwise, it vanishes out}}. \end{align}