Concentration on number of blue balls among n balls uniformly sampled among b blue and g green balls?

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?

• Based on other recent posts, I think you are looking for Azuma-Hoeffding 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

• 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. Mar 6 '20 at 16:59