Let $n$ be a positive integer and let $p = p(n) \in (0, 1)$. Let $X$ be the sum of the i.i.d. random variables $Y_1,\ldots, Y_n$, which are $1$ with probability $p$ and $0$ with probability $1-p$. Define a martingale $X_0,\ldots, X_n$ that satisfies $X_0 = \mathbb{E}[X]$ and $X_n = X$. Compare the bound resulting from Azuma's inequality
$$\mathbb{P}[X > \mathbb{E}[X] + t]$$
with the bounds that our two versions of Chernoff's inequality give us. Which one is better? Does the answer depend on the choice of $p(n)$ and $t$?
I will write out the inequalities as we did them in the lecture:
Azuma: Let $(X_0, \ldots, X_n)$ be a martingale with $X_0 = 0$ and $\lvert X_i - X_{i-1} \rvert \le 1 \quad (\forall 1 \le i \le n)$. Then for any $t > 0$ it holds
$$\mathbb{P}[X_n \ge \mathbb{E}[X]+t] \le \exp\bigg(-\frac{t^2}{2n} \bigg)$$
Chernoff 1: Let $X \sim Bin(n,p)$. Then for any $t > 0$ it holds
$$\mathbb{P}[X \ge \mathbb{E}[X]+t] \le \exp\bigg(-\frac{t^2}{2(\mathbb{E}[X]+t/3} \bigg) = \exp\bigg(-\frac{t^2}{2(np+t/3)} \bigg)$$
Chernoff 2: Let $X \sim Bin(n,p)$ with $\sigma^2 := \mathbb{V}[X]$. Then for any $t > 0$ it holds
$$\mathbb{P}[X \ge \mathbb{E}[X]+t] \le \exp\bigg(-\frac{t^2}{2(\sigma^2+t/3} \bigg) = \exp\bigg(-\frac{t^2}{2(p(1-p)+t/3)} \bigg)$$
So we need to compare the terms $2n, 2(np+t/3)$ and $2(p(1-p)+t/3)$. Since $n \ge 1$ it is clear that
$$2(np+t/3) \ge 2(p(1-p)+t/3).$$
On the other hand I can see that for $p(n) \rightarrow 1$ and , $6n(1-p) \le t$, which I obtained by reordering $2n \le 2np +t/3$, we have
$$2(np+t/3) \ge 2n$$
Similarly I got that for either $6n(1-p) \ge t$ or $p(n) \rightarrow 0$ together with $t \le 3n$ we have
$$2(np+t/3) \le 2n.$$
However, I am wondering if a more sophisticated comparsion is possible.