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

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

1 Answer

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

• Are there closed forms for $c_k$, $k\ge3$? Jan 23, 2017 at 16:19
• I doubt that; this question and the references therein seems relevant: mathoverflow.net/q/63490/56624 Jan 23, 2017 at 16:32
• There are also closed-form formulas for k=3,4,5. For k=3 it is (3/2)/sqrt(pi). For k=4 you can find it at talkstats.com/showthread.php/…. For k=5 it's similar to k=4 and I think given explicitly in David & Nagaraja's book on order statistics. But already for k=4 the formula is messy and not suggestive of any generalizations. Jan 23, 2017 at 19:49