Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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$.

share|improve this answer
    
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 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 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 at 19:09
    
Thank you for this. Is there are clean asymptotic expression for the variance? –  eleanora Jul 2 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 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.

share|improve this answer

$$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}$.

share|improve this answer
1  
Uniform, yes, but discrete. –  Did Jun 30 at 18:42
    
Is there a clean asymptotic expression for the mean and variance? –  eleanora Jul 1 at 6:51
1  
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 at 8:48
    

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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