I asked a similar question a while back. I have reformulated the question. My original intention was to ask this question.

Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are blue. We draw $n$ balls from the urn (without replacement) and let $H(n,N,M)$ denotes the number of red balls in the sample.

We have $Pr[H(n,N,M) = k] = \frac{\binom{M}{k}\binom{N-M}{n-k}}{\binom{N}{n}}$ and $\mathbb{E}[H(n,N,M)] = n\frac{M}{N}$.

Hypergeometric distribution enjoys centain concentration property. Formally for any $\epsilon>0$

$$Pr[H(n,N,M) \geq n\frac{M}{N} + \epsilon n] \leq \exp(-2\epsilon^2 n)$$ and $$Pr[H(n,N,M) \leq n\frac{M}{N} - \epsilon n] \leq \exp(-2\epsilon^2 n)$$

See, for example The tail of the hypergeometric distribution for an elementary proof.

Furthermore from Centering Sequences with Bounded Differences, we also have the following multiplicative version (for $0<\epsilon\leq 1$)

$$Pr\big[H(n,N,M) \geq (1+\epsilon)]\mathbb{E}[H(n,N,M)]\big] \leq \exp\big(-\frac{1}{3}\epsilon^2\mathbb{E}[H(n,N,M)]\big)$$ and $$Pr\big[H(n,N,M) \leq (1-\epsilon)]\mathbb{E}[H(n,N,M)]\big] \leq \exp\big(-\frac{1}{2}\epsilon^2\mathbb{E}[H(n,N,M)]\big)$$

Now suppose we have $\mu_L \leq \mathbb{E}[H(n,N,M)] \leq \mu_H$. My question is whether the following are true.

$$Pr[H(n,N,M) \geq \mu_H + \epsilon n] \leq \exp(-2\epsilon^2 n)$$
$$Pr[H(n,N,M) \leq \mu_L - \epsilon n] \leq \exp(-2\epsilon^2 n)$$ $$Pr\big[H(n,N,M) \geq (1+\epsilon)\mu_H\big] \leq \exp\big(-\frac{1}{3}\epsilon^2\mu_H\big)$$ $$Pr\big[H(n,N,M) \leq (1-\epsilon)\mu_L\big] \leq \exp\big(-\frac{1}{2}\epsilon^2\mu_L\big)$$

Note that this is true (though not obvious) for standard Chernoff–Hoeffding Bounds, where we are dealing with sum of independent random variables. This is stated as Exercise 1.1 in Concentration of Measure for the Analysis of Randomized Algorithms. It is hinted there this follows from the following statement, which can be proved using coupling technique.

Let $X_1,\cdots,X_n$ be independent random variables distributed in $[0,1]$ with $\mathbb{E}X_i = p_i \text{for each } i\in [n]$. Let $Y_1,\cdots,Y_n$ and $Z_1,\cdots, Z_n$ be independent random variables with $\mathbb{E}Y_i=q_i$ and $\mathbb{E}Z_i = r_i$ for each $i\in [n]$. Now suppose $q_i\leq p_i\leq r_i$ for each $i\in [n]$ and define $X = \sum_i X_i$, $Y=\sum_i Y_i$ and $Z=\sum_i Z_i$. Then for any $t$ $$Pr[X > t]\leq Pr[Z>t]$$ and $$Pr[X<t] \leq Pr[Y<t]$$.

Clearly $H(n,N,M)$ is not the sum of independent random variables. I am still trying to understand this coupling argument and whether this can be extended to hypergeometric random variable as well.

The following argument is trivial and both $\mu_L$ and $\mu_H$ appears.

$$Pr\big[X\leq (1+\epsilon)\mu_H\big] \geq 1-\exp(-\frac{\epsilon^2\mu_L}{3})$$


Your Answer

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

Browse other questions tagged or ask your own question.