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

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

• Why does the third bullet point say that the frog is safe when it reaches $3$? It is already safe when it reaches $1.25$. Commented Jun 30 at 16:21
• @JohnBentin 3 is just a red herring here.
– Amir
Commented Jun 30 at 16:29

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$$\sum_{n=1}^\infty \int_{0}^{1}\mathbb P\left(1-t

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

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]$$.

• Nice!!, but still dont know how you are using Irwin Hall CDF when you evaluate $\frac{1}{n!} \int_{\frac14}^{1}\left [\left(\frac54-t \right)^n-\left(1-t \right)^n \right]\text{d}t$ Commented Jun 30 at 16:36
• You may note that both the terms $(1-t)$ and $\frac54-t$ (for $0.25<t<1)$ are less than $1$, so in the summation of the Irwin Hall CDF, only the term with $k=0$ is required (I also fixed a typo in the formula given in the OP).
– Amir
Commented Jun 30 at 16:47
• @SatishRamanathan Aculaty, to be self-contained, in the above proof, we only need to show that the cdf of $S_n$ for $s\in(0,1]$ is $\frac{1}{n!}s^n$, which can be done by induction and the convolution formula for the pdf of the sum of independent random variables.
– Amir
Commented Jun 30 at 20:25

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.

• Agreed!! Attempting to come up with a different solution is sometime desirable Commented Jul 2 at 6:16