MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Consider the well known multinomial setting: there are L balls, thrown at random at n bins so that the probability that a ball falls in bin i is $p_i$, independent of the other balls (the $p_i$’s are all positive and sum to 1).

Let $X_i$ be the number of balls in the ith bin. It is straightforward to show that for any k distinct indices $i_1, i_2,\ldots, i_k$, the events $\lbrace X_{i_1} > 0\rbrace, \lbrace X_{i_2} > 0\rbrace,\ldots, \lbrace X_{i_k} > 0\rbrace$ are negatively dependent in the sense that

$P(X_{i_1} > 0, X_{i_2} > 0,\ldots, X_{i_k} > 0) < P(X_{i_1} > 0)P(X_{i_2} > 0)\ldots P(X_{i_k} > 0)$

The proof is by induction over k: for k = 2, the probability on the LHS is $1 – [(1 - p_{i_1})^L + (1 - p_{i_2})^L - (1 - p_{i_1} - p_{i_2})^L]$, and on the RHS it’s $[1 - (1 – p_{i_1})^L] [1 - (1 – p_{i_2})^L]$. Elementary manipulations show that the inequality holds, and the induction step is easily proven using the multiplication rule $P(A \cap B) = P(A)P(B | A)$.

This negative dependence is also intuitively clear: if we know that there is at least one ball in bin i, there is at least one ball that will surely not fall into bin j, so the probability of bin j being non-empty decreases.

So that was easy. However, for proving a certain bound in my research, I need to do something similar, but for random k indices: suppose that after the balls were thrown into the bins, somebody comes and chooses randomly k distinct bins (so that each set of k bins has the same probability to be chosen, namely, 1/(n choose k)). Let $i_1, i_2, \ldots, i_k$ be the chosen indices, and again, I need to show that the inequality (below the second paragraph above) holds.

I thought to repeat the outline of the previous proof, but had a problem with proving the k = 2 case (the induction step is no problem). To compute each of the sides of the inequality I conditioned on the choice of the two indices (law of total probability), but even though many terms got cancelled, I couldn’t prove the inequality.

I am quite confident that the inequality holds, both by intuition (basically the same argument as in the non-random indices case) and because of numerical calculations.

Any ideas what to do here? I’d be grateful for any help.

share|cite|improve this question

I'm a little confused - could you clarify why the inequality holding for any k distinct indices doesn't imply that it holds for k randomly chosen distinct indices?

share|cite|improve this answer
Well, maybe it does imply, but I don't know how to prove it. In general, one needs to be careful with statements of this type - see Simpson's paradox, for example. – Buchuck Sep 19 '11 at 17:31
The probability of choosing a given index set is independent of the values of the $X_i$s, so for example you have $Pr(X_1>0 | index\ set I\ is\ chosen)=Pr(X_1>0)$. So your inequality is unchanged when conditioned over choice of an index set. This is not just for uniform distribution of bin choices, but any distribution. The only important thing is that the person choosing the bins has not peeked into them. – Brendan McKay Sep 20 '11 at 3:41
Brendan McKay: The choice of the index set is indeed independent of the $X_i$'s, i.e., no peeking (I should have stated that in my original post). Thus, the equality you wrote indeed holds, but I cannot see how that proves the inequality. Could you please elaborate? Thanks in advance. – Buchuck Sep 20 '11 at 12:35

Apologies if this is too silly. As Brendan McKay pointed out, the important thing is that the bins are chosen without peeking into them. Here's an example showing that this condition is actually necessary: Suppose there are three bins and two balls, and $k=2$. After throwing the balls, let the two chosen bins be the two that have the same number of balls. Then one is empty precisely when the other one is.

share|cite|improve this answer

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.