Let $k\in\mathbb N^+$ be a positive integer.

Consider a set of i.i.d. random variables $X_1,X_2,\ldots, X_n$, each of which is distributed uniformly over $\{1,2,\ldots,2k+1\}$.

For $i\in \{1,2,\ldots,2k+1\}$, let $Y_i\triangleq|\{j\mid X_j=i\}|$ denote the number of variables with the value $i$. Notice that each $Y_i$ is distributed $Bin\left(n,p\right)$, for $p\triangleq\frac{1}{2k+1}$.

Finally, let $Z\triangleq \text{Median}(\{Y_1,Y_2,\ldots,Y_{2k+1}\})$ be the median of the $Y_i$ variables.

An answer to this question in math.se indicates that $\mathbb E(Z)=\frac{n}{2k+1}-O(1)\approx \mathbb E(Y_i)$.

To me, it'll be very interesting to understand other properties of $Z$, and mainly:

What is $Var(Z)$? is it $o(np(1-p))$? i.e., is the variance of the median asymptotically smaller than $Var(Y_i)=np(1-p)$? by how much?

The special case of $k=1$, where we have only 3 $Y_i$ variables is also interesting for me.


Here are some heuristic thoughts. They maybe highly imprecise, but hopefully helpful.

The variables $Y_i$, of course, are not independent. But they are approximately independent in the following sense. Their distribution is equal to the conditional distribution of independent $\mathrm{Pois}(np)$ random variables $Z_i$, $i=1,\dots,2k+1$ given that $Z = Z_1 + \dots + Z_{2k+1} = n$. However, by the strong law of large numbers, $Z \approx n$; and, thinking asymptotically, the conditional distribution does not change a lot when moving from $n$ to nearby values.

Thus, the problem boils down to identifying the median of a sample of iid random variables, which are moreover close to $N(np,np)$. That said, the distribution of median is approximately $\sqrt{np}\Phi^{-1} (M)+np$, where $\Phi$ is the standard normal cdf, and $M$ is the median of a sample of $2k+1$ iid $U[0,1]$ variables, so it has the $\beta(k+1,k+1)$ distribution. Therefore, the mean should be close to $\Phi^{-1}(\mathsf E[M]) + np = \Phi^{-1}(1/2) + np = np$, and the variance, to $$np(\Phi^{-1}(1/2)')^2 \mathsf{V}(M) = \frac{\pi np}{2 (2k+3)}.$$

EDIT In fact, the variance is very imprecise, as it is reduced by conditioning. Still, I believe that the order $n$ is correct.

  • $\begingroup$ Thanks for the answer. Am I correct to say that this only holds for $n\gg k$, as otherwise the $Y_i$'s are far from being independent? $\endgroup$
    – R B
    Apr 27 '16 at 14:12
  • $\begingroup$ @RB, yes. I thought that $k$ is fixed and we look at $n\to\infty$. It should work for $k=o(\sqrt{n})$ as well, but beyond that some other methods are needed. $\endgroup$
    – zhoraster
    Apr 27 '16 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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