I have the following problem in my work, which reduces after some modelisation to the following:
Consider random values $(X_t)_t\ge 1$ iid uniform over $\{1,.., h\}$.
I am interested in the random variable $$ T=\min_{1\le k\le h} cardinal \left\{ i\in\{1,..,t_{max}\} : X_t=k \right\}$$
The intuition is that, for a given value of $t_{max}$, the $X_i$ will be well distributed enough should $T$ be small.
The problem is: determine $t$ such as $P(T>t) < \epsilon$. I'm ok with an approximate formula.
Here is what I got to:
- trivial bounds $t_{max}/h \le T \le t_{max}$
- for $h=2$: the problem reduces to the following: given $X_i$ iid with law Bernoulli with $p=1/2$,
$$ P(T>t) = P\left(\left| \sum_{t=1}^{t_{max}} X_i - \frac{t_{max}}2 \right| > \delta \right), \delta=t-\frac {t_{max}}2 $$
From the central limit theorem, I can deduce the approximations $$ P(T>t) \approx P(\left| N(0,1) \right|> 2 \sqrt {t_{max}} \delta ) \\ t \approx \frac{t_{max}}2 + \sqrt{t_{max}} \frac{\alpha_{\epsilon/2} }2 $$
where $\alpha_\epsilon$ is read from a table.
Any idea how to generalize that for $h>2$?