Here is a cool problem that I had in one of the problem sets for my Probability and Random Processes course.

Let (X1,X2,…,Xn)(X_1, X_2, \ldots, X_n) be independent random variables such that

Pr⁡(Xi=1−pi)=pi \Pr(X_i = 1 - p_i) = p_i

and

Pr⁡(Xi=−pi)=1−pi \Pr(X_i = -p_i) = 1 - p_i

Let X=∑i=1nXiX = \sum_{i=1}^{n} X_i. Prove

Pr⁡(∣X∣≥a)≤2e−2a2/n \Pr(|X| \geq a) \leq 2e^{-2a^2/n}

.

Hint: You may use the following inequality

πeλ(1−π)+(1−π)e−λπ≤eλ2/8\pi e^{\lambda(1-\pi)} + (1-\pi)e^{-\lambda\pi} \leq e^{\lambda^2/8}