0
$\begingroup$

I have $X = \sum_{i=1}^n x_i$ where $x_i$ are independent random variables s.t $$x_i \sim Bern(1/n) $$ .
Thefore $X \sim Binom(n, 1/n)$ with $E[X]= np_i = n*1/n = 1$
I have this quantity that I want to find an upper bound with chernoff bounds:
$P[X > (1+ \epsilon)np] $ where p is a constant in $[0, 1]$.

Chernoff bound tells me :
$P[X > (1+\epsilon)\mu ] \leq e^{-\epsilon^2 \mu/3}$
in our case $\mu = 1$

Can I somehow scale this (?) and instead of $(1 + \epsilon) $ have $(1 + \epsilon)np$ in order to use chernoff ?

$\endgroup$

1 Answer 1

2
$\begingroup$

You could do something like this, but there is simpler/tighter -- your random variable is basically $\operatorname{Poi}(1)$, and you have $$ \Pr[ X > 1 + x ] \leq \exp\left(-\frac{x^2}{2(x+1)}\right) \tag{1} $$ (There is a slightly tighter statement possible, adding up to a $\log$ in the exponent); in your case, $x=(1+\varepsilon)np-1$).

(1) follows from applying Bennett's inequality, and then relaxing a little the upper bound obtained that way, which then is $$ \Pr[ X > 1 + x ] \leq \exp\left(-\frac{x^2}{2}h(x)\right) \tag{2} $$ for $h(x) = 2\frac{(1+x)\ln(1+x)-x}{x^2}$.

See, e.g., this note, Section 2 (and references within: Boucheron, Lugosi, and Massart (2013), Chapter 2, for instance, for Bennett's inequality) for (just a little bit) more details.

$\endgroup$
2
  • $\begingroup$ to say that the variable is Poi(1), do you consider that if $n \rightarrow \infty$ binomial approaches poisson (if I undestand well) ? $\endgroup$ Commented May 31, 2022 at 17:59
  • 1
    $\begingroup$ @tonythestark When $n\to \infty$ and the product $n p_n$ stays constant (or bounded), yes. (But the application of Bennett's inequality doesn't rely on this! It just helps understand the final bound -- same result as with a Poisson r.v., and also you can prove the Poisson r.v. bound based on the corresponding Binomial) $\endgroup$
    – Clement C.
    Commented May 31, 2022 at 21:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .