Probabilistic method Alon and Spencer Azuma's inequality

Question

Theorem 7.5.2 states:

Let $v_1, \dots, v_n$ be vectors with $\|v_i\| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=\|\epsilon_1 v_1 + \dots + \epsilon_n v_n\|.$ Then $$\Pr[X - \mathbb{E}[X]] > \lambda \sqrt{n}] < e^{-\lambda^2/2},$$ $$\Pr[X - \mathbb{E}[X]] < \lambda \sqrt{n}] < e^{-\lambda^2/2}.$$

In the solution they state that the corresponding martingale $X_0, \dots, X_n$ obtained by exposing each edge one at a time satisfies $|X_{i+1}-X_i| \leq 2$. Why is this?

Answer 1

$\newcommand\ep\epsilon$The martingale $(X_i)$ is given by the formula $$X_i:=E(X|\ep_1,\dots\ep_i).$$ By the independence of the $\ep_i$'s, $$X_i=g_i(\ep_1,\dots,\ep_i),$$ where $$g_i(t_1,\dots,t_i):=E\Big\|\sum_{j=1}^i t_jv_j+\sum_{j=i+1}^i \ep_jv_j\Big\|$$ for real $t_1,\dots,t_i$. By the triangle/norm inequality, $$|g_{i+1}(t_1,\dots,t_i,t_{i+1})-g_i(t_1,\dots,t_i)| \le E|t_{j+1}-\ep_{j+1}|\,\|v_{j+1}\|\le2\times1=2$$ if $|t_{j+1}|=1$.

So,
$$|X_{i+1}-X_i|=|g_{i+1}(\ep_1,\dots,\ep_i,\ep_{i+1})-g_i(\ep_1,\dots,\ep_i)|\le2,$$ as desired.