Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Your last step can’t possibly be right: for $k>1$ it gives you a probability greater than $1$. –  Brian M. Scott Nov 20 '12 at 6:22

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

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.