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) - \dots -F(N-1) + NF(N)$$
And recalling the expression for $F(z)$ we find:
$$E[Z] = N - (\frac{N-1}{N})^n - \dots - (\frac{1}{N})^n$$
Which converged to $N$ as n goes towards infinity, showing that $max(U_i)$ is an unbiased estimator for N
You will notice that unlike its continuous counterpart where $X \sim unif[0 , \theta]$, $max(X_i)$ is not unbiased, and you can find that $\frac{n+1}{n}[max(X_i)]$ is unbiased for a sample size of n. Indeed, intuitively this makes sense, given that in the continuous case, $max(X_i)$ does not reach $\theta$ with probability 1, hence needs a nudge upwards. In the discrete case, $max(U_i)$ reaches N with probability 1, hence will not need some nudge to reach the value it is attempting to estimate.
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}$.
André, the formula you give for the expectation of $Z$ is wrong. I agree on $E(Z)$ being given by $$ 1(F(1)−F(0))+2(F(2)−F(1))+3(F(3)−F(2))+\cdots+N(F(N)−F(N−1)) $$ But cancellations do not yield the ratio $$ E(Z)=\frac{1^n+2^n+3^n+\cdots+N^n}{N^n} $$ Instead, the correct expression is $$ E(Z) = N- \frac{1^n+2^n+\cdots+(N-1)^n}{N^n} $$ Obviously, those two expressions are not the same
