Finite-sample deviation bound of empirical distribution from true distribution

Question

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.

Answer 1

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

Answer 2

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