I have two martingale difference sequences $X_i$ and $Y_i$ with $|X_i| \leq 2H$ and $|Y_i| \leq 2H$. Then by Azuma Hoeffding inequality, I can say with probability at least $1-\delta/2$,
$$\sum_{i=1}^T X_i \leq \sqrt{2HT\log(2/\delta)}$$
Similarly with probability at least $1-\delta/2$,
$$\sum_{i=1}^T Y_i \leq \sqrt{2HT\log(2/\delta)}$$
By union bound can I say the following?
With probability at least $1-\delta$,
$$\sum_{i=1}^T X_i + \sum_{i=1}^T Y_i \leq 2\sqrt{2HT\log(2/\delta)}$$
Best Answer
If $P(X > c) \le \delta/2$ and $P(Y > c) \le \delta / 2$ then $$P(X+Y > 2c) \le P(X > c \text{ or } Y > c) \le P(X>c) + P(Y>c) \le \delta.$$