# Distribution for the lowest value in a list of values selected uniformly at random

If I select N values at random from the discrete uniform distribution on the integers [1, 2, ..., M] what is the probability distribution for the smallest value?

I'm interested in the discrete probability distribution, but also in a continuous approximation for it (so I could sample randomly from it).

I guess in a sense it's something like the inverse of the german tank problem?

Let $P(i)$ the probability function of the distribution of the smallest value.

$$P(i)=P(\text{the smallest value = i})=$$ $$=P(\text{no value < i }\,\cap\,\text{at least one value = i} )=$$ $$=P(\text{all values} \ge i)·P(\text{at least one value = i | all values} \ge i)$$

You haven't mentioned it, but if we can assume that the $N$ values are chosen independently and with replacement, $P(\text{all values} \ge i)$ and $P(\text{at least one value = i | all values} \ge i)$ can be computed using just the binomial distribution.

$M-i+1$ of the $M$ possible values are larger or equal than $i$, then:

$$P(\text{all values} \ge i)=\bigg(\frac{M-i+1}{M}\bigg)^N$$

And among the $M-i+1$ values larger or equal than $i$, $M-i$ are larger than $i$, then:

$$P(\text{at least one value = i | all values} \ge i)=$$ $$=1-P(\text{all values > i | all values} \ge i)=$$ $$=1-\bigg(\frac{M-i}{M-i+1}\bigg)^N$$

Then:

$$P(i)=P(\text{the smallest value = i})=$$ $$=\bigg(\frac{M-i+1}{M}\bigg)^N·\bigg(1-\bigg(\frac{M-i}{M-i+1}\bigg)^N\bigg)$$

And just an example:

> N<-6
> M<-10
> i<-1:M
> pti<-((M-i+1)/M)^N
> pai<-1-((M-i)/(M-i+1))^N
> (pr<-pti*pai)
[1] 0.468559 0.269297 0.144495 0.070993 0.031031 0.011529 0.003367 0.000665 0.000063 0.000001


That is, if you randomly chose 6 numbers with replacement from $\{1,2,3,4,5,6,7,8,9,10\}$, the probability of the smallest being 1 is 48.86%, of being 2 is 26.92%, and so.

• It needs to be noted that this is a solution for selection with replacement: values that are selected may include duplicates. It would be of interest to have a solution to the more difficult part of the question: what is an efficient way to generate data from this distribution? – whuber Jul 7 '17 at 19:17
• "with replacement" added. Without replacement, the solution would be similar but using factorials instead of exponentiation. @whuber Thanks for pointing. – Pere Jul 7 '17 at 19:29
• For this "with replacement" case, a fast way to generate from it is as follows: If $U$ is uniform then $M-\lfloor M U^{1/N}\rfloor$ should have the required distribution. In R on my laptop generating a million values this way (x = m-trunc(m*runif(nsim)^(1/n)) with m=6 and n=3) seems to take less than a second. (This essentially generates the maximum via the inverse-cdf method and flips it end-for-end to get the distribution of the minimum. I expect @whuber had already thought of this approach or something quite similar to it. ) – Glen_b Jul 9 '17 at 12:08