What is the average minimum value in a set of 100 integers chosen at random uniformly and independently in the range 0-99 inclusive?

Question

Obviously the smallest possible value is 0, but 0 isn't guaranteed to be in the set. I'd assume that most of the time the minimum value would be either 0 or 1, which would make the average minimum be 0.5, but there are also the cases where there is a larger minimum. Of course, the higher the minimum for a specific set, the less likely it is for the set to be chosen, so I'd guess the actual average is a bit more than 0.5, maybe around 0.58. I'm just not sure how to find this value mathematically.

Answer 1

What is the average minimum value in a set of 100 integers chosen at random uniformly and independently in the range 0-99 inclusive?

For $n \in \{0,1,2\cdots,99\}$,
let $f(n)$ denote the probability that the minimum number selected is $n$.

Here it is assumed that the numbers are selected in accordance with the excerpted paragraph, at the start of this answer.

Then, the computation for the average minimum is

$$\sum_{n=0}^{99} n \times f(n). \tag1 $$

Therefore, the problem reduces to computing $f(n)$.

---

For $n \in \{0,1,2,\cdots,99\}$
Let $g(n)$ denote the probability that each of the selected numbers is $\geq n$.

Here $g(n)$ includes the cases where each of the numbers is strictly $> n$.

Then, for illustrative purposes

• $g(0) = 1$

• $\displaystyle g(99) = \left[\frac{1}{100}\right]^{100}.$

Then, you have that in general,

$$g(n) = \left[\frac{100 - n}{100}\right]^{100}.$$

Then,

• $f(99) = g(99)$.

• For $n \in \{0,1,2\cdots,98\} ~: ~f(n) = g(n) - g(n+1).$

---

$\underline{\text{Final Computation of (1) above}}$

$$\sum_{n=0}^{99} n \times f(n) = \left\{ ~\sum_{n = 0}^{98} \left[n \times [g(n) - g(n+1)\right] ~\right\} + \left[99 \times \left(\frac{1}{100}\right)^{100}\right]$$

$$= \left\{ ~\sum_{n = 0}^{98} \left[n \times \left(\frac{100 - n}{100}\right)^{100} - n \times \left(\frac{99 - n}{100}\right)^{100}\right] ~\right\} + \left[99 \times \left(\frac{1}{100}\right)^{100}\right]. \tag2 $$

(2) above can be simplified by algebraic manipulation, to

$$0 \times \left(\frac{100}{100}\right)^{100} + \sum_{n=1}^{99} \left(\frac{100 - n}{100}\right)^{100}. \tag3 $$

For me, part of the challenge of the problem is stretching my intuition around the expression in (3) above. In effect, each incremental probability computation of

$~\displaystyle \left(\frac{100 - n}{100}\right)^{100}$

adds $(+1)$ to the expected minimum.

Answer 2

Let $X$ denote this minimum value. The exact formula for its mean is $$E(X)=\sum_{k \ge 1} P(X \ge k)= \sum_{k =1}^{99} (1-\frac{k}{100})^{100}\,.$$ A good approximation is $$\sum_{k \ge 1} e^{-k}=\frac{1}{e-1}=0.5819\ldots\,.$$