# Distribution of the maximum of $n$ uniform random variables

If $U_1,\dots, U_n$ are independent uniform random variables with range $\{1,\dots,N\}$, what can be said about the distribution of $Z=\max U_i$? I am interested in the case where $n$ is large and $N\geq n$.

In particular, I am interested in tail bounds for $Z$. That is how tightly concentrated it is around its mean $\mathbb{E}(Z)$.

-

It has not been explicitly stated that the $U_i$ are independent. We assume they are.

Let $1\le z\le N$. The probability that $Z\le z$ is the probability all the $U_i$ are $\le z$. This is $\left(\frac{z}{N}\right)^n$. So the expressions for (left and right) tail probabilities are quite simple.

The distribution function of $Z$ readily follows. We have $Z=z$ iff $Z\le z$ and it is not the case that $Z\le z-1$. This has probability $\left(\frac{z}{N}\right)^n-\left(\frac{z-1}{N}\right)^n$.

Added: In comments, we are asked about asymptotic estimates for mean and variance. Let $F(z)=(z/N)^n$. Then the mean is $$1(F(1)-F(0))+2(F(2)-F(1))+3(F(3)-F(2))+\cdots +N(F(N)-F(N-1)).$$ There is a lot of cancellation. Since $F(0)=0$, we find that $E(Z)=F(1)+F(2)+F(3)+\cdots +F(N)$. It follows that $$E(Z)=\frac{1^n+2^n+3^n +\cdots+N^n}{N^n}.$$ While, for fixed $n$, complicated closed forms are available for the numerator above, it might be simplest to use estimates. A first estimate is to replace the random variable $Z$ by the random variable $W$, which has continuous uniform distribution on $[0,N]$. The probability that $W\le w$ is, for $0\le w\le N$, equal to $\frac{w^n}{N^n}$. The density function is $\frac{nw^{n-1}}{N^n}$ on our interval, so the mean of $W$ is $\frac{nN}{n+1}$.

The variance of the continuous analogue is a useful approximation to the variance of $Z$. We have $E(W^2)=\frac{nN^2}{n+2}$, and $\text{Var}(W)=E(W^2)-(E(W))^2$.

-
You need to assume i.i.d. $U_i\sim(1,N)$ (also identically distributed) for your last step , the uniform distribution is in general $U_i\sim(a,b)$..? – emcor Jun 30 '14 at 18:45
$z^n$ is not a probability since $1\leq z\leq N$, you mean $(z/N)$ and $(z/N)^n$ respectively. – emcor Jun 30 '14 at 18:53
Thank you. The fact that $1,2,\dots,N$ are equally likely is built into the statement of the problem. The $z^n$ stuff was of course a (bad) mistake. – André Nicolas Jun 30 '14 at 19:09
Thank you for this. Is there are clean asymptotic expression for the variance? – Lembik Jul 2 '14 at 7:16
I will think about it, but definitely not before tomorrow. Time to sleep. Probably would be a good idea to replace discrete uniform by continuous for asymptotics. – André Nicolas Jul 2 '14 at 7:18

If you are interested in results for large $n$ but with $n\le N,$ I would first consider the variable $Z/N.$ This converges in distribution as $N\to \infty.$ Because: Let $X_n$ be the maximum of $n$ iid Uniform$(0,1)$ so $P(X_n \le x)=x^n.$ Then $P(Z/N\le x)=P(Z\le Nx)=\left(\lfloor Nx \rfloor /N \right)^u\to x^n.$

Now that we are in the Uniform(0,1) case, it is easy to compute the mean and standard deviation of $X_n:$ $$\mu_n=\frac n{n+1}, \sigma_n=\frac 1{n+1}\sqrt\frac n{n+2}.$$

Now we can show $(X_n-\mu_n)/\sigma_n$ converges in distribution:
$$P[(X_n-\mu_n)/\sigma_n \le x] =(x\sigma_n+\mu_n)^n =\left( 1+\frac {x\sqrt {(n/(n+2)} -1}{n+1} \right)^n\to e^{x-1}$$ as $n\to \infty$ for $x \le 1.$ So for an asymptotic result, consider the probability that $X_n$ is between $\mu_n-\sigma_n$ and $\mu_n+\sigma_n$ This can be approximated for any $n$ sufficiently large as $e^{1-1} - e^{-1-1}=0.86$

We can also use other sequences of norming constants. Since $X_n \le 1$ and converges to it and $\sigma_n \sim 1/n$ we can try $n(X_n-1).$ It is easy to show this converges to $e^x$ for $x \le 0.$

The study of the distribution of the max of iid r.v. is called Extreme Value Theory. It models extreme events like a 100-year flood. It is also used in Reliability Theory since the lifetime of $n$ components connected in parallel is given by the max.

-

$$F_Z(x)=P(\max U_i\leq x)=P(U_1,\ldots,U_N\leq x)=F_U(U_1\leq x)\cdots F_U(U_N\leq x)=F_U(x)^n$$

where for the last two steps I assumed i.i.d. for the $U_i$'s, and the discrete Uniform CDF given by

$$F_U(x; 1,N)= \begin{cases} 0 & \text{, }x < 1 \\[8pt] \frac{ x} {N} & \text{, }1 \le x < N \\[8pt] 1 & \text{, }x \ge N \end{cases}$$ , $x\in\mathbb{N}$.

-
Uniform, yes, but discrete. – Did Jun 30 '14 at 18:42
Is there a clean asymptotic expression for the mean and variance? – Lembik Jul 1 '14 at 6:51
The mean of the maximum is $N-\dfrac{N-1}{n+1}$, you can check that it becomes the uniform mean when $n=1$. – emcor Jul 1 '14 at 8:48
statlect.com/subon2/dsconv1.htm – emcor Jul 1 '14 at 8:59