# Concentration on discrete probability estimator

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

• Is $n=t$? Is $X=x$? Apr 21, 2021 at 16:25
• @IosifPinelis yes, thanks for spotting the error Apr 21, 2021 at 16:31
• Still: Is $X=x$? Apr 21, 2021 at 16:32
• yes you are right. Apr 21, 2021 at 16:45

$$\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 (with $$r=t\ep$$, $$D=1$$, and $$b_*^2=2t$$). So, we have desired concerntration.
• I have added details on the second inequality in the last display. As for the first Inequality there, indeed it follows because $\|u\|_\infty\le\|u\|_2$. Apr 21, 2021 at 17:28
• @Apprentice : Think a bit more about the direction of inequality: If a smaller value exceeds some $u$, then a greater value will exceed $u$. Apr 21, 2021 at 17:33
• @Apprentice : (i) With your notation such as $p(x)$ rather than $p_x$, it is better to use $\mathbb R^{[k]}$ than $\mathbb R^k$, because $\mathbb R^{[k]}$ is the set of all functions from $[k]$ to $\mathbb R$. Of course, we can identify $p(x)$ with $p_x$, and thus $\mathbb R^{[k]}$ with $\mathbb R^k$. (ii) The definition of $J_i(x)$ is correct, and it is of zero mean, since $E1(X_i=x)=P(X_i=x)=p(x)$. Apr 22, 2021 at 11:32