4

A drunken walker is on $x=0$, and if $x<0$, he falls and he dies.(Once he gets position $x<0$, he dies permanently.)

There is $0<p<1$ chance to move right ($x \rightarrow x+1$), and $1-p$ chance to move left ($x \rightarrow x-1$).

(1) After $n$th step, what is the probability he is still alive?

(2) I have no idea to how to define probability he is still alive after infinite iteration, since there are infinite state and I can't convince this probability will be limit of (1) when $n$ goes $\infty$. So how to define that probability precisely and why it will be limit of (1)?

Maddy
  • 1,875
  • 3
    (2) Instead of meaningless "after infinite", think of it as "surviving forever". The event "survive forever" is the intersection of events "alive after $n$ steps" over all $n$. Events are just subsets of probability space. It's known (and not hard to prove) that $P(\bigcap E_n)=\lim P(E_n)$ for any nested sequence, $E_n\supset E_{n+1}$. As for (1), it looks pretty complicated to me. Are you sure you need the precise answer to (1), or is the question really about (2)? –  Jul 19 '14 at 16:46

2 Answers2

3

The generating function of the first hitting time $T$ of $-1$ starting from $0$ is $$E(s^T)=\frac{1-\sqrt{1-4pqs^2}}{2ps}=\sum_{n\geqslant0}\frac1{n+1}p^nq^{n+1}{2n\choose n}s^{2n+1},$$ where $q=1-p$. Thus, the probability to be still alive at time $2n+1$ is $$P(T\geqslant2n+3)=1-P(T\leqslant2n+1)=1-\sum_{k=0}^{n}\frac1{k+1}p^kq^{k+1}{2k\choose k}.$$ The probability to stay alive forever is $0$ if $p\leqslant\frac12$ and $1-(q/p)=(2p-1)/p$ if $p\gt\frac12$.

Did
  • 279,727
2

When $p=1/2$, the probability he is still alive after $2n$ steps is given by the Catalan numbers (see http://en.wikipedia.org/wiki/Catalan_number for the classical path-enumeration argument): $$ p_{2n} = \frac{1}{4^n(n+1)}\binom{2n}{n} = O\left(\frac{1}{n^{3/2}}\right)$$ hence the probability to be alive drops to zero quite fast as a function of $n$. The @This is much healthier's comment explains pretty good why the probability to be alive forever is just $\lim_{n\to +\infty}p_n$. If $p<\frac{1}{2}$, then the probability to stay alive forever is clearly still zero. If $p>\frac{1}{2}$ and we remove the sea, the position of the drunk after $n$ steps is concentrated around $(2p-1)n$ with a variance equal to $4p(1-p)n$. Due to the Hoeffding's inequality, the number of $n$-steps paths that land before $0$ is exponentially small in $(2p-1)^2 n$. This gives that after roughly $\frac{1}{(2p-1)^2}$ steps toward the right, the probability of never falling back into the sea becomes closer and closer to one. A careful estimation should show that, if $p>\frac{1}{2}$, the probability to survive forever is greater than: $$ C\cdot p_{\frac{1}{(2p-1)^2}}>\frac{C(2p-1)^3}{\sqrt{2\pi}}.$$

Jack D'Aurizio
  • 353,855
  • @Thisismuchhealthier: yes, I just added a probabilistic framework for the asymmetric case. – Jack D'Aurizio Jul 19 '14 at 19:48
  • Chance of he is still alive after $2n$ steps is higher than $n$th Catalan number. When is exactly $x=0$, it gives $n$th Catalan number. I think I can make rough bound using constant*catalan number – Maddy Jul 20 '14 at 01:28
  • @Maddy: you are clearly right, mine was just a crude bound to show that the probability to survive forever is positive when $p>1/2$. Did gave the true probability in the above answer. – Jack D'Aurizio Jul 20 '14 at 01:37