The probability of choosing items more than a specified number of times I'm working on a programming (Python) project at work, and I'm facing a problem of testing a stochastic function.
The function could have $3$ different outcomes (that I know in advance, say $\{a,b,c\}$) with uniform probability, and I want to check whether the distribution is really uniform.
I cannot run the function MANY times because of runtime considerations, so I'm limited to a few hundred runs.
As a first attempt, I created a test that runs the functions $300$ times and checks whether each outcome is achieved more than $75$ times. 
However, I don't know how to calculate the probability that this test would fail.
Stating the question in mathematical terms:
There are $300$ trials. In each trial one of three items $\{a,b,c\}$ is drawn with a probability of $1/3$. What is the probability that each item was drawn more than $75$ times?
In general, I would like to know that probability for arbitrary numbers, so:
There are $n$ trials. In each trial one of $m$ items $\{a_1, a_2, ... a_m\}$ is drawn with a probability of $1/m$. What is the probability that each item was drawn more than $k$ times (where $k \times m < n$)?
 A: To evaluate the probability of rare events, one can rely on large deviations theory. Whole treatises exist on the subject hence let me explain the parts of the theory relevant to your problem in the first case (300 draws, 3 possible outcomes, at least 75 draws from each outcome).
The object of interest is the empirical measure $L_n$ of a sample of size $n$, that is, for every possible result $x$, $L_n(x)$ is the (random) number of draws yielding the result $x$. Let $u$ denote the uniform measure on the set of results. When the draws are independent, the law of large numbers guarantees that $L_n\to u$ almost surely, that is, $L_n(x)\to\frac13$ for each $x$ in $\{a,b,c\}$.
Large deviations theory allows to estimate the probability that $L_n$ differs significantly from $u$, when $n\to\infty$. More specifically, there exists a functional $I$ such that $P[L_n\in A]\propto\mathrm e^{-nI(A)}$ for every suitable set $A$ of probability measures on $\{a,b,c\}$. (Experts know that $\propto$ means in fact that $\frac1n$ times the logarithm of the LHS converges to $-I(A)$, and that even that is not really true since topology on the space of measures comes into play and convergence to $-I(A)$ should be replaced by bounds on the limsup and liminf involving $-I$ applied to the closure and to the interior of $A$.)
Anyway... what is perhaps more interesting is that $I(A)=\inf\{I(m)\mid m\in A\}$ for some functional $I$ defined on the space of measures and that, in your context, $I(m)=H(m\mid u)$, where $H$, called the relative entropy, is defined by
$$
H(m\mid u)=-\sum_x\log\left(\frac{m(x)}{u(x)}\right)\,u(x).
$$
To estimate the probability of the (nearly 100% certain) event that $L_n(x)\geqslant tu(x)$ for every $x$, with $t\lt1$, one considers the (rare) event $A_t=\{m\mid\exists x,m(x)\leqslant tu(x)\}$. It is relatively easy to show that $I(A_t)$ is realized for each of the three measures $m_t$ such that $m_t(x)=tu(x)$ for some $x$ and $m_t$ is uniform on the rest of the space. Thus,
$$
P[L_n\in A_t]\approx\mathrm e^{-nH(m_t\mid u)}.
$$
Unless I am mistaken, for $n=300$ and $t=\frac34$, numerically,
$$
\mathrm e^{-H(m_{3/4}\mid u)}=3^{5/3}\cdot2^{-8/3},\qquad 
P[L_{300}\in A_{3/4}]\approx3^{500}\cdot2^{-800}\approx.00545.
$$
Thus, the probability that each item amongst three was drawn at least 75 times amongst 300 is of the order of $99.5\%$.
A final word of caution might be needed here: the order of magnitude is relevant, the precise value not so much.
This can be adapted to any alphabet of any size $m$ and to cases when the probable limit is not the uniform measure.
A: You can use pyhon for the combinatorical calculations too. This program gives you the precise probability: http://pastebin.com/NSyWzbEZ
