Probability – World Record for Lowest Number in Random Selection

approximationcombinatoricsexpected valueprobability

I have a random number generator that generates a random real number between $0$ and $1$ at the press of a button. All 8 billion people in the world line up for a try. Occasionally a world record for lowest number is set. (The first person automatically sets the first world record.) Approximately how many times will a world record be set?

Let $n=8\times 10^9$, the world's population.

Approach 1

Let $f(n,k)=$ the number of permutations of the first $n$ positive integers with exactly $k$ numbers that are less than all previous numbers. The first number in any permutation is considered to be less than all previous numbers (in the sense that it sets a new low).

The probability that exactly $k$ world records will be set, is $\frac{f(n,k)}{n!}$.

Then the expected number of world records is $\sum\limits_{k=1}^n k\left(\frac{f(n,k)}{n!}\right)$.

But I do not know how to express $f(n,k)$ so that I can calculate the expectation. Maybe there is a smart way to express $f(n,k)$, like stars and bars.

Approach 2

If I roll a six-sided die $m$ times, the expectation for the number of sixes is $m\times \text{(probability that the $k$th throw is a six)}=\frac{m}{6}$.

Similarly, perhaps the expectation for the number of world records can be approximated as $n\times \text{(probability that the $k$th person sets a world record)}=n\times\frac1k$.

But the problem is that $\frac1k$ is not a constant. However, suppose we use the average value of $\frac1k$, which is $\frac1n \sum\limits_{k=1}^n \frac1k \approx \frac1n \int_0^n \frac1x dx=\frac{\ln{n}}{n}$. Then the expectation would be $n\times \frac{\ln{n}}{n}=\ln{n}\approx 22.8$.

I tested this approach on excel, and it seems to yield reasonable results. But it seems rather hand-wavy.

Context

This question was inspired by a question about the sine of integers.

Best Answer

We invoke the indicator function trick. Let $X_k$ denote the random number generated for the $k$th person. Then we observe:

The $k$th person sets a the world record if and only if $X_k$ is the smallest among the first $k$ numbers $X_1, \ldots, X_k$.

Consequently, the number $N$ of times world record is set can be written as the sum

\begin{align*} N &= \sum_{k=1}^{n} \mathbf{1}\{\text{$k$th person sets a world record}\} \\ &= \sum_{k=1}^{n} \mathbf{1}\{\min\{X_1, \ldots, X_k\} = X_k\} \end{align*}

Then by the linearity of expectation, we have

\begin{align*} \mathbf{E}[N] &= \sum_{k=1}^{n} \mathbf{E}[\mathbf{1}\{\min\{X_1, \ldots, X_k\} = X_k\}] \\ &= \sum_{k=1}^{n} \mathbf{P}(\min\{X_1, \ldots, X_k\} = X_k) \\ &= \sum_{k=1}^{n} \frac{1}{k} = H_n, \end{align*}

where $H_n$ denotes the $n$th harmonic number.

Related Solutions

[Math] A die is rolled 5 times. How many outcomes will result in 5 different numbers? How many outcomes will have the 5th number equal to an earlier number

You could think as follows:

For the first part you have it right, for the first throw you have $6$ distinct possibilities, for the second throw you have $5$ and so on. Using the so called product rule you end up with $$ 6\cdot 5\cdot 4\cdot 3\cdot 2 $$ distinct outcomes.

For the second part your reasoning is not correct. First of all it assumes that all the previous throws are distinct which is not required (as the question stands now) so you missed the outcome $$ 1\ \ 1\ \ 2 \ \ 1\ \ 2 $$ for example.

You could reason instead as follows

$$ \#\text{outcomes with last throw is not unique}=\#\text{all outcomes}-\#\text{outcome with last throw is unique} $$ where $\#$ stands for "number of".

All possible outcomes are easy to enumerate, I put it here but try to find it yourself before you peek (you can peek by mouseovering the yellow part below)

$6^5$ since all $5$ throws can take any of the $6$ possible values

The number of outcomes where the last throw is uniqe is a bit trickier. You could argue that the last throw is going to be some value it actually can be all $6$ possibilities and this cannot be thrown before so you have one less possibility in each of the first $4$ throws

$6\cdot 5^4$ since as we said you have one less possibility with each previous throw

Putting these together you arrive at

$6^5-6\cdot 5^4$

Hope this helped

Probability – Average Number of Random Real Numbers for Sum of Squares to Exceed 1

Simulation in R suggests something near $3.926$ is reasonable.

set.seed(2023)
squaresto1 <- function(power=2, target=1, maxcases=100){
  cs <- cumsum(runif(maxcases)^power) 
  min(which(cs > target))
  }
sims <- replicate(10^6, squaresto1(power=2, target=1))
mean(sims)
# 3.926359

Ways of thinking about this include:

You can extend the uniform distribution on $[0,1]$ to $[-1,1]$ without affecting the distribution of absolute values or squares
This becomes a uniform distribution in the hypercube $[-1,1]^n$ when you take $n$ points
The (square root of) the sum of squares is less than $1$ for points in the $n$-ball radius $1$
The probability the first $n$ squares add up to less than $1$ is the proportion of a hypercube contained in the the largest $n$-ball that fits inside it.
The volume of the $n$-ball is $\frac{\pi^{n/2}}{\Gamma\left(\frac n2+1\right)}$ while the volume of the hypercube is $2^n$
You can find the expected number needed to reach $1$ by summing over $n$ the probabilities that more are needed.

So your expression is $\sum\limits_{n=0}^\infty \dfrac{\pi^{n/2}}{2^n \,\Gamma\left(\frac n2+1\right)}$. This does have a simplified form if you use the CDF of a normal distribution or the error function, namely $$2\, e^{\pi/4}\, \Phi\left(\sqrt{\frac \pi 2}\right) \approx 3.92577.$$ As a check:

n <- 0:100
sum(pi^(n/2) / (2^n * gamma(1+n/2)))
# 3.925771

2 * exp(pi/4) * pnorm(sqrt(pi/2))
# 3.925771

Best Answer

Related Solutions

[Math] A die is rolled 5 times. How many outcomes will result in 5 different numbers? How many outcomes will have the 5th number equal to an earlier number

Probability – Average Number of Random Real Numbers for Sum of Squares to Exceed 1

Related Question