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 cutoff goes to infinity, uniformly in $n$.

$\begingroup$ Are there closed forms for $c_k$, $k\ge3$? $\endgroup$– WolfgangJan 23, 2017 at 16:19

$\begingroup$ I doubt that; this question and the references therein seems relevant: mathoverflow.net/q/63490/56624 $\endgroup$– Kostya_IJan 23, 2017 at 16:32

2$\begingroup$ There are also closedform 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. $\endgroup$– Matt F.Jan 23, 2017 at 19:49