Encore une énigme avec des prisonniers

Lucas

Bonjour
Dans le dernier numéro de "European Mathematical Society Magazine" il y a une liste de problèmes soumis aux lecteurs et lectrices. J'ai été intrigué par le 289, dont voici une traduction.
--------------

C'est l'anniversaire du roi et il décide de faire plaisir à la population en libérant certains prisonniers détenus pour leurs opinions républicaines. Les prisonniers sont supposés être parfaitement rationnels, ils sont placés dans des salles séparées de sorte qu'ils ne peuvent pas parler ni communiquer entre eux. Le roi décide ensuite de défier les prisonniers et leur donne à chacun une pièce de monnaie. Pendant 15 min, chacun d'eux, disons $n$ prisonniers, doit décider s'il veut lancer la pièce ou non. Si au moins une pièce est lancée et que toutes les pièces lancées montrent "pile", les $n$ prisonniers sont tous libérés, sinon aucun d'eux ne l'est. 

Le roi imagine que les prisonniers ont peu de chances d'être libérés. Mais est-ce vraiment le cas ? Quelle est la probabilité qu'ils soient tous libérés ? On suppose que les prisonniers connaissent le nombre $n$.

------------
J'ai une stratégie qui est gagnante avec environ 24% de chances, mais je ne sais pas si elle est optimale! Quelqu'un a mieux ?

PS. J'ai demandé à ChatGPT, qui n'est pas très généreux avec les prisonniers. Il me propose la stratégie où tout le monde doit lancer sa pièce.

gerard0

Bonjour.
II n'est pas clair dans l'énoncé si les prisonniers peuvent se mettre d'accord avant et s'ils savent qui sont les n. Car dans ce cas, décider avant que l'un d'entre eux lancera seul sa pièce donne 50% de chances de libération.
Cordialement. 

Bibix

Donc en gros, il faut minimiser l'espérance du nombre de lancers... . Je ne comprends pas comment on peut établir une stratégie alors que les prisonniers ne peuvent pas communiquer entre eux. Dans ce cas là, je serais plutôt de l'avis de chatGPT (tout lancer et advienne que pourra).

JLT

Il me semble obtenir $(2^{\frac{n}{n-1}}-1)^{1-n}$ mais c'est sous réserve d'erreurs de calculs.

Georges Abitbol

Je ne suis pas sûr d'avoir compris le problème, parce que j'ai pensé à la même chose que gerard0. Ou alors, est-ce que le problème est de trouver une stratégie de la forme "chaque prisonnier décide ou non, indépendamment des autres, de lancer sa pièce ou non, en fonction du résultat d'une Bernoulli de paramètre $p$" telle que la probabilité de libération est maximale (trouver "le bon $p$") ?

lourrran

Je pars du principe que chaque prisonnier connaît le nombre $n$, et ne connaît que ça.
Pour n=2, j'ai une stratégie qui donne une proba 1/3 de se sauver, et c'est effectivement le résultat donné par ta formule.

Lucas

> II n'est pas clair dans l'énoncé si les prisonniers peuvent se mettre d'accord avant.

Il est dit "ils ne peuvent pas parler ni communiquer entre eux. Le roi décide ensuite de défier les prisonniers". Donc non, ils ne peuvent pas communiquer. Ils peuvent quand même réfléchir à la stratégie optimale, et considérer que les autres auront également trouvé cette stratégie.

> II n'est pas clair s'ils savent qui sont les n.
Euh bah si, ça c'est écrit : "On suppose que les prisonniers connaissent le nombre $n$"

@Georges Abitbol. Je suis parti là-dessus. Chaque prisonnier a 15 min pour prendre une décision, et il peut utiliser sa pièce pour le faire.

@JLT. Ta stratégie a l'air un poil meilleure que la mienne !

JLT

Georges Abitbol a dit :

Ou alors, est-ce que le problème est de trouver une stratégie de la forme "chaque prisonnier décide ou non, indépendamment des autres, de lancer sa pièce ou non, en fonction du résultat d'une Bernoulli de paramètre $p$" telle que la probabilité de libération est maximale (trouver "le bon $p$") ?

C'est ce que j'ai fait, avec $p=\frac{2^{1/(n-1)}-1}{2^{1/(n-1)}-\frac12}$, sous réserve d'erreurs.

Soc

S'ils ne peuvent pas communiquer entre eux, ils ne pourront pas se convaincre que c'était JLT qui avait la meilleure stratégie et adapter leur choix en fonction

Georges Abitbol

@Lucas : Si un prisonnier utilise sa pièce pour choisir s'il doit la lancer ou non et qu'elle tombe sur "face", ça ne les fait pas perdre, quand même ? Ou alors on considère qu'ils ont chacun une pièce cachée (les prisonniers savent cacher des choses) ? Qu'ils ont chacun au moins une pièce cachée par biais (il faut avoir beaucoup d'espace pour ranger toutes ces pièces xD) ?

JLT

S'ils n'utilisent pas leur pièce pour générer une loi de Bernoulli de paramètre $p$, ils peuvent également calculer en utilisant un générateur de nombres pseudo-aléatoires. En 15 minutes ils ont le temps s'ils sont rapides en calcul mental.

Dom

Bon. Moi je lance ma pièce, chaque fois que je le peux et on verra bien ce que font les autres. Surtout ne pas conclure que les autres feront nécessairement comme moi. 

Soc

J'avais le principe... mais pas du tout le p qui va avec! Tu peux détailler JLT s'il te plait?

JLT

Chaque prisonnier lance une pièce avec probabilité $p$. La probabilité que $k$ pièces soient lancées est de $\binom{n}{k}p^k(1-p)^{n-k}$, et la probabilité qu'elles tombent toutes sur pile est $2^{-k}\binom{n}{k}p^k(1-p)^{n-k}$. La probabilité que les prisonniers soient libérés est donc

$\sum_{k=1}^n 2^{-k}\binom{n}{k}p^k(1-p)^{n-k} = \sum_{k=0}^n 2^{-k}\binom{n}{k}p^k(1-p)^{n-k}-(1-p)^n$, qui est égal à

$$(1-\frac{p}{2})^n-(1-p)^n.$$

Soit $f(p)=(1-\frac{p}{2})^n-(1-p)^n$. On a $f(0)=0$ et $f(1)=2^{-n}$. La dérivée de $f$ s'annule lorsque $\frac{1}{2}(1-\frac{p}{2})^{n-1}=(1-p)^{n-1}$, ce qui donne $1-\frac{p}{2}=2^{1/(n-1)}(1-p)$ ou encore $p=\frac{2^{1/(n-1)}-1}{2^{1/(n-1)}-\frac12}$. Pour cette valeur de $p$, on a $f(p)=(1-p)^{n-1}(2(1-\frac{p}{2})-(1-p))=(1-p)^{n-1}=(2^{\frac{n}{n-1}}-1)^{1-n}$ qui est plus grande que $f(0)$ et $f(1)$ donc il s'agit bien d'un maximum.

Dom

Pourquoi ne postulat : « Chaque prisonnier lance une pièce avec probabilité p » ?

gerard0

Je ne sais pas "lancer une pièce avec probabilité p".
Comment font les prisonniers pour lancer une pièce avec une proba précise ?
Cordialement.

Dom

Je comprends, à la limite, que le prisonnier $1$ lance sa pièce avec un probabilité $p_1$. Mais c’est chacun la sienne.

[le prisonnier $1$ lance sa pièce avec une probabilité $p_1$ ou ne la lance pas avec la probabilité $1-p_1$]

JLT

Ils peuvent simuler une variable de Bernoulli de paramètre $p$, soit avec un logiciel de calcul scientifique, soit en faisant de tête les calculs du logiciel. Il faut juste être bon en calcul mental.

Titi le curieux

Bonjour,

   @JLT : je crois en effet qu'il y a une erreur de calcul, avec ta formule, on trouve par exemple une probabilité de 2/3 dans le cas $n =2$ alors qu'on s'attend systèmatiquement à une probabilité inférieure à 1/2 (par contre quand $n$ est grand, ça tend vers 0)

J'ai tout refait pour trouver l'erreur, j'ai trouvé la même chose que toi jusqu'à $x =\frac{2^{\frac{1}{n-1}} -1}{2^{\frac{1}{n-1}} -\frac{1}{2}}= 2\frac{\alpha -1}{2\alpha -1}$ (en notant $x$ au lieu de $p$ pour pas confondre avec le résultat final et $\alpha = 2^{\frac{1}{n -1 }}$).
Du coup, j'ai $ 1-\frac{x}{2} = \frac{\alpha}{2\alpha -1}$ et $1 - x = \frac{1}{2\alpha -1}$ et donc $p = \frac{\alpha^n - 1}{(2\alpha -1)^n}$ et sachant que $\alpha^n =2\alpha$,  $ p=\frac{1}{\left( 2\cdot2^{\frac{1}{n-1}} -1 \right)^{n-1}}$.
Ça donne 1/3 dans le cas $n=2$ (et ça doit tendre vers $\frac{1}{4}$ pour $n$ grand).

JLT

On a le même résultat, c'est juste que nos notations diffèrent : mon p est ton x et mon f(p) est ton p.

Titi le curieux

Oups, pardon, j'ai confondu tes deux premiers messages...

lourrran

Chaque prisonnier joue avec sa pièce entre ses doigts, il la retourne dans tous les sens puis la regarde. Pile=1 et Face=0. Et il répète ça une douzaine de fois. Il a ainsi un nombre entre $0$ et $2^{12}-1$. Et selon la valeur de ce nombre, il décide ou non de lancer la pièce.

@Dom
Pour que le prisonnier 1 ait une stratégie particulière, il faut qu'il y ait un prisonnier 1. Qui s'auto-proclame prisonnier 1 ? Comment s'assure-t-il d'être le seul à s'auto-proclamer prisonnier 1, sachant que les prisonniers n'ont aucun moyen de communiquer ? 

Dom

Non je ne parle pas d’un raisonnement sur l’ordre des prisonniers. Je n’ai toujours pas compris pourquoi il existe $p$ tel que chaque prisonnier joue sa pièce ou pas avec la probabilité $p$. 

J’aurais éventuellement dit : quel que soit le prisonnier $i$, il joue sa pièce ou pas avec la probabilité $p_i$. C’est le sens de mon message.

JLT

Pour des raisons de symétrie les $p_i$ sont égaux entre eux.

Soc

Merci JLT!

Dom

Bon, j’avoue ne rien comprendre. Mais peut-être ai-je loupé des messages, voire le sens de l’énigme toute entière. 

Soc

Le principe est qu'il faut qu'ils lancent le moins de pièces possible sans pouvoir se mettre d'accord. On voit bien que l'idéal est de lancer une seule pièce, mais ce n'est pas possible. L'idée est donc que chacun lance une pièce avec une faible probabilité en espérant que tout se passe bien. En reprenant les notations de JLT , on choisit donc pour tous une probabilité $p$ de lancer sa pièce. A partir de cette probabilité $p$ on calcule la probabilité $f(p)$ qu'ils ont d'être libérés. On fait ensuite varier le paramètre $p$ pour maximiser la probabilité $f(p)$ qu'ils soient libérés.

Reste ensuite la problématique de pouvoir faire un tirage aléatoire de probabilité p avant de lancer la pièce. On peut se satisfaire d'une dichotomie pour modéliser cette proba.

Là où je reste encore un peu sur ma faim, c'est sur le fait qu'il ne puisse pas exister de meilleure stratégie.

Edit: @Dom peut-être ce qui te bloque est le fait qu'effectivement rien ne leur garantit que personne ne lancera de pièce, ce qui intuitivement peut paraître une mauvaise idée. Mais ça ne l'est pas!

Dom

C’est ce truc « on choisit donc pour tous une probabilité $p$ de lancer sa pièce » qui me semble osé car ils ne peuvent pas communiquer. 

Mais j’ai fini par comprendre qu’on partait là-dessus pour raisonner. Si c’était dans l’énoncé, ce serait tout de même mieux car pour moi ce n’est pas du tout une conséquence des données.

Soc

Pour illustrer l'efficacité de la stratégie, avec simplement 2 prisonniers:

* S'ils lancent tous les deux leur pièce, ils ont 1 chance sur 4 d'être libérés.
* S'ils décident de lancer leur pièce avec une probabilité de 1/2, ils ont 5 chances sur 16 d'être libérés.
* S'ils décident de lancer leur pièce avec une probabilité de 1/3, ils ont 1 chance sur 3 d'être libérés. (optimal, mais pas intuitif pour moi)

Lucas

J'avais pensé à une stratégie qui ne demande pas vraiment de calcul (bon, il faut quand même connaître par coeur la table des logarithmes en base 2...) :

- On fixe k (à choisir plus tard)
- Chacun lance la pièce k fois.
- Si un prisonnier obtient $k$ fois pile, alors il lancera la pile quand le geôlier reviendra.

Ça donne une proba de gain de

\begin{align}
\mathbb{P}(\text{tout le monde sauvé})&=\sum_{j=1}^n \mathbb{P}(\text{tout le monde sauvé ; $j$ ont lancé la pièce devant le gêolier})\\
&=\sum_{j=1}^n \mathbb{P}(\text{$j$ ont lancé la pièce devant le gêolier})2^{-j}\\
&=\sum_{j=1}^n \mathbb{P}(\text{Binomiale}(N,2^{-k})=j)\times 2^{-j}\\
&=\sum_{j=1}^n \binom{n}{j}(2^{-k})^j (1-2^{-k})^{n-j}\times 2^{-j}\\
&=(1-2^{-k}+2^{-k-1})^n - (1-2^{-k})^n\\
\end{align}
Et en prenant $k\approx \log_2(n)$ on obtient une proba de gain de environ $\exp(-1/2)-\exp(1)=0.23865...$

lourrran

Non Soc,
Si chacun lance sa pièce avec une proba 1/3, on arrive à seulement 25% de se sauver, comme le cas où tous les 2 lancent une pièce.
C'est quand chacun lance sa pièce avec une proba 2/3 qu'on arrive au résultat optimum, 33%.
Et c'est ''un peu'' intuitif''.
Quand chacun lance sa pièce avec une proba 1/2, on vise le cas où en tout, un seul lance sa pièce, ce qui est optimal. Mais si on n'a pas cette chance, soit les 2 se sont abstenus, et c'est mort. Soit les 2 ont lancé, et ce n'est pas mort, on a encore une chance sur 4 de s'en sortir.
C'est donc intuitif que le meilleur résultat, c'est pour une proba $p$ un peu supérieure à 0.5.

@Dom : on ne choisit pas pour tous une proba identique.
Chaque prisonnier est dans sa bulle.
Restons sur le cas n=2 ; si le premier prisonnier choisit une proba différente de 2/3, disons une proba proche de 1 ( je lance ma pièce , j'espère faire pile, et j'espère que mon copain ne lancera pas sa pièce), qu'est-ce qui empêche le prisonnier n°2 de tenir le même raisonnement. 
Personne n'impose aux différents prisonniers d'appliquer la même stratégie, mais c'est en appliquant la même stratégie qu'ils optimisent leurs chances de se sauver. Et comme ils sont tous d'excellents mathématiciens (on trouve beaucoup d'excellents mathématiciens en prison dans les exercices), ils arrivent au raisonnement détaillé par JLT.

Dom

Mouais. Je persiste à trouver cela capillotracté. Mais c’est un détail. Je rajoute tout ce discours là dans l’énoncé et ça me convient. 

C’est de déduire tout ça de l’énoncé qui ne me va pas. 

Georges Abitbol

@Dom : je suis d’accord que la contrainte de symétrie des stratégies ne découle pas logiquement de l’énoncé. Les prisonniers ne sont pas des clones. La stratégie « il n’y a que Charles-Mohammed-Sachiko qui lance sa pièce » marche avec probabilité $\frac{1}{2}$, pour certains ensembles de prisonniers, et je ne pense pas que l’énoncé exclue cette stratégie.

@JLT : ben, non, ils ne peuvent pas utiliser de générateur de nombres aléatoires : comme ils sont indistinguables, ils donneraient chacun la même graine au générateur et lanceraient tous leur pièce (ou aucun ne la lancerait) 

Dom

Par chance leurs pièces tombent toutes sur face ou toutes sur pile 😬

samok

Bonsoir
Agis uniquement d'après la maxime qui fait que tu puisses vouloir en même temps qu'elle devienne une loi universelle.
Est-ce une stratégie ? Est-ce une stratégie optimale ?

samok

re-Bonsoir,
prenons n=3,
les prisonniers sont Socrate, Jésus, Bouddha.
Quelle production mathématique va en suivre ?

Soc

@lourrran Merci, je m'étais effectivement empêtré entre $p$ et $f(p)$. De fait c'est plus rassurant de voir une proba plus grande que 0,5!

@JLT Peux-tu expliciter l'argument de symétrie pour dire que les $p_i$ sont égaux?

JLT

C'est juste que le prisonnier $i$ ne peut pas contrôler le choix des autres prisonniers, donc il ne peut déterminer que son propre $p_i$. Et comme tous les prisonniers sont d'excellents mathématiciens, ils ont tous la même stratégie donc tous les $p_i$ sont égaux.

Dom

Ça va ressembler a du troll (j’ai déjà dit que j’étais sceptique). 

1) Être excellent mathématicien ne signifie pas arriver tous à la même conclusion.
2) sait-on quel est le $p_i$ (plutôt le $p$) le plus favorable ? Là éventuellement, ça aurait de la gueule.
3) pour s’amuser : les prisonniers savent-ils que les autres sont excellents mathématiciens ?

JLT

La valeur optimale de $p$ a déjà été donnée dans l'un de mes messages précédents. Ca fonctionne car $p\mapsto f(p)$ atteint un unique maximum.

Dom

Alors, mea-culpa. 

JLapin

Ça va ressembler a du troll (j’ai déjà dit que j’étais sceptique).

Ce n'est pas une question de scepticisme. C'est une question de savoir qu'en face d'un énoncé de probabilités posé sous forme de jeu comme celui-ci, il y a le plus souvent un travail méta-mathématique qui consiste à présenter un formalisme et à poser une question.

Ici, dire qu'on cherche $p$ entre $0$ et $1$ qui maximise une certaine fonction ne fait pas partie de la démonstration, ça fait partie de la mise en place de l'énoncé.

Ensuite, on fait des maths et on répond à la question.

Dom

Oui, cet éclairage m’a été suggéré par un intervenant que je salue 😀
En l’espèce, ad nauseam, je trolle mais avec bienveillance. 

samok

Lucas,
existe-t-il des énoncés, dans cette même veine où des lois continues de probabilités pourraient être utilisées, une fois passé l'acceptation de la modélisation meta-mathématique.

Je me permets tout de même d'indiquer qu'ici l'optimisation n'a guère de sens puisque l'expérience aléatoire n'a lieu qu'une fois.
Cela pourrait faire penser (en caricaturant d'accord) que si je lance un dé équilibré à 6 faces, il faudrait parier sur le $3,5$, non ?