Le but de ce TP est de vous montrer comment utiliser un environnement dédié au calcul numérique comme ScicosLab/NSP/Scilab/MatLab/Octave/Julia dans un contexte probabiliste. Ce type de langages est particulièrement adapté à un ingénieur souhaitant prototyper son travail rapidement, souvent (mais pas toujours) en sacrifiant le temps de calcul (celui de la machine) au bénéfice du temps passé à programmer (le votre) .
Dans la suite du cours nous utiliserons Scilab pour concrétiser les notions que nous allons introduire.
Aujourd’hui, nous allons illustrer la démarche par la traitement d’une question que nous avons trouvé sur le site de la nsa. Dans la suite les expressions en couleursont (en principe) des liens html cliquables.
On place deux œufs “au hasard” dans une matrice p × q. On considère deux joueurs (A et B). Le joueur A parcours la matrice en colonne, le joueur B en ligne. Le gagnant est celui qui atteint le premier l’un des deux œufs. La question est de savoir si ce jeu est équitable (i.e. les deux joueurs ont ils la même probabilité de gagner ?) et de déterminer, si ce n’est pas le cas, lequel a un avantage.
On trouvera la réponse à cette question lorsque p = 3 et q = 4 sur le site de la NSA. Nous verrons que l’on peut répondre très simplement à ces questions à l’aide de Scilab. Les réponses dépendent des valeurs de p et q de façon surprenante : elles sont différentes pour (p = 3,q = 4), (p = 4,q = 4) et (p = 4,q = 5) !
Les codes qui suivent on été testés avec Scicoslab ou NSP. Il est probable qu’ils fonctionnerons avec peu (ou pas) de modifications dans Scilab, mais nous vous conseillons d’installer Scilab sur votre machine personnelle pour ne pas avoir de problèmes.
Vous pouvez installer ScicosLab à partir de la page http://www.scicoslab.org/ sur la plupart des architectures existantes (MacOS, Windows, Linux). Pour installer NSP, il faut utiliser sur la page dédiée à NSP. Une version corrigée des codes qui suivent sera disponible à la fin du TP.
Pour ces travaux pratiques d’introduction à Scilab, il vous faut lancer le logiciel Scilab et disposer ainsi d’une fenêtre permettant de saisir et d’exécuter des instructions.
Une ligne de commande Scilab est précédée du signe -->. Pour commencer, il vous suffit de les recopier ou de les saisir par copier-coller (sans -->) pour les exécuter immédiatement dans la fenêtre Scilab.
Toute ligne débutant par // est une ligne de commentaires.
Lorsque l’on ne sait pas bien ce que fait une fonction.
On commence par traiter la question par simulation. On suppose (ce qui est implicite dans la formulation du problème) que les 2 œufs sont placés, indépendamment, uniformément sur les p×q cases de la matrice. Il peut donc arriver que les 2 œufs soient au même endroit (à vrai dire le problème ne précise pas ce détail), mais on verra que cela n’a pas d’impact sur la réponse à la question posée.
Quelques compléments sur la syntaxe qui seront utiles.
Une fonction peut renvoyer un vecteur (bien sûr).
La fonction X=grand(m, n, dist_type [,p1,...,pk]) permet de simuler un grand nombre de loi de variables aléatoires en spécifiant dist_type (help grand pour les détails).
Simulation d’une loi discrète On cherche à tirer au hasard selon la loi d’une variable aléatoire discrète N P = (P(k), 1 ≤ k ≤ N).
La primitive grand qui simule pas mal de lois de variables aléatoires (mais pas la loi discrète !). Ce qui nous donne l’occasion de faire une premier exercice de Scicoslab.
Voici une première version itérative (comme on l’écrirait en C).
Par soucis d’efficacité, on cherche souvent à “éviter les boucles” à l’aide de commandes vectorielles. Avant d’écrire une version vectorielle du programme précédent, introduisons quelques primitives adaptées.
Le test booléens fonctionnent sur les types vectoriels. C’est commode.
Retourne les indices “vrai” d’un vecteur de booléen.
Les boucles sont particulièrement adaptées aux vecteurs.
Si vous connaissez C, c’est facile, c’est la même chose.
Simulation “vectorielle” d’une loi discrète On peut écrire une version de la simulation d’une loi discrète sans boucle.
Un premier test pour vérifier que ça marche.
Simulation des temps d’atteinte On tire le premier œuf en (U1,V 1), U1 (l’indice de ligne) et V 1 (l’indice de colonne) étant indépendantes, de loi uniforme respectivement sur {1,…,p} et {1,…,q}. Si le premier œuf se trouve en (U1,V 1), le temps d’atteinte de cet œuf par A (parcours en colonne) est donné par
et, pour B (parcours en ligne), par
avec des formules identiques pour le deuxième œuf :
U2 et V 2 étant indépendantes, toujours de lois uniformes, indépendantes du couple (U1,V 1).
Noter que l’on peut calculer la loi (commune) de t1A, t 1B, t 2A, t 2B (loi uniforme sur {1,…,p × q}) et montrer que t1A s’obtient comme une fonction déterministe de t 1B (voir complément 1).
Avec ces éléments, il est facile d’écrire une fonction qui réalise le tirage des deux œufs dans la matrice et d’en déduire les temps que mettent A et B pour trouver le premier œuf.
Il ne reste plus qu’à faire suffisamment de tirages pour répondre (en partie) à la question posée.
Le elseif et le else sont optionnels.
Noter que le théorème de la limite centrale permet (exercice !) de montrer que l’erreur “probable maximale” est de l’ordre de 1∕ (C’est ce même résultat qui permet d’évaluer approximativement l’erreur d’un sondage d’opinion).
Dans le cas p = 2, q = 3 on arrive assez facilement (N = 10000 suffit largement) à se convaincre que B gagne en moyenne. C’est plus difficile pour (p = 3,q = 4) (N = 100000 convient). Ça devient délicat pour (p = 4,q = 5) (il faut prendre N ≈ 1000000 pour conclure que c’est A qui gagne). Dans les cas où p = q (où l’on peut prouver qu’il y a égalité des probabilités, voir le complément 3), une méthode de simulation ne sera jamais concluante.
Il nous faut une méthode exacte de calcul de ces probabilités. C’est ce que nous allons faire maintenant.
L’espace de probabilité Ω étant fini, il suffit d’énumérer Ω pour calculer la probabilité : on génère toutes les valeurs possibles pour les positions des œufs (i1,j1) et (i2,j2) (tous ces couples (de couples !) sont équiprobables), on calcule TA et TB et l’on fait des stats sur celui qui gagne. On en profite pour calculer la loi du couple (TA,TB) et pour vérifier que les lois de TA et TB sont identiques (voir le complément 2 si vous souhaitez une preuve de ce fait).
Attendu : ones, zeros, initialiser les matrices avant les boucles sum(.,opt) et norm
Les fonctions histo et report. La première calcule un histogramme à partir de valeurs. report imprime quelques informations à l’écran.
Les langages de type Scilab, MathLab sont relativement lents, tout particulièrement lorsque l’on utilise des boucles, ce qui est la cas ici.
On peut accélérer sensiblement les performances de l’algorithme en supprimant les boucles à l’aide de fonctions vectorielles.
On utilise des produits de Kronecker .*. de matrice A et B, où chaque terme Aij de A est remplacé par la matrice AijB. Si A est de taille nA × mA et B est de taille nB × mB, A .*. B est de taille nAnB × mAmA.
Voici un exemple de ce que donne une réécriture efficace de la fonction qui_gagne_elem. Le gain d’efficacité se fait au détriment de la lisibilité des codes et d’une utilisation mémoire qui peut être importante.
Ces compléments sont destinés aux élèves souhaitant avoir des clarifications et des preuves concernant le problème posé. Sa lecture ne vous apprendra à programmer en Scilab, elle est conseillé en révision du cours de probabilité de M. Alfonsi du premier semestre.
Complément 1. Les temps aléatoires t1A et t1B suivent tous les deux une loi uniforme sur {1,…,p×q}. En effet, si k est un nombre entier compris entre 0 et p × q − 1, il s’écrit de façon unique sous la forme k = i1 × p + j1 avec i1 ∈{0,1,…,q − 1} et j1 ∈{0,1,…,p − 1}. On a donc :
Ces temps ne sont pas indépendants, en fait t1B s’obtient par une permutation déterministe à partir de t1A : il existe une permutation σ de {1,…,pq} telle que
Il est facile de s’en convaincre, puisque à chaque case (i,j) correspond un temps d’atteinte diffèrent pour chacun des joueurs : pour construite la permutation, il suffit donc de mettre en relation le temps mis par A pour atteindre (i,j) avec le temps mis par B pour atteindre la même case. Voir page 21 pour un programme qui calcule explicitement cette permutation.
On peut aussi voir que, lorsque l’on considère le jeu avec un seul œuf, on a toujours un problème équitable (i.e. on a P(t1A < t1B) = P(t1B < t1A)). Pour s’en convaincre on écrit
où U′1 = U1 − 1 suit une loi uniforme sur {0,…,q − 1} et V ′1 = V 1 − 1 suit une loi uniforme sur {0,…,p − 1} et sont indépendants. Comme (U′1,V ′1) suit la même loi que (q − 1 − U′1,p − 1 − V ′1), on a
Complément 2. Pour montrer que TA et TB suivent la même loi, on commence par remarquer qu’il existe une permutation σ de {1,…,p × q} telle que tB1 = σ(tA1) et tB2 = σ(tA2) (elle est calculé plus tard, mais c’est facile de s’en convaincre). Comme tA1 et tA2 suivent des lois uniformes sur {1,…,p × q}, c’est aussi le cas de tB1 et tB2 (exercice). tB1 et tB2 sont indépendantes, puisque fonctions de variables aléatoires indépendantes. Les couples (tA1,tA2) et (tB1,tB2) suivent donc la même loi et l’on conclut que TA et TB ont même loi puisque
Il convient de noter que les temps aléatoires TA et TB ne sont pas indépendants. C’est d’ailleurs ce qui fait l’intérêt de la question posée (Que se passerait-il si TA et TB étaient indépendants ?).
Complément 3. On peut montrer que si σ2 = Id, alors la loi du couple (TA,TB) est identique à celle du couple (TB,TA). En effet on a :
Donc, en utilisant le fait que la loi de (tA1,tA2) est identique à celle de (σ(tA1),σ(tA2)), on obtient :
Et lorsque σ2 = Id, on en déduit P = P(TB = k,TA = l). Ceci permet d’en déduire (exercice simple mais instructif) que
La relation σ2 = Id est vérifiée lorsque p = q (on peut le vérifier à l’aide du programme Scilab ou ... le prouver si on est courageux). Ce qui prouve le résultat (attendu !) que lorsque p = q le jeux est équilibré.
On peut généraliser ce jeu à proposant aux deux joueurs de choisir une permutation σ d’un ensemble fini .
On tire alors au hasard indépendemment la place des deux objets entre 1 et taille. On note t1 la première variable aléatoire et t2 la deuxième. t1 et t2 sont supposées indépendantes et de loi uniforme sur .
Le joueur A parcours les cases dans l’ordre σA(1),…,σA(taille) et B dans l’ordre σB(1),…,σB(taille), ainsi
La question est de comparer P(TA < TB) et P(TB < TA). Le programme suivant répond à cette question.
Évidemment pour gagner il faut bien choisir sa permutation (ou avoir de la chance). Voici une fragment qui permet de tester le programme précédent. Exécuter le plusieurs fois et vérifier que l’on peut gagner ou perdre ou (parfois) être dans un cas d’égalité.
On peut expliciter la permutation de [1 : p×q] générée par la transposition d’une matrice p×q en une matrice q × p. Plus précisément, on cherche la permutation qui permet d’exprimer le temps d’atteinte du premier œuf par B tB1 en fonction du temps d’atteinte de ce même œuf par A, tA1 :
Cette permutation est facile à calculer : il suffit, pour tout (i,j) d’envoyer le temps d’atteinte de A sur le temps d’atteinte de B.
Noter que cette permutation σ permet de reformuler le problème initial puisque l’on s’intéresse à la loi de du couple TA = min(tA1,t A2) et T B = min(tB1,t B2) où t A1,t A2 sont indépendants de loi uniforme sur [1 : p × q] et tB1 = σ(t A1) et t B2 = σ(t A2). La permutation σ est le seul paramètre à la question.
Le fragment suivant répond à la question initiale en utilisant σ.
On vérifie que la loi reste identique avec les deux méthodes proposées.
On peut montrer (voir le complément 3 pour une preuve détaillée) que si σ2 = Id, la loi du couple (TA,TB) est identique à celle du couple (TB,TA) (la loi du couple est symétrique), et donc que P(TA > TB) = P(TA > TB) (on est dans un cas d’égalité). C’est en particulier le cas lorsque p = q, ce qui n’est pas surprenant.
A partir d’une permutation σA choisie par A, B peut construire une permutation σB meilleure en probabilité et ce quel que soit le choix de A ! ... et B peut aussi faire la même chose. Pour cela il suffit de trouver un permutation σ0 meilleure que l’identité (il en existe toujours) et le choix σB−1 = σ 0(σA−1) convient alors.
On peut choisir, par exemple, σ0 = [N; 1; 2; 3; 4; …; (N − 1)]. Mais il en existe d’autres.
On peut aussi construire la permutation qui correspond au “zig-zag” (en colonne pour A et en ligne pour B) et comparer avec le choix classique.
On regarde l’effet du choix du zig-zag.