Finite-sample deviation bound of empirical distribution from true distribution

Let $$P=(p_1,\ldots,p_k) \in \Delta_k$$ be distribution supported on set of size $$k$$ and let $$\hat{P}_n$$ be an empirical version of $$P$$ based on an iid sample of size $$n$$.

Question

What's a good non-asymptotic tail-bound of the form $$\text{Proba}(\|\hat{P}_n-P\|_2^2 \le \epsilon) \ge 1 - \delta$$ ?

Take 1

One may write $$\hat{P}_n = (X_1/n,\ldots,X_k/n)$$, where $$X_j$$ is the number of times $$j$$ was observed in the sample. It's clear that $$(X_1,\ldots,X_k) \sim \text{Multinomial}(p_1,\ldots,p_k)$$.

Now, $$\|\hat{P}_n-P\|_2^2 = (1/n^2)\sum_{j=1}^k (X_j-np_j)^2$$, and so to have $$\|\hat{P}_n-P\|_2 \le \epsilon$$, it suffices to have $$|X_j-np_j| \le n^2\epsilon^2/k$$. Noting that $$X_j$$ has mean $$\mathbb E[X_j] = np_j$$ and variance $$\operatorname{Var}[X_j] =np_j(1-p_j) \le n/4$$, we may apply Hoeffding's inequality to obtain that

$$|X_j-np_j| \ge \epsilon$$ with probability at most $$2\exp(-(n^2\epsilon^2/k)/2(n/4))=2\exp(-n\epsilon^2/k)$$.

A direct computation then gives $$\begin{split} \text{Proba}(\|\hat{P}_n-P\|_2^2 \le \epsilon) &= \text{Proba}(\sum_{j=1}^k (X_j-np_j)^2 \le n^2\epsilon^2) \ge \text{ Proba}(|X_j-np_j| \le n^2\epsilon^2/k\;\forall j)\\ &=1-\text{Proba}(\exists j\;|X_j-np_j| \ge n^2\epsilon^2/k)\\ & \overset{(a)}{\ge} 1 - \sum_{j=1}^k\text{Proba}(|X_j-np_j| \ge n^2\epsilon^2/k) \overset{(b)}{\ge} 1-2k\exp(-n\epsilon^2/k), \end{split}$$ where (a) is a union bound and (b) is Hoeffding bound obtained earlier.

Disclaimer: The multiplicative factor $$k$$ in the above bound is probably suboptimal.

• Note that in the question you compare the squared norm of $P_n-P$ to $\epsilon$ while in Take 1 you consider the norm itself. – Yuval Peres May 20 '19 at 8:33
• That's a typo. Thanks. – dohmatob May 20 '19 at 17:08

I will answer the question as stated though I am not sure you wanted to square the norm of $$P_n-P$$. Let $$e_1,\ldots,e_k$$ be the standard basis of $${\bf R}^k$$. Write $$\mu:=\sum_{j=1}^k p_j e_j$$. Let $$d_t$$ be independent random variables for $$t=1,\ldots,n$$ with $${\bf Pr}[d_t=(e_i-\mu)/\sqrt{n}]=p_i$$ for $$i=1,\ldots,k$$. Then $${\bf Pr}[\| P_n-P\|_2^2 \ge \epsilon]= {\bf Pr}[\|\sum_{t=1}^n d_t \| \ge \sqrt{n\epsilon}] \le 2\exp(-n\epsilon/2)$$ by Theorem 3 in [1]. This avoids the dependence on $$k$$ in the bound.

[1] Pinelis, Iosif. "An approach to inequalities for the distributions of infinite-dimensional martingales." In Probability in Banach Spaces, 8: Proceedings of the Eighth International Conference, pp. 128-134. Birkhäuser, Boston, MA, 1992. See https://link.springer.com/chapter/10.1007/978-1-4612-0367-4_9#page-1

• Nice. Also reference 1 is really nice. Thanks – dohmatob May 20 '19 at 17:09
• Can you accept the answer? – Yuval Peres May 20 '19 at 17:46
• Answer accepted. – dohmatob May 20 '19 at 17:54
• Hum, it seems this result would hold for countably supported (not just finitely supported) $P$. Also, unfortunately, I don't have access to ref [1]. I was wondering whether the ideas presented there can be used to bound a general $L_p$-norm (where $1 \le p \le \infty$, and my original problem corresponds to the case $p=2$) of $\hat{P}_n-P$ ? – dohmatob May 21 '19 at 5:59
• Pinelis' paper covers $L^p$ for $p \ge 2$ provided $p$ is finite. I can send you the proof if you write to me at yuval@yuvalperes.com Note the inequality definitely fails for $p=\infty$ where you need the $k$-dependence. – Yuval Peres May 21 '19 at 7:47

A self-contained proof.

• Step 1: $$\mathbb{E} \|\hat{P}_n - P\|_2^2 \leq \frac{1}{n}$$.
• Step 2: McDiarmid's inequality.

Let $$X_i$$ be the number of samples of $$i \in \{1,\dots,k\}$$. Then $$X_i \sim \text{Binom}(p_i,n)$$. \begin{align*} \mathbb{E} \|\hat{P}_n - P\|_2^2 &= \frac{1}{n^2} \sum_{i=1}^k \mathbb{E} \left( X_i - \mathbb{E} X_i \right)^2 \\ &= \frac{1}{n^2} \sum_{i=1}^k \text{Var}(X_i) \\ &= \frac{1}{n^2} \sum_{i=1}^k n P(i) (1-P(i)) \\ &\leq \frac{1}{n^2} \sum_{i=1}^k n P(i) \\ &= \frac{1}{n} . \end{align*} Jensen's inequality now implies $$\mathbb{E} \|\hat{P}_n - P\|_2 \leq \sqrt{\frac{1}{n}}$$.

Now to apply McDiarmids, let $$Y_j \in \{1,\dots,k\}$$ be the $$j$$th sample, for $$j=1,\dots,n$$. Write $$f(\vec{Y}) = \|\hat{P}_n - P\|_2$$. Suppose we change $$Y_j$$ to $$Y_j'$$, changing $$\hat{P}_n$$ to $$\hat{P}_n'$$. Then the vector $$v := \hat{P}_n - \hat{P}_n'$$ has two nonzero entries, a $$\frac{1}{n}$$ and a $$\frac{-1}{n}$$, so $$\|v\|_2 = \frac{\sqrt{2}}{n}$$. By the triangle inequality, \begin{align*} \left| f(\vec{Y}) - f(\vec{Y}') \right| \leq \|v\|_2 = \frac{\sqrt{2}}{n} . \end{align*} So McDiarmid's gives \begin{align*} \Pr\left[ \|\hat{P}_n - P\|_2 \geq \sqrt{\frac{1}{n}} + \epsilon \right] \leq \exp\left(-n\epsilon^2 \right) . \end{align*}

In particular, assume $$\epsilon \geq \sqrt{\frac{1}{n}}$$ and let $$\alpha = (2\epsilon)^2$$:

For $$\alpha \geq \frac{4}{n}$$, \begin{align*} \Pr\left[ \|\hat{P}_n - P\|_2^2 \geq \alpha \right] \leq \exp\left( \frac{- n \alpha}{4}\right) . \end{align*}

I first learned of Step 1 here: https://cstheory.stackexchange.com/a/18498/8243

• Excellent answer. Thanks! – dohmatob May 21 '19 at 5:49
• Hum, it seems this result would hold for countably supported (not just finitely supported) $P$. Right ? – dohmatob May 21 '19 at 6:02