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


  • $\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}$
  • $\begingroup$ According to MO guidelines, please limit your post to just one question. $\endgroup$ Aug 24 at 18:05
  • $\begingroup$ Done. See updated post. $\endgroup$
    – dohmatob
    Aug 24 at 18:24
  • $\begingroup$ Surely we can make this rate as slow as we want, by letting $p$ put arbitrarily low weight on many points? For instance, $p = (1-\alpha, \alpha/(N-1), \dots, \alpha/(N-1))$. Now even if we just consider $p_T(1)$, we have $n_T(1) \to 1$ very quickly, but $N_T$ grows toward $N$ arbitrarily slowly as we choose $\alpha$ small enough. $\endgroup$
    – usul
    Sep 27 at 18:56

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.