Algorithmes et simulation

Introduction

L'espérance se calcule avec la loi. Mais on peut aussi l'observer : en répétant l'expérience un grand nombre de fois, la moyenne des résultats s'en approche. Cette leçon fait les deux avec Python : calculer espérance et variance à partir d'une loi, puis simuler une variable aléatoire et mesurer de combien la moyenne d'un échantillon s'écarte de l'espérance.

1. Calculer l'espérance et la variance d'une loi

Une loi se donne par deux listes de même longueur : les valeurs, et leurs probabilités. Les fonctions suivantes traduisent mot pour mot les définitions.

from math import sqrt

def esperance(valeurs, probas):
    E = 0
    for i in range(len(valeurs)):
        E = E + valeurs[i] * probas[i]
    return E

def variance(valeurs, probas):
    E = esperance(valeurs, probas)
    V = 0
    for i in range(len(valeurs)):
        ecart = valeurs[i] - E
        V = V + pow(ecart, 2) * probas[i]
    return V

def ecart_type(valeurs, probas):
    return sqrt(variance(valeurs, probas))

Le jeu de dé de la leçon 1 : esperance([-2, 10], [5/6, 1/6]) affiche -2.220446049250313e-16, soit -0,000…0002 : c'est 0, à l'arrondi de la machine près. Et variance([-2, 10], [5/6, 1/6]) affiche 19.999999999999996 : c'est 20.

Les nombres à virgule de la machine : Python calcule avec des nombres à virgule approchés : 5/6 ou 0,3 n'ont pas d'écriture exacte en machine. De même, variance([0, 1, 2], [0.3, 0.5, 0.2]) affiche 0.49000000000000005 au lieu de 0,49. Ce n'est pas une erreur de la fonction : on arrondit l'affichage.

2. Simuler une variable aléatoire

Le module random fournit le hasard :

random() renvoie un nombre au hasard dans [0 ; 1[ ; la condition random() < p est donc vraie avec la probabilité p ;
randint(a, b) renvoie un entier au hasard entre a et b inclus, chacun avec la même probabilité.

from random import random, randint

def gain():
    # le jeu de dé : +10 € sur un 6, -2 € sinon
    if randint(1, 6) == 6:
        return 10
    return -2

Chaque appel de gain() simule une partie : il renvoie une valeur de la variable aléatoire, avec la bonne probabilité.

3. La moyenne d'un échantillon

Un échantillon de taille n de X, ce sont n résultats obtenus en répétant l'expérience n fois, de façon indépendante. On fait la moyenne m de ces n résultats.

def moyenne_echantillon(n):
    s = 0
    for i in range(n):
        s = s + randint(1, 6)
    return s / n

Ici X est le résultat d'un dé équilibré : μ = E(X) = 3,5. Chaque appel de moyenne_echantillon(100) renvoie une moyenne différente — une exécution a donné 3,6, puis 3,32 —, en général proche de 3,5, mais rarement égale.

Ce qu'on observe : Plus l'échantillon est grand, plus sa moyenne est proche, en général, de l'espérance. C'est cette observation que la Terminale démontrera (loi des grands nombres).

4. Mesurer l'écart : la règle des 2σ/(√(n))

On simule N échantillons de taille n, et l'on compte la proportion de ceux dont la moyenne m est à une distance de μ au plus égale à 2σ/(√(n)), où σ est l'écart type de X.

def proportion(N, n, mu, sigma):
    compteur = 0
    for j in range(N):
        m = moyenne_echantillon(n)
        if abs(m - mu) <= 2 * sigma / sqrt(n):
            compteur = compteur + 1
    return compteur / N

Le dé, avec N = 1000 échantillons : Pour un dé, μ = 3,5 et σ = √(35/12) ≈ 1,708.

avec n = 25 : 2σ/(√(25)) ≈ 0,68, et une exécution a donné une proportion de 0,957 ;
avec n = 100 : 2σ/(√(100)) ≈ 0,34, et une exécution a donné 0,962.

Dans les deux cas, environ 95 % des moyennes d'échantillons tombent à moins de 2σ/(√(n)) de l'espérance — et l'intervalle est deux fois plus étroit quand l'échantillon est quatre fois plus grand.

Une observation, pas un théorème : Les proportions obtenues changent d'une exécution à l'autre, et « environ 95 % » est ce qu'on constate sur de nombreux exemples : le programme de Première demande de l'observer. La Terminale démontrera une garantie plus faible — au moins 75 % des moyennes à moins de 2σ/(√(n)) de l'espérance, par l'inégalité de Bienaymé-Tchebychev — ; les 95 % s'expliquent au-delà du lycée.

5. Un autre algorithme : la fréquence des lettres d'un texte

Compter les lettres d'un texte, c'est simuler… sans hasard : on parcourt le texte et l'on calcule la fréquence de chaque lettre. On n'utilise que des listes : la lettre "e" est à la position alphabet.index("e") de la chaîne alphabet.

def frequences(texte):
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    effectifs = [0] * 26
    total = 0
    for lettre in texte.lower():
        if lettre in alphabet:
            effectifs[alphabet.index(lettre)] += 1
            total = total + 1
    return [e / total for e in effectifs]

Sur un long texte, en français comme en anglais, la lettre la plus fréquente est le e, mais les fréquences des autres lettres diffèrent d'une langue à l'autre : comparer les deux listes permet de reconnaître la langue d'un texte. Ces fréquences, stables d'un long texte à l'autre, se comportent comme des probabilités : c'est sur elles que reposent les premières méthodes pour casser un code secret.

À retenir

Résumé :

Une loi se code par deux listes, valeurs et probabilités ; espérance et variance s'en déduisent par une boucle.
random() < p simule un événement de probabilité p ; randint(a, b) un entier équiprobable entre a et b.
La moyenne d'un échantillon varie d'un échantillon à l'autre, et se rapproche en général de l'espérance quand n augmente.
On observe qu'environ 95 % des moyennes d'échantillons de taille n sont à moins de 2σ/(√(n)) de l'espérance.