Stanford Math Tournament Calculus Problem: Probability that a frog with uniformly distributed step length can pass an abyss on real line

Question

A frog hops on the real number line, starting from the origin:

• Each second, it moves right uniformly at random a distance between $0$ and $1$.
• There is an abyss between $1$ and $5/4$, and if the frog lands there it will fall into the abyss.
• If the frog makes it to or passes $3$ without falling in the abyss, then the frog is safe. $$ \large\mbox{What is the probability it is safe ?.} $$ Let us invoke Irwin Hall Distribution and work on the probability of falling into abyss and then inferring probability that it is safe.

The CDF of the sum of $n$ independent random variables uniformly distributed on $(0,1)$ [1]:

$$P(X\le x,n) = \dfrac{1}{n!} \sum_{k=0}^{\lfloor x \rfloor} (-1)^k {n\choose k} {(x-k)}^n$$

Thus $P(X\le x)$, given that x of abyss is in the range $(1\le x \le2)$,

for n=1, $P(X\le x) =1$

for n=2, $P(X\le x) = \dfrac{1}{2.2!}\left[(-1)^0.{2\choose0}x^2 +(-1)^1.{2\choose 1} (x-1)^2\right]$

For n=3, $P(X\le x) =\dfrac{1}{3.3!}\left[ (-1)^0.{3\choose0}x^3 +(-1)^1.{3\choose 1} (x-1)^3\right]$

and n=..

To summarise

CDF can be be written such as

$P(X\le x) = \left[1+ \dfrac{x^2}{2.2!}+\dfrac{x^3}{3.3!}+\cdots\right] - \left[ \dfrac{(x-1)^2}{2!} + \dfrac{(x-1)^3}{3!}-\cdots\right]$

PDF is the derivative of this

P(X = x) $= \left[\dfrac{(x)}{2!}+\dfrac{(x^2)}{3!}+\cdots \right] - \left[(x-1) + \dfrac{(x-1)^2}{2!}+\dfrac{(x-1)^3}{3!}+\cdots\right]$

This translates $ P(X= x) = \dfrac{(e^x - 1)}{x} - e^{x-1}$

Thus $P(\text{falling into the abyss}) = \int_{1}^{5/4} P(X=x) = 0.178761$

$P(\text{the frog is safe}) = 1-.178761 = 0.821$

It sounds logical but to see if abyss happens to be (1.1 and 1.75),say, the probability results in 0.56

https://www.stanfordmathtournament.com/pdfs/smt2023/calculus-tiebreaker-solutions.pdf

Answer 1

Denoting $S_n=\sum_{i=1}^nX_i$ for independent $X_1,\dots,X_n \sim \mathcal U(0,1)$, the fall probability can be obtained as follows: $$\sum_{n=1}^\infty \mathbb P(S_n<1, 1<S_n+X_{n+1}<\frac54)= \sum_{n=1}^\infty \int_{0}^{1} \mathbb P(S_n<1, 1<S_n+t<\frac54) \text{d}t=$$$$\sum_{n=1}^\infty \int_{0}^{1}\mathbb P\left(1-t<S_n<\min\left(1,\frac54-t\right) \right) \text{d}t. \tag{1}$$

Using the cdf of $S_n$ for $s\in(0,1]$, which can be obtained from the Irwin Hall's cdf by considering the first term with $k=0$ (a simpler proof is given below), each inner integral can be written as

$$\int_{0}^{\frac14}\mathbb P(1-t<S_n<1) \text{d}t+\int_{\frac14}^{1}\mathbb P\left(1-t<S_n<\frac54-t \right) \text{d}t=\\\frac{1}{n!} \int_{0}^{\frac14}\left [1-\left(1-t \right)^n \right]\text{d}t+\frac{1}{n!} \int_{\frac14}^{1}\left [\left(\frac54-t \right)^n-\left(1-t \right)^n \right]\text{d}t=\\ \frac{1}{n!}\left(\frac14-\frac{\left(\frac14 \right)^{n+1}}{n+1}\right), $$

which after putting in the summation (1) gives $1-e^{\frac 1 4}+\frac{e}4 ,$ and thus the desired probability is $e^{\frac 1 4}-\frac{e}4$, which is also obtained by a different method in the pdf.

---

PS: To be self-contained, we can directly derive the cdf of $S_n$ for $s∈(0,1]$ using the following formula for $s∈(0,1]$ and $n\ge 2$:

$$f_{S_n}(s)=\int_{0}^{s} f_{S_{n-1}}(s-t)f_{X_{n}}(t) \text{d}t=\int_{0}^{s} f_{S_{n-1}}(s-t) \text{d}t=\frac{1}{(n-1)!}s^{n-1}$$

where $f_{S_1}(x)=f_{X_1}(x)=1$. Hence, $F_{S_n}(s)=\frac{1}{n!}s^{n}$ for $s∈(0,1]$.

Answer 2

A simple experiment shows Stanford is right.

The derivation is flawless and simple with some elementary knowledge of solving a trivial linear ODE of first order.

    exp[n_] := 
    Table[
      Nest[(If[ #1 < 1 || # > 1 + 1/4, # + RandomReal[], #] &), 0,  144],
       {n}]

     Count[exp[10000], _?(1 < # < 1 + 1/4 &)]/10000.
         0.3912`

      1 - (E^(1/4) - E/4.)
         0.3955450404270199`

The possibilities to miscount complicated probabilities by partitions are indenumerable. So a short analytical solution that fits the data is always preferable.