2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Is $n=t$? Is $X=x$? $\endgroup$
    – Iosif Pinelis
    Apr 21, 2021 at 16:25
  • $\begingroup$ @IosifPinelis yes, thanks for spotting the error $\endgroup$
    – Apprentice
    Apr 21, 2021 at 16:31
  • $\begingroup$ Still: Is $X=x$? $\endgroup$
    – Iosif Pinelis
    Apr 21, 2021 at 16:32
  • $\begingroup$ yes you are right. $\endgroup$
    – Apprentice
    Apr 21, 2021 at 16:45

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$
    – Iosif Pinelis
    Apr 21, 2021 at 17:28
  • 1
    $\begingroup$ @Apprentice : Think a bit more about the direction of inequality: If a smaller value exceeds some $u$, then a greater value will exceed $u$. $\endgroup$
    – Iosif Pinelis
    Apr 21, 2021 at 17:33
  • $\begingroup$ Ok thanks @Iosif! Is there any assumption on the probability distribution in order for the concentration bound to hold? $\endgroup$
    – Apprentice
    Apr 21, 2021 at 18:39
  • 1
    $\begingroup$ @Apprentice : There are no assumptions at all in addition to the assumptions stated in your post. $\endgroup$
    – Iosif Pinelis
    Apr 21, 2021 at 18:56
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – Iosif Pinelis
    Apr 22, 2021 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.