Rate of convergence to uniform distribution

Question

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}$

Answer 1

Disclaimer. This is just a partial solution to the auxiliary problem (estimating $N_T$).

---

It appears $N_T$ is related to The Coupon Collector's Problem with unequal probabilities https://en.wikipedia.org/wiki/Coupon_collector%27s_problem. Indeed, each $i \in [N]$ can be seen as a "coupon", $T$ is the collector's budget, and $p_i$ is the probability that a random box contains the $i$th coupon. Let $T_N := \inf\{t \mid \inf_i n_t(i) \ge 1\}$. Note that $N_T = N$ iff $T_N \le T$. On the other hand, in a variety of scenarios it is well-known that

$$ \mathbb P(\frac{T_N - b_N}{k_N} \le c) = e^{-e^{-c}} + o_N(1), \tag{1}\label{1} $$

where $b_N$ and $k_N$ only dependend on the $p_i$'s. For example, in the case of uniform distribution where $p_i = 1/N$ for all $i$, then $b_N = N\log N$ and $k_N = N$. (\ref{1}) is then a classical result due to Laplace. In this case, we see that for any $T \ge b_N + ck_N = N\log N + cN$ $$ \mathbb P(N_T = N) = \mathbb P(T_N \le T) = e^{-e^{-c}} + o_N(1). $$

In particular, this means that if $T \ge (C+1)N\log N$, then $N_T = N$ w.p $1-N^{-C}$.

A more general scenario where (\ref{1}) holds is when $p_i = a_i/A_N$, where $A_N := \sum_i a_i$ and $a_i = 1/f(i)$ where $f$ is a decreasing function satisfying some regularity conditions. For example, when $f(x) := x^a$ for some $a \gt 0$ with $a \ne 1$, we have

$$ b_N = N^{\overline a}\log N,\, k_N = N^{\overline a}, $$ where $\overline a := \max(a,1)$. See Theorem 4.2 of this paper https://arxiv.org/abs/1412.3626. We deduce that in this setting: if $T \ge (C+1)N^{\overline a}\log N$, then $N_T = N$ w.p $1-N^{-C}$.