We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$ and $U_{n} = \left(\frac{S_{n}}{n}\right)^{4}$.
Show that, for all $n \in \mathbb{N}^{*}$, $$P\left(U_{n} \geqslant \frac{1}{\sqrt{n}}\right) \leqslant \frac{3}{n^{3/2}}$$

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$, $U_{n} = \left(\frac{S_{n}}{n}\right)^{4}$, and $$\mathcal{Z}_{n} = \left\{\omega \in \Omega, \exists k \geqslant n, U_{k}(\omega) \geqslant \frac{1}{\sqrt{k}}\right\}$$ Show that $\mathcal{Z}_{n} \in \mathcal{A}$ for all $n \in \mathbb{N}^{*}$ and that $\lim_{n \rightarrow \infty} P\left(\mathcal{Z}_{n}\right) = 0$.

We consider a sequence $\left(X_{n}\right)_{n \in \mathbb{N}^{*}}$ of mutually independent random variables, taking values in $\{1, -1\}$ and such that, for all $k \in \mathbb{N}^{*}$, $$P\left(X_{k} = 1\right) = P\left(X_{k} = -1\right) = \frac{1}{2}$$ For all $n \in \mathbb{N}^{*}$, we set $S_{n} = X_{1} + \cdots + X_{n}$, $U_{n} = \left(\frac{S_{n}}{n}\right)^{4}$, and $$\mathcal{Z}_{n} = \left\{\omega \in \Omega, \exists k \geqslant n, U_{k}(\omega) \geqslant \frac{1}{\sqrt{k}}\right\}$$ By considering $Z = \bigcap_{n \in \mathbb{N}^{*}} \mathcal{Z}_{n}$, show that $\left(\frac{S_{n}}{n}\right)$ converges almost surely to $0$.

Justify that for all $\ell \geqslant 0$ and $n \in \mathbb{N}$, $(N(0,\ell) = n+1) = (S_n \leqslant \ell < S_{n+1})$ up to a negligible set. Deduce that, up to negligible sets, $$\left(S_n \leqslant \ell\right) = (N(0,\ell) \geqslant n+1) \quad \text{and} \quad \left(S_n \geqslant \ell\right) \subset (N(0,\ell) \leqslant n+1).$$

Show that for all $n \in \mathbb{N}$ and $\ell \geqslant 0$, $$\mathbb{P}\left(S_n \leqslant \ell\right) \leqslant \mathbb{E}\left(\exp\left(\ell - S_n\right)\right)$$ then that $$\mathbb{P}\left(S_n \leqslant \ell\right) \leqslant e^{\ell} \mathbb{E}(\exp(-X))^n$$

Deduce that $\mathbb{P}\left(S_n \leqslant \ell\right)$ tends to 0 when $n \rightarrow +\infty$ and that $$\mathbb{E}(N(0,\ell)) \leqslant \frac{e^{\ell}}{1 - \mathbb{E}(\exp(-X))}$$

Show that for all $x \in \mathbb{R}, \ell \geqslant 0, k \in \mathbb{N}^*$ and $n \in \mathbb{N}^*$, $$\mathbb{P}\left(S_{n-1} < x \leqslant S_n, N(x, x+\ell) \geqslant k\right) \leqslant \mathbb{P}\left(S_{n-1} < x \leqslant S_n\right) \mathbb{P}(N(0,\ell) \geqslant k)$$ then that $$\mathbb{E}(N(x, x+\ell)) \leqslant \frac{e^{\ell}}{1 - \mathbb{E}(\exp(-X))}$$

Let $K > 0$ and $g : \mathbb{R} \rightarrow \mathbb{R}$ be a positive bounded function with support in $[0, K]$. The sequence of functions $f_n : \mathbb{R} \rightarrow \mathbb{R}$ is defined for $n \geqslant 0$ by $$f_n(x) = \sum_{k=0}^{n} \mathbb{E}\left(g\left(x - S_k\right)\right)$$ Deduce that for all $x \in \mathbb{R}$ and $n \in \mathbb{N}$, $$0 \leqslant f_n(x) \leqslant \|g\|_{\infty} \frac{e^K}{1 - \mathbb{E}(\exp(-X))}$$

Let $h : \mathbb{R} \rightarrow \mathbb{R}$ be a bounded function that satisfies $h(x) = \sum_{i=0}^{+\infty} p_i h\left(x - x_i\right)$ for all $x \in \mathbb{R}$, and such that for all $x \in \mathbb{R}$ and $n \in \mathbb{N}$, $h(x) = \mathbb{E}\left(h\left(x - S_n\right)\right)$. Deduce that if moreover the support of $h$ is included in $\mathbb{R}^+$, then for all $x \in \mathbb{R}$, $h(x) = 0$.

Let $a$ be a real number. Show $P(X \geqslant a) = 0 \quad \Longleftrightarrow \quad \forall n \in \mathbb{N}^{*}, \quad P\left(S_{n} \geqslant na\right) = 0$.

Let $X$ be a bounded infinitely divisible random variable defined on a probability space $(\Omega, \mathcal{A}, \mathbb{P})$. We denote $M = \sup_{\Omega} |X|$, so that $|X(\omega)| \leqslant M$ for all $\omega \in \Omega$.
Let $n \in \mathbb{N}^{*}$ and let $X_{1}, \ldots, X_{n}$ be independent random variables with the same distribution, such that $X_{1} + \cdots + X_{n}$ has the same distribution as $X$.
a) For all $i \in \llbracket 1, n \rrbracket$, show that $X_{i} \leqslant \frac{M}{n}$ almost surely, then $\left|X_{i}\right| \leqslant \frac{M}{n}$ almost surely.
b) Deduce that $\mathbb{V}(X) \leqslant \frac{M^{2}}{n}$, where $\mathbb{V}(X)$ denotes the variance of $X$.

Let $X : \Omega \rightarrow \mathbb{R}$ be a real-valued random variable. We assume that there exist two strictly positive reals $a$ and $b$ such that, for all non-negative real $t$,
$$\mathbb{P}(|X| \geqslant t) \leqslant a \exp(-bt^{2})$$
Show that the second moment of $X$ is less than or equal to $\frac{a}{b}$.

We consider $g(X)$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable with independent Rademacher coefficients and $g(M) = \|M \cdot u\|$ for a fixed unit vector $u$, and $m$ is a median of $g(X)$. Deduce that $(\sqrt{k} - m)^{2} \leqslant \mathbb{E}\left((g(X) - m)^{2}\right)$.

We consider $g(X)$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable with independent Rademacher coefficients and $g(M) = \|M \cdot u\|$ for a fixed unit vector $u$. Show that, for every strictly positive real number $t$
$$\mathbb{P}(|g(X) - \sqrt{k}| \geqslant t) \leqslant 4\exp(4)\exp\left(-\frac{1}{16}t^{2}\right)$$

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$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160\frac{\ln(1/\delta)}{\varepsilon^{2}}$. Show that, for every unit vector $u$ in $\mathbb{R}^{d}$:
$$\mathbb{P}\left(\left|\|A_{k} \cdot u\| - 1\right| > \varepsilon\right) < \delta$$

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$, $E_{ij}$ denotes 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}\|$$
Deduce that $\mathbb{P}\left(\bigcap_{1 \leqslant i < j \leqslant N} E_{ij}\right) \geqslant 1 - \frac{N(N-1)}{2}\delta$.

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. For every $(i, j) \in \llbracket 1, N \rrbracket^{2}$ such that $i < j$, $E_{ij}$ denotes 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}\|$$
Deduce the Johnson-Lindenstrauss theorem: there exists an absolute constant $c > 0$ such that for any natural integers $N$ and $d$ greater than or equal to 2 and for any distinct $v_{1}, \ldots, v_{N}$ in $\mathbb{R}^{d}$, it suffices that
$$k \geqslant c\frac{\ln(N)}{\varepsilon^{2}}$$
for there to exist an $\varepsilon$-isometry $f : \mathbb{R}^{d} \rightarrow \mathbb{R}^{k}$ for $v_{1}, \ldots, v_{N}$.

Let $X : \Omega \rightarrow \mathbb{R}$ be a real-valued random variable. We assume that there exist two strictly positive reals $a$ and $b$ such that, for all non-negative reals $t$,
$$\mathbb{P}(|X| \geqslant t) \leqslant a \exp(-bt^{2})$$
Show that the second moment of $X$ is less than or equal to $\frac{a}{b}$.

We consider the space $E = \mathcal{M}_{k,d}(\mathbb{R})$ equipped with the inner product defined by
$$\forall (A, B) \in E^{2}, \quad \langle A \mid B \rangle = \operatorname{tr}\left(A^{\top} \cdot B\right)$$
We fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define $g(M) = \|M \cdot u\|$. Let $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ be a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $m$ be a median of $g(X)$.
Deduce that $(\sqrt{k} - m)^{2} \leqslant \mathbb{E}\left((g(X) - m)^{2}\right)$.

We consider the space $E = \mathcal{M}_{k,d}(\mathbb{R})$ equipped with the inner product defined by
$$\forall (A, B) \in E^{2}, \quad \langle A \mid B \rangle = \operatorname{tr}\left(A^{\top} \cdot B\right)$$
We fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define $g(M) = \|M \cdot u\|$. Let $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ be a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables.
Show that, for every strictly positive real number $t$
$$\mathbb{P}(|g(X) - \sqrt{k}| \geqslant t) \leqslant 4 \exp(4) \exp\left(-\frac{1}{16} t^{2}\right)$$

We consider the space $E = \mathcal{M}_{k,d}(\mathbb{R})$ equipped with the inner product defined by
$$\forall (A, B) \in E^{2}, \quad \langle A \mid B \rangle = \operatorname{tr}\left(A^{\top} \cdot B\right)$$
We fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define $g(M) = \|M \cdot u\|$. Let $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ be a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. We set $A_{k} = \frac{X}{\sqrt{k}}$. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$.
Show that, for every unit vector $u$ in $\mathbb{R}^{d}$:
$$\mathbb{P}\left(\left|\left\|A_{k} \cdot u\right\| - 1\right| > \varepsilon\right) < \delta$$

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 taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. 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 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 taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. 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}\|$$
Deduce that $\mathbb{P}\left(\bigcap_{1 \leqslant i < j \leqslant N} E_{ij}\right) \geqslant 1 - \frac{N(N-1)}{2} \delta$.

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 taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. 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}\|$$
Deduce the Johnson-Lindenstrauss theorem: there exists an absolute constant $c$ strictly positive such that for any natural integers $N$ and $d$ greater than or equal to 2, and for any distinct $v_{1}, \ldots, v_{N}$ in $\mathbb{R}^{d}$, it suffices that
$$k \geqslant c \frac{\ln(N)}{\varepsilon^{2}}$$
for there to exist an $\varepsilon$-isometry $f : \mathbb{R}^{d} \rightarrow \mathbb{R}^{k}$ for $v_{1}, \ldots, v_{N}$.