Skip to main content
1 of 4
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Finite-sample deviation bound of empirical distribution from true distribution

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

dohmatob
  • 6.9k
  • 1
  • 18
  • 76