> Le Site du Zéro - Informatique

> Cours

> Tutoriels

> Programmation

> Algorithmique

> A la découverte de l'aléatoire et des probabilités

> Simuler l'aléatoire

> Simuler une distribution de cartes géométrique

> Lecture du tutoriel

Simuler une distribution de cartes géométrique

Par

sebsheep

Mise à jour : 25/05/2010

Difficulté : Difficile

Durée d'étude : 2 heures

583 visites depuis 7 jours, dont 48 sur ce chapitre classé 194/786

Dis, pourquoi y'a que 32 cartes dans ton jeu ?

Voici la question que m'a posé Titi, alors que nous terminions une partie endiablée de "bataille".

Je lui ai alors répondu que j'avais sous la main un jeu de 54 cartes, mais ça ne lui suffisait pas : "Pourquoi QUE 54 cartes ?" ; commençant à m'impatienter, j'espérais lui clouer le bec avec les 78 cartes du jeu de tarot, mais c'était peine perdu : "Pourquoi QUE 78 cartes ? Pourquoi est-ce qu'on ne peut pas avoir autant de cartes différentes que l'on veut, ça serait plus marrant non ?".

Au début, en tant que grande personne, j'étais sceptique, mais Titi a été très indulgent avec moi ; il m'a donné et redonné ses explications... Je vous transcris ici ce que j'en ai compris.

Son idée était d'inventer une variante au jeu de la bataille : au lieu de tirer les cartes dans le tas devant soi, on prend les cartes délivrées par une machine, avec une infinité de cartes différentes. Et ensuite de programmer une telle machine.

Pour comprendre tout cela, il m'a d'abord expliqué comment simuler un simple jeu de cartes, puis comment simuler un dé pipé. Il en a profité pour m'expliquer ce qu'étaient un espace de probabilité et une loi de probabilité, et comment simuler ces lois.

Il m'a ensuite emmené dans le monde de l'infini, j'ai alors compris que réaliser cette machine n'était pas une sinécure !

Retour en haut

Sommaire du chapitre :

Un brave jeu de 32 cartes
Un jeu infini !
Q.C.M.

Retour en haut

Un brave jeu de 32 cartes

Une machine "équilibrée"

D'entrée de jeu, Titi m'a déstabilisé en changeant le nom des cartes. Il m'a dit que cela n'avait pas d'importance ; au lieu d'avoir "As de cœur", "Roi de pique" ... Nous aurons simplement des entiers : 1, 2, 3, et ce jusqu'à 32. Il suffira d'avoir une liste dans un coin où l'on a noté que 1 correspond à "As de cœur", 2 à "As de carreau", etc.

Du coup, j'ai proposé moi-même une méthode pour simuler cette machine : tirer un nombre aléatoirement entre 1 et 32 et écrire le nombre obtenu sur un carton ! J'ai testé ça dans mon langage favori... et ça marche !

Évidement, Titi n'a pas pu s'empêcher de faire son intéressant :

Euh oui, ça marche, mais quel est ton espace de probabilité ? Quelle est ta loi de probabilité ?

Devant mes yeux grands comme des soucoupes, il se sentit obligé de m'expliquer. Au début, je ne voyais pas l'intérêt de se compliquer la vie avec de nouveaux noms, mais très vite, je me suis rendu compte ces notions nous facilitaient grandement la tâche ; soyez donc patients et attentifs, je vous promets que le résultat sera convaincant !

Espace de probabilité

C'est tout simplement l'ensemble de tous les événements possibles. C'est pourquoi on l'appelle aussi "univers des possibles". Dans notre cas c'est très simple, il s'agit de {1, 2, 3, ..., 30, 31, 32}.

Probabilité

La probabilité d'un événement, c'est un nombre qui caractérise la fréquence d'un événement. Si ce nombre est très proche de 0, l'événement aura très peu de chances de se produire ; s'il est très proche de 1, l'événement aura au contraire beaucoup de chance de se produire.

Par exemple, quand on tire à pile ou face, la probabilité de tomber sur face est de 0,5 (=1/2) : on a 1 chance sur 2 que cela arrive. Quand on lance un dé, la probabilité de tomber sur le 3 est de 0,166... (=1/6) : on a 1 chance sur 6 que cela arrive. La probabilité de tirer la dame de pique (ou toute autre carte) dans notre jeu de 32 cartes est de 1/32.

Retenez bien : si la probabilité d'un événement est 0 (tout pile), l'événement ne se produira jamais ; si c'est 1, l'événement se produira toujours. Une probabilité est toujours comprise entre 0 et 1.

Loi de probabilité

Une loi de probabilité, c'est ce qui détermine la probabilité de chaque événement.

C'est quoi la différence avec une probabilité ?

C'est complètement différent. Après de longues réflexions, j'ai compris qu'en fait, connaître une loi de probabilité, ça revient à connaître un tableau qui indique à quelle probabilité apparaît chaque élément. Par exemple, pour notre jeu, la loi est donnée par :

Loi de probabilité d'une machine "équilibrée"
Carte n°	1	2	3	...	30	31	32
Probabilité	$\frac{1}{32}$	$\frac{1}{32}$	$\frac{1}{32}$	...	$\frac{1}{32}$	$\frac{1}{32}$	$\frac{1}{32}$

Comme vous pouvez le voir sur le tableau, la loi de probabilité pour notre jeu de carte est assez simple : chaque élément a la même probabilité d'apparition, à savoir 1/32.

Pour faire un peu plus sérieux, je me suis permis d'introduire une notation pour cette loi de probabilité : dans notre cas par exemple, je noterai la probabilité que le "3" apparaisse avec : P({3}). Ici, on a donc P({3})= 1/32. De même, pour n'importe quel entier n entre 1 et 32, on a P({n})=1/32. J'appellerai {3} un "événement élémentaire", et P({3}) une "probabilité élémentaire".

Vous avez donc une deuxième manière de connaître une loi, c'est de connaître chaque probabilité élémentaire ; autrement dit, pour tous les événements élémentaires e de l'univers des possibles, vous connaissez P(e).

Vous avez donc deux manières de représenter une loi : soit grâce à un tableau, soit grâce à P. Vous devez vous assurer que vous avez bien compris que ces deux notations servent à la même chose. Dans la suite, on utilisera soit l'un soit l'autre suivant ce qui est le plus adapté : il faut pouvoir jongler entre les deux sans problèmes !

Au passage, vous aurez remarqué que je dis maintenant simplement "loi" au lieu de "loi de probabilité" car je suis un gros fainéant, et que tout le monde sait bien de quoi on parle. Si un plouc pense que je parle de la "loi française", je lui conseille d'arrêter la fac de droit>

Ne voulant pas en rester là, j'ai eu envie de connaître la probabilité que le 3 ou le 7 apparaisse. En gardant la même notation, cette probabilité sera représentée par P({3,7}) qui est clairement égale à P({3}) + P({7}) = 2/32 (ou 1/16 pour les puristes).

Les plus malins d'entre vous tenteront de calculer P({3,3}). On peut le faire bien sûr, mais cela ne vaut pas P({3}) + P({3}) ; {3, 3} représente l'événement : "le 3 sort" OU "le 3 sort"... Vous admettrez qu'il s'agit tout simplement de l'événement "le 3 sort" et donc que sa probabilité est égale à P({3}).

Parti sur ma lancée, j'ai cherché la probabilité que 5 cartes données apparaissent, puis 10, et puis tant qu'à faire 32 (c'est à dire, la totalité du jeu). Cette probabilité est de : P({1, 2, ..., 31, 32}) = P({1}) + P({2}) + ... + P({31}) + P({32}) = 32/32 = 1. Vous allez me dire que j'aurais pu m'en douter : l'événement que je considère se produit tout le temps (lorsqu'on tire une carte, on tire soit le 1, soit le 2, ...., soit le 32). Or un événement qui se produit tout le temps a une probabilité de 1 !

Titi m'a alors fait remarquer la chose suivante : la somme de toutes les probabilités élémentaires est égale à 1 !

Ça ne marche que pour notre jeu de cartes ça non ?

Eh bien non, c'est en fait très général. Si vous reprenez le paragraphe au-dessus, vous vous rendez compte que vous pouvez le modifier pour l'adapter à n'importe quel univers des possibles. On peut donc caractériser une loi de probabilité : il suffit que lorsqu'on additionne toutes les probabilités élémentaires, on obtienne 1.

Après m'avoir expliqué tout ça, Titi n'était pas encore très satisfait : "Ta machine elle marche, mais elle est pas drôle ; et puis les cartes, j'en ai ma claque, j'ai envie de jouer aux dés maintenant ! Je veux une machine qui simule un dé pipé : plein de 4 et pas beaucoup d'autres chiffres !"

Une machine déséquilibrée

Faites votre loi !

Pour faire cela, Titi m'a dit qu'il suffisait de définir une nouvelle loi de probabilité.

Ce que veut Titi, c'est avoir beaucoup de "4". Pour cela, je mets donc une grosse probabilité sur "4", disons 0,6. Une fois que j'ai fixé cette probabilité, je ne peux pas prendre ce que je veux pour les autres probabilités élémentaires. Souvenez vous, il faut que la somme de toutes les probabilités élémentaires soit égale à 1. Il me reste alors 0,4 (= 1 - 0,6) à répartir entre les valeurs restantes.

Par exemple, je peux avoir la loi suivante :

Loi de probabilité d'une machine "déséquilibrée"
Face n°	1	2	3	4	5	6
Probabilité	0.08	0.08	0.08	0.6	0.08	0.08

Évidemment, je ne suis pas obligé de mettre la même probabilité pour "1", "2", "3" ,"5" et "6". Je peux aussi prendre :

Loi de probabilité d'une machine "déséquilibrée"
Face n°	1	2	3	4	5	6
Probabilité	0.05	0.05	0.1	0.6	0	0.2

Vous remarquez ici que la probabilité de tirer un 5 est de 0 ; cela veut dire que le 5 ne sortira jamais !

Je vous laisse le soin de vérifier que la somme des probabilités fait bien 1. Et coup de chance, cette loi plaît beaucoup à Titi !

Construire la machine

Mais cette loi est un peu plus dure à simuler que la première : chaque élément a une probabilité différente de sortir. Tirer "au hasard" ne rendra pas compte de cette loi.

L'approche ici est totalement différente. Elle part du constat suivant : si on tire un nombre au hasard dans l'intervalle [0;1], ce nombre aura par exemple beaucoup plus de chances de se trouver dans le sous-intervalle [0;0,8] que dans [0,8;1]. De façon générale, plus le sous-intervalle sera grand, plus la probabilité de tirer un nombre à l'intérieur sera grande.

On peut même être plus précis

: la probabilité de tirer un nombre dans le sous-intervalle [a,b] est égale à la longueur de ce dernier, c'est à dire (b-a). Et c'est là que va se situer toute l'astuce de la technique : à un événement élémentaire de probabilité p, on associe un sous-intervalle de [0,1] de longueur p.

En se débrouillant pour que les sous-intervalles ne se chevauchent pas, on aura donc complétement recouvert notre segment [0,1] ! Pour m'assurer que j'avais bien compris, Titi m'a demandé de lui faire un dessin ; il fut relativement déçu de mes talents artistiques :

Comme vous pouvez le constater, j'ai construit mes sous-intervalles pour coller avec la loi ci-dessus. La partie verte est associée à l'événement "le 1 sort", la partie violette à l'événement "le 4 sort", et ainsi de suite. On constate aussi que chaque sous-intervalle a bien la bonne longueur : la partie verte mesure 0.05, la violette 0.6 (=0.8 - 0.2), etc.

Maintenant, pour simuler notre machine, il suffira de tirer un nombre au hasard entre 0 et 1. Sa position dans le schéma ci-dessus déterminera quelle carte doit sortir : si le nombre est dans la partie bleue, on sortira le 3, s'il est dans la partie rouge, on sortira le 6. De cette manière, le 1 et le 2 sortiront avec une probabilité de 0.05 (les longueurs des parties verte et orange), le 3 avec une probabilité de 0.1, etc. Donc la machine suivra bien la loi que Titi avait choisie !

Certains se demandent peut-être s'il faut prendre des sous-intervalles fermés ou ouverts (c'est à dire, en incluant ou pas les bornes de l'intervalle) ; en théorie, cela n'a en fait aucune importance. Effectivement, la probabilité de tomber dans un intervalle est égale à sa longueur. Ici, la "longueur" d'un intervalle constitué d'un seul nombre est de 0, et donc la probabilité de tomber dessus tout pile est également 0 ! Donc, même si en pratique le générateur aléatoire n'est pas parfait, il s'agit d'un événement qui se produit extrêmement peu souvent. En résumé, faites comme vous voulez !

Pour l'implémenter, pas d'astuces : on tire un nombre aléatoire x entre 0 et 1. On regarde si x est inférieur à la première valeur dans le tableau ; dans ce cas, on renvoie 1 ; sinon, on regarde s'il est inférieur à la somme des deux premières valeurs du tableau auquel cas on renvoie 2, et ainsi de suite ...

Hein ? Pourquoi la somme des deux premières valeurs ? Pourquoi pas la deuxième valeur directement ?

Revenez au petit schéma ci-dessus : on veut d'abord savoir si x est dans la zone verte, donc on le compare à 0,05. Après, on veut savoir s'il est dans la zone bleue, autrement dit, s'il est

supérieur à 0,05 : de ce côté là, pas de problème, si on arrive à cet endroit du code, c'est que x n'est pas inférieur à 0,05 ;
ET inférieur à 0,1 : autrement dit s'il est inférieur à 0,05 + 0,05, ce qui correspond aux 2 premières valeurs du tableau. Si c'est le cas, on renvoie 2.

Et on continue ainsi jusqu'à ce que x soit inférieur à la somme de tous les éléments parcourus.

Pour faire plaisir à Titi, j'ai implémenté cet algo en C, il fut cette fois très content du résultat (pour une fois !) :
Secret (cliquez pour afficher)

Code : C

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

/* Renvoie un nombre aléatoire entre 0 et 1 */
double rand_0_1(){	return rand()/(double)RAND_MAX; }

/*Génère un entier entre 1 et taille suivant la loi modélisée par le tableau
passé en paramètre */
int alea_perso(double loi[], int taille){
	int i=0;
	double x=rand_0_1();
	double somme=0;
	/* Dans le premier passage dans la boucle, on testera
           si x est inférieur à somme, c'est à dire loi[0]. Si ce n'est pas le cas
           on relance la boucle : somme vaudra alors loi[0] + loi[1]
           ... et ainsi de suite.
        */
	do{
		somme += loi[i];
		i++;
	}while( somme < x && i < taille  );
	return i;
}

int main(){
	const int NB_EVT=5;
	double loi[]={0.05,0.05,0.1,0.6,0,0.2};
	int nb_tirages=0;
	int i=0;
	int carte=0;
	srand(time(NULL));
	
	do{
		printf("Combien de tirages voulez-vous effectuer ? ");
		scanf("%d",&nb_tirages);
	}while(nb_tirages <= 0);
	
	printf("Voici la liste des tirages : \n");
	for(i=0; i<nb_tirages;i++){
		carte=alea_perso(loi,NB_EVT);
		printf("%d ",carte);
	}
	printf("\n");
	return 0;
}

Attention, la méthode que Titi vous a présentée ici ne simule pas un paquet fini de cartes. Effectivement, si la carte n°1 est déjà sortie, elle peut sortir encore une fois. Pour simuler un paquet "réel" de manière correcte, il faudrait modifier la loi après chaque tirage.

Retour en haut

Un jeu infini !

Maintenant, on passe à la vitesse supérieure, on va construire une machine qui sort un nombre infini de cartes (Titi s'est vite lassé des dés) ! Pour utiliser le vocabulaire que Titi m'a appris, cela signifie que l'univers des possibles sera infini. Vous allez voir que ce n'est pas une mince affaire.

Un problème épineux

Comme le dit Titi, "il faut réutiliser ce qu'on sait déjà faire" : dans la partie précédente, on a vu que si on connaît une loi, on a alors une méthode pour simuler une machine qui suit cette loi. Je pensais être sorti d'affaire : "Il me suffit de déterminer cette loi et le tour est joué !".

Mais si l'univers des possibles est infini, comment stockeras-tu ta loi ? Tu ne pourras pas utiliser un tableau !

Il est énervant à toujours avoir raison ce Titi ! Ma solution est de remplacer notre tableau par une gentille fonction qui prend un entier en paramètre et qui renvoie sa probabilité d'apparaître. Par exemple, j'ai eu l'idée d'utiliser le même type de loi que pour la machine équilibrée : toutes les cartes ont la même probabilité, et je choisis cette proba à 0,05 ! Ce qui nous fait une fonction du type :

Code : C

double loi(int n){
    if(n>0)
        return 0.05;
    else
        return 0; /* La numérotation des cartes commence à 1, donc 
                     la probabilité de tirer un nombre inférieur 
                     ou égal à 0 est nulle ! */
}

C'est un peu mieux ... Mais cette fonction ne représente absolument pas une loi de probabilité : en additionnant les 20 premières probabilités élémentaires, on obtient 1, et si on continue, on dépasse le allégrement ; c'est même pire que ça, vu qu'il y en a un nombre infini, la somme de toutes les probabilités sera ... infinie !

Et prendre une probabilité plus petite ne changera rien, on mettra juste "plus de temps à atteindre l'infini".

Gare à celui qui me propose d'alterner des nombres positifs et négatifs pour faire en sorte que certains termes en annulent d'autres : une probabilité négative n'a aucun sens !

J'ai alors pensé à ne mettre une probabilité que sur un nombre fini de cartes, le reste des cartes ayant une probabilité nulle. Ce qui correspondrait à :
Code : C

double loi(int n){
    if(n>0 && n<=20)
       return 0.05;
    else
       return 0;
}

C'est bien une loi, mais on n'a rien gagné par rapport à la première partie ! En effet, on simule ici une machine qui ne tire qu'un nombre fini de carte ... Retour à la case départ !

Au lieu de chercher à construire une loi à tâtons, on va plutôt tenter de modéliser une situation "réelle" ; on s'assurera ensuite que ce qu'on a trouvé est bien une loi.

Un jeu de pile ou face

Le jeu

Titi m'a proposé le jeu suivant : je lance une pièce jusqu'à ce que je tombe sur pile. Mon score est alors le nombre de lancers que j'ai effectués. Par exemple, si je tire face, face puis pile, mon score est de 3 ; si je tire pile du premier coup, mon score est de 1.

Bien sûr, ce qu'on va essayer de faire, c'est simuler ce jeu par une machine : on lance la machine, elle calcule notre score puis l'inscrit sur une carte.

L'algorithme le plus naïf serait de tirer au hasard 0 (pour pile) ou 1 (pour face), compter le nombre de fois qu'on le fait et de s'arrêter lorsqu'on tire un face. De façon plus concise, cela donne :
Code : Autre

compteur=0
faire
    nombre = tirer 0 ou 1 au hasard
    compteur ++
tant que nombre = 0
afficher compteur

Mais je me suis vite rendu compte que cela n'allait pas du tout : on tire potentiellement pleins de nombres aléatoires, ce qui n'est pas du tout économique ! Cherchons maintenant à trouver la loi de cette machine pour pouvoir appliquer l'algo de la première partie, et être plus efficace.

La probabilité que je tire pile du premier coup est de 1/2 (Titi n'est pas encore assez âgé pour avoir la fourberie de me donner une pièce déséquilibrée

). On connaît donc déjà une probabilité élémentaire : P({1})=1/2 (c'est la traduction de la phrase d'avant : la probabilité que mon score soit 1 est de 1/2).

Pour que je tire pile au deuxième coup (sans l'avoir fait au premier), il faut que je tire:

face au premier coup, ce qui a une probabilité de 1/2;
ET pile au deuxième, ce qui a aussi une probabilité de 1/2.

Croyez moi sur parole, nous avons : P({face au premier lancer} ET {pile au second lancer}) = P({face au premier lancer})*P({pile au second}) = 1/2 * 1/2 = 1/4.

Et donc P({2}) = 1/2² = 1/4. De la même manière, vous pouvez trouver que P({3}) = 1/2 * 1/2 * 1/2 = 1/2³=1/8, P({4})=1/2⁴, ... On peut alors généraliser : P({n}) = 1/2ⁿ. Nous connaissons donc bien notre loi vu que pour chaque événement élémentaire, on a une probabilité.

Mais avons nous bien une loi ? Autrement dit, la somme de toutes les probabilités élémentaires fait-elle bien 1 ?

La loi du gâteau idéal

Déjà, quel est l'univers des possibles ? Le score du jeu peut être 1, 2, 3, 42,512, ... en fait, n'importe quel entier positif non nul. Donc on a bien un univers infini.

Et on veut vérifier que la somme des probabilités élémentaires soit égale à 1. Autrement dit que :

$P({1}) + P({2}) + P({3}) +\ \dots \ = \ \frac{1}{2} + \left( \frac{1}{2} \right)^2 + \left( \frac{1}{2} \right)^3 + \ \dots \ = \ \frac{1}{2} \ + \ \frac{1}{4} \ + \ \frac{1}{8} \ + \ \dots \ =\ 1$

Vous remarquerez que j'ai utilisé cette fois "..." sans rien mettre derrière ; cela signifie qu'on continue la somme "à l'infini". Si j'avais mis "0.1+ 0.2 +0.3 +... + 0.9" cela signifierait que j'ai une somme finie.

Pour m'expliquer ce problème, Titi m'a raconté ce qu'il a fait à son dernier anniversaire. Comme à tous les anniversaires, il y avait un beau gros gâteau, comme on les aime de par chez nous, un gâteau "idéal" : on peut en couper des parts aussi fines qu'on veut, sans en perdre une miette.

Et Titi a beaucoup de chance, il a beaucoup d'amis. Quand je dis beaucoup, ce n'est pas 10, 100 ou 100 000. Non, beaucoup. Une infinité !

Et comme Titi est à moitié généreux, à chaque nouvel arrivant, il offrait la moitié restante du gâteau. Donc pour le premier invité, le gâteau était entier, il a donné la moitié du gâteau ; donc 1/2. Il restait alors la moitié du gâteau ; le deuxième invité a donc reçu la moitié de la moitié, autrement dit un quart (1/4). Et ainsi de suite, le troisième a reçu 1/8, le quatrième 1/16 ...
La question est : quand il aura servi tous ses amis, restera-t-il du gâteau pour Titi ?

Pour déjà faire le lien avec notre problème, on peut remarquer que la quantité de gâteau donnée par Titi correspond à la somme qui nous intéresse.

On remarque immédiatement que cette somme ne dépassera jamais 1 : Titi ne peut pas donner plus de gâteau que le gâteau lui même ! Et en regardant les images ci-dessus, on voit bien qu'à la fin, Titi aura distribué tout le gâteau et qu'il n'en aura pas ; pas de chance, il fallait se servir avant ! Tout ça pour dire que la somme qui nous intéresse fait bien 1.

Pourquoi n'a-t'il pas la moitié de la dernière part ?

Il y a une infinité d'ami... Du coup, pas de dernière part !

Nous sommes maintenant sûr d'avoir affaire à une loi de probabilité, on peut maintenant essayer de la simuler !

Une machine rapide !

Maintenant qu'on a une loi, on peut réadapter le programme qu'on avait fait pour simuler ce jeu dans la première partie. Je vous rappelle la méthode : on tire un nombre x compris entre 0 et 1, puis on regarde dans quelle "zone" il se situe. Ici le découpage des zones se fait ainsi :

Pour "regarder dans quelle zone x se situe", je vous rappelle (n'hésitez pas à relire la première partie) qu'en gros, on teste si x est dans la zone "1", puis s'il est dans la zone "2", et ainsi de suite.

Pour appliquer le même algo, il faut alors définir une fonction qui représentera notre loi :
Code : C

#include <math.h>
double loi(int n){
    if(n<=0) return 0;
    else return pow(0.5,n); // = (1/2)^n
}

Ce qui au final donnerait un programme de ce type :
Secret (cliquez pour afficher)

Code : C

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

/* Renvoie un nombre aléatoire entre 0 et 1 */
double rand_0_1(){	return rand()/(double)RAND_MAX; }

double loi(int n){
    if(n<=0) return 0;
    else return pow(0.5,n); // = (1/2)^n
}

/*Génère un entier suivant la loi modélisée par la fonction "loi" */
int alea_perso(){
	int i=0;
	double x=rand_0_1();
	double somme=0;
	
	do{
		somme += loi(i);
		i++;
	}while( somme < x );
	return i-1;
}

int main(){
	int nb_tirages=0;
	int i=0;
	int carte=0;
	srand(time(NULL));
	
	do{
		printf("Combien de tirages voulez-vous effectuer ? ");
		scanf("%d",&nb_tirages);
	}while(nb_tirages <= 0);
	
	printf("Voici la liste des tirages : \n");
	for(i=0; i<nb_tirages;i++){
		carte=alea_perso();
		printf("%d ",carte);
	}
	printf("\n");
	return 0;
}

Mais en fait, ce n'est pas beaucoup mieux que la première version. Je vous rappelle que dans la première version, on tirait un nombre 0 ou 1 tant que ce nombre n'était pas 1 ; donc si le score valait 5, on avait donc 5 "tours de boucles". Ici, si on regarde de la même façon le "nombre de tours", on se rend compte très vite qu'il est aussi égal au score ; donc niveau efficacité, c'est la loose

.

On va donc essayer d'être plus efficace : on va réfléchir pour trouver directement dans quelle zone se situe x sans faire aucune boucle. Autrement dit, on va chercher une formule mathématique qui nous donnera la zone directement à partir de x.

Pour certaines valeurs, c'est très facile de dire "à l'œil nu" dans quelle région est x. Par exemple, si x=0.2, il est clairement dans la région "1" ; si x=0.6, il est dans la région "2". Mais si x=0.9876, vous serez bien en peine de me dire - sans calculs ! - dans quelle région est x ! C'est cette "recherche de zone" que l'on va automatiser dans ce qui suit.

La partie qui suit, même si expliquée en détail, est relativement technique ; savoir ce qu'est une inéquation est fortement recommandé. Si vous voyez que vous ne comprenez rien à mon charabia, sautez à la formule finale sans états d'âmes.

Pour bien comprendre, mettons que x est dans la zone "3". Regardez le schéma au-dessus, cela veut dire que x est compris entre P({1})+P({2}) et P({1})+P({2})+P({3}). Autrement dit : $P(\{1\})+P(\{2\})\ <\ x \ \le \ \ P(\{1\})+P(\{2\})+P(\{3\}).$

On connaît très bien P({1}),P({2}) et P({3}), on peut donc écrire :
$\frac{1}{2} + \left( \frac{1}{2} \right)^2 \ <\ x \ \le \ \frac{1}{2} + \left( \frac{1}{2} \right)^2 + \left( \frac{1}{2} \right)^3$

Mais la zone dans laquelle est x, c'est pas ce qu'on cherche à trouver ? On se mord la queue là, non ?

Oui, c'était un exemple pour bien comprendre la formule que je vais vous balancer. Maintenant, mettons que x est dans la zone "n" (que nous ne connaissons pas); on peut donc écrire : $\frac{1}{2} + \left( \frac{1}{2} \right)^2 + \dots + \left( \frac{1}{2} \right)^{n-1}\ <\ x \ \le \ \frac{1}{2} + \left( \frac{1}{2} \right)^2 + \dots +\left( \frac{1}{2} \right)^n$ .

Nous avons donc une superbe inéquation, et le but du jeu, c'est de trouver n (nous connaissons déjà la valeur de x) :-°

!

Dans un premier temps, nous allons trouver une forme plus sympathique aux grosses sommes de part et d'autre des inégalités. Vous remarquerez que :
$\frac{1}{2} + \left( \frac{1}{2} \right)^2 \ =\ \frac{3}{4} \ =\ 1 - \left( \frac{1}{2} \right)^2$

$\frac{1}{2} + \left( \frac{1}{2} \right)^2 + \left( \frac{1}{2} \right)^3 \ =\ \frac{7}{8} \ =\ 1 - \left( \frac{1}{2} \right)^3$

...

$\frac{1}{2} + \left( \frac{1}{2} \right)^2 + \dots + \left( \frac{1}{2} \right)^{n-1} \ =\ 1 - \left( \frac{1}{2} \right)^{n-1}$

$\frac{1}{2} + \left( \frac{1}{2} \right)^2 + \dots + \left( \frac{1}{2} \right)^n\ =\ 1 - \left( \frac{1}{2} \right)^n$

Donc notre grosse inégalité se re-écrit : $1 - \left( \frac{1}{2} \right)^{n-1} < x \le 1 - \left( \frac{1}{2} \right)^n$ . Ce qui me fait déjà beaucoup moins peur. En enlevant 1 à chaque bout, puis en multipliant par (-1) on a (multiplier par un nombre négatif change le sens d'une inégalité) :
$\left( \frac{1}{2} \right)^{n-1} > 1-x \ge \left( \frac{1}{2} \right)^n$

Gloups ... et comment je fais "sauter" la puissance ?

Alors pour faire ça, rappelez vous de la façon dont vous faites "sauter" un carré : vous prenez la racine carré !

Mais qu'est-ce que la racine carré ? Vous connaissez surement très bien la fonction "carré" f(x)=x² qui a pour effet de multiplier un nombre par lui même. Eh bien la racine carré est la fonction qui fait le boulot inverse de la fonction carré.

Dans notre cas, nous avons la fonction "puissance de 1/2" $f(n)=\left( \frac{1}{2} \right) ^n$ ; eh bien il existe une fonction qui fait le boulot inverse la fonction "puissance de 1/2". Cette fonction s'appelle le logarithme de base 1/2 (évidement, si on considère la fonction "puissance de a", on aura affaire au "logarithme de base a"). Je le noterai log_1/2. Ainsi, on aura : $log_{\tiny{1/2}}\left( \left(\frac{1}{2}\right)^n \right)= n$

Vous pouvez remarquer que log_1/2 est décroissante, donc quand je l'applique, les inégalités "changent de sens".

Revenons à notre calcul, j'applique le log_1/2 :magicien:

:

$n-1 < log_{\tiny{1/2}} \left( 1-x \right) \le n$

Donc il n'y a plus qu'une seule possibilité pour n : c'est l'entier qui est juste au-dessus (fonction ceil en C) de log_1/2(1-x).

Une dernière petite optimisation (c'est vraiment du bout de chandelles ...) : x est un nombre aléatoire compris entre 0 et 1 ... c'est aussi le cas de 1-x, donc dans l'argument du log_1/2, on peut se contenter de prendre x au lieu de 1-x.

Dernière note technique : pour calculer log_1/2(x) concrètement en C, vous devrez faire le calcul suivant : log(x)/log(0.5) (en ayant inclus math.h évidemment).

Pfiou, j'ai enfin fini ! Bah ... pourquoi tout le monde est parti ? :euh:

La formule finale

Tout ceci nous mène à ce superbe résultat ; pour savoir dans quelle zone se situe x, il suffit de faire le calcul :

ceil( log(x) / log(0.5) );

Cela correspond au score que j'ai obtenu au jeu de pile ou face. Il ne me reste plus qu'à l'écrire sur une carte !

Tout ce patacaisse pour une pauvre petite malheureuse formule ? Mais qu'est-ce qu'on a gagné ?

Vous avez gagné sur plusieurs points :

efficacité du code : le calcul du log est très rapide, optimisé par des grosses brutes des mathématiques, beaucoup plus efficace que notre boucle !
simplicité du code : nous n'avons plus besoin de définir une fonction "loi" auxiliaire, la simulation du score se fait en 1 ligne (voir code plus loin).
vous avez appris quelques techniques mathématiques qui vous resserviront peut-être .

Pour simuler le score à ce jeu, il suffit de faire une fonction ressemblant à (je vous laisse faire le main qui va autour) :
Code : C

int score_pile_face(){
        double x=rand_0_1();
        int score=ceil(log(x)/log(0.5));
        return score;
}

Que l'on peut condenser en un ligne return ceil(log(rand_0_1())/log(0.5)) . Le simple appel à cette fonction renverra le score qu'on obtient en jouant à ce jeu ; l'entier qu'elle renverra pour donc ne pas être toujours le même !

Des variantes

Titi est content, il a sa machine qui lui permet de simuler un jeu infini de cartes ; mais nous pouvons encore trouver d'autres lois. Par exemple, nous pouvons prendre une pièce "déséquilibrée" qui tombe sur face avec une probabilité de 0,7. Vous pouvez tenter de refaire les calculs ci-dessus pour obtenir une formule pour cette nouvelle machine.

Nous pouvons aussi modifier un peu le jeu : on tire 100 fois à pile ou face, et notre score est le nombre de "piles" que nous avons obtenus.

On pourrait faire le même genre d'étude que juste au-dessus, mais malheureusement, nous ne pourrons pas nous servir du logarithme, ni d'aucune fonction "simple" pour inverser l'expression que nous allons trouver (Titi a tenté de m'expliquer le calcul, je n'y ai rien compris ...). Le plus efficace est alors d'appliquer un algo "naïf" :
Code : Autre

compteur=0
faire 100 fois
    nombre = tirer 0 ou 1 au hasard
    si nombre = 0
        compteur ++
afficher compteur

Je l'ai répété assez de fois, pour avoir une loi, il suffit que la somme des probabilités élémentaires soit égale à 1 ; mais, vu qu'il y a une infinité de termes, cela force chacun de ces termes à devenir de plus en plus petit.

Pour construire une loi, vous pouvez donc essayer de trouver une suite (infinie) de nombres qui tend vers 0 et faire en sorte que leur somme vaille 1 ; le problème n'est pas évident car si les nombres ne tendent pas "assez vite" vers 0, la somme explose et tend vers l'infini ! Mais comme je suis gentil, je ferai un petit article à ce sujet dans pas longtemps...

Retour en haut

Nous avons donc rempli notre objectif initial : construire une machine délivrant une infinité de cartes.

En réalité, pour employer le vocabulaire mathématique, Titi vous a initié à la simulation de "variables aléatoires" (que j'avais appelées "machines" dans le tuto pour ne pas vous surcharger en vocabulaire), et vous a fait découvrir une loi bien connue des probabilistes : la loi géométrique.

Parfois on parle de "distribution" géométrique à la place de "loi" géométrique. Ce n'est pas exactement la même chose mais revient au même. Vous pouvez donc maintenant comprendre le double sens du titre de ce tuto !

Nous avons aussi effleuré le problème de la loi binomiale : il s'agit du jeu où l'on lance 100 fois une pièce et où l'on compte le nombre de "faces". Je vous ai dit qu'il n'y avait pas de méthodes "malines" pour simuler cette loi ; mais lorsque le nombre de tirages est grand, on peut approcher la loi binomiale par une autre - la loi de Poisson - qui elle est facile à simuler.

Il y a un point que nous n'avons absolument pas abordé dans ce tuto : les lois continues. Effectivement, nous n'avons parlé que de lois discrètes (c'est le mot mathématique pour désigner ce qui n'est pas continu), or il en existe d'autres ! Prenez par exemple le retard de votre bus sur son horaire : l'univers des possibles est [0,+infini[, ce qui est un ensemble infini, mais "beaucoup plus grand" (et donc compliqué à appréhender) que ce que nous avons vu (c'est à dire l'ensemble des entiers : {0,1,2,3,...}).

Voici donc ce que vous avez à creuser si le sujet vous intéresse... Mais comme vous avez pu le sentir, avant de pouvoir vraiment faire des probabilités intéressantes, il faut d'abord avoir un bagage mathématique convenable pour pouvoir se dépêtrer d'inégalités tordues et de sommes gigantesques !

Retour en haut

Retour en haut

Face n°	1	2	3	4	5	6	7	8	9	10	11	12
Probabilité	0,16	0	0,05	0,2	0,2	0,15	0	0,12	0,14	0,02	0,28	0,3

	A la découverte de l'aléatoire et des probabilités
	[TP] Le mot mystère
	Fabriquez votre propre fonction "rand"
	Bruits et nombres aléatoires cohérents

Les cours phares

Tous les cours par catégories

Autres

Programmation (263 Cours)

Graphisme (29 Cours)

Bureautique (27 Cours)

Jeux Vidéo (18 Cours)

Matériel (7 Cours)

Dernières annonces

Recrutement à Bac / Bac +1

Recrutement à Bac +2

Recrutement à Bac +3 / Bac +4

Recrutement à Bac +5

Dynamisez vos sites web avec JavaScript

Créez des applications pour iPhone, iPad et iPod Touch

Cours

Nouveau ?

Nouveautés

Site Web

Programmation

Bases de données

Mobiles

Systèmes d'exploitation

Graphisme

Infographie 3D

Bureautique

Réseaux

Matériel

Mapping

Simuler une distribution de cartes géométrique

Une machine "équilibrée"

Espace de probabilité

Probabilité

Loi de probabilité

Une machine déséquilibrée

Faites votre loi !

Construire la machine

Un problème épineux

Un jeu de pile ou face

Le jeu

La loi du gâteau idéal

Une machine rapide !

La formule finale

Des variantes

Partager

Lire aussi