Nombre de jet moyen nécessaire pour obtenir PileFaceFace

[GaBuZoMeu]

Quelques petites expériences sur l'espérance du nombre de tirages pour obtenir une suite donnée de P ou F.

J'ai écrit les procédures suivantes en SageMath (c'est presque du python, mais j'ai eu la flemme de tout écrire en python) :

# Inverse le dernier caractère d'une chaîne de P et F

Code: Tout sélectionner

def changeder(S) :
    if S[-1]=="P" : return S[:-1]+"F"
    else : return S[:-1]+"P"

# Calcule la longueur du plus grand segment final de
# la chaîne S qui matche avec le début de la chaîne T

Code: Tout sélectionner

def nbmatch(S,T) :
    n=len(S)
    i=0
    while S[i:]!=T[:n-i] : i+=1
    return n-i

# Calcule l'espérance du nb de tirages pour
# voir apparaître la chaîne S

Code: Tout sélectionner

def EspApp(S) :
    N=len(S)
    M=matrix(QQ,N,N)
    for i in range(N-1) : M[i,i+1]=1/2
    for i in range(N) :
        j=nbmatch(changeder(S[:i+1]),S)
        M[i,j]=1/2
    Un=vector(QQ,N)
    for i in range(N) :
        Un[i]=1
    E=(identity_matrix(QQ,N)-M)^(-1)*Un
    return E[0]

# Produit la liste des chaînes de P ou F de longueur N

Code: Tout sélectionner

def ltiragesPF(N) :
    if N==0 : return [""]
    else :
        prec=ltiragesPF(N-1)
        L=["F"+t for t in prec]+["P"+t for t in prec]
    return L

Voila ce que ça donne pour les chaînes de longueur 7 : à côté de chaque chaîne, l'espérance du nombre de tirages pour la voir apparaître.

[('FFFFFFF', 254),
('FFFFFFP', 128),
('FFFFFPF', 130),
('FFFFFPP', 128),
('FFFFPFF', 134),
('FFFFPFP', 128),
('FFFFPPF', 130),
('FFFFPPP', 128),
('FFFPFFF', 142),
('FFFPFFP', 128),
('FFFPFPF', 130),
('FFFPFPP', 128),
('FFFPPFF', 134),
('FFFPPFP', 128),
('FFFPPPF', 130),
('FFFPPPP', 128),
('FFPFFFF', 134),
('FFPFFFP', 136),
('FFPFFPF', 146),
('FFPFFPP', 128),
('FFPFPFF', 134),
('FFPFPFP', 128),
('FFPFPPF', 130),
('FFPFPPP', 128),
('FFPPFFF', 134),
('FFPPFFP', 136),
('FFPPFPF', 130),
('FFPPFPP', 128),
('FFPPPFF', 134),
('FFPPPFP', 128),
('FFPPPPF', 130),
('FFPPPPP', 128),
('FPFFFFF', 130),
('FPFFFFP', 132),
('FPFFFPF', 138),
('FPFFFPP', 128),
('FPFFPFF', 146),
('FPFFPFP', 132),
('FPFFPPF', 130),
('FPFFPPP', 128),
('FPFPFFF', 130),
('FPFPFFP', 132),
('FPFPFPF', 170),
('FPFPFPP', 128),
('FPFPPFF', 130),
('FPFPPFP', 132),
('FPFPPPF', 130),
('FPFPPPP', 128),
('FPPFFFF', 130),
('FPPFFFP', 132),
('FPPFFPF', 130),
('FPPFFPP', 136),
('FPPFPFF', 130),
('FPPFPFP', 132),
('FPPFPPF', 146),
('FPPFPPP', 128),
('FPPPFFF', 130),
('FPPPFFP', 132),
('FPPPFPF', 130),
('FPPPFPP', 136),
('FPPPPFF', 130),
('FPPPPFP', 132),
('FPPPPPF', 130),
('FPPPPPP', 128),
('PFFFFFF', 128),
('PFFFFFP', 130),
('PFFFFPF', 132),
('PFFFFPP', 130),
('PFFFPFF', 136),
('PFFFPFP', 130),
('PFFFPPF', 132),
('PFFFPPP', 130),
('PFFPFFF', 128),
('PFFPFFP', 146),
('PFFPFPF', 132),
('PFFPFPP', 130),
('PFFPPFF', 136),
('PFFPPFP', 130),
('PFFPPPF', 132),
('PFFPPPP', 130),
('PFPFFFF', 128),
('PFPFFFP', 130),
('PFPFFPF', 132),
('PFPFFPP', 130),
('PFPFPFF', 128),
('PFPFPFP', 170),
('PFPFPPF', 132),
('PFPFPPP', 130),
('PFPPFFF', 128),
('PFPPFFP', 130),
('PFPPFPF', 132),
('PFPPFPP', 146),
('PFPPPFF', 128),
('PFPPPFP', 138),
('PFPPPPF', 132),
('PFPPPPP', 130),
('PPFFFFF', 128),
('PPFFFFP', 130),
('PPFFFPF', 128),
('PPFFFPP', 134),
('PPFFPFF', 128),
('PPFFPFP', 130),
('PPFFPPF', 136),
('PPFFPPP', 134),
('PPFPFFF', 128),
('PPFPFFP', 130),
('PPFPFPF', 128),
('PPFPFPP', 134),
('PPFPPFF', 128),
('PPFPPFP', 146),
('PPFPPPF', 136),
('PPFPPPP', 134),
('PPPFFFF', 128),
('PPPFFFP', 130),
('PPPFFPF', 128),
('PPPFFPP', 134),
('PPPFPFF', 128),
('PPPFPFP', 130),
('PPPFPPF', 128),
('PPPFPPP', 142),
('PPPPFFF', 128),
('PPPPFFP', 130),
('PPPPFPF', 128),
('PPPPFPP', 134),
('PPPPPFF', 128),
('PPPPPFP', 130),
('PPPPPPF', 128),
('PPPPPPP', 254)]

On peut faire un certain nombre de conjectures en voyant cette liste.
Déjà, on constate qu'il faut en moyenne nettement plus de temps pour voir apparaître 7 P (ou 7 F) consécutifs que toute autre chaîne. Ça n'a rien de surprenant.

[lyceen95]

On peut 'qualifier' chaque séquence en lui donnant un handicap.
Notons la chaine abcdefg
Si a<>g, handicap = 0, le temps moyen pour atteindre cette séquence sera court.
Si a=g et ab<>fg, handicap = 1
Si a= g et ab=fg et abc<>efg , handicap = 3
Etc etc.
Avec cette qualification, il y a 4 chaines qui ont un handicap de 7 : PPPPPPP FFFFFFF PFPFPFP et FPFPFPF.
Et ces 4 chaines ont des scores de 254, 254 170 et 170. Nettement plus que les autres chaines.
Pas de handicap de 6 ni 5 ni 4.
handicap 3 : FFFPFFF et FPFFFPF et les 2 symétriques. Scores : 142 et 138

Pour avoir un score bas, il faut avoir un handicap 0 ( 1ère lettre différente de dernière lettre). Mais ça ne suffit pas. On a par exemple les séquences avec abc=efg, mais a<>g, qui ont des scores élevés.

Ce n'est pas abouti, c'est un début de conjecture. Et c'est évident que pour des chaines plus longues la logique serait la même.

Ici, on se limite à des Piles ou Face, ce serait intéressant de regarder la même chose avec des dés : combien de fois faut-il lancer un dé, en moyenne, pour avoir la séquence 1234 ? ou la séquence 1212 ?

[GaBuZoMeu]

On peut calculer effectivement avec des suites de tirages de dés.
Je te laisse modifier les procédures ?

[lyceen95]

Je ne veux pas te priver de ce plaisir.

[GaBuZoMeu]

Non, les jours prochains, j'aurai quelque chose de plus urgent à faire.

[GaBuZoMeu]

Vite fait, je répète ma question :
1°) Quelqu'un a-t-il une démonstration directe que l'espérance du nombre de tirages pour voir apparaître piles consécutifs est ?

D'autres questions, pour préciser les conjectures qu'on peut faire au vu de la liste des espérances de nombres de tirages pour voir apparaître les chaînes de 7 piles ou faces.
La matrice de transition que j'utilise a des états qui sont les segments initiaux de la chaîne dont on guette l'apparition. C'est un peu comme au jeu de l'oie : on progresse d'une case si on a la chance, sinon on revient en arrière. Prenons un exemple, la chaîne 'FFPFFFP'
Partant de '' si on n'a pas de chance on obtient 'P' et on revient à '' : 0
Partant de 'F' si on n'a pas de chance on obtient 'FP' et on revient à '' : 0
Partant de 'FF' si on n'a pas de chance on obtient 'FFF' et on revient à 'FF' : 2
Partant de 'FFP' si on n'a pas de chance on obtient 'FFPP' et on revient à '' : 0
Partant de 'FFPF' si on n'a pas de chance on obtient 'FFPFP' et on revient à '' : 0
Partant de 'FFPFF' si on n'a pas de chance on obtient 'FFPFFP' et on revient à 'FFP' : 3
Partant de 'FFPFFF' si on n'a pas de chance on obtient 'FFPFFFF' et on revient à 'FF' : 2
On obtient ainsi un vecteur de "retours en arrière" [0, 0, 2, 0, 0, 3, 2] qui décrit entièrement la matrice de transition et détermine donc l'espérance du nombre de tirages pour l'apparition. Mes questions :
2°) Quels vecteurs de "retours en arrière" peut-on obtenir ?
3°) Peut-on donner une règle simple qui permet d'obtenir l'espérance à partir du vecteur de "retours en arrière" ? (Par simple, je veux dire différente de la construction de la matrice de transition et du calcul de la première coordonnée du vecteur , où est le vecteur dont toutes les coordonnées valent 1.)

Pour nourrir la réflexion :

('FFFFFFF', [0, 0, 0, 0, 0, 0, 0], 254),
('FFFFFFP', [0, 0, 0, 0, 0, 0, 6], 128),
('FFFFFPF', [0, 0, 0, 0, 0, 5, 0], 130),
('FFFFFPP', [0, 0, 0, 0, 0, 5, 1], 128),
('FFFFPFF', [0, 0, 0, 0, 4, 0, 0], 134),
('FFFFPFP', [0, 0, 0, 0, 4, 0, 2], 128),
('FFFFPPF', [0, 0, 0, 0, 4, 1, 0], 130),
('FFFFPPP', [0, 0, 0, 0, 4, 1, 1], 128),
('FFFPFFF', [0, 0, 0, 3, 0, 0, 0], 142),
('FFFPFFP', [0, 0, 0, 3, 0, 0, 3], 128),
('FFFPFPF', [0, 0, 0, 3, 0, 2, 0], 130),
('FFFPFPP', [0, 0, 0, 3, 0, 2, 1], 128),
('FFFPPFF', [0, 0, 0, 3, 1, 0, 0], 134),
('FFFPPFP', [0, 0, 0, 3, 1, 0, 2], 128),
('FFFPPPF', [0, 0, 0, 3, 1, 1, 0], 130),
('FFFPPPP', [0, 0, 0, 3, 1, 1, 1], 128),
('FFPFFFF', [0, 0, 2, 0, 0, 3, 3], 134),
('FFPFFFP', [0, 0, 2, 0, 0, 3, 2], 136),
('FFPFFPF', [0, 0, 2, 0, 0, 2, 0], 146),
('FFPFFPP', [0, 0, 2, 0, 0, 2, 4], 128),
('FFPFPFF', [0, 0, 2, 0, 2, 0, 0], 134),
('FFPFPFP', [0, 0, 2, 0, 2, 0, 2], 128),
('FFPFPPF', [0, 0, 2, 0, 2, 1, 0], 130),
('FFPFPPP', [0, 0, 2, 0, 2, 1, 1], 128),
('FFPPFFF', [0, 0, 2, 1, 0, 0, 3], 134),
('FFPPFFP', [0, 0, 2, 1, 0, 0, 2], 136),
('FFPPFPF', [0, 0, 2, 1, 0, 2, 0], 130),
('FFPPFPP', [0, 0, 2, 1, 0, 2, 1], 128),
('FFPPPFF', [0, 0, 2, 1, 1, 0, 0], 134),
('FFPPPFP', [0, 0, 2, 1, 1, 0, 2], 128),
('FFPPPPF', [0, 0, 2, 1, 1, 1, 0], 130),
('FFPPPPP', [0, 0, 2, 1, 1, 1, 1], 128),
('FPFFFFF', [0, 1, 0, 2, 2, 2, 2], 130),
('FPFFFFP', [0, 1, 0, 2, 2, 2, 1], 132),
('FPFFFPF', [0, 1, 0, 2, 2, 1, 0], 138),
('FPFFFPP', [0, 1, 0, 2, 2, 1, 3], 128),
('FPFFPFF', [0, 1, 0, 2, 1, 0, 2], 146),
('FPFFPFP', [0, 1, 0, 2, 1, 0, 4], 132),
('FPFFPPF', [0, 1, 0, 2, 1, 3, 0], 130),
('FPFFPPP', [0, 1, 0, 2, 1, 3, 1], 128),
('FPFPFFF', [0, 1, 0, 1, 0, 4, 2], 130),
('FPFPFFP', [0, 1, 0, 1, 0, 4, 1], 132),
('FPFPFPF', [0, 1, 0, 1, 0, 1, 0], 170),
('FPFPFPP', [0, 1, 0, 1, 0, 1, 5], 128),
('FPFPPFF', [0, 1, 0, 1, 3, 0, 2], 130),
('FPFPPFP', [0, 1, 0, 1, 3, 0, 1], 132),
('FPFPPPF', [0, 1, 0, 1, 3, 1, 0], 130),
('FPFPPPP', [0, 1, 0, 1, 3, 1, 1], 128),
('FPPFFFF', [0, 1, 1, 0, 2, 2, 2], 130),
('FPPFFFP', [0, 1, 1, 0, 2, 2, 1], 132),
('FPPFFPF', [0, 1, 1, 0, 2, 1, 3], 130),
('FPPFFPP', [0, 1, 1, 0, 2, 1, 1], 136),
('FPPFPFF', [0, 1, 1, 0, 1, 3, 2], 130),
('FPPFPFP', [0, 1, 1, 0, 1, 3, 1], 132),
('FPPFPPF', [0, 1, 1, 0, 1, 1, 0], 146),
('FPPFPPP', [0, 1, 1, 0, 1, 1, 4], 128),
('FPPPFFF', [0, 1, 1, 1, 0, 2, 2], 130),
('FPPPFFP', [0, 1, 1, 1, 0, 2, 1], 132),
('FPPPFPF', [0, 1, 1, 1, 0, 1, 3], 130),
('FPPPFPP', [0, 1, 1, 1, 0, 1, 1], 136),
('FPPPPFF', [0, 1, 1, 1, 1, 0, 2], 130),
('FPPPPFP', [0, 1, 1, 1, 1, 0, 1], 132),
('FPPPPPF', [0, 1, 1, 1, 1, 1, 0], 130),
('FPPPPPP', [0, 1, 1, 1, 1, 1, 1], 128)

[beagle]

"En attendant beagle"
ne m'attendez pas, avancez ...

[GaBuZoMeu]

Bonjour beagle,

Ça serait gentil de citer la question sans oublier les formules (sinon, ça devient incompréhensible). Tu as le bouton "Citer" qui te permet de faire ça (tu peux couper tout ce que tu ne veux pas citer).

Quelqu'un a-t-il une démonstration directe que l'espérance du nombre de tirages pour voir apparaître piles consécutifs est ?

Je suis sincèrement très intéressé par tes explications (et s'il te plaît, cette fois-ci, pas de cachotteries interminables, merci !).

PS. Si ce message est devenu incompréhensible, c'est à cause de l'effacement par beagle du contenu de son message précédent. Si beagle s'est aperçu que ce qu'il pensait voir n'aboutissait en fait à rien, pourquoi ne pas l'écrire tout simplement ?

[GaBuZoMeu]

En attendant beagle, une petite simulation.

La procédure suivante donne le nombre de tirages à pile ou face pour arriver à voir apparaître la chaîne "But" :

Code: Tout sélectionner

from random import *

def jeu(But) :
    N=len(But)
    Der=""
    for i in range(N) :
        if randrange(2)==1 : Der+="P"
        else : Der+="F"
    nbtir=N
    while Der != But :
        if randrange(2)==1 : Der=Der[1:]+"P"
        else : Der=Der[1:]+"F"
        nbtir+=1
    return nbtir

Elle est écrite en Python3 : tout le monde peut tester.

Et maintenant, voyons. La théorie dit que l'espérance du nombre de tirages pour voir apparaître "PPPPPPP" est . Faisons l'expérience et calculons la moyenne du nombre de tirages pour 1000 jeux, 20 fois de suite :

Code: Tout sélectionner

from statistics import *

for i in range(20) :
    L=[jeu(7*"P") for i in range(1000)]
    print("moyenne :",round(mean(L)),", écart type :",round(stdev(L)))

moyenne : 255 , écart type : 251
moyenne : 245 , écart type : 249
moyenne : 244 , écart type : 241
moyenne : 235 , écart type : 228
moyenne : 262 , écart type : 272
moyenne : 240 , écart type : 228
moyenne : 253 , écart type : 249
moyenne : 269 , écart type : 272
moyenne : 253 , écart type : 247
moyenne : 245 , écart type : 239
moyenne : 261 , écart type : 255
moyenne : 259 , écart type : 256
moyenne : 260 , écart type : 261
moyenne : 262 , écart type : 255
moyenne : 242 , écart type : 229
moyenne : 250 , écart type : 245
moyenne : 247 , écart type : 236
moyenne : 254 , écart type : 258
moyenne : 257 , écart type : 261
moyenne : 257 , écart type : 243

Pas mal. Ça vaudrait aussi le coup de voir ce que prévoit la théorie pour l'écart-type.

[Ben314]

Vite fait, je répète ma question :
1°) Quelqu'un a-t-il une démonstration directe que l'espérance du nombre de tirages pour voir apparaître piles consécutifs est ?

Je sais pas ce que c'est que tu appelle méthode "directe", mais pour obtenir N+1 pile consécutifs, il faut d'abord en faire N puis, si le suivant est un pile, c'est gagné et sinon on est bon pour repartir de zéro.
Si on note l'espérance du nombre de tirages pour voir apparaître piles, ça signifie que qui donne le résultat quasi immédiatement.
Mais ça utilise une récurrence donc je sais pas si c'est du "direct" au sens où tu l'entend . . .

[GaBuZoMeu]

Merci Ben314, c'est effectivement du direct et je m'en veux de ne pas y avoir pensé ! On a effectivement la relation de récurrence qui avec donne sans problème .
Ça résout ma question 1°). Il reste les questions 2°) et 3°).

[Ben314]

Pour la 2) ça semble évident que la fonction de "retour en arrière" ne peut pas être quelconque, mais j'ai pas trop réfléchi pour voir s'il y avait de "fortes contraintes" ou pas (Perso, j'aurais tendance à commencer par regarder si, connaissant , il est possible ou pas de retrouver le mot de départ à permutation 'P'<->'F' prés)

Sinon, pour la 3), c'est de nouveau pas indispensable d'utiliser toute la théorie des processus stochastique pour trouver une méthode rapide de calcul de l'espérance (calcul qui correspond bien sûr à la résolution du système linéaire dont tu parle).
Si on note l'espérance du nombre de tirages nécessaires pour obtenir le mot complet de lettres 'P' ou 'F' sachant qu'on a déjà les premières alors ce qu'on cherche c'est sachant que et que c'est à dire .
On peut légèrement simplifier en écrivant avec puis donc l'espérance cherchée est .

Avec ton exemple de FFPFFFP ça donne
où, par exemple,
Vu la formule de récurrence, on a plus ou moins l'impression que si on écrit l'espérance cherchée en base 2 les digits vont être liés au différents , mais je ne suis pas allé regarder de plus prés pour trouver le lien et voir si c'est plus rapide que le bête calcul récursif çi dessus...