Corrigé ENS Ulm 2026 Maths D MP — Partie 3.2 (Q21 à Q23) : Permutations aléatoires : concentration de sommes de Hoeffding, points fixes

On note ${\tau }_{i,j}=(i,j)$ et, pour $\sigma \in {\mathfrak{S}}_N$, $f(\sigma )={\sum }_i{a}_{i,\sigma (i)}$, de sorte que $S_N=f({\pi }_N)$.

Q21. Soient $\sigma ,{\sigma }^{\prime }\in {\mathfrak{S}}_N$. Par indépendance de ${\pi }_N$, $I$, $J$,

$$\begin{array}{rl}\mathbb{P}({\pi }_N=\sigma ,{\pi }_N^{\prime }={\sigma }^{\prime })& =\sum _{i,j}\mathbb{P}({\pi }_N=\sigma )\mathbb{P}(I=i)\mathbb{P}(J=j)1_{\sigma \circ {\tau }_{i,j}={\sigma }^{\prime }}\\ & =\frac{1}{N!N^2}\#\{(i,j):\sigma \circ {\tau }_{i,j}={\sigma }^{\prime }\}.\end{array}$$

Comme ${\tau }_{i,j}\circ {\tau }_{i,j}=\mathrm{id}$, on a $\sigma \circ {\tau }_{i,j}={\sigma }^{\prime }⟺\sigma ={\sigma }^{\prime }\circ {\tau }_{i,j}$ : l'ensemble compté est le même quand on échange $\sigma$ et ${\sigma }^{\prime }$. Donc $\mathbb{P}({\pi }_N=\sigma ,{\pi }_N^{\prime }={\sigma }^{\prime })=\mathbb{P}({\pi }_N={\sigma }^{\prime },{\pi }_N^{\prime }=\sigma )=\mathbb{P}(({\pi }_N^{\prime },{\pi }_N)=(\sigma ,{\sigma }^{\prime }))$ : le couple est échangeable.

Q22a. Fixons $i,j$ et posons $x=a_{i,\pi (i)}$, $y=a_{j,\pi (j)}$, $u=a_{i,\pi (j)}$, $v=a_{j,\pi (i)}$, tous dans $[0,1]$. Alors $x+y\in [0,2]$ et $u+v\in [0,2]$, donc $d=x+y-u-v\in [-2,2]$ et

$$d^2=|d|\cdot |d|\le 2|d|\le 2((x+y)+(u+v)),$$

la dernière inégalité car $|d|\le \max (x+y,u+v)\le x+y+u+v$ (nombres positifs). En sommant sur $(i,j)$, on obtient l'inégalité demandée.

Q22b. On applique la partie 2.2 avec $W={\pi }_N$, $W^{\prime }={\pi }_N^{\prime }$, $E={\mathfrak{S}}_N$ (fini) et $F(\sigma ,{\sigma }^{\prime })=\frac{N}{2}(f(\sigma )-f({\sigma }^{\prime }))$, antisymétrique et bornée ($E$ est fini) ; le couple est échangeable (Q21).