Comments on Un joli problème paradoxal de théorie de l'information

Titillant.

Cette entrée et le commentaire de CB me font vaguement penser à l'inégalité FKG, utile notamment en percolation.

On peut modifier le problème pour que le raisonnement devienne correct : Alice a le droit de regarder sa suite avant de donner le numéro à Bob mais Bob doit donner un numéro avant de regarder sa propre suite. Dans cette situation, toute stratégie a une proba de victoire de 1/4.

Théorème : une proba sur ce genre d'énoncés infinis vaut soit 0, soit 1 soit 1/e.

Les bornes obtenues placent la probabilité entre 35% et 38%, donc la stratégie optimale donne 1/e, par application immédiate du théorème.

"je reste incapable de me faire intuitivement à l'idée que ça l'est."

Cf http://www.madore.org/~david/math/proba.html#treasure : "j'ai du mal à comprendre ce que certains trouvent de difficile à ce problème" ?

Ce problème est vraiment intéressant. Il n'y a pas un seul qbit à l'horizon et pourtant le fait qu'on puisse dépasser 1/4 me donne une sensation de spooky action at distance. D'un côté je comprends bien la stratégie 1/3 (qui consiste à faire disparaître le cas 0-0, donc il ne reste que deux cas perdants à côté du cas gagnant), d'un autre, dès que j'essaye d'avoir une intuition sur une variante du problème ou de la stratégie, mon cerveau se retrouve comme chaussé de patins pour une première séance de patinage.
Genre, (a) qu'est-ce qui se passe si Alice confond les 0 et les 1 ? (A choisit le 1er 0 et B le 1er 1)
Ou (b) si Alice et Bob veulent perdre et donnent tous les deux l'indice du premier 0 ?
(c) Pour n fixé, si le Dr No utilise une permutation des indices cachée (Alice dit 3 mais il regarde s(3)), A et B peuvent-ils encore s'éloigner de 1/4 ?
(Réponses plus bas, sans garanties)

Une application pratique évidente est de prouver en société qu'Alice et Bob sont doués de télépathie. On les met dans des pièces éloignées, les participants tirent des suites à pile ou face etc., et plus les essais s'accumulent, plus il est clair qu'Alice et Bob parviennent à dépasser significativement le 1/4 !
A et B peuvent maquiller partiellement leur stratégie en remplaçant la sous-suite d'indices 1,2,3,4… par un nombre pseudo-aléatoire pour l'indice de départ et un pas variable. Avec la stratégie de Milhaid ils choisiront le même indice dans 1/5 des cas, à voir s'il est possible de diminuer ces coïncidences…

(a) 0-0 perd, 0-1 perd, 1-1 → 1/2, 1-0 disparaît donc 1/6, stratégie simple pour perdre
(b) 0-0 perd, 0-1 et 1-0 → 1/2, 1-1 disparaît donc 1/3. S'ils sont d'accord pour perdre ils gagnent autant qu'en cherchant à gagner :)
(c) si A et B sont informés du résultat de chaque essai, ils peuvent s'entendre sur un ordre des permutations et sur des critères pour faire des stats jusqu'à découvrir la permutation cachée. Sinon mon intuition me dit 1/4 mais va savoir !

Le fil de MathOverflow a été récemment (?) updaté pour obtenir la borne supérieure 3/8 (mais la valeur 7/20 n'a pas été améliorée, et la valeur 7/20-1/4^N est démontrée correcte pour des suites aléatoires de N tirages si N<5)

énervant :-)

en fait, je crois qu'il est plus simple de considérer l'explication suivante :
Le problème en cours a plusieurs expressions dont une clairement non explicite (et qui fait apparaitre d'autres propriétés) qui le rend équivalent au problème suivant : si A tire à pile ou face de façon continue jusqu'à ce qu'il obtienne un 1, et si B fait la même chose, alors quelle est la probabilité que A et B tirent leur premier 1 en même temps.

je viens de le programmer avec 1 million d'essais plusieurs fois, voila le résultat :
gains : 333575 et perte : 666425 et donc ratio de gain : 33.3575
gains : 333910 et perte : 666090 et donc ratio de gain : 33.391
gains : 332823 et perte : 667177 et donc ratio de gain : 33.2823
gains : 332579 et perte : 667421 et donc ratio de gain : 33.2579
gains : 333394 et perte : 666606 et donc ratio de gain : 33.3394

Puisque les séquences binaires sont aléatoires, Alice peut choisir a priori n’importe quelle réponse a et Bob peut choisir n’importe quelle réponse b. Et puisqu’Alice et Bob peuvent communiquer avant l’expérience, ils peuvent donc s’informer de ce qu’ils ont l’intention de répondre et se trouver dans la situation où Alice sait que Bob répondra b, et où Bob sait qu’Alice répondra a.

Lorsque qu’Alice découvre sa propre séquence binaire aléatoire, elle sait si la réponse b de Bob sera correcte ou non. Si la réponse b de Bob n’est pas correcte, s’en tenir aux réponses a et b comme prévu est donc voué à l’échec… Mais Alice et Bob ont aussi convenu que, dans le cas où l’un deux se rendrait compte que ce plan initial va échouer, il suivrait un second plan selon lequel Alice répond a’ et Bob b’. Et donc, si Alice et Bob se rendent comptent tous les deux que le plan initial va échouer (une chance sur quatre), c’est le second plan qui s’applique, dans lequel ils ont encore une chance de gagner. Mais aussi, Alice peut savoir si la réponse b’ est correcte, et Bob, de son côté, peut savoir si la réponse a’ est correcte : ils ont donc tout intérêt à avoir prévu un troisième plan, et même un quatrième, et un cinquième, etc.

Bref, Alice et Bob conviennent de s’informer non pas de la réponse que chacun a l’intention de donner, mais d’une suite de réponses qui correspondent respectivement aux plans 1, 2, 3… et on calcule alors que leur probabilité de gagner est de 1/3, les plans successifs ayant à chaque fois une chance sur quatre de réussir en étant suivis à la fois par Alice et par Bob, et une chance sur quatre d’être abandonné à la fois par Alice et par Bob au profit du plan suivant. Bien sûr, la réponse d’Alice prévue pour le plan n ne devra pas avoir été utilisée par elle pour un plan de rang inférieur, car si le plan n doit réussir, c’est que tous les plans précédents devaient rater. Idéalement, chaque suite doit donc être non seulement infinie, mais aussi sans répétition, sans quoi la probabilité de réussite de la stratégie dépassera certes les 1/4, mais restera inférieure à 1/3.

Pour simplifier, et s’ils ne sont pas particulièrement superstitieux quant aux choix de leurs réponses, ils peuvent convenir d’utiliser tous les deux la suite des entiers naturels, et dans ce cas, ils gagneront si et seulement si ils suivent tous les deux le plan n, qui correspond alors au cas où le premier 1 dans leurs suites respectives est à la énième position. Mais ils peuvent aussi convenir d’attribuer à Alice, disons, la suite des nombres premiers et à Bob celle des nombres paires à partir de 42, puis, une fois à l’isolement, de voir quel plan ils devront suivre personnellement en confrontant la suite utilisée pour les réponses de l’autre à leurs séquences binaires aléatoires respectives ; leur probabilité de gagner resterait la même au final.

***

Voilà comment j’ai fini par m’expliquer cette solution, après l’avoir lue et avoir pris le temps de la digérer… Il me semble que généraliser la stratégie en disant qu’Alice et Bob doivent convenir de suivre respectivement deux suites d’entiers, chacune infinie et non répétitive, permet peut-être de rendre tout cela plus compréhensible, même si le cas le plus simple est bien sûr celui où ces deux suites sont toutes les deux celle des entiers naturels, auquel cas la stratégie peut effectivement se résumer à : Alice choisit l'indice du premier 1 dans sa propre suite, et Bob fait pareil de son côté. Mais formulé comme ça, c’est sûr que ce n’est vraiment pas évident…

En revanche, j’avoue que je n’ai aucune idée de comment marche la stratégie qui donne une meilleure probabilité. Je n’ai pas trop le niveau pour suivre les discussion dans les liens que tu donnes. Est-ce que d’une façon ou d’une autre c’est un raffinement de celle-ci, ou c’est un truc complètement différent ?

Merci de nous faire découvrir ce problème sur ton blog et pas uniquement sur Twitter dont le format des billets rend la lecture vraiment pénible.

Ce problème m’intéresse parce qu’il nous questionne sur ce que c’est que comprendre et sur la distinction entre calculer et comprendre. Je n’ai pas osé aller voir la solution à 35% car avec les probabilités conditionnelles, on a vite fait de passer une journée à tenter de résoudre un problème sans aucun rapport avec ceux qu’on était censé résoudre ce jour là…

Je suis très perturbé par le (bien que tout à fait convaincu du) fait qu’il existe une meilleure stratégie que la stratégie de l’arrêt au premier coup. J’aimerais trouver un moyen de reformuler l’énoncé ou d’expliquer de manière limpide qu’une meilleure stratégie existe.

Concernant la stratégie du premier 1, le mieux que j’aie trouvé est de considérer la cas équivalent où Bob et Alice font des tirages synchrones indépendants jusqu’à ce que l’un d’entre eux au moins obtienne 1. On s’intéresse alors à la probabilité qu’à ce moment là, l’autre obtienne 1 aussi. Si l’arrêt intervient au premier coup, alors l’évènement heureux a une probabilité 1/3 (probabilité que les deux joueurs aient tiré 1 sachant qu’au moins l’un des deux a tiré 1), si l’arrêt intervient au deuxième coup, alors cet évènement heureux a une probabilité 1/3, au troisième coup, 1/3 aussi etc. Quel que soit le temps avant arrêt, la probabilité que l'arrêt se fasse sur l'évènement heureux est de 1/3.

Dans l'ensemble, pour tout choix de stratégie, avoir eu *tous les deux* "beaucoup de 1" est une "bonne nouvelle".

La "mauvaise nouvelle", c'est que *l'un des deux au moins* ait eu "peu de 1".

Quand cette "mauvais nouvelle" arrive, l'un des deux doit s'en rend compte, pour réagir.

--

*Exemple de coopération sans communication*

Supposons qu'Alice et Bob sont initialement d'accord pour toujours tous les deux répondre : rang 1.

Simplement, si ("mauvaise nouvelle") Alice tire un 0 au rang 1, elle sait que leur stratégie a failli.

Quoiqu'elle fasse, elle ne peut pas faire pire que de suivre la stratégie.

Perdu pour perdu, elle se rebelle donc en faisant n'importe quoi d'autre.

Elle mise ainsi sur le fait que Bob aura aussi eu la mauvaise nouvelle, et se sera aussi rebellé.

Ce pari ne lui coûte rien : en suivant la stratégie elle a déjà perdu !

Ce faisant, ils ont coopéré gratuitement en utilisant les infos à leur disposition, qui leur disaient que les conditions étaient défavorables à leur stratégie, et en ont donc adopté une autre.

Ils ont ainsi amélioré leur stratégie.

--

*Remarque*

Ici, les deux joueurs gagnent un point quand *les deux* tapent juste.

On pourrait décider qu'ils gagnent un point *par réponse juste".
(0,1 ou 2 points au total)

Noter que la coopération "perdu pour perdu" n'est pas possible dans cette deuxième situation.

En effet, pour n'importe quelle stratégie, chaque point vient avec probabilité 1/2, pour une espérance totale 2/2 = 1.