Quasi-orthogonalité par une méthode probabiliste

1. Soient $X, Y \in \mathbb{R}^{n}$ deux vecteurs aléatoires de Rademacher indépendants, et $t \in \mathbb{R}$. On calcule
   $$\exp(t \langle X, Y\rangle) = \exp\left(\frac{t}{n} \sum_{i = 1}^{n} X_{i} Y_{i}\right) = \prod_{i = 1}^{n} \exp\left(\frac{t}{n} X_{i} Y_{i}\right).$$Puisque les $(X_{i})$ sont indépendants et les $(Y_{i})$ le sont aussi, on en déduit
   $$\mathbb{E}[\exp(t \langle X, Y\rangle)] = \mathbb{E}\left[\exp\left(\frac{t}{n} X_{1} Y_{1}\right)\right]^{n}.$$De plus, $X_{1}$ et $Y_{1}$ sont deux variables aléatoires de Rademacher indépendantes, donc
   $$\mathbb{E}\left[\exp\left(\frac{t}{n} X_{1} Y_{1}\right)\right] = \sum_{x, y \in \{-1, +1\}} \mathbf{P}[X = x] \mathbf{P}[Y = y] \exp\left(\frac{t}{n} x y\right) = \frac{1}{2} \exp(t / n) + \frac{1}{2} \exp(-t/n) = \cosh(t/n).$$On conclut $\mathbb{E}[\exp(t \langle X, Y\rangle)] = \cosh(t/n)^{n}$.

L’inégalité de Markov et le résultat précédent donnent alors
$$\mathbf{P}[\langle X, Y\rangle \geq \varepsilon] = \mathbf{P}[\exp(t \langle X, Y\rangle) \geq \exp(t \varepsilon)] \leq \exp(-t \varepsilon) \mathbb{E}[\exp(t \langle X, Y\rangle)] \leq \exp(-t \varepsilon) \cosh(t/n)^{n}.$$La majoration $\cosh(x) \leq \exp(x^{2}/2)$ donne $\mathbf{P}[\langle X, Y\rangle \geq \varepsilon] \leq \exp(-t \varepsilon + n (t / n)^{2} / 2)$. Puisque c’est vrai pour tout $t \in \mathbb{R}$, on peut choisir le $t$ qui minimise cette borne. C’est l’exponentielle d’un polynôme de degré $2$ qui tend vers l’infini en l’infini. Le minimum de ce polynôme est atteint en $\varepsilon n$ et vaut $\exp(-n \varepsilon^{2}/2)$. On conclut $\mathbf{P}[\langle X, Y\rangle \geq \varepsilon] \leq \exp(-n \varepsilon^{2} / 2)$ comme demandé.

2. Soit $\varepsilon \in (0, 1)$ et $N < \exp(n \varepsilon^{2}/4)$. On considère $N$ vecteurs aléatoires $(X_{i})_{1 \leq i \leq N}$ de Rademacher indépendants. Ils sont unitaires par définition.

Pour tout $i \neq j \in \{1, \ldots, N\}$, l’événement $A_{i, j} = \{|\langle X_{i}, X_{j}\rangle| \geq \varepsilon\}$ est la réunion des événements disjoints $\{\langle X_{i}, X_{j}\rangle \geq \varepsilon\}$ et $\{-\langle X_{i}, X_{j}\rangle \geq \varepsilon\}$. On a donc
$$\mathbf{P}[A_{i, j}] = \mathbf{P}[\langle X_{i}, X_{j}\rangle \geq \varepsilon] + \mathbf{P}[-\langle X_{i}, X_{j}\rangle \geq \varepsilon] \leq 2 \exp(-n \varepsilon^{2} / 2).$$La majoration vient de la question précédente ; pour le deuxième terme, on utilise le fait que $-X_{i}$ est aussi un vecteur aléatoire de Rademacher et on réécrit $-\langle X_{i}, X_{j}\rangle$ en $\langle -X_{i}, X_{j}\rangle$.

L’événement $A = \bigcup_{1 \leq i < j \leq N} A_{i, j}$ correspond au fait qu’il existe au moins un couple de vecteurs distincts dont le produit scalaire est, en valeur absolue, strictement supérieur à $\varepsilon$. Par l’inégalité de l’union, on obtient
$$\mathbf{P}[A] \leq \sum_{1 \leq i < j \leq N} \mathbf{P}[A_{i, j}] \leq \binom{N}{2} 2 \exp(-n \varepsilon^{2} / 2) = N (N - 1) \exp(-n \varepsilon^{2} / 2).$$L’hypothèse sur $N$ donne finalement $\mathbf{P}[A] < 1$. Par conséquent, l’événement complémentaire $\bar{A} = \bigcap_{1 \leq i < j \leq N} \bar{A}_{i, j}$ a une probabilité strictement positive. Or $\bar{A}_{i, j} = \{|\langle X_{i}, X_{j}\rangle| < \varepsilon\}$, donc il existe au moins une réalisation $(x_{i})$ telle que $|\langle X_{i}, X_{j}\rangle| < \varepsilon$ pour tout $i \neq j \in \{1, \ldots, N\}$, ce qui conclut.

Un résultat plus fort pour pas cher

La majoration de la première question peut être améliorée. Au lieu de majorer $\cosh(x)$ par $\exp(x^{2} / 2)$, on peut chercher à minimiser directement la fonction $t \mapsto \exp(-t \varepsilon) \cosh(t/n)^{n}$. Une étude de fonction montre que le minimum est atteint en $t = n \operatorname{arctanh}(\varepsilon)$ et en évaluant ce minimum, on obtient
$$\mathbf{P}[\langle X, Y\rangle \geq \varepsilon] \leq \exp\left(-n \left[\varepsilon \operatorname{arctanh}(\varepsilon) + \frac{1}{2} \ln(1 - \varepsilon^{2})\right]\right).$$Pour appliquer la même démarche qu’à la deuxième question, il suffit alors de choisir $N$ tel que
$$N (N - 1)\exp\left(-n \left[\varepsilon \operatorname{arctanh}(\varepsilon) + \frac{1}{2} \ln(1 - \varepsilon^{2})\right]\right) < 1,$$c’est-à-dire
$$N < \frac{1}{2} + \frac{1}{2} \sqrt{1 + 4 \exp\left(n \left[\varepsilon \operatorname{arctanh}(\varepsilon) + \frac{1}{2} \ln(1 - \varepsilon^{2})\right]\right)}.$$