4
$\begingroup$

Suppose there is a bag with $M$ white marbles and $N - M$ black marbles. Let $H(n, N, M)$ be a random variable which is number of white marbles in a draw, without replacement, of $n$ marbles from a bag.

It is known (see [1]) that $$ Pr\left[ \frac{H(n, N, M)}{n} \geq \frac{M}{N} + t\right] \leq e^{-2t^2 n} $$ and $$ Pr\left[ \frac{H(n, N, M)}{n} \leq \frac{M}{N} - t\right] \leq e^{-2t^2 n} $$

I am looking for a similar lower bound to the left hand side. Specifically a function $f(n, N, M, t)$ such that

  1. $Pr\left[ \frac{H(n, N, M)}{n} \geq \frac{M}{N} + t\right] \geq f(n, N, M, t)$

  2. $Pr\left[ \frac{H(n, N, M)}{n} \leq \frac{M}{N} - t\right] \geq f(n, N, M, t)$

  3. For all $\epsilon$ there are $k$ and $t^*$ such that $$ \frac{1}{2} - \epsilon < f(kn, kN, kM, t^*) $$

Note $\frac{H(n, N, M)}{n}$ is the fraction of balls from the sample which are white and $\frac{M}{N}$ is the expected value of $\frac{H(n, N, M)}{n}$. Let $T_t$ be the even that $$ \left|\frac{H(n, N, M)}{n} - Exp\left[\frac{H(n, N, M)}{n}\right]\right|\geq t. $$

Condition 3. can be thought of as saying,

"if we imagine the balls are infinitely divisible, then $$ \lim_{t \to 0} \Pr(T_t) = 1, $$ i.e. as $t$ goes to $0$ the probability of a sample being at least $t$ away from the expected value goes to 1."

$\endgroup$
2
$\begingroup$

It is known from this paper http://epubs.siam.org/doi/abs/10.1137/1127084?journalCode=tprbauV. of Vatutin and Mikhailov (1982) that every hypergeometric law is a convolution of Bernoulli laws, and that hence the (Berry-)Esseen theorem (for nonidentically distributed summands) applies. More precisely, if $F$ is the distribution function of the standardization of a hypergeometric law and if $G$ denotes the standard normal distribution function, then we have $$ \frac{1}{2\sqrt{1+12\sigma^2}} \,\ \le\,\ \|F-G\|^{}_\infty \,\ <\,\ \frac{0.5583}{\sigma}$$
with $\sigma$ denoting the standard deviation of the original hypergeometric law. Here, as indicated above, the right hand inequality is due to Vatutin and Mikhailov (1982), except that we have used a recent Berry-Esseen constant anounced by Irina Shevtsova, and the more elementary left hand inequality (showing that the right hand one is sharp up to a constant factor after taking the minimum with $1$) follows from an inequality of Paul L\'evy, see http://arxiv.org/abs/1404.7657 around display (17) for some details and appropriate references.

In your question, $\sigma$ is asymptotically proportional to $\sqrt{k}$ and hence you should get what you want.

| cite | improve this answer | |
$\endgroup$

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.