2
$\begingroup$

Given a set of $n$ balls where $\displaystyle\frac{n}{3}$ balls are blue and $\displaystyle\frac{2n}{3}$ balls are red, we throw each one, at random, into one of $k$ bins with uniform probability. After throwing all $n$ balls, bin $k$ is said to contain $n_k$ balls ($R_k$ being red and $B_k$ being blue).

Define a new variable for each bin, $M_k$, that is $1$ if red balls compose the majority of balls in bin $k$, and $0$ otherwise. Another way to think of this is $M_k = 1$ if bin $k$ has more red balls than blue balls, and $0$ otherwise.

Define $A$ to be the sum of the number of balls in each bin ($n_k$) if $M_k = 1$. i.e: $A = \sum\limits_{i=0}^k M_i n_i$

What is the upper bound of $A$?

$\ldots\ldots\ldots\ldots$

So far what I have is a hint that a clever solution using Markov's inequality exists, but I'm failing to see it. What I've worked out so far is the following (though perhaps I'm mistaken somewhere): $\mathop{E}(n_k) = \frac{n}{k}$ $\mathop{E}(R_k) = \frac{\mathop{E}(n_k)}{3} = \frac{n}{3k}$ And I believe the Markov solution follows something along the lines of: $\mathcal P (R_k > \frac{n_k}{2}) = \frac{2\mathop{E}(R_k)}{n_k} = \frac{2nk}{3kn} = \frac{2}{3}$ Meaning the final solution I'm getting, using union bound: $\mathcal P (\bigcup\limits_{i=0}^k(R_k > \frac{n_k}{2})) = k\frac{2}{3}$ In other words...this should be the maximum value of $A$...

Which doesn't entirely make sense to me. So I ask you, stackexchange...Am I heading down the right path? Have I overlooked something extremely important? Or am I completely lost? Any help on the matter would be greatly appreciated.

  • 0
    Your last step can’t possibly be right: for k>1 it gives you a probability greater than $1$.2012-11-20

1 Answers 1

2

If you want upper bounds, you should ignore expectation values. The upper bound on $A$ is $n$. Just put all the balls in one bin. Or just group the balls into batches of 2 red and 1 blue and put each batch into any bin. All the balls will be in bins with a clear majority of red. There are more configurations that achieve this limit. If there aren't too many bins, most configurations will have $A=n$.