Simple comme les pb de pile ou face

[ortollj]

Cet apres midi j’ai lu un article etonnant de mathematique.qui ne neccessite quasi aucune connaissances mathematiques préalable.
Il faut juste un peu quelques efforts pour comprendre(enfin pour moi tout du moins !), avec un crayon et un papier, pour refaire les calculs tout seul, mais on a rien sans rien.
Je vous conseille cet article (les abonnés de « pour la science », peuvent recupérer le pdf sur le site de « pour la science »). 2 extraits ci-dessous.

L’algorythme (voir ci-dessous)trouvé par John Horton Conway est tout aussi etonnant !.

http://fr.wikipedia.org/wiki/John_Horton_Conway

Les surprises du jeu de pile ou face
Les erreurs de nos jugements spontanés sont parfois étonnantes.
Le hasard créé par les lancers d’une pièce de monnaie en est l’exemple
le plus frappant : tout y semble paradoxal.
Jean-Paul DELAHAYE
146] Logique & calcul © Pour la Science - n° 409 - Novembre 2011

Voici quelques extraits ci-dessous
Les suites de piles ou faces obtenues
avec une pièce non truquée
nous semblent sans grand
mystère et nous ne doutons
guère de nos prédictions statistiques. Ce
faisant, nous ignorons une multitude de
subtilités, ignorance qui nous conduit à l’erreur,
voire nous ferait perdre de l’argent
en cas de paris. Comprendre pourquoi et
tirer toutes les leçons des pièges tendus à
la raison par ces suites de tirages équitables
et indépendants est un travail délicat et difficile
comme l’attestent les dizaines d’articles
publiés depuis 40 ans sur ce sujet.
Un premier exemple de piège, dont l’idée
a été proposée en 1969 par l’amateur de
récréations mathématiques Walter Penney,
consiste à lancer une pièce de monnaie
(non truquée) autant de fois qu’il le
faut jusqu’à obtenir des séquences de piles
ou faces fixées à l’avance. On cherche par
exemple à obtenir la séquence pile-face,
notée PF, ou face-face, notée FF. La question
posée est: laquelle a le plus de chances
de se présenter en premier, et combien estil
raisonnable de parier sur elle ?
Raisonnement A. Considérons deux
tirages successifs d’une pièce de monnaie;
il y a autant de chances d’obtenir PF que FF,
et cette probabilité est (1/2)2 = 1/4. Les
deux séquences PF et FF étant équiprobables,
chacune a la même probabilité de
sortir en premier, et la probabilité que PF
survienne avant FF est donc 1/2. Les
deux séquences mises en compétition partant
sur des bases égales, si l’on nous propose
de parier, nous pouvons choisir indifféremment
l’une ou l’autre et miser 1 euro
contre 1 euro.
Or la réalité est bien différente : dans
une compétition entre PF et FF, la séquence
PF gagnera trois fois sur quatre. Il est
donc intéressant d’accepter de miser
2 euros pour PF contre 1 euro en faveur de
FF ; un pari ne favorisant aucun joueur
consiste à miser 3 euros pour PF contre 1
pour FF. Voici la démonstration de ces
affirmations.
Raisonnement B. Les deux premiers
tirages peuvent être PF, FP, PP ou FF. Ces
quatre débuts possibles sont équiprobables,
chacun survenant avec une probabilité 1/4.
Si c’est FF qui sort, la séquence FF aura gagné
la compétition. Dans les trois autres cas, la
gagnante sera toujours PF. En effet, dès qu’un
P tombe, FF ne peut plus sortir avant PF :
tant que des P continuent de tomber, aucune
ne gagne, et dès que F tombe, PF gagne. Si
l’on vous propose ce jeu, choisissez PF: vous
gagnerez trois fois sur quatre.
Où est l’erreur dans le raisonnementA?
Sa première phrase est indubitable. Elle
implique d’ailleurs que dans une longue
séquence de P ou F tirée avec une pièce de
monnaie non truquée, il y aura en moyenne
autant de couples PF que de couples FF.
L’erreur est dans la seconde phrase: «Les
deux séquences PF et FF étant équiprobables,
chacune a la même probabilité d’être obtenue
en premier, et donc, la probabilité que
PF survienne avant FF est 1/2. » En effet,
même si les deux séquences sont équiprobables,
les relations qu’elles entretiennent,
comme le détaille le raisonnement B, ont
pour conséquence que dès qu’un P est tombé,
FF ne peut plus gagner, ce qui entraîne
alors que la séquence PF apparaîtra en premier
trois fois plus souvent que FF.
Le même type de blocage d’une
séquence par une autre montre que si l’on
oppose PFF à FFF, la première séquence
gagne sept fois sur huit. Plus généralement,
si l’on oppose PF...F ((n – 1) fois F)
à FF...F (n fois F), alors la première
séquence gagne (2n–1) fois sur2n : nous
ne devons donc pas hésiter à parier
1 000 euros contre 1 euro en choisissant
PFFFFFFFFF contre FFFFFFFFFF.
Si votre doute persiste, opérez un
contrôle expérimental avec une pièce de
monnaie, en programmant une simulation
avec votre ordinateur ou encore en
associant P aux décimales impaires de _
et F aux décimales paires (voir la série illustrée
ci-dessus et ci-contre). Dans ce dernier
cas, vous pouvez commencer la série


John Conway a conçu un algorithme qui,
sans utiliser la méthode des graphes d’états,
indique le résultat des confrontations d’une
séquence contre une autre et cela quelles que
soient leurs complexités et leurs longueurs.
Considérons par exemple les séquences
A = PFPP et B = PPFF.
Plaçons A au-dessus de B:
A PFPP
B PPFF
Si les séquences coïncident, écrivons 1 sur les
séquences ; sinon, écrivons 0, comme c’est le
cas ici :
0
A PFPP
B PPFF
Comparons maintenant les trois derniers symboles
de la première séquence (FPP) avec les trois
premiers de la seconde (PPF). Si ces sousséquences
coïncident, on ajoute un 1, sinon un 0:
00
A PFPP
B PPFF
On compare les deux derniers symboles (PP) de
la première séquence avec les deux premiers de
la seconde (PP), etc. Nous obtenons finalement :
0011 = 3
A PFPP
B PPFF,
la suite de 0 et de 1 étant lue comme un entier
en base 2. C’est la clef de A par rapport à B; on
la note Clef (A, B). Ici, Clef (A, B) = 3. Le rapport
de la probabilité que B gagne sur la probabilité
que A gagne est alors donné par :
[Clef(A, A) – Clef(A, B)]/[Clef(B, B)–Clef(B, A)].
L’application de l’algorithme de Conway donne :
0011 = 3 1001 = 9 0000 = 0 1000 = 8
A PFPP A PFPP B PPFF B PPFF
B PPFF A PFPP A PFPP B PPFF
Clef (A, A) – Clef (A, B)) = 6
Clef (B, B) – Clef (B, A))= 8.
Ainsi, B = PPFF gagne six fois quand A=PFPP
gagne huit fois. Autrement dit, la probabilité
de gain de A contre B est : 8/(6 + 8) = 4/7
Autre exemple : A = PFP, B = PPF.
001 = 1 101 = 5 010 = 2 100 = 4
A PFP A PFP B PPF B PPF
B PPF A PFP A PFP B PPF
Clef (A, A) – Clef (A, B)) = 4
Clef (B, B) – Clef (B, A))= 2.
Donc B = PPF gagne quatre fois quand
A = PFP gagne deux fois. Dit autrement, la probabilité
de gain de Acontre B est: 2/(2 + 4)=1/3.
Le fait que cet algorithme fonctionne correctement
est bien sûr difficile à démontrer, mais
cela a été fait de plusieurs manières.
Autre miracle de l’algorithme de Conway :
le nombre 2 Clef(A, A) est le temps moyen d’attente
de la séquence A. Cela permet de vérifier
les résultats de l’encadré 1, qui indiquaient que
le temps moyen d’attente de FF est 6 et que celui
de PF est 4.
4. L’algorithme magique de John Conway
_

[bauzau]

Pas mal du tout!