Nombre de faces successifs

[Vassillia]

Bonjour à tous,
Ma dernière question sur les boules arc-en-ciel n'ayant pas eu de succès, je retente ma chance avec une thématique ayant eu plus de succès

On fixe le nombre de lancers d'une pièce équilibrée.
Quelle est la probabilité d'avoir une suite d'au moins faces successifs ?
Que peut-on dire sur la longueur de la plus grande suite de faces successifs ?

Comme d'habitude, toute autre question qui vous parait pertinente...ou pas d'ailleurs

[Vassillia]

Je précise pour notre nemesis des mathématiciens et pour d'autres si ce n'était pas clair. Mes questionnements portent sur avoir une suite d'au moins faces successifs n'importe où entre le 1er lancer et le nième lancer avec

Pour une fois qu'il dit quelque chose de vrai, je recopie sa réponse car il a résolu avec succès le cas où . La probabilité que les premiers lancers soient face est bien sur . Bravo, dommage pour la suite sur le rattrapage du retard mais je vais faire comme si je ne l'avais pas vu.

[hdci]

Bonsoir,
A priori, je dirais : probabilité d'avoir les k premiers lancers "faces" et on se fiche des derniers lancers (puisque c'est "au moins k faces") ; plus l a probabilité d'un "pile" suivi de k "faces", plus..., plus (n-k) "piles" suivi de k "faces".

Comme on est en équiprobabilité, cela fait la somme*

[Vassillia]

C'est une première approche mais il te manque pas mal de configurations selon moi.

Pour avoir au moins 2 faces sucessifs, pourquoi on ne pourrait pas avoir FPFF... par exemple ? Tu considères que dès que tu as face pour la première fois, tu vas directement tomber sur une "bonne suite avec k faces" mais ce n'est pas obligatoire.

[hdci]

Effectivement, je suis allé un peu top vite.

[GaBuZoMeu]

Bonjour,

On peut encore mettre des chaînes de Markov absorbantes là-dedans : k+1 états 0F, 1F, ..., kF avec probabilité de transition
depuis iF si i<k : 1/2 pour 0F, 1/2 pour (i+1)F
depuis kF : 1 pour kF (état absorbant).

PS. Il serait plus moral de noter >=kF l'état absorbant.

[hdci]

Après un peu plus de réflexion : si n<=2k, voilà où j'en suis arrivé : il suffit de modifier mon approche initiale (qui était j "piles" suivi de au moins k "faces", addition sur j) en j-2 "quelconque", suivi de 1 "pile", suivi de k "faces" ; en effet, j étant inférieur ou égal à k puisque n<=2k, il suffit d'avoir un pile juste avant la séquence de k faces consécutives pour caractériser une séquence de k faces au moins commençant à la jème position.

Dans cette situation, la probabilité est donc, avec j = position de la série initiale de k "faces"

• pour j=1 : (évidemment il n'y a rien "avant", donc pas de j-2 "quelconque" et pas de "1 pile"
• pour j=2 : le premier pile, suivi de k face, donc
• pour j=3 : le premier quelconque, le second pile, suivi de k faces donc à nouveau
• etc.
• pour j=n-k+1, à nouveau j-2 quelconques suivi de 1 pile et de k faces, donc à nouveau

Ce qui donne finalement


Si n=2k+1 on peut ajouter, pour le cas où la séquence de k arrive au (k+1)ème lancer, le fait que les k premiers lancers ne doivent pas contenir k "faces", ce qui correspond à une probabilité de qui multiplie la probabilité d'avoir ensuit un pile puis k faces et la probabilité devient alors



... Pas le temps aujourd'hui de poursuivre...

[Vassillia]

@GaBuZoMeu, j'aurai parié que si tu t’intéressais au problème, on aurait le droit à des chaines de markov absorbantes Je suis tout à fait d'accord sur le principe, je ne suis pas certaine que ce soit la méthode plus simple mais comme j'aime bien alors...

@hdci, ton idée est bonne, c'est plus ou moins comme cela que je faisais aussi initialement. Pour l'utiliser avec , on peut essayer de trouver une récurrence sur une suite qui dépend de et .

[GaBuZoMeu]

Vassilia, tu n'es pas certaine que c'est la méthode la plus simple ou tu es certaine que ce n'est pas la méthode la plus simple ?

Question : on oublie qu'on joue en n coups et on se demande l'espérance du temps d'attente pour obtenir k faces de suite (ça a sans doute été déjà discuté, sur ce forum ou un autre).

[Vassillia]

Tout dépend du point de vue : tant que c'est toi qui rentres la matrice et calcules les puissances, c'est suffisamment simple pour moi comme je n'ai rien à faire
Blague à part, la formule de récurrence est très facile à programmer en récursif mais tu pourras me rétorquer que je ne te donne pas la valeur directement.

Pour répondre à ta question, je vais ressortir l'algorithme de Conway, chacun sa marotte L’espérance du temps d'attente est donc

Je le rappelle pour mémoire

une première suite
une deuxième suite
pour tout entier de à alors si et sinon
est écrit en base 2 qu'on transforme ensuite en base 10
P( gagne devant ) =
Avec comme info gratuite =temps moyen d'attente de la séquence

[GaBuZoMeu]

Pour ne pas me fatiguer, je code en SageMath :

Code: Tout sélectionner

def TransMat(k) :
    P = matrix(QQ,k+1,k+1)
    for i in range(k) :
        P[i,0] = 1/2 ; P[i,i+1] =1/2
    P[k,k]=1
    return P

def ProbaSuite(k,n) :
    p=(TransMat(k)^n)[0,k]
    pre=RR(p)
    print("La probabilité d'avoir une suite d'au moins {0} faces successifs\n\
en {1} tirages est de {2}, soit environ {3:.2%}".format(k,n,p,pre))
   
def EspLonMax(n) :
    s=0
    for k in range(n) :
        s += (TransMat(k+1)^n)[0,k+1]
    sre=RR(s)
    print("L'espérance de la longueur maximale d'une suite de faces successifs\n\
en {0} tirages est {1}, soit environ {2:.2f}".format(n,s,sre))

et je fais travailler mon esclave numérique, par exemple :
La probabilité d'avoir une suite d'au moins 7 faces successifs
en 50 tirages est de 11634300868893/70368744177664, soit environ 16.53%
L'espérance de la longueur maximale d'une suite de faces successifs
en 50 tirages est 2818601410768169/562949953421312, soit environ 5.01

[Vassillia]

Joli code, ton esclave personnel se laisse convaincre en peu de lignes surtout sans formation préalable au calcul matriciel ! Je ne sais pas si je vais réussir à le persuader de se révolter en lui promettant une charge de travail moindre mais je lui propose :

Soit la probabilité d'avoir au moins faces successifs parmi lancers
alors
pour alors
alors

Ce n'est rien d'autre que l'idée de hdci un peu généralisée :
- soit j'ai une suite d'au moins faces successifs dans les premiers lancers donc proba
- soit je dois attendre les derniers lancers pour avoir cette fameuse suite. Je finis par 1 pile puis faces successifs donc proba . Le tout après l'événement ne pas avoir eu au moins faces successifs dans les lancers précédents donc proba

Tu es d'accord avec mon calcul d’espérance de temps d'attente ? C'est surement trouvable aussi avec les matrices mais à première vue, cela m'a l'air plus pénible.
Pour la longueur de la plus grande suite, une équivalence en peut-être ?

[GaBuZoMeu]

Jolie formule de récurrence. Je comparerai plus tard les temps d'éxécution.

En attendant, une petite simulation :

Code: Tout sélectionner

def Simul(k,n) :
    nb=0
    for i in range(n) :
        tirage=randrange(2)
        if tirage==1 :
            nb += 1
            if nb >= k : return 1
        elif tirage==0 :
            nb = 0
    return 0

def Simuls(k,n,p) :
    succ = 0
    for i in range(p) :
        succ += Simul(k,n)
    return succ

J'ai fait 20 fois 1000 simulations de séries de 50 tirages en comptant les succès (au moins 7 faces successifs). Voici les résultats :
[180, 165, 171, 155, 169, 142, 172, 151, 160, 164, 181, 179, 177, 167, 174, 164, 156, 166, 177, 186]
Moyenne du nombre de succès : 167.8
Écart-type : 10.9

[Vassillia]

Pas surprenant vu la valeur théorique calculée précédemment. Je n'avais aucun doute ni sur le fait que les chaines de Markov font le job ni sur ton implémentation.
Je retrouve évidemment la même valeur théorique avec la récursivité :

Version Python

Code: Tout sélectionner

def P(k,n) :
    if n<k : return 0
    if n==k : return 1/2**k
    if n>k : return P(k,n-1)+(1-P(k,n-k-1))/2**(k+1)   
print (P(7,50))

Version C++

Code: Tout sélectionner

#include <stdio.h>
#include <math.h>

double P(int k, int n)
{
    if (n<k)
        return 0;
    if (n==k)
        return 1/exp2(k);
    if(n>k)
        return P(k,n-1)+(1-P(k,n-k-1))/exp2(k+1);
} 

int main()
{
    double p=P(7,50);
    printf("%f ",p);
    return 0;
}

C'est l'avantage des mathématiques, comme on ne peut pas faire "comme on veut", les résultats sont cohérents. Si quelqu'un conteste, qu'il publie son code, je m'adapte au langage choisi

[GaBuZoMeu]

J'ai mesuré les temps d'éxécution pour calculer la probabilité d'avoir une suite d'au moins 9 faces successifs en 100 tirages, avec mon code et avec le tien. On trouve le même résultat bien sûr, mais les temps d'exécution sont sensiblement différents :



J'ai déjà rencontré plusieurs fois ce problème avec les algorithmes récursifs : si on ne fait pas gaffe, ça explose.

[Vassillia]

Effectivement, tu gagnes largement, c'est indiscutable
Je n'ai pas optimisée puisque je calcule plusieurs fois les mêmes valeurs mais à ce point, ton esclave numérique va m'en vouloir. Si je voulais t'embetter, je te demanderai quand même une démo de l’espérance du temps d'attente avec les matrices.

Pour les simulations, le code C++ de Dlzlogic est, pour moi, publiable sans problème. Il est correct (j'ai juste enlevé ce qui ne sert à rien, rajouté les librairies qui vont bien, et remplacé le fameux affichage par une impression de la liste de valeurs)

Code: Tout sélectionner

#include<stdlib.h>
#include <stdio.h>

int main()
{
  int P7Face[20];
  for (int fois=0; fois<20; fois++)
  {
    int NbP=0;
    for (int i=0; i<1000; i++)
    {
      int nbF=0;
      for (int t=0; t<50; t++)
      {
        int r=rand()%2;
        if (r == 0)
        {
          nbF++;
          if (nbF >= 7)
          {
            NbP++;
            break;
          }
        }
        else nbF=0;
      }
    }
    P7Face[fois]=NbP;
    printf("%d ",NbP);
  }
//  AfficheNormale(20, P7Face, "\n Nombre de suite de 7 faces ");
  return 0;
}

J'ai testé :
166 176 170 159 152 157 181 190 169 161 184 151 152 151 169 175 160 160 176 182
moyenne du nombre de succès 167,1
ecart-type 11,7

Mais revenons à nos moutons, il reste la longueur de la plus grande suite, en cela donne quoi ?

[GaBuZoMeu]

Si je voulais t'embetter, je te demanderai quand même une démo de l’espérance du temps d'attente avec les matrices.

Tu ne m'embêtes pas, puisqu'il me suffit de te redonner le lien
https://www.idpoisson.fr/berglund/probamass_html/node18.html

Mais revenons à nos moutons, il reste la longueur de la plus grande suite, en cela donne quoi ?

Tu veux un équivalent de l'espérance de la longueur de la plus grande suite de faces en n tirages, en termes n, quand n tend vers l'infini, c'est ça ? Je ne sais pas, pas d'idée qui me vienne à la seconde.

[Vassillia]

Oui, je sais que tu vas calculer la somme des valeurs de la première ligne de avec la matrice carré de taille qui a des 0 partout sauf des 1/2 dans la première colonne et des 1/2 juste à droite de la diagonale.
C'est peut-être trivial pour toi les coefficients de cette matrice mais pour moi nettement moins. Sans l'avoir écrit proprement, j'ai l'impression qu'on va avoir les puissances de 2 dans la première ligne et donc la somme va bien redonner ce que je proposais précédemment mais je dis cela un peu à l'intuition. J'avais essayé de le faire vraiment et de manière générale pour retrouver la formule de Conway mais j'ai abandonné en cours de route.

Tant pis pour l’espérance,
Si on appelle l(n) la longueur de la plus longue suite de faces successifs obtenus en n lancers, est-ce qu'on peut trouver f tel que l(n)/f(n) tend vers 1 avec une probabilité 1 ?

[GaBuZoMeu]

Une façon assez directe d'accéder à l'espérance du temps d'attente de la suite de faces :
Je note l'espérance du temps d'attente de la suite de faces en partant d'une situation où les derniers tirages ont été des faces, mais pas les derniers, ceci pour . Alors on a :

d'où l'on tire :

[Vassillia]

Merci à toi, en plus, on peut changer en avec qui revient au bon endroit pour les autres cas de figures. Cela donne forcément la méthode que je connaissais.
Sinon, normalement, on devrait avoir qui tend vers 1 avec une probabilité de 1.