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

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.

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 \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| \ge 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.

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

Let $P \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$ ?

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 \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| \ge 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.