# Median of a uniform multinomial variable

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.

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.
• 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? – R B Apr 27 '16 at 14:12
• @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. – zhoraster Apr 27 '16 at 17:39