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?



Probabilistic method Alon and Spencer Azuma's inequality
$\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.


