Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid sample from $p$, and for any $i \in [N]$ let $n_T(i)$ be the number of times $i$ occurs in the sample, i.e $$ n_T(i) = \#\{t \in [T] \mid i_t = i\}. $$ Consider the random probability distribution $p_T$ on $[N]$ defined by $$ p_T(i) := \frac{1[n_T(i) \ge 1]}{N_T} = \frac{1}{N_T} \begin{cases} 1,&\mbox{ if }n_T(i) \ge 1,\\ 0,&\mbox{ otherwise,} \end{cases} $$ where $N_T := \#\{i \in [N] \mid n_T(i) \ge 1\}$.

Intuitively, it is clear that for any $i \in [N]$, we have $p_T(i) \to 1/N$ (in some sense) in the limit $T \to \infty$. An intuitive argument for this is that $N_T \to N$ a.s and $1[n_T(i) \ge 1] \to 1$ a.s.

**Question.** What is the rate of convergence of $p_T(i)$ to $1/N$ ? That is, I wish to obtain good upper-bounds for
$\mathbb P(|p_T(i) - 1/N| \ge \epsilon)$ as a function of $\epsilon$, $i$ (via $p(i)$), $T$, and $N$.

**N.B.:** To a lesser extent, I'm also interested in upper-bounding $\mathbb P(|N_T - N| \ge \epsilon N)$.

**Related:** https://math.stackexchange.com/q/4757006/168758

## Observations

- $\mathbb E\,[1[n_T(i) \ge 1] = \mathbb P(n_T(i) \ge 1) = 1-(1-p(i))^T \asymp 1-e^{-p(i)T}$