# Can I "scale" Chernoff Bounds in this inequality?

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 ?

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}$$.
• to say that the variable is Poi(1), do you consider that if $n \rightarrow \infty$ binomial approaches poisson (if I undestand well) ? Commented May 31, 2022 at 17:59
• @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) Commented May 31, 2022 at 21:15