Suppose I have $n$ independent 0-1 random variables $X\_1, \cdots, X\_n$ and I want to show a concentration of $X = \sum\_i X\_i$.


I can use either the Chernoff bound or the Hoeffding bound.


Suppose $E[X] = O(1)$. Then, I should use the Chernoff bound which will give me Poissonian tails. On the other hand, if $E[X] = O(n)$ then using the Hoeffding bound will give me a better result -- namely Gaussian tails. 


However, what if, say, $E[X] = \sqrt{n}$. It is hard to believe that Chernoff is the best I can do. Is there some better inequality for this case? And what if $E[X] = n/\log n$ or anything else between $O(1)$ and $O(n)$?




---


Edit in response to Kodlu's answer: Using Chernoff, one gets that there is subgasussian concentration at an interval around the mean that gets bigger with increasing $\mu$. However, outside of this interval ($\delta > 1$), this still gives us only Poissonian tails. Now, my conjecture is that one can actually get better bounds.



Something between the Chernoff and Hoeffding bounds
$\newcommand\ep{\varepsilon}$ $\newcommand\si{\sigma}$ $\newcommand\Ga{\Gamma}$ $\newcommand\tPi{\tilde\Pi}$ 
It follows from Theorem 2.1 of [this paper](https://projecteuclid.org/download/pdfview_1/euclid.aihp/1388545263) or of its [better version](https://arxiv.org/pdf/0902.4058v1.pdf)  that for a large class, say $\mathcal F$, of nondecreasing functions $f$, containing the class of all increasing exponential functions, we have 
$$Ef(X-EX)\le Ef(Y),\tag{1}$$
where 
$$Y:=\Ga\_{(1-\ep)\si^2}+y\tPi\_{\ep\si^2/y^2},$$
$\Ga\_{a^2}\sim N(0,a^2)$, $\tPi\_\theta$ has the centered Poisson distribution with parameter $\theta$, $\Ga\_{(1-\ep)\si^2}$ and $\tPi\_{\ep\si^2}$ are independent, 
$$y:=\max\_i q\_i,\quad \si^2:=\sum\_i p\_i q\_i,\quad\ep:=\sum\_i p\_i q\_i^3/(\si^2 y)\in[0,1],$$
$p\_i:=P(X\_i=1)$, and $q\_i:=1-p\_i$. 
We see that $\ep\in[0,1]$ "interpolates" between the Gaussian and (re-scaled centered) Poisson random variables (r.v.'s) $\Ga\_{\si^2}$ and $y\tPi\_{\si^2/y^2}$.


From here, one can immediately get exponential bounds on the tails of $X$, or one can get better bounds such as 
$$P(X-EX\ge x)\le\frac{2e^3}9\,P^{LC}(Y\ge x)$$
for all real $x$, where $P^{LC}(Y\ge\cdot)$ denotes the least log-concave majorant of the tail function $P^{LC}(Y\ge\cdot)$; see Corollary 2.2 and Corollary 2.7 in the linked papers, respectively. 


To see better how this works, consider the iid case, with $p\_i=p$ and hence $q\_i=q=1-p$ for all $i$. Then $y=q=\ep$ and 


(i) if $p$ is small then $\ep=q$ is close to $1$ (and $y=q$ is also close to $1$) and hence $Y$ is close to the centered Poisson r.v. $\tPi\_{\si^2}$;


(ii) if $q$ is small then $\ep=q$ is small and hence $Y$ is close to the Gaussian r.v. $\Ga\_{\si^2}$; 


(iii) if neither $p$ nor $q$ is small but $n$ is large then $\ep=q$ is not small and $\si^2$ is large, and hence $\tPi\_{\ep\si^2/y^2}$ is close to $\Ga\_{\ep\si^2/y^2}$ in distribution, so that 
$Y$ is close in distribution to the Gaussian r.v. $\Ga\_{\si^2}$, just as in Case (ii). 




---


For $f(x)\equiv e^{tx}$ with real $t\ge0$, (1) becomes 
$$E\exp\{t(X-EX)\}
\le\exp\Big\{\frac{t^2}2\si^2(1-\ep)+\frac{e^{ty}-1-ty}{y^2}\,\si^2\ep\Big\}\tag{2};$$
cf. e.g. formula (1.5) in the [better version](https://arxiv.org/pdf/0902.4058v1.pdf)  of the linked paper, which implies 
$$P(X-EX\ge x)
\le\inf\_{t\ge0}\exp\Big\{-tx+\frac{t^2}2\si^2(1-\ep)+\frac{e^{ty}-1-ty}{y^2}\,\si^2\ep\Big\}$$
for real $x\ge0$. 
The latter $\inf$ can be explicitly expressed in terms of Lambert’s product-log function -- see the expression in formula (3.2) in [the same paper](https://arxiv.org/pdf/0902.4058v1.pdf); another useful expression for the same $\inf$ is given by formula (A.3) in [this other paper](https://projecteuclid.org/download/pdfview_1/euclid.ejs/1460463653). 


