45
$\begingroup$

A drunk man stands with a cliff one step to his left. He takes steps randomly left and right. Each step has probability $p$ of going left and probability $q=1-p$ of going right. Each step is the same size.

If allowed to randomly step indefinitely, what is the probability that the drunk falls off the cliff?

In purely mathematical terms, the drunkard starts at $x=0$ and steps $+1$ or $-1$ with each step. If he ever gets to $x=-1$ he falls off the cliff.

$\endgroup$
  • 1
    $\begingroup$ When I first solved this problem I used a technique known mostly to mathematicians and physicists. However, I later learned that a clever sixth grade student could solve it. $\endgroup$ – DanielSank Dec 25 '14 at 21:05
  • 5
    $\begingroup$ I'm not necessarily opposed to having this question here, but it might be a better fit at Mathematics $\endgroup$ – Julian Rosen Dec 25 '14 at 22:00
  • 4
    $\begingroup$ IMO it has enough of an "aha!" moment that it fits equally well here. However, the solution I know needs a small technical aside showing that for $p < 1/2$, the probability is not 1. $\endgroup$ – Lopsy Dec 25 '14 at 22:15
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Gambler's_ruin $\endgroup$ – KSmarts Feb 18 '15 at 14:46
  • 1
    $\begingroup$ A question always of interest to me in these contexts... Zero probability still means there can be a countable collection of trajectories for which the drunkard does not fall off the cliff, correct? So at what point in these derivations do we 'handle', in some sense, these solutions? Where do these countably many walks 'go'? $\endgroup$ – user13598 Jun 27 '15 at 1:18
21
$\begingroup$

First, let's consider a modified problem. Suppose that the position of the cliff is moved from $x=-1$ to $x=a$ for some integer $a<0$. Suppose also that the drunkard has a home at $x=b$ for some integer $b>0$, and that if the drunkard reaches his home, he stops walking. Let $d(x)= d_{a,b}(x)$ be the probability the drunkard falls of the cliff, given that the drunkard is at position $x$. We have a recurrence relation $$ d(x)=p\,d(x-1)+(1-p)\,d(x+1). $$ The characteristic polynomial of this recurrence is $(1-p)r^2-r+p$. If we assume $p\neq\frac{1}{2}$, this polynomial has two distinct roots: $$ r=1,\hspace{1cm} r=\frac{p}{1-p}. $$ This means that $d(x)$ has the form $$ d(x)=c_1+c_2\left(\frac{p}{1-p}\right)^x, $$ where $c_1$ and $c_2$ are constants which may depend on $a$, $b$, and $p$ but are independent of $x$. We have boundary conditions $d(a)=1$ and $d(b)=0$, so we can solve for $c_1$ and $c_2$: $$ c_1=\frac{1}{1-\left(\frac{p}{1-p}\right)^{a-b}},\,\,\,c_2=\frac{1}{\left(\frac{p}{1-p}\right)^a-\left(\frac{p}{1-p}\right)^b}. $$


We recover the original question by taking $x=0$, $a=-1$, and letting $b$ go to infinity. The probability the drunkard falls in the original question is $$ \begin{align*} \lim_{b\to\infty} d_{-1,b}(0)&=\lim_{b\to\infty}\frac{1}{1-\left(\frac{p}{1-p}\right)^{-1-b}}+\frac{1}{\left(\frac{p}{1-p}\right)^{-1}-\left(\frac{p}{1-p}\right)^b}\left(\frac{p}{1-p}\right)^0\\ &=\lim_{b\to\infty}\frac{\left(\frac{p}{1-p}\right)^b-1}{\left(\frac{p}{1-p}\right)^b-\frac{1-p}{p}}\\ &=\begin{cases}1:p>\frac{1}{2},\\\frac{p}{1-p}:p<\frac{1}{2}.\end{cases} \end{align*} $$ Since the probability of falling approaches $1$ as $p$ approaches $\frac{1}{2}$ from below, the probability of falling must be $1$ when $p=\frac{1}{2}$.

$\endgroup$
  • 1
    $\begingroup$ The answers already posted are terrific, but I figure it can't hurt to have another solution $\endgroup$ – Julian Rosen Dec 26 '14 at 19:44
  • $\begingroup$ This is an awesome solution. I have never seen an analysis of a recurrence relation quite like this. I really like this solution because it's an easy generalization of Jan Dvorak's. $\endgroup$ – DanielSank Dec 26 '14 at 22:11
  • $\begingroup$ Such neat approach! +1 $\endgroup$ – Phonon Dec 26 '14 at 23:47
  • $\begingroup$ Clever idea taking b to infinity. I' had tried solving the recurrence without doing this and was short a boundary condition on the right side. $\endgroup$ – xnor Dec 27 '14 at 2:52
  • $\begingroup$ Accepted this answer because it is (I think) the one which most clearly shows why there is a different behavior for $p<1/2$ and $p>1/2$. Please note @xnor's answer as well which does explain this point (and is really cool!). This answer is also pretty easy to follow which may be nice for future hapless readers :) $\endgroup$ – DanielSank Jan 1 '15 at 19:28
21
$\begingroup$

The probability of dying eventually is the probability of moving to the left from x=0 eventually. Denote the probability of moving to the left of some point eventually when starting at that point by $p_d$. The probability $p_d$ is equal to the probability of moving left immediately ($p$), plus the probability of moving to the right immediately ($1-p$), then to the left eventually (back to the starting point) ($p_d$), then to the left eventually ($p_d$ again). In other words:

$$ \begin{align} p_d &= p + (1-p){p_d}^2 \\ (1-p) {p_d}^2 - p_d + p &= 0 \,. \end{align} $$

Plugging into the quadratic formula:

$$ \begin{align} p_d &= {1 \pm \sqrt {1-4(1-p)p} \over 2(1-p)} \\ &= {1 \pm \sqrt {1-4p+4p^2} \over 2(1-p)} \\ &= {1 \pm \sqrt {(1-2p)^2} \over 2(1-p)} \\ &= {1 \pm (1-2p) \over 2(1-p)}\,. \end{align} $$ Evaluating for the two cases of plus and minus sign: $$ \begin{align} p_{d1} &= {2-2p \over 2-2p} = 1 \quad \text{(first branch)} \\ \text{and} \qquad p_{d2} &= {2p \over 2(1-p)} = p/q \quad \text{(second branch)} \end{align} $$

  • For $p>1/2$ the second branch is physically impossible and the first branch applies.
  • For $p=0$ the second branch clearly applies, not the first one.
  • For $p=1/2$ both branches coincide and never intersect otherwise.
  • For similar probabilities the results should be similar ($p_d(p)$ is continuous), otherwise enough simulation would be able to distinguish arbitrarily small changes in step-wise probability with arbitrary confidence just by observing the survival rate. Thus, the second branch applies to the entire range of $(0,1/2)$

    I don't have a formal proof unfortunately, but I did run an automated test (1000 runs, give up after 1000 steps, tested for multiple values of $p$, distribution of survival times compared to expectations (unimodality with mode at 1 step) visually).


In total:

If the probability of moving towards the cliff, $p$, is at least $1/2$, death occurs with a probability of one. Otherwise, death occurs with a probability of $p\over{1-p}$.

$\endgroup$
  • $\begingroup$ The math looks solid, but I can't tell what is "the first branch" and what is "the second branch". Could you add clear conclusions (for p > 1/2 the probability is ??? and so on)? $\endgroup$ – Moyli Dec 26 '14 at 8:39
  • $\begingroup$ @Moyli done. I could use some mathjax help, though. $\endgroup$ – John Dvorak Dec 26 '14 at 8:50
  • $\begingroup$ This may be a nitpick, but I'm not sure that the elegant simulation argument can rule out the possibility that for $p=0$ the answer is 0 and for $p>0$ the answer is 1. $\endgroup$ – Lopsy Dec 26 '14 at 13:44
  • $\begingroup$ There's also a monotonicity argument, but that doesn't rule out $p_d = 1$ either, unfortunately. If I come up with a better argument (read: proof), I'll update the answer. I'm open to suggestions, too. $\endgroup$ – John Dvorak Dec 26 '14 at 13:47
  • $\begingroup$ @Lopsy Would a ruby script simulating a particular probability suffice to validate the branch choice? $\endgroup$ – John Dvorak Dec 26 '14 at 14:23
16
$\begingroup$

Answer: The probability he dies is $D = p/q$ for $q>1/2$, and $D=1$ otherwise.

We'll prove the answer in a circumspect way by solving a different problem. The method doesn't use any summations.

First, I claim that if $q < 1/2$, then the pirate dies with probability $D=1$. After $t$ steps, his position is the sum of $t$ independent random variables with negative mean. So, far large $t$, it approaches a normal distribution with negative mean $-O(t)$ and standard deviation $O(\sqrt{t})$. Therefore, his position remaining non-negative requires a z-score of $O(\sqrt{t})$, the probability of which approaches $0$ as $t \to \infty$.

Now for the modified problem. Label the pirate's possible positions as integers $x$. Imagine there's a pit at $x=0$ that kills the pirate if he steps into it. Say he also starts at $x=0$, but is exempt from dying to the pit only then. Because it's a pit rather than a cliff, the pirate can move left into the negatives.

Assume $q>1/2$. There's two cases. If the pirate moves right on his first move, we have the original problem (shifted right by 1), since he can never cross into the negatives without dying. If he moves left, he dies with probability 1, since we have a mirrored problem with $q<1/2$ where the pirate tends towards the pit.

The key idea is that the pirate has an equal probability to die starting left as starting right. Each of these is a total, not a conditional, probability.

$$\Pr(\text{Die and Left}) = \Pr(\text{Die and Right})$$

This is because there's a bijection between the two types of dying paths: mirror the path by flipping the direction of each move. For example,

$$\text{LLRLLRRR} \leftrightarrow \text{RRLRRLLL}$$

Mirroring preserves the fact that the pirate dies at the end of the path and no earlier. Moreover, it preserves probabilities: because the pirate starts and ends at $x=0$, each path must have an equal number $n$ of lefts and rights, and its overall probability $p^n q^n$ depends only on this number. Summing the probabilities over all these paths, we find the pirate has an equal chance of dying going left and right.

We now expand the probabilities conditional on which way the pirate went.

$$\Pr(\text{Die} \mid \text{Left}) \Pr(\text{Left}) = \Pr(\text{Die} \mid \text{Right}) \Pr(\text{Right})$$

Let $D$ be the probability we want to compute, the probability that the pirate dies if he starts right, and recall that he dies with probability $1$ if he starts left. This lets us solve for $D$ in terms of $p$ and $q$.

$$1 \times p = D \times q$$

which gives the answer $D = p/q$ for $q>1/2$. Recall that we argued separately that $D=1$ for $q < 1/2$. Finally, it remains to observe that when $q$ is exactly $1/2$, we must have $D=1$, since $D$ must be non-increasing in $q$.

We can check that this has the right behavior: $D$ is decreasing in $q$, has $D=1$ at $q=1/2$, and has $D=0$ at $q=1$.

$\endgroup$
  • 1
    $\begingroup$ Wow, and I thought my generating functions were elegant. This is a really, really clever trick. $\endgroup$ – Lopsy Dec 26 '14 at 6:37
  • 4
    $\begingroup$ @Lopsy I love generating functions, but I love bijective arguments even more. $\endgroup$ – xnor Dec 26 '14 at 6:37
  • $\begingroup$ It's easy to see that for q<1/2, the pirate drifts left off the cliff. How can you claim this? There's a chance of going right forever. $\endgroup$ – warspyking Dec 26 '14 at 15:13
  • $\begingroup$ Yes, the statement about $q<1/2$ giving unit probability of falling off, while correct, is hand wavy in this answer. $\endgroup$ – DanielSank Dec 26 '14 at 15:26
  • 4
    $\begingroup$ Why are you referring to the "drunk man" as a pirate? That's stereotyping pirates. $\endgroup$ – JoshDM Dec 26 '14 at 18:39
7
$\begingroup$

Having seen other people's answers, and pretty much understood them (I think), I thought I'd run a test.

I tried values of p ranging from 0.05 upwards in 0.05 increments. For each value of p i ran 10,000 tests, each with a limit of 10,000 steps.

I used the code below

Dim x As Integer
Dim die As Integer
Dim randomNum As Single
Dim test As Integer
Dim footstep As Integer
Dim location As Integer
Dim p As Single
Dim dead As boolean
location = 0
Randomize
For p = 0.05 To 0.95 Step 0.05
    die = 0
    For test = 1 To 10000
        location = 0        
        For footstep = 1 To 10000
            randomNum = Rnd
            If randomNum < p Then 
                location = location -1
            Else
                location = location +1
            End If
            If location <0 Then
                die = die + 1
                footstep = 10000
            End If
        Next 
    Next
    Print "p = " & p & "  Died " & die & "/10000"
Next

I achieved the following results:

p = .05  Died  523/10000 (p/q = 0.0526)
p = .10  Died 1134/10000 (p/q = 0.1111)
p = .15  Died 1732/10000 (p/q = 0.1764)
p = .20  Died 2457/10000 (p/q = 0.2500)
p = .25  Died 3273/10000 (p/q = 0.3333)
p = .30  Died 4286/10000 (p/q = 0.4286)
p = .35  Died 5433/10000 (p/q = 0.5385)
p = .40  Died 6658/10000 (p/q = 0.6667)
p = .45  Died 8179/10000 (p/q = 0.8182)
p = .50  Died 9918/10000 (p/q = 1.0000)
p = .55 and over  Died 10000/10000

In most cases the number of deaths is a little lower than expected but very close. I did only run each test for a limit of 10,000 steps, so that would have a small effect, but not a good enough mathematician to work out how much.

$\endgroup$
4
$\begingroup$

We solve the problem in two steps. First we solve the problem of a random walk with no cliff. Then we show how the solution to the problem with the cliff can be expressed in therms of the solution without the cliff.

Unconstrained walk

Consider the problem of a random walker moving without a cliff, i.e. just an unconstrained random walker. Denote the probability of arriving at point $j$, having started at point $i$, after $n$ steps, by the symbol $p_{ji}(n)$. Let $k$ denote the number of rightward steps. Then the number of leftward steps is $n - k$. The number of ways we can arrange $k$ rightward and $n - k$ leftward steps is

$$\frac{n!}{k! (n - k)!}$$

and the probability of getting any such string of steps is

$$p^{n - k}q^{k} \, ,$$

so the probability of such a walk is

$$p_{ji}(n) = p^{n - k}q^{k} \frac{n!}{k! (n - k)!} \, . $$

The displacement $d$ of this walk is the distance between the end and start points, $d \equiv j - i$. This displacement must also be equal to the the number of rightward steps minus the number of leftward steps,

\begin{align} d &= k - (n - k) \\ \implies k &= (d + n) / 2 \, . \end{align}

Therefore, $$p_{ji}(n) = p^{(n - d)/2} q^{(n + d)/2} \frac{n!}{\Big(\frac{n - d}{2}\Big)! \Big(\frac{n + d}{2}\Big)!} \, . $$

Note that this expression is only valid when $n$ and $d$ are both even or both odd. Otherwise, $p_{ji}(n)$ is zero. Note also that the problem has translational symmetry; $i$ and $j$ do not appear in the expression for $p_{ji}(n)$. The random walk probabilities depend only on the translation, so we replace the $ji$ subscript with $d$, writing $$p_d(n) = p^{(n - d)/2} q^{(n + d)/2} \frac{n!}{\Big(\frac{n - d}{2}\Big)! \Big(\frac{n + d}{2}\Big)!} \, . $$

Generating functions

Of course, we need to solve the original problem which includes the cliff. Let $f_{ji}(n)$ denote the probability that the walker arrives at point $j$ for the first time, having started at point $i$, after $n$ steps. Again, by translational symmetry we can write this as $f_d(n)$. The answer to the question "what is the probability that the walker ever falls off the cliff" is $$\text{Probability of falling} = \sum_{n=0}^\infty f_{-1}(n) \, .$$

Now here's the amazing part: if we define generating functions for $p_d(n)$ and $f_d(n)$ as $$ P_d(z) \equiv \sum_{n=0}^\infty p_d(n) z^n \qquad F_d(z) \equiv \sum_{n=0}^\infty f_d(n) z^n \, , $$ then it turns out that $^{[a]}$ $$F_d(z) = P_d(z) / P_0(z) \, .$$

This is awesome because the the probability that the walker ever falls off the cliff is \begin{align} \text{Probability of falling} &=\sum_{n=0}^\infty f_{-1}(n) \\ &= \lim_{z \rightarrow 1} F_{-1}(z) \\ &= \lim_{z \rightarrow 1} P_{-1}(z) / P_0(z) \\ &= \lim_{z \rightarrow 1} \left( \sum_{n=0}^\infty p_{-1}(n)z^n \right) / \left( \sum_{n=0}^\infty p_0(n) z^n \right) \, . \end{align}

Thus, we've written the solution to the problem purely in terms of the unconstrained probabilities for which we already found a solution! All that remains is doing the sums.

Solution

It turns out that

$$P_{-1}(z) = \sum_{n=0}^\infty p_{-1}(n)z^n = \frac{1}{2qz} \frac{1 - \sqrt{1 - 4 pqz^2}}{\sqrt{1 - 4pqz^2}}$$

and

$$P_0(z) = \sum_{n=0}^\infty p_0(n)z^n = \frac{1}{\sqrt{1 - 4pqz^2}}$$

so

\begin{align} \text{Probability of falling} &= \lim_{z \rightarrow 1} P_{-1}(z) / P_0(z) \\ &= \lim_{z \rightarrow 1} \frac{1 - \sqrt{1 - 4pqz^2}}{2qz} \\ &= \lim_{z \rightarrow 1} \frac{1 - \sqrt{1 - 4p(1-p)z^2}}{2(1-p)z} \\ &= \frac{1 - 2\sqrt{(p - 1/2)^2}}{2(1-p)} \\ &= \left\{ \begin{array}{ll} \frac{p}{1-p} & p < 1/2 \\ 1 & p > 1/2 \end{array} \right. \end{align}

which solves the problem.

It's pretty cool that this method got the kink at $p=1/2$ without us having to make any extra logical arguments.

$\lim_{z \rightarrow 1}$

It's interesting to think about the meaning of the limit $z \rightarrow 1$. The sums over $n$ in the generating functions involve the factor $z^n$. For $|z|<1$, the sums de-emphasize terms with large numbers of steps. In other words, $z<1$ means that we don't count long walks as much when computing the probability of falling off the cliff. In Figure 1 we plot the probability of falling off the cliff for various values of $z$. For low values of $z$ the probability of falling off the cliff is low for all $p$. This makes sense because low $z$ means that we strongly de-emphasize longer walks; even with $p=1$ we may not fall off the cliff because $z<1$ means we don't always even count the first step. For higher values of $z$ the probability to fall off increases. At $z=1$, which represents the original problem, the curve forms a cusp at $p=1/2$. It is interesting that the sequence of curves for values of $z$ less than one has no cusp, yet the limiting curve for $z=1$ does have a cusp. For $z>1$ the curve diverges.

enter image description here Figure 1: Absorption probability as a function of $p$ for a few values of $z$.

Higher moments

Note that if we want to compute higher moments of the number of steps of the random walk we can do it by differentiating the expression we already found. For example, the mean number of steps before falling off the cliff is

\begin{align} \sum_{n=0}^\infty f_{-1}(n) n &= \lim_{z \rightarrow 1} \frac{d}{dz} \sum_{n=0}^\infty f_{-1}(n) z^n \\ &= \lim_{z \rightarrow 1} \frac{d}{dz} F_{-1}(z) \\ &= \frac{p}{\sqrt{(p - 1/2)^2}} - \frac{1 - 2\sqrt{(p - 1/2)^2}}{2(1 - p)} \\ &= \left\{ \begin{array}{ll} \frac{p}{p-1/2} - 1 & p > 1/2 \\ \frac{p}{1/2 - p} - \frac{p}{1 - p} & p < 1/2 \, . \end{array} \right. \end{align}

Note that this function goes to $1$ as $p \rightarrow 1$, which makes sense because the walker has to fall off on the first step. The other asymptotic behaviors look wrong though, so maybe I messed up some algebra.

$[a]$: You can prove this by thinking of every walk as two parts: a first part which gets to $j$ for the first time, and then a second part which wanders off but eventually ends up at $j$.

$\endgroup$
0
$\begingroup$

The answer is if he is allowed to take an infinite number of steps the probability of him stepping off the cliff eventually is 1 (certain) for every value of p>0

To demonstrate this, if you could continue flipping a coin infinitely it would not matter how many times your flipped it, at some point (because it is certain to happen if you could do it infinitely) you would flip a consecutive number of either tails or heads greater than the total number of flips you have already had. Therefore no matter whether the tails or the heads represent a 'step to the left' the man would always end up stepping over the line of the cliff that he started next to.

$\endgroup$
  • $\begingroup$ Your second paragraph is only true for a fair coin. The statement "an event repeated infinitely times will eventually occur" is only true when the the probability of the event stays constant. However, the probability of flipping a consecutive number of heads greater than number of tails so far decreases over time (for coin biased towards tails). It decreases so quickly that it is possible it will never happen. $\endgroup$ – Mike Earnest Apr 23 '15 at 15:45
  • $\begingroup$ Welcome to Puzzling SE, Tommy! This question has been already answered correctly months ago, adding another answer is recommended only when you are sure to know a better answer than those already posted. When there are already several complete and clear answers for a problem (this is the case), it's not needed to post another one! $\endgroup$ – leoll2 Apr 23 '15 at 15:46
  • 2
    $\begingroup$ @leoll2 Do we really want to discourage answers like this? While this new answer is wrong as noted by Mike, it does give a thus far unique approach which could be improved. Also, I strongly recommend the use of the down-vote button if you think an answer is low quality. That's what it's for. $\endgroup$ – DanielSank Apr 23 '15 at 16:05
  • 1
    $\begingroup$ @DanielSank That's not what I meant, I try to rephrase. If you have a better solution than those existing, where "better" means "complete, correct, original, clear", then your answer is welcome! On the contrary, if you post an answer lacking of a foolproof demonstration (did he prove his statement about the coins?), then we don't benefit from it. $\endgroup$ – leoll2 Apr 23 '15 at 16:11
  • 1
    $\begingroup$ @Tommy Your statement "even if there was a 99.99% chance of flipping heads and only 0.01% of flipping tails, if you could flip the coin infinitely it is certain that eventually you would flip tails more times in a row than you had previously flipped the coin" Is quite simply false. The probability of a row of tails longer than the number of flipped coins at any given time decreases exponentially. $\endgroup$ – Taemyr May 4 '15 at 14:25
0
$\begingroup$

Umm, doesn't it have to be 100%?

If allowed to randomly step indefinitely means he keeps stepping until he falls off the cliff.

This turned into a semantic argument in comments, I thought I'd summarise my position here. It is a, possibly naive, argument from when does the result get evaluated?

If he never falls off the cliff, the evaluation never takes place as it is still an undetermined result.

If the problem was altered to say it terminates when he falls off a cliff or walks into a wall, that would give a definite stopping point to evaluate the failed to fall off cliff result.

My math extends as far as limit theorem in 1st year Engineering Calculus, so am obviously willing to bow to the assembled wisdom above that says I'm wrong ;-)

$\endgroup$
  • 1
    $\begingroup$ Nope. There are many many infinite sequences of steps which never cross the cliff. $\endgroup$ – DanielSank Dec 27 '14 at 2:14
  • $\begingroup$ I'm a programmer so I think of things that are halting. $\endgroup$ – Andy Dent Dec 27 '14 at 2:16
  • 1
    $\begingroup$ Right. So If you could somehow collect an infinitely large set of computers and run a simulation, I maintain that a nonzero fraction of them would run without halting forever! $\endgroup$ – DanielSank Dec 27 '14 at 2:17
  • $\begingroup$ If an infinite sequence never goes off the cliff then it can never be evaluated thus is discarded from the set of potential results, in my cosmology. $\endgroup$ – Andy Dent Dec 27 '14 at 2:17
  • 4
    $\begingroup$ What do you mean by "can never be evaluated"? You can't just willy-nilly throw out some test cases to make your answer true :) $\endgroup$ – DanielSank Dec 27 '14 at 2:17

protected by leoll2 May 3 '15 at 12:35

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.