4
$\begingroup$

I recently came across a (very simple) high school probability problem which simply asked for the probability that the robot described below falls off the cliff after exactly 5 steps with $p$ specified. I'm more interested in the random variable implied in that problem than this specific case, which can be calculated by simply following the relevant branches in a tree. To put the problem that I am interested in into words:

Problem

A robot stands at the edge of a cliff and continues taking fixed-sized steps either towards the cliff with probability $p$ or away from the cliff (with probability $1-p$) until it falls over the edge.

Let's define a random variable $X$ as the number of steps the robot takes before it falls over the edge of the cliff.

What is the probability mass function of $X$?

Here are my thoughts so far.

  • In order for the robot to walk off the cliff, it must take $n$ steps away from the edge and $n+1$ towards the edge. This rules out the possibility of the robot falling over the edge after an even number of steps. Further (for an odd number of steps) it suggests that the probability that the robot walks off the cliff may be expressed in the form $C \cdot p^{n+1}\cdot (1-p)^{n}$ where $2n+1=x$ is the total number of steps, and $C$ is some coefficient to be determined.

  • I'm assuming that, given an eternity, the robot must at some point fall off the cliff (an assumption that niggles me a little), but that there is no upper bound on the number of steps that it will take.

  • The last step must, of course, be the step that takes the robot over the edge. Further, none of the preceding steps can take the robot over the edge in the meantime. (This prevents us from using a binomial distribution to model the situation.)

  • If $p<0.5$ the robot tends to get further away from the cliff as time goes by and the characteristic values of $X$ grow astronomically. Even with $p=0.5$, computer simulations show that some very large values of $x$ do sometimes occur in a moderate number of simulations. For $p$ even slightly below $0.5$ the computer hangs (as expected) for even a moderate number of simulations.

In addition to playing around with simulations, I have got the computer to start off with a binomial tree associated with $x$ steps and to then lop off any branches that do not meet the criteria specified above so that I can see some sample values of $C$, the coefficient described above. Below is a sample of the output along with the successful sequences of steps; A stands for a step away from the cliff, T for a step towards the cliff.

Steps: 1
Coefficient: 1
  T
Steps: 3
Coefficient: 1
  ATT
Steps: 5
Coefficient: 2
  AATTT
  ATATT
Steps: 7
Coefficient: 5
  AAATTTT
  AATATTT
  AATTATT
  ATAATTT
  ATATATT
Steps: 9
Coefficient: 14
  AAAATTTTT
  AAATATTTT
  AAATTATTT
  AAATTTATT
  AATAATTTT
  AATATATTT
  AATATTATT
  AATTAATTT
  AATTATATT
  ATAAATTTT
  ATAATATTT
  ATAATTATT
  ATATAATTT
  ATATATATT
Steps: 11
Coefficient: 42
  AAAAATTTTTT
  AAAATATTTTT
  AAAATTATTTT
  AAAATTTATTT
  AAAATTTTATT
  AAATAATTTTT
  AAATATATTTT
  AAATATTATTT
  AAATATTTATT
  AAATTAATTTT
  ...
  ATAATAATTTT
  ATAATATATTT
  ATAATATTATT
  ATAATTAATTT
  ATAATTATATT
  ATATAAATTTT
  ATATAATATTT
  ATATAATTATT
  ATATATAATTT
  ATATATATATT
Steps: 13
Coefficient: 132
  (etc.)
Steps: 15
Coefficient: 429
  (etc.)
Steps: 17
Coefficient: 1430
  (etc.)
Steps: 19
Coefficient: 4862
  (etc.)
Steps: 21
  Coefficient: 16796
  (etc.)
Steps: 23
  Coefficient: 58786
  (etc.)
Steps: 25
  Coefficient: 208012
  (etc.)
Steps: 27
  Coefficient: 742900 
  (etc.)

Does this random variable have a name? Do you recognise the coefficient?

$\endgroup$
1
$\begingroup$

I wasn't originally planning to answer my own question, but I returned to this problem recently and thought that I might as well share my further thoughts, which at least somewhat answer my original questions.

I haven't found this distribution discussed in literature (though I'm sure that this is just because I haven't searched in the right places) so I'll just call it the Catalan probability distribution for now because of the coefficients that arise in the terms.

Everything turns out to be a little cleaner if we rather express this distribution in terms of $\displaystyle u=\frac{x-1}{2}$, where $x$ is the number of steps the robot takes before it falls over the edge of the cliff. ($u$ is the number of steps the robot takes away from the cliff.)

Then:

$$\begin{align} P(U=0)&=1\cdot p^1(1-p)^0\;\text{(falls after one step)}\\ P(U=1)&=1\cdot p^2(1-p)^1\;\text{(falls after three steps)}\\ P(U=2)&=2\cdot p^3(1-p)^2\;\text{(falls after five steps)}\\ P(U=3)&=5\cdot p^4(1-p)^3\;\text{(etc.)}\\ P(U=4)&=14\cdot p^5(1-p)^4\\ P(U=5)&=42\cdot p^6(1-p)^5\\ \vdots\\ P(U=u)&=\frac{1}{u+1} {2u \choose u}\cdot p^{u+1}(1-p)^u \end{align}$$


It is pretty straightforward, using the ratio test, to show that the sum

$$\sum_{u=0}^\infty \frac 1 {u+1} {2u \choose u}\cdot p^{u+1}(1-p)^u$$

converges for $|1-p||p|<\frac 1 4$, which (after testing endpoints) includes $0\le p\le 1$ (i.e. $p$ being a probability).

Interestingly, however, the sum only converges to $1$ (i.e. the above is only a valid probability distribution) for $\frac 1 2 \le p \le 1$ (otherwise the sum appears to converge to $\frac p {1-p}$). (The niggling feeling that I expressed in my post appears to have had some foundation! If it is - even slightly - more probable for the robot to step away from the cliff then it appears to be possible for the robot to never walk off the cliff, even with no limit on the number of steps it can take!)

In any case,

$$U \sim \text{Cat}(p) \implies P(U=u)=\frac{1}{u+1} {2u \choose u}\cdot p^{u+1}(1-p)^u$$

where $\frac 1 2 \le p \le 1$, the lone parameter, is the probability of stepping towards the cliff, appears to be a decent description of the random variable in question. (The associated number of steps in the original problem would, of course, just be $x=2u+1$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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