I am looking to prove a tight concentration on the expected number of blue-colored balls in a sample of $n$ balls chosen randomly from a pool of $b$ blue balls and $g$ green balls.

Namely, after sampling $n$ balls without replacement from a collection of $b$ blue balls and $g$ green balls, prove that the number of blue balls in the sample is tightly concentrated around the expected value $\frac{nb}{(b+g)}$. In other words, if $X$ is the number of blue balls in the sample find an upper bound on:

$$P(|X-E(X)| \geq \epsilon) \leq ???$$

I thought about using Chernoff bounds but that can't be done since the sampling is done without replacement. Any other way of doing it?

  • $\begingroup$ Based on other recent posts, I think you are looking for Azuma-Hoeffding $\endgroup$ Mar 6 '20 at 4:52

b Blue and g Green balls are mixed. From this collection probability of picking a particular ball is $1/(b+g)$ and probability of picking a blue ball = probability of picking $b$ particular balls.

So probability of picking a blue ball from the collection = $b/(b+g)$

Similarly, proabbilty of picking a green ball = $g/(b+g)$

The n balls are picked at random. When you pick something at random, the probability of something being present among the picked items = probability of it being picked

Probable number of blue balls = (Total number of balls) x (Probability of picking a blue ball)

= $(n) (b/(b+g))$

= $nb/(b+g)$

Assumptions :

  1. n is less than (b+g)

  2. $nb/(b+g)$ is an integer

But assumption 2 can be relaxed if we are allowed to round off the answer

  • $\begingroup$ Thank you! But I was actually more concerned with finding a tight concentration around the expected value, whose calculation is quite elementary. I edited the question to reflect that. $\endgroup$ Mar 6 '20 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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