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 [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 


*

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

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

*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."
 A: 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.
