Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$) ?

share|cite|improve this question
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. – User1234 Oct 2 '11 at 10:01
up vote 1 down vote accepted

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

share|cite|improve this answer
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 ! – User1234 Oct 2 '11 at 12:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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