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

  • $\begingroup$ Are there closed forms for $c_k$, $k\ge3$? $\endgroup$
    – Wolfgang
    Jan 23, 2017 at 16:19
  • $\begingroup$ I doubt that; this question and the references therein seems relevant: mathoverflow.net/q/63490/56624 $\endgroup$
    – Kostya_I
    Jan 23, 2017 at 16:32
  • 2
    $\begingroup$ 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. $\endgroup$
    – user44143
    Jan 23, 2017 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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