Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
273 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Petit problème de pile ou face

Petit problème de pile ou face
il y a cinq semaines
Bonsoir à tous
C'est un problème posté sur internet et dont je n'ai pas le niveau pour trouver la réponse sachant qu'elle n'y était pas.

"Alice et Bob coopèrent pour essayer de gagner au jeu suivant.
Chacun de son côté va tirer à pile ou face 100 fois (évidemment de façon indépendante). Puis, après avoir observés leurs pièces respectives, ils choisissent (secrètement) chacun un nombre entre 1 et 100. Disons que Alice a choisi n, et que Bob a choisi m. Ils gagnent alors si le n-ième lancé de Bob est un pile, et que le m-ième lancé d'Alice est aussi un Pile. Donc en gros, chacun essaye de "prédire" un résultat pile de l'autre.
Peuvent-ils élaborer une stratégie meilleure que la stratégie naïve consistant à choisir un entier au hasard / choisir 1 quoi qu'il arrive ?"

Si quelqu'un a une piste, merci beaucoup.



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par AD.
Re: Petit problème de pile ou face
il y a cinq semaines
Il y a bel et bien une stratégie pour gagner strictement plus qu'une fois sur 4.
Re: Petit problème de pile ou face
il y a cinq semaines
avatar
Citation

Ils gagnent alors si le n-ième lancé de Bob est un pile, et que le m-ième lancé d'Alice est aussi un Pile.

Tu peux expliquer plus précisément ?

Ils gagnent tous les deux simultanément si les deux conditions sont vérifiées ?
Ou bien ils gagnent chacun s'ils ont réussi leur épreuve sur l'information qu'ils ignorent ?
Re: Petit problème de pile ou face
il y a cinq semaines
avatar
@Foys : Tu veux dire que sachant que les deux ont eu un succès, ils ont une stratégie qui leur donne une chance sur trois, c'est ça ?

Je crois que je dis des trucs que je ne comprends pas moi-même, je vais aller me coucher !



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par marsup.
Re: Petit problème de pile ou face
il y a cinq semaines
marsup écrivait:
Citation

Tu peux expliquer plus précisément ?

J'ai trouvé le sujet sur internet et il n'est pas de moi donc je n'ai pas envie de dire une bêtise.
Cependant, je pense qu'ils gagnent tous les deux si les 2 conditions sont vérifiées.
Re: Petit problème de pile ou face
il y a cinq semaines
@marsup: s'il y a $k$ pièces, j'ai sans conditionnement une stratégie qui me garantit une probabilité de $\sum_{j=1}^k 4^{-j}$ de gain au moins. Je pense qu'on pense à la même chose. Peut-on montrer que c'est optimal d'ailleurs?
Enigme de probabilités
il y a cinq semaines
Edit : à supprimer



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par noobey.
Re: Enigme de probabilités
il y a cinq semaines
avatar
Re: Enigme de probabilités
il y a cinq semaines
avatar
Par contre, ta version de la question, même si elle arrive après l'autre, est bien mieux énoncée. Il faudrait fusionner les deux fils.
Re: Enigme de probabilités
il y a quatre semaines
Je pense avoir trouvé la stratégie dont Foys parle mais je trouve ça vraiment fou. J'arrive à démontrer que ça marche mais ça ne m'éclaire absolument pas (d'ailleurs pour réussir à trouver la stratégie je me suis servi de la formule donnée par Foys).
Est-ce que quelqu'un saurait un peu expliquer avec des phrases en français "pourquoi ça marche" ou s'il y a une heuristique générale derrière? Je sais que ce n'est pas une demande usuelle en maths mais là mon intuition se heurte tellement à la réalité mathématique que c'en est troublant.



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par AD.
Re: Enigme de probabilités
il y a quatre semaines
Par exemple est-ce que quelqu'un saurait dire rapidement et sans faire les calculs si la stratégie suivante est aussi meilleure que la stratégie naïve?
Alice parie sur l'entier i tel que i est la première fois qu'un pile apparaît chez elle et Bob parie sur l'entier j tel que j est la dernière fois qu'un pile apparaît chez lui.
Re: Petit problème de pile ou face
il y a quatre semaines
@Liederberg: Alice et Bob peuvent renuméroter leurs essais comme ils le veulent (et qualifier le premier de dernier, le deuxième d'avant dernier etc).

EDIT: non! Voir plus bas.



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par Foys.
Re: Petit problème de pile ou face
il y a quatre semaines
Merci Foys. C'est l'intuition que j'avais eue mais le fait que je ne vois pas comment montrer que ça marche aussi bien sans passer par le calcul montre que je ne comprends pas trop ce qui se passe.
Tu voulais bien dire que Alice et Bob peuvent renuméroter chacun.e différemment leurs lancers respectifs et que ça marche quand même? (par exemple Alice garde l'ordre originel et Bob inverse l'ordre)



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par Liedeberg.
Re: Petit problème de pile ou face
il y a quatre semaines
Citation
PJSNEM
après avoir observés leurs pièces respectives
Citation
Foys
s'il y a $k$ pièces

Bonjour,

Quelqu'un peut m'expliquer ce que ça veut dire ?
Re: Petit problème de pile ou face
il y a quatre semaines
@Gabuzomeu : Bob et Alice sont dans deux pièces séparées et n'interagiront à aucun moment dans l'expérience ni n'auront connaissance de ce que fait l'autre, sauf à la toute fin.
Bob lance k fois une pièce équilibrée et Alice lance également k fois une pièce équilibrée.
Elles observent chacune leurs lancers (ie : Alice regarde les lancers d'Alice et Bob regarde les lancers de Bob).
À la fin elles proposent chacune un entier : Bob propose un entier m, Alice propose un entier n.
Elles mettent en commun leurs résultats (c'est le premier instant auquel l'une a accès aux résultats de l'autre) et gagneront si et seulement si le m ème lancer d'Alice est un pile et le n ème lancer de Bob est un pile.



Edité 2 fois. La dernière correction date de il y a quatre semaines et a été effectuée par Liedeberg.
Re: Petit problème de pile ou face
il y a quatre semaines
@GaBuZoMeu: je voulais dire: si on lance $k$ pièces avec $k$ entier naturel (au lieu de 100 comme dans le message original).
Re: Petit problème de pile ou face
il y a quatre semaines
Moi je voyais plutôt une pièce tirée 100 fois. Mais peu importe.
La seule information possédée par Alice quand elle choisit un entier n est la suite des 100 résultats de ses propres tirages.
De même la seule information possédée par Bob quand il choisit m est la suite des résultats de ses 100 tirages.
Et si Alice et Bob choisissent n et m avant de faire les tirages ? Je ne vois pas quelle différence cela ferait.
Re: Petit problème de pile ou face
il y a quatre semaines
AD, puis-je savoir pourquoi tu as enlevé l'écriture inclusive de mes messages?
Je trouve ça assez scandaleux.

[J'ai simplement corrigé les typos "iels". J'avais laissé les écritures inclusives avec les points ! C'est toi qui les a retirées !
Je trouve tes accusations assez scandaleuses (pour reprendre tes termes) ! AD]

AD : d'accord, excuse-moi, je t'ai prêté de mauvaises intentions. En fait "iels" n'était pas une typo. C'est une façon de ne pas préférer un genre à un autre lorsqu'on désigne un groupe d'individus comportant au moins un membre de chaque sexe.



Edité 2 fois. La dernière correction date de il y a quatre semaines et a été effectuée par Liedeberg.
Re: Petit problème de pile ou face
il y a quatre semaines
avatar
$\def\P{\mathbb{P}}$
Moi, je note $n=100$, au lieu de $k=100$ comme Foys.
Pour Alice : $(A_i)_{i=1\dots n} \leadsto X = \min\{i, A_i\}$ (rang du premier succès)
Pour Bob : $(B_j)_{j=1\dots n} \leadsto Y = \min\{j, B_j\}$

La probabilité de gain sous la stratégie de Foys est
$
\begin{aligned}
\P(A_Y, B_X) & = \sum_{i,j=1}^n \P(X=i,Y=j,A_j,B_i) \\
& = \sum_{i,j=1}^n \underbrace{\P(X=i,Y=j)}_{\frac{1}{2^{i+j}}} \times \underbrace{\P(A_j,B_i\vert X=i,Y=j)}_{=1_{i=j}} \\
& = \sum_{i=1}^n \frac{1}{4^i} \approx \frac{1}{3}. \\
\end{aligned}
$

Par contre, je ne suis pas d'accord avec ça
Citation

Alice parie sur l'entier i tel que i est la première fois qu'un pile apparaît chez elle et Bob parie sur l'entier j tel que j est la dernière fois qu'un pile apparaît chez lui.
Citation

Alice et Bob peuvent renuméroter leurs essais comme ils le veulent (et qualifier le premier de dernier, le deuxième d'avant dernier etc
Pour $Z$ le rang du dernier succès de Bob, je trouve :
$
\begin{aligned}
\P(A_Z, B_X) & = \sum_{i,j=1}^n \P(X=i,Z=j,A_j,B_i) \\
& = \sum_{i,j=1}^n \underbrace{\P(X=i,Z=j)}_{\frac{1}{2^{i}}\times\frac{1}{2^{n-j+1}}} \times \underbrace{\P(A_j,B_i\vert X=i,Z=j)}_{=1_{i=j} + \frac{1}{4} \times 1_{i<j}} \\
& \approx \text{beaucoup plus proche d'un quart que d'un tiers à mon avis !}
\end{aligned}
$

Autrement dit, je réponds non à la question de Linderberg ici : [www.les-mathematiques.net]



Edité 4 fois. La dernière correction date de il y a quatre semaines et a été effectuée par marsup.
Re: Petit problème de pile ou face
il y a quatre semaines
avatar
Voici une intuition qui vaut ce qu'elle vaut.

Toujours $n=100$ lancers pour chaque joueur, mais cette fois-ci avec une proba de succès très faible de $p = 10^{-6}$.

Les joueurs ont pratiquement perdu d'office, car ils n'ont qu'une chance sur $10,000$ d'avoir un succès chacun, donc une chance sur $10,000^2$ d'en avoir un tous les deux.

Si jamais ils devaient avoir tous les deux eu un succès, pour gagner, ils devraient encore deviner la position du succès de l'autre. (on néglige les cas où ils auraient eu plusieurs succès !)

Ils ont 1 chance sur 100 d'avoir eu leur succès au même tirage.
Ils n'ont qu'1 chance sur 10000 de deviner autrement tous deux le succès de l'autre.

C'est vite vu, ils doivent chacun miser sur leur rang d'apparition !



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par marsup.
Re: Petit problème de pile ou face
il y a quatre semaines
avatar
Si jamais les deux devaient avoir eu 2 succès ou plus, ils auraient de plus intérêt à biaiser leur décision dans le même sens pour avoir la coïncidence !

Mieux vaut qu'ils décident tous les deux de miser sur le premier ou tous les deux sur le dernier, mais pas de croiser leurs choix.
Re: Petit problème de pile ou face
il y a quatre semaines
Citation
GaBuZoMeu
Moi je voyais plutôt une pièce tirée 100 fois. Mais peu importe.
La seule information possédée par Alice quand elle choisit un entier n est la suite des 100 résultats de ses propres tirages.
De même la seule information possédée par Bob quand il choisit m est la suite des résultats de ses 100 tirages.
Et si Alice et Bob choisissent n et m avant de faire les tirages ? Je ne vois pas quelle différence cela ferait.
Essayons d'exprimer ce phénomène autrement.

Soit $d\in \N$
Soit $f$ l'application de $\{0,1\}^d$ dans $\{0,1,...,d\}$ définie par $f(0,0,..,0):=0$ et $f(x):=\min \left \{k\in \{1,2,...,d\} \mid x_k=1\right\}$ si $x\neq (0,0,...,0)$.

Lorsque $A\subseteq \{0,1\}^d \times \{0,1\}^d $ notons $$P(A):= \frac{card(A)}{card \left ( \{0,1\}^d \times \{0,1\}^d \right)} = \frac{card(A)}{2^{2d}}$$
On note également les projections sur les coordonnées de la façon suivante: $\pi^1_k (x_1,x_2,...,x_d,y_1,y_2,...,y_d):= x_k$ et $\pi^2_k (x_1,x_2,...,x_d,y_1,y_2,...,y_d):=y_k$ pour tout $k\in \{1,...,d\}$ et tout $(x,y)\in \{0,1\}^d \times \{0,1\}^d$.

Pour tous $p,q\in \{1,...,d\}$ soit $B_{p,q}:= \left \{ (x,y) \in \{0,1\}^d \times \{0,1\}^d \mid f(x)=p \text{ et } f(y)=q\right \}$.
Alors $P(B_{p,q})=2^{-p-q}$. Les $p,q\mapsto B_{p,q}$ sont évidemment disjoints. De plus $$\begin{align}\bigcup_{k=1}^d B_{k,k}= & \left \{ (x,y) \in \{0,1\}^d \times \{0,1\}^d \mid f(x)= f(y) \text{ et } f(x)>0\right \}\\ \subseteq & \left \{ (x,y) \in \{0,1\}^d \times \{0,1\}^d \mid f(x)>0,f(y)>0,\pi^2_{f(x)}(x,y)=1 \text{ et } \pi^2_{f(y)}(x,y) = 1\right \} \tag 1\end{align}$$ Et bien sûr $P\left ( \bigcup_{k=1}^d B_{k,k} \right )=\sum_{k=1}^d 4^{-k}$.

Après on peut donner un habillage probabiliste à l'énoncé de pur dénombrement fini ci-dessus ($(1)$ est l'ensemble où Alice et Bob gagnent quand ils choisissent la stratégie consistant à jouer $f$).



Edité 3 fois. La dernière correction date de il y a quatre semaines et a été effectuée par Foys.
Re: Petit problème de pile ou face
il y a quatre semaines
D'accord, j'ai compris, c'est la proba que le premier pile de Alice arrive au même numéro que le premier pile de Bob. Joli !
Mais si Alice et Bob s'entendent sur une permutation $\sigma$ de $\{1,\ldots, n\}$ :
Alice parie sur $\sigma(X)$ où $X$ est le numéro de son premier pile.
Bob parie sur $Z$ qui est le premier tel que le tirage $\sigma(Z)$ soit pile.
Alors ça marche aussi, n'est-ce pas ?

PS. Ce qui fait la différence entre parier avant les tirages ou parier après, c'est que Alice sait que Bob va parier le numéro de son premier pile. Si le premier pile d'Alice est le numéro k, il serait idiot pour elle de parier sur une numéro plus petit que k, ça serait de toutes façons perdu.



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par GaBuZoMeu.
Re: Petit problème de pile ou face
il y a quatre semaines
En effet Marsup, j'avais fait le même calcul que toi et je trouvais également que ça n'avait pas vraiment l'air de se rapprocher de $\frac{1}{3}$. Mais je m'étais dit que j'avais dû faire une faute de calcul quelque part.

EDIT : je parle du message où tu montres qu'a priori on ne peut pas permuter comme on veut l'ordre des lancers et rester sur une stratégie qui tend vers 1/3 pour un grand nombre de lancers



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par Liedeberg.
Re: Petit problème de pile ou face
il y a quatre semaines
@Gabuzomeu le calcul fait par MArsup montre qu'a priori non on ne peut pas permuter les lancers de Bob comme on veut.
Re: Petit problème de pile ou face
il y a quatre semaines
avatar
Citation

Après on peut donner un habillage probabiliste
Pas la peine d'être méprisant pour les probas, Foys moody smiley.

D'autant moins que le problème est probabiliste, car la probabilité de succès $p=\frac{1}{2}$ y est choisie arbitrairement, et que c'est tout à fait pertinent de la faire varier, en particulier de la choisir très faible, comme je montre ici : [www.les-mathematiques.net]

Voici un paradoxe analogue, pour mieux illustrer mon argument sous hypothèse d'unicité du succès.

Citation

Dans 5 minutes, Alice et Bob vont être séparés, et chacun lancera un dé à 1000 faces. Ils gagneront simultanément ssi chacun arrive à prédire le résultat de l'autre. En attendant, ils ont le droit de se concerter sur leur stratégie, et ils sont très futés. Comment s'y prendront-ils ?
Re: Petit problème de pile ou face
il y a quatre semaines
Liedeberg écrivait:
-------------------------------------------------------
> @Gabuzomeu le calcul fait par MArsup montre qu'a
> priori non on ne peut pas permuter les lancers de
> Bob comme on veut.

As-tu vraiment réfléchi à ce que j'ai écrit ?
Re: Petit problème de pile ou face
il y a quatre semaines
avatar
Oui, il y a un paradoxe apparent, qui est que si Alice et Bob choisissent une permutation $\sigma_A$, $\sigma_B$ et qu'ils parient leur $\sigma_J(T_J)$ où $T_J$ est le premier succès obtenu par le joueur $J$, leur succès n'est pas du tout indépendant du couple $\sigma_A,\sigma_B$.

Le fait que les deux permutations soient inverses l'une de l'autre est favorable à leur succès.

La formule de conditionnement sachant le nombre de points fixes de $\sigma_{A} \circ \sigma_B^{-1}$ est sans doute assez jolie.



Edité 1 fois. La dernière correction date de il y a quatre semaines et a été effectuée par marsup.
Re: Petit problème de pile ou face
il y a quatre semaines
@tous
effectivement on ne peut pas choisir les permutations comme on veut, je m'étais trompé là-dessus. Alice et Bob doivent s'entendre sur les permitations choisies à l'avance pour que leurs réponses coïncident et ce sur un pile (environ 1 fois sur 3) pour que la même idée marche.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 244, Messages: 1 507 384, Utilisateurs: 27 667.
Notre dernier utilisateur inscrit Setif.


Ce forum
Discussions: 9 228, Messages: 70 115.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page