AnnalesÉcoles d'ingénieurs

X-ENS PC 2019 — Maths

Reconstruction d'une suite binaire à partir d'observations bruitées · 7 pages

Le sujet démontre d'abord, au moyen d'une dilatation unitaire et de la norme d'opérateur, que le maximum du module d'un polynôme sur le disque unité fermé est atteint sur le cercle unité. Il en déduit qu'un polynôme non nul de degré au plus $n - 1$ à coefficients dans $\{-1, 0, 1\}$ vérifie $\sup_{\theta \in [-\pi/L, \pi/L]} |A(e^{i\theta})| \geqslant 1/n^{L-1}$ , puis établit l'inégalité de concentration $P(|S_n/n - q| \leqslant |S_n/n - p|) \leqslant e^{-n(p-q)^2/2}$ pour une somme de variables de Bernoulli. La dernière partie combine ces résultats pour montrer qu'une source $x \in \{0, 1\}^n$ peut être reconstruite avec grande probabilité à partir de $e^{3 \ln(n) n^{1/3}}$ observations bruitées où chaque coordonnée est conservée avec probabilité $p$ .

Le sujet, partie par partie

Notations et Préliminaires p. 3

Normes subordonnées et applications linéaires continues · Espaces préhilbertiens et euclidiens · Matrices remarquables — matrice unitaire, norme subordonnée, norme euclidienne, matrice diagonale, matrices unitairement semblables

Première partie — Principe du maximum pour les polynômes p. 4

Normes subordonnées et applications linéaires continues · Polynômes d'endomorphismes · Analyse complexe · Diagonalisation · Nombres complexes — principe du maximum, disque unité, dilatation unitaire, polynôme de matrice, matrice unitaire

Deuxième partie — Minoration d'un polynôme à coefficients $-1, 0, 1$ sur un arc p. 4–5

Polynômes · Nombres complexes · Analyse complexe — polynômes à coefficients $-1, 0, 1$ , racines de l'unité, produit de polynômes tournés, minoration sur un arc du cercle

Troisième partie — Inégalité de concentration pour une somme de Bernoulli p. 5

Inégalités de concentration · Lois de Bernoulli et binomiale · Inégalités de Markov et de Bienaymé-Tchebychev · Dérivabilité — inégalité de Hoeffding, borne de Chernoff, fonction génératrice des moments, inégalité de Markov exponentielle, inégalité de Taylor-Lagrange

Quatrième partie — Reconstruction à partir d'observations bruitées p. 6–7

Inégalités de concentration · Statistique : estimation et tests · Espérance, variance, moments · Polynômes · Nombres complexes · Coefficients binomiaux · Lois de Bernoulli et binomiale — reconstruction de traces, observation bruitée, canal à effacement, estimateur empirique, borne de l'union, partie entière