1

In a recent answer I gave a combinatorial interpretation for the sum $\sum_{n=1} \binom{2n}{n}\frac{4^{-n}}{n+1}=1$: namely, that it corresponded to the probability of all outcomes adding to $1$. A few commentators objected that I was taking for granted that such a game had no chance of lasting forever. That was a valid point, though one I felt comfortable leaving out of an intuitive explanation...

However, that left me wondering about the following question. What are some good examples of terminating random walks with finite 'escape' probability? (That is, a random what such that the stopping probability does not go to one as the number of steps goes to infinity.) As a secondary question: What are some notable summations implied by such walks?

Community
  • 1
Semiclassical
  • 15,842
  • ${{}}$ random what? – SBF Jul 28 '14 at 14:51
  • Makes sense---heck, I wouldn't be surprised if it was actually a probability of 1 in that case. (I chiefly had 1D models in mind, since it seems much more likely to find tractable summations in that case.) @JackD'Aurizio – Semiclassical Jul 28 '14 at 14:57
  • I am not an expert in the field, but I would bet that for a random walk in $\mathbb{Z}^3$ the probability of never hitting again the line $x=y=z$ after the start in the origin is positive. – Jack D'Aurizio Jul 28 '14 at 15:02
  • I was inspired by the non-ergodicity of the 3d-Brownian motion and the fact that $\mathbb{R}^2\setminus\gamma$ has two connected components, while $\mathbb{R}^3\setminus\gamma$, where $\gamma$ is a curve, is connected, so I am expecting that there are plenty of random paths avoiding a special $\gamma$ (the line $x=y=z$) in $\mathbb{Z}^3$. – Jack D'Aurizio Jul 28 '14 at 15:05
  • @JackD'Aurizio: Agreed. I'd even expect there to be many many more random walks that escape than return in that case. – Semiclassical Jul 28 '14 at 15:07
  • @Semiclassical: we may study the distribution of $D=(x-y)^2+(x-z)^2+(y-z)^2$ for the $n$-th step of the random walk, and see if the expected value stay bounded or diverges. – Jack D'Aurizio Jul 28 '14 at 15:10
  • 3
    @JackD'Aurizio The probability to never hit this line is zero in 3D because "nice" 2D random walks are recurrent. – Did Jul 28 '14 at 15:14
  • @Did: Right. Not sure how one comes up with a summation identity in that case...(maybe some kind of tabulation of all the 'ways' it can escape? not seeing an easy route.) – Semiclassical Jul 28 '14 at 15:19
  • @JackD'Aurizio Sorry but we are not here to exchange arguments (in the sense of feelings, really): the statement in my last comment is well known and can easily be made fully rigorous, if one desires. Note that already in 1D, the expected value of the distance to the starting point goes to infinity. – Did Jul 28 '14 at 15:23
  • ((Comment by @JackD'Aurizio now deleted.)) – Did Jul 28 '14 at 15:24
  • @Did: I was considering the squared distance from the line $x=y=z$, indeed. Am I wrong by saying that such a random variable has a $\chi^2$ distribution with a larger and larger expected value? – Jack D'Aurizio Jul 28 '14 at 15:29
  • Mmh, I just realized that the distribution of the squared distance is a $\chi^2$ with only two degrees of freedom. Ok, but this should work for real: the $\chi^2$ random variable with $3$ degrees of freedom has a bounded pdf in a a neighourhood of zero, hence for a random walk in $\mathbb{Z}^4$ the probability of never hitting again the line $x=y=z=w$ after the start is positive. – Jack D'Aurizio Jul 28 '14 at 15:32

1 Answers1

3

A simple example is a biased $\pm1$ random walk with $p\gt1/2$ probability of a $+1$ step, starting from $1$, stopped when it first hits $0$. Probability of "escaping" to infinity is $2-1/p$.

"Hence", for every $p$ in $(0,1)$, $$\sum_{n=0}^{\infty}\frac1{n+1}{2n\choose n}p^n(1-p)^n=\left\{\begin{array}{ccc}\frac1p&\text{if}&p\gt\frac12\\\frac1{1-p}&\text{if}&p\leqslant\frac12\end{array}\right.$$ (Which is the extension to every $p$ of the summation you recalled for $p=1/2$ at the beginning of your post.)

Did
  • 279,727