Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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.
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}$.
b to infinity. I' had tried solving the recurrence without doing this and was short a boundary condition on the right side.
$\endgroup$
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 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}$.
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$.
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.
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.
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)!} \, . $$
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.
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.
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.
Figure 1: Absorption probability as a function of $p$ for a few values of $z$.
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$.
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.
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 ;-)
