
> 
> Let $X\_1,\dots, X\_n\sim\operatorname{Bern}(\frac{1}{2})$ be independent, identically distributed random variables, and $\alpha=(\alpha\_1,\dots,\alpha\_n)\in[0,1]^n$ a vector of non-negative weights satisfying $\sum\_{k=1}^n \alpha\_k = 1$.
> 
> 
> Define the random variable $X\stackrel{\rm def}{=} \sum\_{k=1}^n \alpha\_k X\_k$. Given parameter $\delta > 0$, what is the best concentration bounds I get on $X$ in terms of the $p$-'norms' (allowing $p\in(0,1)$) of $\alpha$, i.e.
>  $$
> \mathbb{P}\{ X \leq \delta\} \leq \varphi(\delta, (\lVert\alpha\rVert\_p)\_{p>0})
> $$
>  ?
> 
> 
> 


I was thinking of using Berry—Esseen-like approximations to reduce this to studying a Gaussian random variable (leading to a bound in terms of $\frac{1}{\lVert \alpha\rVert\_2^2}$, but this falls short of what I want (as, if I am not mistaken, this requires the vector $\alpha$ to be more or less uniform). Using Chernoff/Hoeffding bounds will get me a bound expressed in terms of $\frac{1}{\lVert \alpha\rVert\_\infty}$, but it feels very loose.




---


**Edit:** using the conversion Bernoulli/Rademacher and the bounds for [those](https://en.wikipedia.org/wiki/Rademacher_distribution#Bounds_on_sums), I get an upper bound of $e^{-\frac{(1-2\delta)^2}{\lVert \alpha\rVert\_2^2}}$, similar to what the Gaussian approximation would result in. But I still don't really know if this is tight, that is if the "right" parameter for this is indeed $\lVert \alpha\rVert\_2$, or something more "exotic" that just happens to coincides with $\lVert \alpha\rVert\_2$ in the "uniform-weights regime."



Concentration bounds on weighted sum of i.i.d. Bernoulli random variables
*An almost complete answer. First of all, indeed the $\lVert \alpha\rVert\_2$-based bound mentioned in the question can be shown to be tight for many "simple" $\alpha$'s, such as balanced, or uniform/balanced on a subset of $m$ coordinates. However, it is not tight in general, and the right answer appears to be captured by a quantity, the [$K$-functional](https://en.wikipedia.org/wiki/Interpolation_space#K-method) between $\ell\_1$ and $\ell\_2$.* 


Converting the problem to that of looking at a weighted sum $Y\stackrel{\rm def}{=}\sum\_{k=1}^n \alpha\_k Y\_k$ of Rademacher random variables $Y\_1,\dots, Y\_n$ (where $Y\_k = 1-2X\_k$),
$$
\mathbb{P}\{ X \leq \varepsilon \}
= \mathbb{P}\{ Y \geq 1-2\varepsilon \}.
$$
In Montgomery-Smith **[1]**, the following is shown: 



> 
> **Theorem.** For $c\stackrel{\rm def}{=} \frac{1}{4\ln 12}\simeq \frac{1}{10}$, we have
>  $$\begin{align}
> \mathbb{P}\{ Y > K\_{1,2}(\alpha,t) \} &\leq e^{-\frac{t^2}{2}}, \tag{1} \\ \mathbb{P}\{ Y > cK\_{1,2}(\alpha,t) \} &\geq ce^{-\frac{t^2}{c}} \tag{2}
> \end{align}$$
>  where $K\_{1,2} (\alpha,t) \stackrel{\rm def}{=} \inf\{\lVert \alpha'\rVert\_1+t\lVert \alpha''\rVert\_2 \ \colon\ \alpha',\alpha'' \in \ell\_2,\ \alpha'+\alpha'' = \alpha\}$.
> 
> 
> 


Moreover, the following bound holds for $K\_{1,2}(\alpha,t)$, (**[1]**, citing Theorem 4.2 of **[2]**): assuming wlog that $\alpha\_1 \geq \alpha\_2 \geq \dots\geq \alpha\_n$,
$$
\gamma K\_{1,2}(\alpha,t) \leq \sum\_{k=1}^{\lfloor t^2\rfloor} \alpha\_k + \left(\sum\_{k=\lfloor t^2\rfloor+1}^n \alpha\_k^2\right)^{\frac{1}{2}} \leq K\_{1,2}(\alpha,t) \tag{3}
$$
for some absolute constant $\gamma \in (0,1)$.


This gives the following corollary, that can be found in **[1]**:



> 
> **Corollary.** With $c$ as above, we have that for all $\alpha\in\ell\_2$ *(which is trivial in our case as $\alpha$ has finite support)* and $0 < t \leq c\frac{\lVert \alpha\rVert\_2^2}{\lVert \alpha\rVert\_\infty}$,
>  $$\begin{align}
> ce^{-\frac{t^2}{c^3\lVert \alpha\rVert\_2^2}} \leq \mathbb{P}\{ Y >t \} \leq e^{-\frac{t^2}{2\lVert \alpha\rVert\_2^2}}, \tag{4} 
> \end{align}$$
>  where the upper bound holds for all $t>0$.
> 
> 
> 


Since the range of interest is $t\in(0,1]$, the above shows that the $e^{-\Theta\left(\frac{t^2}{\lVert \alpha\rVert\_2^2}\right)}$ dependence is tight as long as $\lVert \alpha\rVert\_2^2$ and $\lVert \alpha\rVert\_\infty$ are within constant factors, which happens to be the case for $\alpha$ roughly balanced or uniform on a subset of coordinates, for instance.


Now, for a counter example, one can consider (a variant of) the "truncated random Harmonic series," where we set, for $1\leq k\leq n$,
$$
\alpha\_k \stackrel{\rm def}{=} \frac{1}{k H\_n} \operatorname\*{\sim}\_{n\to \infty} \frac{1}{k\ln n}.
$$


Then, using techniques similar as **[1]**, one [can show](https://math.stackexchange.com/questions/1822574/tail-bound-for-the-truncated-random-harmonic-series) that 
$$
\mathbb{P}\{ Y > t \} \leq e^{-\Theta(n^t)}
$$
for $t\in(0,1)$. However, $
\lVert \alpha\rVert\_2^2 {\displaystyle\operatorname\*{\sim}\_{n\to\infty}} \frac{\pi^2}{6\ln^2 n}
$, so (4) would only yield
$$
\mathbb{P}\{ Y > t \} \leq e^{-\Theta( t^2 \ln^2 n )}.
$$


Note that (sanity check) in this case, $\lVert \alpha\rVert\_\infty = \frac{1}{H\_n}$, so the lower bound of (4) does not apply: $\frac{\lVert \alpha\rVert\_2^2}{\lVert \alpha\rVert\_\infty} {\displaystyle\operatorname\*{\sim}\_{n\to\infty}} \frac{1}{\ln n} = o(1)$.




---


**Edit:** based on results from **[3]** *(adapting and generalizing the proof of Theorem 2.2)*, one can get the following refinement of (2) above:



> 
> **Theorem.** Fix any $c>0$. Then, for any $\alpha\in\ell\_1+\ell\_2$, we have that for all $t\geq 1$,
>  $$
>  \mathbb{P}\left\{ Y \geq \frac{1}{1+c}K\_{1,2}(\alpha,t) \right\} \geq e^{-\left( \frac{2}{c}\ln\frac{\sqrt{6}(1+c)}{c}\right) (t+c)^2 }.
> $$
>  In particular,
>  $$
>  \mathbb{P}\left\{ Y \geq \frac{1}{2}K\_{1,2}(\alpha,t) \right\} \geq e^{-\left( \ln 24 \right) (t+1)^2 } \geq e^{-\left( 4\ln 24 \right)t^2 }.
> $$
> 
> 
> 




---


**[1]** Montgomery-Smith S.J. (1990) *[The distribution of Rademacher sums.](http://www.ams.org/journals/proc/1990-109-02/S0002-9939-1990-1013975-0/)* Proc. Amer. Math. Soc. 109:517522


**[2]** Holmstedt, Tord. (1970) *[Interpolation of quasi-normed spaces.](https://www.jstor.org/stable/24489757)* Math. Scand. 26, 177–199.


**[3]** Astashkin, S.V. (2010) *[Rademacher functions in symmetric spaces](http://link.springer.com/article/10.1007/s10958-010-0074-z)* Journal of Mathematical Sciences, 169(6):725–886


