(Je n'ai pas de poisson d'avril à proposer cette année, mais je vous donne deux entrées pour le prix d'une.)
Même s'il a déjà été signalé hier en commentaire à cette vieille entrée, je ne peux pas ne pas écrire une petite entrée sur ce magnifique problème qui continue à narguer mon intuition — il s'agit d'un de ces cas où les mathématiques font quelque chose qui devrait être très sérieusement impossible, et j'ai beau arriver à prouver (et à comprendre la preuve intellectuellement) que c'est possible, je reste incapable de me faire intuitivement à l'idée que ça l'est. (Je sais, je sais : In mathematics you don't understand things. You just get used to them.)
Le problème est très simple (mais je l'écris de façon un peu longue pour qu'il n'y ait aucune ambiguïté sur les règles du jeu) :
Le cruel Docteur No a capturé deux mathématiciens, que nous appellerons Alice et Bob. Après avoir permis à ceux-ci de se concerter sur leur stratégie, il va les soumettre à son épreuve dont il leur communique les termes : chacun des deux pourra observer une suite binaire infinie aléatoire uniformément distribuée (c'est-à-dire une suite de 0 et 1 dont chaque terme vaut 0 ou 1 avec probabilité ½, indépendamment les uns des autres ; on peut imaginer une suite de résultats de tirages de pile ou face), les deux suites (celle qu'Alice observe et celle que Bob observe) étant indépendantes. Pour fixer les idées, mettons que les termes de chaque suite sont numérotés par les entiers naturels (0, 1, 2, 3, etc.) : appelons (An) la suite observée par Alice et (Bn) la suite observée par Bob. Alice et Bob ne peuvent pas communiquer entre eux (une fois finie la concertation initiale sur leur stratégie commune, mais celle-ci est antérieure à l'observation des suites). Alice, après avoir observé sa suite choisit un entier naturel a qui sera le numéro d'un terme dans la suite de Bob ; de même, Bob, après avoir observé sa suite, choisit un entier naturel b qui sera le numéro d'un terme dans la suite d'Alice. Alice et Bob gagnent (un gentil petit cadeau de la part du Docteur No) si chacun a choisi un terme valant 1 dans la suite de l'autre, c'est-à-dire, si la valeur Ab du terme de la suite d'Alice numéroté par l'entier b choisi par Bob et la valeur Ba du terme de la suite de Bob numéroté par l'entier a choisi par Alice valent tous les deux 1.
Quelle stratégie Alice et Bob peuvent-ils employer pour maximiser leur chance de gain ?
(Formellement : une stratégie d'Alice est une fonction borélienne α:{0,1}ℕ→ℕ et une stratégie de Bob est une fonction borélienne β:{0,1}ℕ→ℕ. La probabilité de succès est la mesure de l'ensemble des couples (A,B) ∈ {0,1}ℕ × {0,1}ℕ tels que A(β(B)) = B(α(A)) = 1, pour la mesure de probabilité uniforme sur {0,1}ℕ × {0,1}ℕ (les valeurs α(A) et β(B) sont les entiers noté a et b). Et on demande de maximiser cette probabilité.)
Remarque : Si on est gêné par les suites infinies (et c'est vrai que c'est agaçant de parler de l'observation d'une suite infinie), on peut ramener le problème à niveau fini : soit N un entier, Alice verra le résultat de N tirages de pile ou face uniformes et indépendant, Bob verra le résultat de N autres tels tirages (indépendants entre eux et indépendants de ceux d'Alice), et chacun devra choisir un entier entre 0 inclus et N exclu faisant référence à un tirage de l'autre, les deux gagnant s'ils ont choisi un tirage valant 1 chez l'autre. La situation paradoxale décrite ci-dessous est la même pour N fini que pour des suites infinies, c'est juste que les nombres sont moins ronds. (Formellement, dans le cas fini, une stratégie d'Alice est une fonction α:{0,1}N→{0,…,N−1} et une stratégie de Bob est une fonction β:{0,1}N→{0,…,N−1}. La probabilité de succès est la mesure de l'ensemble des couples (A,B) ∈ {0,1}N × {0,1}N tels que A(β(B)) = B(α(A)) = 1, pour la mesure de probabilité uniforme sur {0,1}N × {0,1}N.)
Une stratégie évidente consiste à ce qu'Alice et Bob choisissent tous les deux l'entier 0 (faisant référence au premier terme de la suite de l'autre). Dans ce cas, ils gagnent avec probabilité ¼, puisque chacun de A₀ et de B₀ vaut 1 avec probabilité ½, indépendamment l'un de l'autre. Choisir d'autres entiers constants (par exemple si Alice choisit 42 et Bob choisit 1729) donne toujours exactement la même chose.
L'idée intuitive qu'on a spontanément (en tout cas que j'ai eue, et dont je n'arrive toujours pas vraiment à me défaire) est qu'on ne peut pas faire mieux que ¼ :
Raisonnement incorrect : Alice et Bob ne peuvent pas communiquer, n'ont aucune information sur la suite de l'autre, et leurs deux suites sont indépendantes, donc il est impossible que l'observation de sa propre suite puisse aider Alice à faire quoi que ce soit d'utile sur la suite de Bob. Donc il n'y a rien de mieux à faire que de choisir des a et b constants (dont la valeur n'a pas d'importance).
Raisonnement incorrect (variante) : Quelle que soit la manière dont Alice choisit a, la valeur Ba vaudra 0 avec probabilité ½ et 1 avec probabilité ½ (puisque le choix de a ne peut dépendre que de A, qui est indépendant de B), et de même Ab vaudra 0 avec probabilité ½ et 1 avec probabilité ½. Puisque les suites A et B sont indépendantes et que (du coup) les variables a et b le sont, on a Ab = Ba = 1 avec probabilité ¼, et on ne peut pas faire mieux.
Et pourtant, c'est faux.
Et ce n'est même pas très compliqué de faire mieux que 1/4. Voici une stratégie simple qui donne une probabilité 1/3 de succès à Alice et Bob : Alice choisit pour a l'indice du premier 1 dans sa propre suite, et Bob choisit de même pour b l'indice du premier 1 dans la sienne. La probabilité d'avoir a=b est la somme de 1/4 (probabilité d'avoir a=b=0) plus 1/4² (probabilité d'avoir a=b=1) plus 1/4³ (probabilité d'avoir a=b=2), etc., c'est-à-dire la somme des 1/4k, qui vaut 1/3 ; et lorsque c'est le cas, par construction, Ab = Ba = 1 ; par ailleurs, si a≠b, alors Alice et Bob perdent (par exemple, si a<b, on a Ba = 0 puisque b est l'indice du premier 1 dans la suite B). Donc la probabilité de succès de cette stratégie est exactement 1/3.
J'ai beau avoir écrit cette preuve. Je n'arrive vraiment pas à me faire une idée intuitive de comment il est possible que cette stratégie fonctionne.
Mais je peux quand même dire ceci : la raison pour laquelle les raisonnements ci-dessus (tendant à « prouver » l'impossibilité) sont incorrects, c'est que s'il est bien vrai que chacun de Ab et Ba vaut 0 ou 1 avec probabilité ½, ils ne sont pas indépendants (puisque a dépend de A et b de B), et plus exactement, Alice et Bob peuvent s'arranger (et c'est ce qu'ils font dans la stratégie ci-dessus) pour que les deux événements Ab = 1 et Ba = 1 soient corrélés. Autrement dit, si on ne peut pas améliorer la chance d'avoir Ab = 1, on peut au moins s'arranger pour que, lorsque c'est le cas, ceci apporte des informations sur a ou sur B qui font que Ba = 1 a plus de chances de se produire. Je continue à trouver ça peu clair intuitivement, mais c'est déjà ça.
Maintenant, ce qui est amusant (et presque un peu décevant ?),
c'est que cette jolie stratégie donnant 1/3 n'est toujours pas
optimale : comme il est expliqué sur le fil MathOverflow lié au début
de cette entrée (dans
la réponse
de mihaild
), on peut faire 7/20 (c'est-à-dire 35%). Mais
on ne sait pas si c'est optimum, et on n'a pas (au moment où j'écris,
d'après de fil de discussion) de borne supérieure autre que le ½
évident.
Référence croisée : ce fil Twitter.
Mise à jour () : La borne supérieure a été améliorée à 3/8 dans le fil MathOverflow avec un argument très simple (quand j'aurai le temps, j'essaierai de mettre à jour ce paragraphe pour le donner). Par ailleurs, il apparaît que problème était déjà discuté (de façon un peu généralisée) dans ce papier, qui prouve une borne supérieure de 3/8, et annonce mais sans preuve une borne supérieure de 81/224.
Complément () : Pour la complétude de cette entrée, je reproduis en la paraphrasant la preuve de la borne supérieure par 3/8 de la probabilité de succès. Si on note a l'entier choisi par Alice et a′ l'entier qu'elle choisirait avec la même stratégie si elle observait la suite (1−An) au lieu de (An) (i.e., si on échange les 0 et 1 dans ce qu'Alice observe), et de même b et b′ pour Bob, alors on peut remarquer que l'espérance E(Ab Ba) de Ab Ba (qui est la probabilité de succès p qu'on cherche à maximiser) est aussi égale à l'espérance de (1−Ab′) Ba (puisque 1−A est une variable distribuée comme A et toujours indépendante de B) ou de Ab (1−Ba′) ou encore de (1−Ab′) (1−Ba′). La somme de ces quatre espérances (qui est 4p) est donc l'espérance de (Ab+1−Ab′) (Ba+1−Ba′), soit 4p ≤ E((Ab+1−Ab′) (Ba+1−Ba′)) = 1 + E(Ab−Ab′) + E(Ba−Ba′) + E((Ab−Ab′) (Ba−Ba′)) soit encore 1 + E((Ab−Ab′) (Ba−Ba′)) puisque E(Ab) = E(Ab′) et E(Ba) = E(Ba′) (en fait, chacune de ces quatre espérances vaut ½). Enfin, comme Ab−Ab′ vaut +1 ou −1, l'espérance E((Ab−Ab′) (Ba−Ba′)) est majorée par E(|Ba−Ba′|), elle-même majorée par ½ (si i≠j alors E(|Bi−Bj|)=½). Au final, on a prouvé 4p≤1+½, soit p≤3/8 comme annoncé.