Let $t>1$ and $X\_1,..., X\_t$ a set of real random variables from a discrete distribution, whose pmf is $p(x)$, supported on the points $1,...,k$.


Let $N\_t(x) = \sum\_{i = 1}^t \mathbb{1}\_{X\_i =\, x}.$ It is easy to show that
$$
P\left[\max\_x\left|\frac{1}{t} N\_t(x) - p(x)\right| <\varepsilon\right] \geq 1- 2k\cdot e^{-2t\varepsilon^2}
$$


by applying a union bound and Bernstein inequality.


**Is there any concentration bound independent of the number of support points $k$?**



Concentration on discrete probability estimator
$\newcommand\ep\varepsilon$For $[t]:=\{1,\dots,t\}$, we have
$$N\_t-tp=\sum\_{i\in[t]}J\_i,$$
where $N\_t$ is the random vector in $\mathbb R^{[k]}$ with coordinates $N\_t(x)$ for $x\in[k]$, $p$ is the vector in $\mathbb R^{[k]}$ with coordinates $p(x)$ for $x\in[k],$ and
the $J\_i$'s are iid zero-mean random vectors in $\mathbb R^{[k]}$ with coordinates $J\_i(x)=1(X\_i=x)-p(x)$ for $x\in[k]$. For the $2$-norm $\|J\_i\|\_2$ of $J\_i$ we have
$$\|J\_i\|\_2^2=\sum\_{x\in[k]}(1(X\_i=x)-p(x))^2
\le\sum\_{x\in[k]}(1(X\_i=x)+p(x)^2)=1+\sum\_{x\in[k]}p(x)^2\le2.$$


So,
$$P\left(\max\_x\left|\frac1t\, N\_t(x)-p(x)\right|\ge\ep\right)
=P\left(\max\_x\left|N\_t(x)-tp(x)\right|\ge t\ep\right)
\le P\left(\|N\_t-tp\|\_2\ge t\ep\right)
\le2e^{-t\ep^2/4},$$
by [Theorem 3.5](https://projecteuclid.org/journals/annals-of-probability/volume-22/issue-4/Optimum-Bounds-for-the-Distributions-of-Martingales-in-Banach-Spaces/10.1214/aop/1176988477.full) (with $r=t\ep$, $D=1$, and $b\_\*^2=2t$). So, we have desired concerntration.


