Problème de Math (probabilités)

[jgricourt]

Bon je vois que certains ont bien cogité depuis cette nuit

 

Bruno a donné un moyen de calculer cette proba par une suite de fibonacci mais sans réellement démontrer le résultat (enfin j'ai pas encore vérifié la formule que tu as trouvé sur le site). Je vais tenter d'exposer ma propre démonstration qui rejoint le résultat déjà donné. Pour y arriver il faut à première vue passer par le dénombrement des suites de 1000 lancés contenant au moins 10 faces consécutives. Mais prenons le pb autrement et considérons le dénombrement des suites de 1000 lancés ne contenant pas de séquence de 10 tirage identiques donc soit 10 faces ou soit 10 piles consécutifs et notons ce dénombrement S1000.

 

Considérons le sous ensemble des suites définit plus haut et se terminant par PF ou FP il s'agit alors d'un ensemble de suite de 999 lancés dénombré par S999. Faisons de même pour le sous ensemble des suites définit plus haut et se terminant par PFF ou FPP il s'agit alors d'un ensemble de suite de 98 lancés dénombré par S998. On poursuit l'analyse jusqu'à dénombrer l'ensemble des suites se terminant par PFFFFFFFFF ou FPPPPPPPPP qui est un ensemble de suite de 91 lancés dénombré par S991. On arrête le schéma là car sinon on aurait des suites de 10 pile ou 10 faces consécutifs. Par construction ces 9 sous ensembles sont tous disjoints entre eux et lorsqu'on les unifie ils forment l'ensemble complet dénombré initialement par S1000. Sans surprise nous pouvons donc écrire la chose suivante:

 

S1000 = S999 + S998 + S997 + S996 + S995 + S994 + S993 + S992 + S991

 

Si on généralise ce raisonnement en prenant en compte n lancés ne contenant pas de séquence de 10 tirage identiques on obtient:

 

Sn = Sn-1 + Sn-2 + Sn-3 + Sn-4 + Sn-5 + Sn-6 + Sn-7 + Sn-8 + Sn-9

 

Maintenant tentons de mettre en pratique cette récurrence permettant de proche en proche de déterminer S1000. Pour cela commençons par calculer chacune des quantités S en partant de 1.

 

S1 = 2 ici toutes les suites de 1 lancé ne contenant pas de séquence de 10 tirages identiques

S2 = 4 ici toutes les suites de 2 lancé ne contenant pas de séquence de 10 tirages identiques

S3 = 8 ici toutes les suites de 3 lancé ne contenant pas de séquence de 10 tirages identiques

...

S9 = 512 ici toutes les suites de 9 lancé ne contenant pas de séquence de 10 tirages identiques

 

Donc rien de bien compliqué car on prend tous les cas possibles à chaque fois vu l'impossibilité de former une suite de 10 tirage identiques sur un nombre de lancé inférieur à 10. Ensuite pour déterminer S10 il suffit alors d'utiliser la formule générale (la suite récurrente) trouvée plus haut.

 

S10 = S9 + S8 + S7 + S6 + S5 + S4 + S3 + S2 + S1

 

Par récurrence et donc de proche en proche on arrivera à trouver la valeur de S1000 ! Un petit programme informatique va nous aider à trouver la valeur.

 

Mais avant cela retournons aux probabilités le sujet de la question. La probabilité notée Pinv(n) de ne pas trouver une série consécutive de 10 tirage identiques dans n lancés s'écrit de la manière suivante:

 

Pinv(n) = Sn / 2^n où 2^n représente tous les cas de figure possibles de suites de n lancés

 

La probabilité P(n) de trouver au moins une série consécutive de 10 tirages identiques dans n lancés est le complément de la probabilité Pinv(n) de ne pas trouver une série consécutive de 10 dans n lancés. Or l'addition des deux donne forcement 1:

 

P(n) + Pinv(n) = 1

P(n)= 1 - Pinv(n)

 

Donc en combinant les deux derniers résultats on obtient:

 

P(n)= 1 - Sn / 2^n

 

Pour enfin avoir la probabilité Pface(n) de trouver au moins une série consécutive de 10 'face' dans n lancés il faut diviser se résultat par deux sachant que il y a autant de chance de tomber sur une série de 10 'face' consécutifs que de tomber sur une série de 10 'pile' consécutifs.

 

Pface(n) = P(n)/2

Pface(n) = (1 - Sn / 2^n)/2

 

Je ferais un petit programme en C pour faire le calcul si toutefois mes enfants veulent bien faire la sieste pendant ce temps parce que là c'est le bazar !

 

 

Edit: si on avait pris en compte dans l'énoncé que 10 'face' consécutifs exactement on aurait une solution plus simple qui consiste à diviser la combinaison C(n=1000,p=10) par 2 puissance 1000.

['Bruno]

J'y pige rien aux probas[...]

La suite de ton message le prouve... (Argh, le coup bas... )

 

Essayez voir pour le loto, vous verrez que vous tombez sur une proba si faible qu'on aurait un gagnant tous les dix ans.

Tu confonds probabilité et espérance. Si 1 million de personnes jouent à un jeu pour lequel ils ont 1 chance sur 1 million de gagner, l'espérance sera de l'ordre de 1 (ça dépend de la loi de probabilité).

 

M'étonnerait beaucoup qu'on retombe sur ce qu'on observe.

Je suis persuadé qu'on retombe exactement sur ce qu'on observe.

 

---------

Concernant le problème initial, Estonius a donné la solution.

 

Bruno a donné un moyen de calculer cette proba par une suite de fibonacci

Non, non, j'ai juste appliqué bêtement et sans le vérifier la formule de l'article cité par Estonius. (Dans les essais que j'avais fait hier en pure perte, j'avais essayé par récurrence,; mais en commenceçant du début. Ton idée de commencer par la fin est bien plus intéressante et donne une démonstration rapide !)

[Leimury]

Bonjour,

 

A l'IUT on avait un chef de département qui s'y connaissait encore moins.

Il était également prof de RDM et d'info (oula ! ça foutait les chtons) entre autre.

Ce #!@ prenait les notes des étudiants, ce qui représente une population de l'ordre de 100 personnes (moins en fait) et il traficotait le barème pour avoir une courbe de gauss parfaite.

 

Quant tu passais le contrôle, une question vallait 4 point.

Une fois tout le toutim retouché si tout le monde avait réussi elle n'en vallait plus que 3.07 et c'est la question à 1 point qui passait à 2.23.

 

Un de mes collègues avait posé la question au prof de maths. Sa réponse ?

Un sourire avec cette phrase: Mais c'est n'importe quoi, Gauss ne s'applique pas à un échantillon de cette taille

 

Avantage: personne pouvait avoir 0.

C'était tout de même étrange de se retrouver avec un 14,751423

 

Oh Mulhousiens, Mr R sévit il encore à l'IUT ?

 

Ce genre de traficotage vous dégoutte des probas et des stats à vie.

 

Bon ciel

[Mathed]

Sur une sequence de 10 lancés consécutifs il y a 0.5x0.5x0.5x0.5x0.5x0.5x0.5x0.5x0.5x0.5 de chance que le même coté de la piece soit retourné,soit1/2 exposant 10.

 

Or sur 1000 lancés il y a 991 séquences de 10.

 

-1,2,3,4,5,6,7,8,9,10

-2,3,4,5,6,7,8,9,10,11

...............................

-990,991,992,993,994,995,996,997,998,999

-991,992,993,994,995,996,997,998,999,1000.

 

Donc la probabilité qu'il y ait 10 rétournés identiques consécutifs ne serait-elle pas ( 0.5 exposant 10) X 991?

[jarnicoton]

je ne suis pas aller en bac S

 

Tu n'as pas dû non plus allé en bac L ?

 

(et encore un coup bas)

['Bruno]

Mathed : il y a peut-être 991 suites de 10, mais il y a beaucoup, beaucoup plus de séquences de 1000 lancers contenant ces 991 suites. Par exemple avec la suite 1-2-...-10, on peut avoir face aux 10 premiers lancers puis pile-face-pile-face-..., ou bien face aux 10 premiers lancers puis pile-pile-face-face-pile-pile-face-face-..., ou encore de nombreuses autres possibilités. Et ce pour chacun des 991 suites de 10 possibles.

 

En outre, on a le droit d'avoir plusieurs suites de 10 dans la série des 1000 lancers. C'est beaucoup plus compliqué !

 

De toute façon la solution donnée par Estonius est forcément la bonne puisqu'elle provient d'un site professionnel (à moins qu'une erreur ait échappé à la communauté des mathématiciens évidemment...)

[pas03410]

Tu n'as pas dû non plus allé en bac L ?

 

(et encore un coup bas)

 

Tu n'as pas dû non plus aller .....

Re coup bas:p

[jgricourt]

Bon ben finalement pas eu le temps de coder le calcul de ma solution pour cause de festival de Jazz à Vienne ce soir (Herbie Hancock / Wayne Shorter / Marcus Miller ... non vous avez bien lu je ne délire pas). Je repasserai donc demain.

[astrogaro]

Tu n'as pas dû non plus allé en bac L ?

 

(et encore un coup bas)

 

ça aurait pu le faire si il n'y avait pas de faute mais là ça casse le mythe

 

EDIT : grillé j'avais pas vu le :

Tu n'as pas dû non plus aller .....

Re coup bas

[jarnicoton]

MM. pas03410 et astrogaro, j'ai l'impression que vous êtes un peu naïfs...

[pas03410]

MM. pas03410 et astrogaro, j'ai l'impression que vous êtes un peu naïfs...

 

Oui, probablement. Coup bas haut placé et subtil donc;)

[astrogaro]

MM. pas03410 et astrogaro, j'ai l'impression que vous êtes un peu naïfs...

 

Tu dis ça parce que t'es énervé d'avoir fait une faute, et que tu veux faire croire qu'elle est volontaire c'est tout

[jgricourt]

Je reviens avec le résultat final donc je reprends la question initiale pour ceux qui auraient oublié de quoi il s'agissait

 

Sur 1000 lancé quelle est la probabilité pour qu'il y ait au moins une fois 10 'faces' consécutifs ?

 

31 % environ (31.1935 plus exactement).

 

Pour la démonstration complète voir mon poste précédent et voici le petit programme qui a permis de le calculer ci-dessous:

 

#include <iostream>
#include<math.h>

using namespace std;

int main(int argc, char *argv[]) {
 int nombre_lance = 1000;
 double s[nombre_lance];

 for (int i=0; i<9; i++) {
   s[i] = pow(2, i+1);
 }

 for (int i=9; i<nombre_lance; i++) {
   s[i] = s[i-1] + s[i-2] + s[i-3] + s[i-4] + s[i-5] + s[i-6] + s[i-7] + s[i-8] + s[i-9];
 }

 double proba = 1.0 - s[nombre_lance-1] / pow(2, nombre_lance);

 cout << "pface=" << (proba / 2.0)*100.0 << "%" << endl;
}

 

PS: Bruno tu as juste oublié de diviser par 2 le résultat car sur la page de matheux que tu as trouvé il est écrit: "The probability that no runs of k consecutive tails will occur in n coin tosses" donc ils n'ont pas choisi pile ou face mais les deux en fait et comme les chances sont équiprobables ...

[Lolo]

Considérons la fonction f de deux variables telles que f(n,k) représente la probabilité qu'une série d'exactement n lancés consécutifs se termine par une série d'exactement k lancés face et ne possède aucune sous-série de 10 lancés face consécutifs.

 

La réponse qu'on cherche est alors 1-f(1000,0)-f(1000,1)-f(1000,2)-...-f(1000,9).

 

De plus, pour tout entier n au moins égal à 1, nous avons l'égalité f(n+1,k+1)=f(n,k)/2 pour chaque valeur de k dans l'ensemble {0,1,2,...,8}, et l'égalité f(n+1,0)=[f(n,0)+f(n,1)+f(n,2)+...+f(n,9)]/2.

 

En rajoutant en plus les dix conditions initiales f(1,0)=f(1,1)=1/2 et f(1,2)=f(1,3)=...=f(1,9)=0, on a réduit le problème à un système de dix équations récurrentes linéaires d'ordre 1. Il existe des méthodes algébriques générales pour résoudre cela.

 

Première méthode : par calcul matriciel.

On note V(n) le vecteur colonne (f(n,0),f(n,1),f(n,2),...,f(n,9)). Il existe alors une matrice carré A de taille 10 telle que V(n+1)=A V(n). Cette matrice est facile à écrire à partir des systèmes linéaires plus haut (c'est leur traduction matricielle) et ne comporte presque que des coefficients égaux à 0 ou à 1/2. On a alors V(1000)=A^999 V(1). Pour faire le calcul de A^999, on peut passer par une diagonalisation de la matrice A. C'est assez long à calculer, mais c'est connu (et il n'est pas exclu qu'il y aura des polynomes difficiles à factoriser).

 

Seconde méthode : en se ramenant directement à une unique équation récurrente linéaire d'ordre 10.

['Bruno]

Jgricourt : tu es sûr qu'il faut diviser par 2 le résultat de la page citée par Estonius ? Car "tail" signifie face (pile ou face = heads or tails).

[jgricourt]

Jgricourt : tu es sûr qu'il faut diviser par 2 le résultat de la page citée par Estonius ? Car "tail" signifie face (pile ou face = heads or tails).

 

Ben tu as peut être raison mais alors je vois pas pourquoi ce résultat vaudrait exactement le double selon ta formule ...

[Wincy]

Il faut diviser par deux (multiplier par 0.5 en faite) si on inclus une condition, càd 10 faces consécutives piles ou 10 faces consécutive face.

 

Là, pile ou face peut importe du moment que c'est 10 faces consécutives

[Toutiet]

C'est marrant, tout le monde "blablatte" mais je ne vois pas encore de convergence vers la bonne réponse à la question initiale posée...

[Lolo]

C'est marrant, tout le monde "blablatte" mais je ne vois pas encore de convergence vers la bonne réponse à la question initiale posée...

 

J'ai expliqué la réponse ci-dessus. On a la réponse exacte, même si ce n'est pas sous une forme simplifiée. C'est un peu lourd niveau calcul, mais conceptuellement, c'est fini.

 

Soit A la matrice carrée de taille 10 dont l'élément de la ligne i et de la colonne j vaut 1/2 si i=1 (première ligne) ou i=j+1 (diagonale juste en dessous de la diagonale principale) et 0 dans tous les autres cas.

 

On calcule A^999 puis on multiplie cette matrice par le vecteur colonne (1/2,1/2,0,0,0,0,0,0,0,0). On obtient un vecteur. On déduit de 1 la somme des éléments de ce dernier vecteur et on a la réponse finale.

[Lolo]

Pour illuster que cela marche sans faire trop de calcul, je propose de faire explicitement le calcul dans le cas d'une série de 2 lancés face consécutifs à obtenir (au lieu de 10) dans une série de 5 lancés en tout (au lieu de 1000).

 

On applique d'baord la méthode que j'ai donnée. Dans ce cas, la première ligne de la matrice A est (1/2,1/2) et sa seconde ligne est (1/2,1/2). On doit calculer A^(5-1) et l'appliquer au vacteur colonne (1/2,1/2). On obtient le vecteur colonne (1/4,5/32). On retire de 1 la somme des éléments de ce veteur et on obtient la réponse finale de 19/32.

 

On vérifie ensuite que cette réponse est la bonne en résolvant le problème manuellement (on regarde tous les cas favorables). Sur 32 possibilités, on en a 19 qui marches. En effet, les voici :

 

FFFFF : oui 1

 

FFFFP : oui 2

FFFPF : oui 3

FFPFF : oui 4

FPFFF : oui 5

PFFFF : oui 6

 

FFFPP : oui 7

FFPFP : oui 8

FFPPF : oui 9

FPFFP : oui 10

FPFPF : non

FPPFF : oui 11

PFFFP : oui 12

PFFPF : oui 13

PFPFF : oui 14

PPFFF : oui 15

 

FFPPP : oui 16

FPFPP : non

FPPFP : non

FPPPF : non

PFFPP : oui 17

PFPFP : non

PFPPF : oui 18

PPFFP : non

PPFPF : non

PPPFF : oui 19

 

FPPPP : non

PFPPP : non

PPFPP : non

PPPFP : non

PPPPF : non

 

PPPPP : non

[Lolo]

J'ai écrit un petit programme en php pour calculer la réponse de l'énoncé d'origine (dans le cas général 10 et 1000). La réponse est (approximativement) : 0.38544975241248.

 

 

Voici le programme. On peut y mettre $n=5 et $m=2 et vérifier que cela fait bien 19/32.

 

<?php

 

$n=1000;

$m=10;

 

for ($i=1;$i<=$m;$i++)

{

for ($j=1;$j<=$m;$j++)

{

if ($i==1 or $i==$j+1)

{

$a[1][$i][$j]=0.5;

}

else

{

$a[1][$i][$j]=0;

}

}

}

 

for ($k=2;$k<=$n-1;$k++)

{

for ($i=1;$i<=$m;$i++)

{

for ($j=1;$j<=$m;$j++)

{

$a[$k][$i][$j]=0;

for ($l=1;$l<=$m;$l++)

{

$a[$k][$i][$j]=$a[$k][$i][$j]+$a[$k-1][$i][$l]*$a[1][$l][$j];

}

}

}

}

 

$reponse=1;

for ($i=1;$i<=$m;$i++)

{

$v[$i]=0;

for ($k=1;$k<=2;$k++)

{

$v[$i]=$v[$i]+$a[$n-1][$i][$k]*0.5;

}

$reponse=$reponse-$v[$i];

}

 

echo $reponse;

 

?>

[Lolo]

Bruno, ta probabilité est le complémentaire de la mienne (du moins pour les décimales significatives). Je n'ai pas lu ton calcul, mais n'aurais-tu pas oublié de repasser au complémentaire ?

['Bruno]

C'est marrant, tout le monde "blablatte" mais je ne vois pas encore de convergence vers la bonne réponse à la question initiale posée...

Tu plaisantes ! Estonius a donné le lien vers la réponse (avec la suite de Fibonacci de paramètre 10) et Jgricourt a même démontré la formule du lien. Que demander de plus La question est donc réglée, et c'est d'ailleurs pour ça que je n'ai pas lu en détail la réponse de Lolo (concise, donc pas évidente à suivre) - en tout cas le début coïncide avec celui de Jgricourt.

 

De plus Lolo a trouvé la faille dans mon calcul (suis-je bête !!!!!) : j'ai effectivement calculé la probabilité qu'il n'y ait pas la moindre suite de 10 dans la série des 1000 lancers (je viens de relire l'article cité par Estonius, je m'étais jeté sur la formule de Fibonacci trop vite...) Il faut donc faire 1 - le résultat, et ça donne... 0.385449752. Ça colle avec le résultat de Lolo !

[Toutiet]

J'adore cette prolifération de chiffres significatifs... !

['Bruno]

Il s'agit de maths, pas de physique, le résultat est un nombre bien défini, on ne peut donc pas parler de chiffres significatifs comme lorsqu'il s'agit d'une approximation.

 

Dans mon premier calcul où j'avais donné une approximation, je m'étais limité à une seule décimale, peu confiant en la précision de cette approximation, mais là c'est le calcul exact.)

[jgricourt]

Lolo si je crois que ta fonction f(n,k) qui "représente la probabilité qu'une série d'exactement n lancés consécutifs se termine par une série d'exactement k lancés face" vaut exactement la combinaison C(n,k) qui se calcul simplement avec des factorielles de n et k. Après le résultat 1-f(1000,0)-f(1000,1)-f(1000,2)-...-f(1000,9) revient dans un premier temps à additionner les C(n,k) que l'on peut certainement factoriser ... (mais j'ai pas le courage de coucher ça sur papier ce matin). Ceci dit ta solution est déjà très élégante

['Bruno]

En tout cas le calcul de Lolo correspond à celui de la page cité par Estonius puisqu'il donne pile poil le même résultat, donc sans doute qu'on retrouve les suites de Fibonacci (*).

 

C'est intéressant d'avoir indiqué ces petits programmes : on voit bien que le langage Fortran est le plus lisible et que le PHP est moche... (c'est juste mon avis, hein).

 

-----

(*) d'ordre 10. (J'ajoute cette précision suite au message ci-dessous de Lolo.)

[Lolo]

Lolo si je crois que ta fonction f(n,k) qui "représente la probabilité qu'une série d'exactement n lancés consécutifs se termine par une série d'exactement k lancés face" vaut exactement la combinaison C(n,k) qui se calcul simplement avec des factorielles de n et k. Après le résultat 1-f(1000,0)-f(1000,1)-f(1000,2)-...-f(1000,9) revient dans un premier temps à additionner les C(n,k) que l'on peut certainement factoriser ... (mais j'ai pas le courage de coucher ça sur papier ce matin). Ceci dit ta solution est déjà très élégante

 

Non, le coefficient C(n,k) représenterait le nombre de série d'exactement n lancés qui continennent exactement k lancés face. Cela fait trois différences :

- j'ai désigné une porbabilité, et non pas un comptage des cas favorable;

- mes k lancés face sont à la fin de la série, et non pas répartis un peu partout dans celle-ci;

- je n'ai rien contre le fait d'avoir plus de k lancés face dans la série.

 

C'est intéressant d'avoir indiqué ces petits programmes : on voit bien que le langage Fortran est le plus lisible et que le PHP est moche... (c'est juste mon avis' date=' hein).[/quote']

 

Sur ce forum, mon code n'est pas très lisible. Mais sur mon éditeur, j'ai des décalages et des couleurs. C'est nettement plus clair.

 

Il y a moyen de retomber sur une pure relation récurrente linéaire (et non un système) pour calculer f(n,0). Celle-ci est d'ordre 10 :

f(n+10,0) = f(n+9,0)/2 + f(n+8,0)/4 + f(n+7,0)/8 + ... + f(n,0)/1024. C'est effectivement similaire à Fibonacci qui est d'ordre 2 : F(n+2)=F(n+1)+F(n).

[jgricourt]

Depuis j'ai généralisé mon petit programme C pour calculer la proba sur n'importe quel nombre de série. Cela m'a permis de vérifier sur des cas facilement dénombrables à la main que ma solution donne le bon résultat !

 

#include <iostream>

#include<math.h>

 

using namespace std;

 

double calcul(int nombre_lance, int nombre_serie);

 

int main(int argc, char *argv[]) {

double proba = calcul(1000, 10);

 

cout << "pface=" << proba << "%" << endl;

cout << "Press ENTER to leave ...";

cin.get();

}

 

double calcul(int nombre_lance, int nombre_serie) {

double s[nombre_lance];

double tmp;

 

for (int i=0; i<(nombre_serie-1); i++) {

s = pow(2, i+1);

}

 

for (int i=(nombre_serie-1); i<nombre_lance; i++) {

 

tmp = 0;

for (int j=1; j<nombre_serie; j++) {

tmp = tmp + s[i-j];

}

s = tmp;

}

 

double proba = s[nombre_lance-1] / pow(2, nombre_lance);

proba = 1.0 - proba;

proba = (proba / 2.0)*100.0;

 

return proba;

}

[Toutiet]

Depuis j'ai généralisé mon petit programme C pour calculer la proba sur n'importe quel nombre de série. Cela m'a permis de vérifier sur des cas facilement dénombrables à la main que ma solution donne le bon résultat !

 

Voici la réponse "pour les nuls" :

La probabilité de tirer 10 fois de suite "face" est égale a 1 / 2^10

Sur le champs de l'expérience, cette éventualité peut se produire a chaque nouveau tirage, soit 991 possibilités offertes.

Au total, la probabilité de tirer une série de 10 "faces" consecutives est de :

1 / 2^10 x 991

= 1/1024 x 991

= 991/1024

= 0,967

Et voilà !