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


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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Peres May 20 '19 at 8:33
  • $\begingroup$ That's a typo. Thanks. $\endgroup$ – 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

  • $\begingroup$ Nice. Also reference 1 is really nice. Thanks $\endgroup$ – dohmatob May 20 '19 at 17:09
  • $\begingroup$ Can you accept the answer? $\endgroup$ – Yuval Peres May 20 '19 at 17:46
  • $\begingroup$ Answer accepted. $\endgroup$ – dohmatob May 20 '19 at 17:54
  • $\begingroup$ 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$ ? $\endgroup$ – dohmatob May 21 '19 at 5:59
  • $\begingroup$ 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. $\endgroup$ – 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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