1
$\begingroup$

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?

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – whuber♦ Jul 7 '17 at 19:17
  • 1
    $\begingroup$ "with replacement" added. Without replacement, the solution would be similar but using factorials instead of exponentiation. @whuber Thanks for pointing. $\endgroup$ – Pere Jul 7 '17 at 19:29
  • $\begingroup$ 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. ) $\endgroup$ – Glen_b Jul 9 '17 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.