# Rate of convergence to uniform distribution

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)$$.

## 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}$$
• According to MO guidelines, please limit your post to just one question. Aug 24 at 18:05
• Done. See updated post. Aug 24 at 18:24
• 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.
– usul
Sep 27 at 18:56

## 1 Answer

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