Tail of sum of discrete random variables

Question

I'm trying to derive the tail of $\sum_{i\in[n]}Z_i$, where $Z_i= \begin{cases} (1-p)^2, & w.p.\quad p \\ p^2, & w.p. \quad 1-p \end{cases}$ are independent and $np\geq\log n$. A most straight forward way is by $$\mathbb{P}(\sum_{i\in[n]}Z_i\geq t)\leq e^{-\lambda t}\prod_{i\in[n]}\mathbb{E}[e^{\lambda Z_i}]\leq e^{-\lambda t}\prod_{i\in[n]}\Big[pe^{\lambda(1-p)^2}+(1-p)e^{\lambda p^2}\Big]. $$ However, I 'm very miserable after getting this equation and not sure how I can simplify it so that I can take a good $\lambda$ to get a tight tail bound. Is there any intuition how I can simplify this bound?

Answer 1

You could try using Hoeffding's inequality; the random variables $Z_i - \mathbb{E}(Z_i) = Z_i - p(1-p)$ are clearly bounded (e.g. you can easily see $-1 \le Z_i - \mathbb{E}(Z_i) \le 1$ if you are not interested in good constants; the best bound should be $-1/4 \le Z_i - \mathbb{E} Z_i \le 1$) - of course you'd have to recenter the sum. Hoeffding's inequality gives you $$\mathbb{P}(\sum_{i = 1}^n Z_i \ge t) = \mathbb{P}(\sum_{i = 1}^n Z_i - np(1-p) \ge t - np(1-p)) \le 2 \exp\left(- \frac{(t-np(1-p))^2}{2n}\right).$$ Now it highly depends which asymptotic you're interested in. For example, taking the squares and ignoring the parts which will vanish when $n \to \infty$, you can for example show $$\mathbb{P}\left(\sum_{i = 1}^n Z_i \ge t\right) \le 2 \exp \left( tp(1-p) - \frac{n}{2}p^2(1-p)^2\right). $$ If you do not care for a good constant, you can throw away the first part, since it is bounded (for fixed $t$ that is). However, I do not believe that you can find a good bound of the form $\exp(-C(p)t)$ - the expectation of your sum is $np(1-p)$, and you should study the fluctuations around this point, rather than $0$.

Answer 2

Very intuitive feedback guiding me to the correct way!

We can check $\mathbb{E}[Z_i]=p(1-p)$ and $\text{Var}(Z_i)=p(1-p)(1-2p)^2$. Using Bernstein inequality, we get $$\mathbb{P}\Big(|\sum_{i=1}^n Z_i-np(1-p)|\geq t\Big)\leq2\exp\Big(-\frac{t^2/2}{np(1-p)(1-2p)^2+t/3}\Big)\leq 2\exp\Big(-\frac{t^2/2}{np+t/3}\Big).$$ This is indeed a nice bound I'm looking for. Actually if we let $Y=\sum_{i=1}^n Z_i$, one can prove (just skip that) that $\mathbb{E}[\max_{j\in [n]}Y_j]\leq 20np/3$ for independent copies $Y_j\stackrel{d}{=}Y$. Comparing that $\mathbb{E}[Y_j]=np(1-p)$, we are just paying a small factor 20/3 to get a uniform bound when $p$ is small, $n$ is large, and $np\geq\log n$, for arbitrary $n$. Comparing that the compensation factor is $\sqrt{\log n}$ for independent Gaussian case.