# Decreasing numbers

Pick a random number (evenly distributed) between 0 and 1. Continue picking random numbers as long as they keep decreasing; stop picking when you obtain a number that is greater than the previous one you picked. What is the expected number of numbers you pick?

Note by Jinay Patel
4 years, 9 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

This is a non-combinatorial solution. The probability of successfully finding a run of at least length one is $$\int_0^1 dx_1$$. It's easy to argue that the probability of successfully finding a run of at least length two is $$\int_0^1 (\int_0^{x_2} dx_1) dx_2$$, and in general $\int_0^1 \int_0^{x_n} \cdots \int_0^{x_2} dx_1 \cdots dx_n$ parameterizing this over $$x$$ as $p_n(x) = \int_0^x \int_0^{x_n} \cdots \int_0^{x_2} dx_1 \cdots dx_n$ we soon find that $$p_1(x) = x, p_2(x) = \frac{x^2}{2}, p_3(x) = \frac{x^3}{3!}, \dots, p_k(x) = \frac{x^k}{k!}$$ such that the probability of encountering a run of at least length $$k$$ is $$\frac{1}{k!}$$ (by instantiating $$p$$ at $$x = 1$$). Let $$P[X = k]$$ be the probability of encountering a run of exactly length $$k$$, then $P[X = k] = p_k(1) - p_{k+1}(1) = \frac{1}{k!} - \frac{1}{(k+1)!} = \frac{k}{(k+1)!}$ the generating function of the expected value is then just $f(x) = \sum_k \frac{k^2}{(k+1)!}x^k$ evaluated at $$x = 1$$; this is clearly analytic around $$x = 0$$ and also around $$x = 1$$, so we can manipulate this series keeping in mind that the OGF of $$e^x = \sum_k \frac{x^k}{k!}$$: \begin{align*} f(x) &= \sum_k \frac{k^2}{(k+1)!}x^k \\\\ &= x^{-1} \sum_k \frac{(k-1)^2}{k!} x^k \\\\ &= x^{-1} \left(\sum_k k^2 \frac{x^k}{k!} - 2\sum_k \frac{x^k}{(k-1)!} + \sum_k \frac{x^k}{k!}\right) \\\\ &= x^{-1} \left(\sum_k k \frac{x^k}{(k-1)!} - 2x\sum_k \frac{x^{k-1}}{(k-1)!} + e^x\right) \\\\ &= x^{-1} \left(x \sum_k (k+1) \frac{x^k}{k!} - 2xe^x + e^x\right) \\\\ &= \frac{x^2 - x + 1}{x} e^x\end{align*} where $E[X] = f(1) = e$

- 4 years, 9 months ago

Not sure whether this is correct, but let's try.

The probability that you will get the chance of getting the $$n$$th number is $$\frac{1}{(n-1)!}$$, as you need the previous $$n-1$$ numbers to be ordered decreasing and all $$(n-1)!$$ possible orderings are equally likely. Summing over all $$n$$ gives the expected number:

$$\displaystyle\sum_{n=1}^\infty \dfrac{1}{(n-1)!} = \boxed{e}$$

- 4 years, 9 months ago