# Lower bound on the tail of the hypergeometric distribution

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 ) 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."

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.