- $\mathbb{E}(V_{i} | X_{1}, \ldots, X_{i-1}) = 0$
Let us introduce some notation, $X_{1:i} = X_{1}, \ldots, X_{i}$.
\begin{align*}
\mathbb{E}(V_{i} | X_{1:i-1}) &= \mathbb{E}\left( \left[\mathbb{E}(g | X_{1:i}) - \mathbb{E}(g | X_{1:i-1})\right] | X_{1:i-1}\right) \\\\
&=\mathbb{E}\left( \mathbb{E}(g | X_{1:i}) | X_{1:i-1}\right)- \mathbb{E}\left( \mathbb{E}(g | X_{1:i-1}) | X_{1:i-1} \right)
\end{align*}
Next apply the definitions of iterated expectations to $\mathbb{E}\left( \mathbb{E}(g | X_{1:i}) | X_{1:i-1}\right)$
First let us work with inner expectation.
\begin{align*}
\mathbb{E}(g | X_{1:i}) &= \int_{x_{i+1:n}} g f_{X_{1:n} | X_{1:i}} \mathrm{d}x_{i+1:n}
\end{align*}
Since $X_{i}$ are independent, we can reduce the joint pdf to
\begin{align*}
f_{X_{1:n} | X_{1:i}} &= \frac{\prod_{j=1}^{n} f_{X_{j}}(x_{j})} {\prod_{j=1}^{i} f_{X_{j}}(x_{j})} \\\\
&= \prod_{j=i+1}^{n} f_{X_{j}}(x_{j})
\end{align*}
Substituting the joint pdf in the inner expectation integral we get,
\begin{align*}
\mathbb{E}(g | X_{1:i}) &= \int_{x_{i+1:n}} g \prod_{j=i+1}^{n} f_{X_{j}}(x_{j})\text{dx}_{i+1:n}
\end{align*}
Observe that $\mathbb{E}(g | X_{1:i})$ is some function of $X_{1:i}$ only. Thus while doing the outer expectation, the conditional pdf will be $f_{X_{1:i} | X_{1:i-1}}$
Now the outer expectation:
\begin{align*}
\mathbb{E}\left( \mathbb{E}(g | X_{1:i}) | X_{1:i-1} \right)
&= \int_{x_{i}} \left ( \int_{x_{i+1:n}} g \prod_{j=i+1}^{n} f_{X_{j}}(x_{j}) \mathrm{d}x_{i+1:n} \right) \frac{\prod_{j=1}^{i} f_{X_{j}}(x_{j})}{\prod_{j=1}^{i-1} f_{X_{j}}(x_{j})} \mathrm{d}x_{i}\\\\
& = \int_{x_{i:n}} g \prod_{j=i}^{n} f_{X_{j}}(x_{j}) \mathrm{d}x_{i:n} \\\\
& = \mathbb{E}(g | X_{1:i-1})
\end{align*}
Using the same argument used above one can prove,
\begin{align*}
\mathbb{E}\left( \mathbb{E}(g | X_{1:i-1}) | X_{1:i-1} \right)
& = \mathbb{E}(g | X_{1:i-1})
\end{align*}
which leads to
\begin{align*}
\mathbb{E}(V_{i} | X_{1}, \ldots, X_{i-1}) &= \mathbb{E}\left( \mathbb{E}(g | X_{1:i}) | X_{1:i-1}\right)- \mathbb{E}\left( \mathbb{E}(g | X_{1:i-1}) | X_{1:i-1} \right) \\\\
&= \mathbb{E}(g | X_{1:i-1}) - \mathbb{E}(g | X_{1:i-1}) \\\\
&= 0
\end{align*}
- $\mathbb{E}(e^{t V_{i} } | X_{1}, \ldots, X_{i-1}) \le e^{t^2c_{i}^{2}/8}$
The above inequality will follow from Hoeffding's lemma if we can prove $(V_{i} | X_{1}, \ldots, X_{i-1})$ is both upper and lower bounded. We have already proved $\mathbb{E}(V_{i} | X_{1}, \ldots, X_{i-1}) = 0$.
The following proof is taken from John Duchi's wonderful notes on the inequalities. Let
\begin{align*}
U_{i} &= \sup_{u} \quad \mathbb{E}(g | X_{1:i−1}, u) − \mathbb{E}(g | X_{1:i−1}) \\\\
L_{i} &= \inf_{l} \quad \mathbb{E}(g | X_{1:i−1}, l) − \mathbb{E}(g | X_{1:i−1})
\end{align*}
Now
\begin{align*}
U_{i} - L_{i}
&\le \sup_{l,u} \,
\mathbb{E}(g | X_{1:i−1}, u) - \mathbb{E}(g | X_{1:i−1}, l) \\\\
&\le \sup_{l,u}
\left (
\int_{x_{i+1}:n}
[
g(X_{1:i-1}, u, x_{i+1:n}) - g(X_{1:i-1}, l, x_{i+1:n})
]
\prod_{j=i+1}^{n} f_{X_{j}}(x_{j})
\mathrm{d}x_{i+1:n}
\right )
\\\\
&\le
\int_{x_{i+1}:n}
\sup_{l,u} \;
\left (
g(X_{1:i-1}, u, x_{i+1:n}) - g(X_{1:i-1}, l, x_{i+1:n})
\right )
\prod_{j=i+1}^{n} f_{X_{j}}(x_{j})
\;
\mathrm{d}x_{i+1:n}
\\\\
&\le
\int_{x_{i+1}:n}
c_{i}
\prod_{j=i+1}^{n} f_{X_{j}}(x_{j})
\;
\mathrm{d}x_{i+1:n}
\\\\
&= c_{i}
\end{align*}
The third line follows from Jensen's inequality since $\sup$ is convex and the fourth line from the assumptions in the McDiarmid Inequality. Hence $L_{i} \le V_{i} \le U_{i}$ and we can apply Hoeffding's lemma to get
\begin{align*}
\mathbb{E}(e^{t V_{i} } | X_{1}, \ldots, X_{i-1}) &\le e^{t^2c_{i}^{2}/8}
\end{align*}
- $\mathbb{E} \left( e^{t \sum_{i=1}^{n} V_{i}} \right) =
\mathbb{E} \left( e^{t \sum_{i=1}^{n-1} V_{i}}
\mathbb{E} \left( e^{tV_{n}} | X_{1}, \ldots, X_{n-1} \right) \right)$
A straightforward application of iterated expectation will lead us to the above result.
\begin{align*}
\mathbb{E} \left( e^{t \sum_{i=1}^{n} V_{i}} \right)
&=
\mathbb{E} \left(
\mathbb{E} \left( e^{t \sum_{i=1}^{n} V_{i}} | X_{1}, \ldots, X_{n-1} \right)
\right) \\\\
&=
\mathbb{E} \left(
e^{t \sum_{i=1}^{n-1} V_{i}}
\mathbb{E} \left( e^{t V_{n}} | X_{1}, \ldots, X_{n-1} \right)
\right) \\\\
\end{align*}
The inner expectation is wrt $X_{n}$ while the outer expectation is wrt $X_{1:n-1}$
On applying the Hoeffding's inequality $n$ times repeatedly, we get:
\begin{align*}
\mathbb{E} \left( e^{t \sum_{i=1}^{n} V_{i}} \right)
&=
\mathbb{E} \left(
e^{t \sum_{i=1}^{n-1} V_{i}}
\mathbb{E} \left( e^{t V_{n}} | X_{1}, \ldots, X_{n-1} \right)
\right) \\\\
&\le
\mathbb{E} \left(
e^{t \sum_{i=1}^{n-1} V_{i}}
\exp \left( t^{2} c_{n}^{2}/8 \right)
\right) \\\\
&\le \exp\left( \frac{1}{8} \sum_{i=1}^{n} t^{2} c_{i}^{2} \right)
\end{align*}
Now we are ready to prove McDiarmid's inequality,
\begin{align*}
\mathbb{P} \left( g(X_{1}, \ldots, X_{n}) - \mathbb{E}(g(X_{1}, \ldots, X_{n})) \ge
\epsilon \right)
&= \mathbb{P} \left( \sum_{i=1}^{n} V_{i} \ge \epsilon \right) \\\\
&= \mathbb{P} \left( e^{t \sum_{i=1}^{n} V_{i}} \ge e^{t \epsilon} \right) \\\\
& \le \exp(-t \epsilon) \mathbb{E} \left( e^{t \sum_{i=1}^{n} V_{i}} \right) \\\\
& \le \exp(-t \epsilon) \exp\left( \frac{1}{8} \sum_{i=1}^{n} t^{2} c_{i}^{2} \right) \\\\
& = \exp \left (-t \epsilon + \frac{1}{8} \sum_{i=1}^{n} t^{2} c_{i}^{2} \right)
\end{align*}
The third line follows from Markov's inequality. To get the final result,
we need to minimize the expression wrt $t$. This occurs at $t = 4 \epsilon / \sum_{i=1}^{n} c_{i}^{2}$.
The meaning of $P$ is monotone relative to set containment is this:
If $A \subseteq B$ then $P(A)\leq P(B)$.
Now here for every $\omega\in\Omega$, we have
$$\begin{align*}
A &= \left\{\omega : \left| (X_n(\omega) + Y_n(\omega)) - ( X(\omega) + Y(\omega) ) \right| \geq \epsilon \right\}, \text{ and}\\
B &= \{ \omega : \left| X_n(\omega) - X(\omega) \right| + \left| Y_n(\omega) - Y(\omega) \right| \geq \epsilon \}.
\end{align*}$$
From your first inequality and for every $\omega\in\Omega$ and $\varepsilon >0$, we have
$$\left\{ \left| (X_n(\omega) + Y_n(\omega) - (X(\omega) + Y(\omega)) \right| \geq \varepsilon \right\} \subseteq \left\{ \left|X_n(\omega) - X(\omega)\right| + \left|Y_n(\omega) - Y(\omega)\right| \geq \varepsilon \right\}.$$
So from the statement above
$$P\left( \left| (X_n(\omega) + Y_n(\omega) - (X(\omega) + Y(\omega)) \right| \geq \varepsilon \right) \leq P\left( \left|X_n(\omega) - X(\omega)\right| + \left|Y_n(\omega) - Y(\omega)\right| \geq \varepsilon \right).$$
To show the last inequality, first we prove that for every for every $\omega\in\Omega$ and $\varepsilon >0$ we have
$$\begin{multline*}
\{\omega : \left|X_n(\omega) - X(\omega)\right| + \left|Y_n(\omega) - Y(\omega)\right| \geq \varepsilon \}\\
\subseteq \{\omega : \left|X_n(\omega) - X(\omega) \right| \geq \varepsilon/2\} \cup \{\omega : \left|Y_n(\omega) - Y(\omega) \right| \geq \varepsilon/2\}.
\end{multline*}$$
This can be simply shown by contradiction, i.e. if
$$\{ \omega : \left|X_n(\omega) - X(\omega) \right| < \varepsilon/2 \} \text{ and } \{\omega : \left|Y_n(\omega) - Y(\omega) \right| < \varepsilon/2 \}$$
then we can sum them up to get $\{ \omega : \left|X_n(\omega) - X(\omega)\right| + \left|Y_n(\omega) - Y(\omega)\right| < \varepsilon \}$, which is a contradiction.
Hence,
$$\begin{align*}
P\bigl( \{ \omega : &\left| X_n(\omega)-X(\omega) \right| + \left| Y_n(\omega) - Y(\omega) \right|\geq \varepsilon \} \bigr)\\
&\leq P\left( \{\omega : \left| X_n(\omega) - X(\omega) \right| \geq \varepsilon/2\} \cup \{\omega : \left| Y_n(\omega) - Y(\omega) \right| \geq \varepsilon/2 \} \right)\\
&\leq P\left( \{\omega : \left| X_n(\omega) - X(\omega) \right| \geq \varepsilon/2\}\right) + P\left( \{\omega : \left| Y_n(\omega) - Y(\omega) \right| \geq \varepsilon/2 \} \right),
\end{align*}$$
where the last inequality comes from $P(C \cup D) \leq P(C) + P(D)$. Cheers!
Best Answer
When you use $p_{\epsilon,B}>0.5$ then you are effectively applying Hoeffding's inequality with negative $t$
With Hoeffding's inequality
$$P\left(\frac{1}{K} \sum_{\ell=1}^{K}\left(Z_{\ell}-\mathbb{E}\left(Z_{\ell}\right)\right) \geq t\right) \leq e^{-2 K t^{2}}$$
you do not use $t<0$. For $t = 0$ the upper limiting probability is already $1$.