Let X1,…,Xn∈{0,1}X_1, \ldots , X_n \in \{ 0, 1 \} be nn independent Poisson trials. For each i∈[n]i \in [n], define μi≐E[Xi]\mu_i \doteq \mathbb{E} [X_i]. Let X≐∑i∈[n]XiX \doteq \sum_{i \in [n] } X_i and μ≐E[X]\mu \doteq \mathbb{E} \left[ X \right].

Theorem 1.
For all ϵ>0\epsilon > 0,

Pr⁡[X≥(1+ϵ)μ]≤(eϵ(1+ϵ)1+ϵ)μ. \Pr[X \ge (1 + \epsilon)\mu] \le \left( \frac{e^\epsilon}{ (1 + \epsilon)^{1 + \epsilon} } \right)^\mu.

For all ϵ∈(0,1)\epsilon \in (0, 1),

Pr⁡[X≥(1+ϵ)⋅μ]≤e−ϵ2μ/3. \Pr \left[ X \ge (1 + \epsilon) \cdot \mu \right] \le e ^ {- \epsilon^2 \mu / 3}.

Proof: Noting that exe^x is a non- decreasing function and by applying Markov's Inequality, for any t > 0, we obtain

Pr⁡[X≥(1+ϵ)⋅μ]=Pr⁡[etX≥e(1+ϵ)tμ]≤E[etX]e(1+ϵ)tμ. \begin{aligned} \Pr \left[ X \ge (1 + \epsilon) \cdot \mu \right] & = \Pr \left[ e^{tX} \ge e^{ (1 + \epsilon) t \mu } \right] \\ & \le \frac{\mathbb{E} \left[ e^{tX} \right] }{e^{(1 + \epsilon)t\mu} }. \end{aligned}

From independence of XiX_i, we get

E[etX]=∏E[etXi]=∏(etμi+(1−μi))=∏(1+μi(et−1))≤∏eμi(et−1)=eμ(et−1). \begin{aligned} \mathbb{E} \left[ e^{tX} \right] &= \prod \mathbb{E} \left[ e^{t X_i} \right] \\ & = \prod (e^t \mu_i + (1 - \mu_i)) \\ & = \prod(1 + \mu_i (e^t -1)) \\ &\le \prod e^{ \mu_i (e^t - 1)} \\ &= e^{\mu (e^t -1)}. \end{aligned}

Hence:

Pr⁡[X≥(1+ϵ)⋅μ]≤E[etX]e(1+ϵ)tμ=eμ(et−1)e(1+ϵ)tμ. \Pr \left[ X \ge (1 + \epsilon) \cdot \mu \right] \le \frac{\mathbb{E} \left[ e^{tX} \right] }{ e^{ (1 + \epsilon)t\mu} } = \frac{e^{\mu (e^t -1)} }{e^{(1 + \epsilon)t\mu} }.

By minimizing the inequality over t, we have

Pr⁡[X≥(1+ϵ)μ]≤min⁡t>0eμ(et−1)e(1+ϵ)tμ. \Pr[X \ge (1 + \epsilon)\mu] \le \underset{t > 0}{\min } \frac{e^{\mu (e^t -1)} }{e^{(1 + \epsilon)t\mu} }.

It can be shown that when t=ln⁡(1+ϵ)t = \ln (1 + \epsilon ), the bound is tightest:

Pr⁡[X≥(1+ϵ)μ]≤eμ(ϵ−(1+ϵ)ln⁡(1+ϵ))=(eϵ(1+ϵ)1+ϵ)μ. \Pr[X \ge (1 + \epsilon)\mu] \le e ^ {\mu ( \epsilon - ( 1 + \epsilon) \ln(1 + \epsilon))} = \left( \frac{e^\epsilon}{ (1 + \epsilon)^{1 + \epsilon} } \right)^\mu.

By Taylor series expansion for ln⁡(1+ϵ)\ln(1 + \epsilon),

(1+ϵ)ln⁡(1+ϵ)=ϵ+∑i=2∞(−ϵ)i(1i−1−1i)≥ϵ+ϵ212−ϵ316≥ϵ+ϵ213. \begin{aligned} (1 + \epsilon)\ln(1 + \epsilon) &= \epsilon + \sum_{i=2}^{\infty} (-\epsilon)^i \left( \frac{1}{i - 1} - \frac{1}{i} \right) \\ & \ge \epsilon + \epsilon^2 \frac{1}{2} - \epsilon^3 \frac{1}{6} \\ & \ge \epsilon + \epsilon^2 \frac{1}{3}. \end{aligned}

Substitute it back into the inequality, we obtain the desired result:

Pr⁡[X≥(1+ϵ)μ]≤e−ϵ2μ3. \Pr[X \ge (1 + \epsilon)\mu] \le e ^ {- \epsilon^2 \frac{\mu}{3} }.

Theorem 2 For all ϵ∈(0,1)\epsilon \in (0, 1),

Pr⁡[X≤(1−ϵ)μ]≤e−ϵ2μ2. \Pr[X \le (1 - \epsilon)\mu] \le e ^ {- \epsilon^2 \frac{\mu}{2} }.

Proof: As before,

Pr⁡[X≤(1−ϵ)μ]=Pr⁡[e−tX≥e−(1−ϵ)tμ]≤E[e−tX]e−(1−ϵ)tμ≤e(1−ϵ)tμeμ(et−1). \begin{aligned} \Pr \left[ X \le (1 - \epsilon) \mu \right] & = \Pr \left[ e^{-tX} \ge e^{-(1 - \epsilon) t \mu} \right] \\ & \le \frac{ \mathbb{E} \left[ e^{-tX} \right] }{e^{-(1 - \epsilon) t \mu} } \\ & \le \frac{e^{ (1 - \epsilon) t \mu} }{e^{ \mu(e^t -1) } }. \end{aligned}

Let t=ln⁡(1+ϵ)t = \ln (1 + \epsilon ),

Pr⁡[X≤(1−ϵ)⋅μ]≤eμ((1−ϵ)ln⁡(1+ϵ)−ϵ). \Pr \left[ X \le (1 - \epsilon) \cdot \mu \right] \le e ^ {\mu ( ( 1 - \epsilon) \ln(1 + \epsilon) - \epsilon ) }.

Applying Taylor expansion, we get

(1−ϵ)ln⁡(1+ϵ)=ϵ+∑i=2∞(−ϵ)i(−1i−1+1i)≥ϵ−ϵ212. \begin{aligned} (1 - \epsilon)\ln(1 + \epsilon) &= \epsilon + \sum_{i=2}^{\infty} (-\epsilon)^i \left(- \frac{1}{i - 1} + \frac{1}{i} \right) \\ & \ge \epsilon - \epsilon^2 \frac{1}{2}. \end{aligned}

Finally,

Pr⁡[X≤(1−ϵ)⋅μ]≤e−ϵ2μ2. \Pr \left[ X \le (1 - \epsilon) \cdot \mu \right] \le e ^ {- \epsilon^2 \frac{\mu}{2} }.

□\square