6
$\begingroup$

Assume you draw a uniformly distributed random number between 0 and 1 n times. How would one go about calculating the expected minimum number drawn after n trials?

In addition, how would one go about calculating a confidence interval to state that the minimum number drawn is in the interval [a,b] with m% confidence?

$\endgroup$
7
$\begingroup$

You are looking for order statistics. The wiki indicates that the distribution of the minimum draw from a uniform distribution between 0 and 1 after $n$ trials is a beta distribution (I have not checked it for correctness which you should probably do.). Specifically, let $U_{(1)}$ be the minimum order statistic. Then:

$U_{(1)} \sim B(1,n)$

Therefore, the mean is $\frac{1}{1+n}$. You can use the beta distribution to identify $a$ and $b$ such that

$Prob(a \le U_{(1)} \le b) = 0.95$.

By the way, the use of the term confidence interval is not appropriate in this context as you are not performing inference.

Update

Calculating $a$ and $b$ such that $Prob(a \le U_{(1)} \le b) = 0.95$ is not straightforward. There are several possible ways in which you can calculate $a$ and $b$. One approach is to center the interval around the mean. In this approach, you would set:

$a = \mu - \delta$ and

$b = \mu + \delta$

where

$\mu = \frac{1}{1+n}$.

You would then calculate $\delta$ such that the required probability is 0.95. Do note that under this approach you may not be able to identify a symmetric interval around the mean for high $n$ but this is just my hunch.

$\endgroup$
3
$\begingroup$

As Srikant suggests, you need to look at order statistics.

To add to Srikant's answer, you can simulate this process easily in R:

n = 10
N = 1000;sims = numeric(N)
for(i in 1:N)
  sims[i] = min(runif(n))

hist(sims, freq=FALSE)
x = seq(0,1,0.01)
lines(x, dbeta(x, 1, n), col=2)

To get

alt text http://img441.imageshack.us/img441/6826/tmpe.jpg


Slight digression

This question is related to one of my favourite statistics problems, the German tank problem. This problem is about the maximum of uniform distributions, and can be summarised as:

Suppose one is an Allied intelligence analyst during World War II, and one has some serial numbers of captured German tanks. Further, assume that the tanks are numbered sequentially from 1 to N. How does one estimate the total number of tanks?

Taken from wikipedia

Check out the wikipedia page for more details.

$\endgroup$
1
$\begingroup$

following @Srikant, one can compute the CDF of the beta distribution, and find conditions on $a, b$ such that the interval $[a,b]$ contains the minimum of $n$ draws of a uniform with 95% probability. The condition is: $(1-a)^n - (1-b)^n = 0.95$. One attractive choice would then be the interval $[0,1 - 0.05^{1/n}]$. This is also the smallest interval with the desired property.

$\endgroup$

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.