Mathematical expectation of minimum of k random variables with fixed sum n

Question

We have $n$ independent identically distributed random variables $X_1$, $X_2$, ..., $X_N$, $X_i=j$ with probability $1/k$ for $j=1, 2, ... k$. Let $Y_j$ be a number of random variables $X_i$, which are equal to $j$, i.e. $Y_j=|i:X_i=j|$. I'm interested in mathematical expectation of $\min(Y_1, Y_2, ..., Y_k)$ as $n\to\infty$. My hypothesis is as follows $$ {\mathbf E} \min(Y_1, Y_2, ..., Y_k)=\frac{n}{k}-c_k\sqrt{\frac{n}{k}}+o\left(\sqrt{\frac{n}{k}}\right),\quad n\to\infty. $$ I proved that formula for $k=2$ and found $c_2=\frac{1}{\sqrt{\pi}}$. Computer calculation shows that $c_3\approx 0.84$, $c_4\approx 1.02$.

Answer 1

Your formula is correct.

Let $Y^{(n)}_j:=\#\{i\leq n: X_i=j\}$. Then, $Y^{(n)}=(Y_1^{(n)},\dots,Y_k^{(n)})$ can be viewed as a sum of $k$-dimensional i. i. d. random variables, with terms uniform among $(1,0,\dots,0)$, $(0,1,\dots,0)$, .... Note that $$\mathbb{E}Y^{(n)}=\left(\frac{n}{k},\dots,\frac{n}{k}\right),$$ and by Central Limit theorem, $\frac{1}{\sqrt{n}}(Y^{(n)}-\mathbb{E}Y^{(n)})$ converges in distribution to the $k$-dimensional Gaussian $\mathcal{N}(0,\Sigma)$ with covariance matrix given by $\Sigma_{ii}=\frac{1}{k}-\frac{1}{k^2}$, $\Sigma_{ij}=-\frac{1}{k^2}$ for $i\neq j$.

The minimum of the coordinates is a continuous function on $\mathbb{R}^k$. If it were bounded, we could conclude straight away that $$ \frac{1}{\sqrt{n}}\left(\min_{1\leq i\leq k}\mathbb{E}Y^{(n)}_i-\frac{n}{k}\right)=\mathbb{E}\min_{1\leq i\leq k}\left[\frac{1}{\sqrt{n}}(Y^{(n)}-\mathbb{E}Y^{(n)})\right]_i\to \mathbb{E}\min_{1\leq i\leq k}[\mathcal{N}(0,\Sigma)]_i, $$ which is equivalent to your formula. To complete the proof, you can, for example, truncate the minimum of the coordinates to make it bounded, and then apply Chernoff's bounds to show that the probability to end up in a truncated part is exponentially small as the cut-off goes to infinity, uniformly in $n$.