Un jeu de prédiction

par Thomas Budzinski (ENS de Lyon)

mercredi 10 déc. 2025, 12:15 → 14:15 Europe/Paris

Fokko du Cloux (Braconnier)

Considérons le jeu suivant : je choisis un mot $a_1...a_n$ de $n$ bits dans $\{0,1\}$, et commence à vous révéler les $a_i$ un par un. Quand vous le souhaitez, vous pouvez m'arrêter, choisir un entier $k$ et essayer de deviner la moyenne de mes $k$ prochains bits. Un résultat de Valiant et Qiao montre que vous avez une stratégie aléatoire pour laquelle l'espérance de votre erreur tend vers $0$ quand $n$ tend vers l'infini, quel que soit le mot que je choisis !