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