We keep the notations and hypotheses from above. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. We set $A_{k} = \frac{X}{\sqrt{k}}$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable with independent Rademacher coefficients. Let $\varepsilon \in ]0,1[$, $\delta \in ]0, 1/2[$, and $k \geqslant 160\frac{\ln(1/\delta)}{\varepsilon^{2}}$. For every $(i, j) \in \llbracket 1, N \rrbracket^{2}$ such that $i < j$ we denote by $E_{ij}$ the event $$(1 - \varepsilon)\|v_{i} - v_{j}\| \leqslant \|A_{k} \cdot v_{i} - A_{k} \cdot v_{j}\| \leqslant (1 + \varepsilon)\|v_{i} - v_{j}\|$$ Show that $\mathbb{P}\left(\overline{E_{ij}}\right) < \delta$, where $\overline{E_{ij}}$ denotes the complementary event of $E_{ij}$.
We keep the notations and hypotheses from above. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. We set $A_{k} = \frac{X}{\sqrt{k}}$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable with independent Rademacher coefficients. Let $\varepsilon \in ]0,1[$, $\delta \in ]0, 1/2[$, and $k \geqslant 160\frac{\ln(1/\delta)}{\varepsilon^{2}}$. For every $(i, j) \in \llbracket 1, N \rrbracket^{2}$ such that $i < j$ we denote by $E_{ij}$ the event
$$(1 - \varepsilon)\|v_{i} - v_{j}\| \leqslant \|A_{k} \cdot v_{i} - A_{k} \cdot v_{j}\| \leqslant (1 + \varepsilon)\|v_{i} - v_{j}\|$$
Show that $\mathbb{P}\left(\overline{E_{ij}}\right) < \delta$, where $\overline{E_{ij}}$ denotes the complementary event of $E_{ij}$.