Jtdylktuy

I'm trying to derive the tail of
$sum_{iin[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 $npgeqlog n$. A most straight forward way is by
$$mathbb{P}(sum_{iin[n]}Z_igeq t)leq e^{-lambda t}prod_{iin[n]}mathbb{E}[e^{lambda Z_i}]leq e^{-lambda t}prod_{iin[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?

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 expleft(- 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 tright) le 2 exp left( tp(1-p) - frac{n}{2}p^2(1-p)^2right). $$
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$.

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 tBig)leq2expBig(-frac{t^2/2}{np(1-p)(1-2p)^2+t/3}Big)leq 2expBig(-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_{jin [n]}Y_j]leq 20np/3$ for independent copies $Y_jstackrel{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 $npgeqlog n$, for arbitrary $n$. Comparing that the compensation factor is $sqrt{log n}$ for independent Gaussian case.