The proportion between distinct labels in a multiset and the total amount of labels

Say we have a (multi)set $\alpha$ of $n$ balls, each of them is labeled with a number in $\{1,\ldots,m\}$ (where $m<n$ ). Denote by $d$ the amount of distinct labels in $\alpha$. Is it true that there exists a constant $c$ such that for every $\alpha$ as such, if we uniformly select a subset of $\alpha$ of size $\sqrt{m}$, then with high(say $2/3$) probability (over the selected subset) the number of distinct labels in the subset we picked is not greater than $c\sqrt{d}$ (for every $m$) ?

-
What does it mean that a number is $O(\sqrt d)$ with high probability? Being $O(\sqrt d)$ is a property that pertains to some limit ($n\to\infty$? $m\to\infty$?), whereas the probability pertains to some particular case. Do you mean that there is a constant $c$ such that the probability that the number (not "amount") of distinct labels is greater than $c\sqrt d$ remains high as $m\to\infty$? –  joriki Oct 2 '11 at 9:11
@joriki Yes, that's exactly what I mean - I'll change it accordingly. Thanks. –  Tom Oct 2 '11 at 10:01

1 Answer

I wonder whether the question now says what you intended it to say; it seems strange to have two different variables for the number $d$ of actual labels and the number $m$ of potential labels that aren't actually used.

The answer is no. You can always choose $m=n-1$. For any given $d$, you can make $n$, and thus $m$, and thus $\sqrt m$, arbitrarily large by having an arbitrarily large number $k$ of instances of each label, resulting in $n=kd$. Thus, you can pick an arbitrarily large number $\sqrt m$ of balls out of a population where every one of a fixed number of $d$ distinct labels has the same probability, and the probability of picking anything other than a full set of $d$ distinct labels goes to zero as $k$ goes to infinity. Since $d$ cannot be bounded by $c\sqrt d$ with constant $c$, there is no such constant. (The fact that you're drawing without replacement only works in favour of the argument, since it increases the probability of drawing distinct labels.)

-
That is actually the "catch" I was looking for. I can see why the problem may sound rather queer as a combinatorial problem. But in fact it stems from a question in theoretical computer science, and in that context it makes much more sense. Thanks ! –  Tom Oct 2 '11 at 12:01