Module L11 · Partie G · Mathématiques de l’informatique

Probabilités et statistiques : raisonner sous incertitude.

Un capteur ment un peu à chaque mesure. Un modèle d’IA se trompe parfois. Un algorithme aléatoire est plus rapide qu’un déterministe. Ce module donne les outils pour quantifier l’incertitude : lois, espérance, variance, loi des grands nombres, théorème central limite, estimation, Bayes, tests — toujours vérifiés par simulation, parce que la simulation est l’expérience du probabiliste.

Durée : 3 séances · Prérequis : modules 3e « simulations », L10. Objectifs : variables aléatoires et lois usuelles, espérance/variance et leurs propriétés, LGN et TCL, estimation et intervalles de confiance, règle de Bayes et inférence, chaînes de Markov, tests d’hypothèses, Monte-Carlo et bootstrap.

Fiche de cours · Définitions

Probabilités et statistiques : définitions

Fiche de cours · Formules

Lois et formules à connaître

Fiche de cours · Théorèmes et démonstrations

Démonstrations à savoir refaire (1/2)

Fiche de cours · Théorèmes et démonstrations

Démonstrations à savoir refaire (2/2)

Fiche de cours · Méthodes

Méthodes et pièges

Pièges : confondre P(A | B) et P(B | A) (procureur) ; supposer indépendantes des variables corrélées (les capteurs d’un même robot subissent les mêmes vibrations) ; corrélation ≠ causalité ; « significatif » ≠ « important » ; oublier que la variance de la moyenne décroît en 1/n, pas l’écart-type ; utiliser la normale pour des quantités positives (durées) ou bornées (proportions proches de 0 ou 1).

Fiche de cours · Exercices corrigés

Exercices corrigés

01 / Lois

Les lois usuelles, simulées et comparées à la théorie

01 / Lois

Espérance, variance, et leurs règles

La linéarité de l’espérance ne demande aucune indépendance : c’est l’outil le plus puissant de l’analyse d’algorithmes aléatoires (« le nombre attendu de comparaisons est la somme des probabilités de chaque comparaison »). La variance, elle, ne s’additionne que pour des variables indépendantes (ou non corrélées).

02 / Grands nombres

Loi des grands nombres et théorème central limite

02 / Grands nombres

Estimer, avec un intervalle de confiance

Un intervalle de confiance à 95 % n’est pas « la vraie valeur a 95 % de chances d’être dedans » (elle est fixe !) mais « la procédure qui produit cet intervalle capture la vraie valeur 95 % du temps ». La simulation ci-dessus le montre. Le bootstrap (rééchantillonner ses propres données) est l’outil moderne quand la formule n’existe pas.

03 / Bayes

La règle de Bayes : mettre à jour une croyance

03 / Bayes

Chaînes de Markov : le futur ne dépend que du présent

Les chaînes de Markov modélisent les machines à états probabilistes, les files d’attente, les textes (le « modèle de langue » le plus simple, ancêtre des LLM), PageRank, et servent d’outil de simulation (MCMC) en physique et en statistique bayésienne. Les temps d’atteinte se calculent par un système linéaire (module L10) — c’est aussi la base de l’apprentissage par renforcement (module L16).

04 / Tests

Tester une hypothèse : le dé est-il truqué ? le modèle est-il meilleur ?

04 / Tests

Algorithmes aléatoires : quand le hasard est plus rapide

Miller-Rabin est un algorithme Monte-Carlo (toujours rapide, parfois faux avec probabilité contrôlée) ; le tri rapide randomisé est Las Vegas (toujours juste, temps aléatoire). Le hasard sert aussi au hachage (module L03), aux protocoles réseau (backoff), à la cryptographie, aux tests par propriétés et à l’optimisation (recuit simulé).

Cours

Cours 1 — Le formalisme : univers, événements, probabilités, variables aléatoires

Cours

Cours 2 — Exemple travaillé : combien de mesures pour décider ? (puissance d’un test)

Problème. Un nouveau firmware est censé réduire le temps de parcours de 52 s à 50 s (σ ≈ 6 s entre essais). Combien d’essais par version pour le détecter avec un test au seuil 5 % et une probabilité de détection (puissance) de 80 % ?

Raisonnement. La différence des moyennes de deux échantillons de taille n a un écart-type σ√(2/n). Rejeter H₀ si la différence dépasse 1,96 σ√(2/n) (seuil 5 % bilatéral). Sous H₁ (vraie différence 2 s), on veut P(dépasser le seuil) = 0,8, soit 2 ≥ (1,96 + 0,84) σ√(2/n) ⇒ n ≥ 2 (2,8 σ / 2)² ≈ 141 essais par version. Avec 30 essais (module L11 §04), la puissance n’est que ≈ 25 % : on ratera l’amélioration trois fois sur quatre.

Avant toute expérience (module L24), calculez la puissance : une expérience sous-dimensionnée ne peut conclure ni dans un sens ni dans l’autre, et coûte autant qu’une bonne. Les deux erreurs : type I (fausse alerte, contrôlée par le seuil α) et type II (rater l’effet, contrôlée par la puissance 1 − β).

Cours

Cours 3 — Estimation : biais, variance, maximum de vraisemblance

Estimateur : une fonction des données qui vise un paramètre θ. Ses qualités : biais E[θ̂] − θ (nul pour la moyenne empirique ; non nul pour la variance divisée par n, d’où n − 1) ; variance ; consistance (θ̂ → θ quand n → ∞). Erreur quadratique = biais² + variance : le compromis biais-variance du module L13 vient de là.

Maximum de vraisemblance (MV). Choisir θ qui rend les données observées les plus probables : θ̂ = argmax P(données | θ). Pour des observations indépendantes, on maximise Σ log P(x_i | θ). Exemples : proportion de succès (θ̂ = k/n), moyenne d’une normale (θ̂ = x̄), et — module L13 — la régression logistique est exactement le MV d’un modèle de Bernoulli.

TP guidé

TP — Un rapport statistique complet sur des données de capteurs (sur PC, 2 h 30)

• Données. 10 minutes de lectures d’un capteur de distance (ou simulez : valeur vraie qui change par paliers, bruit gaussien, 2 % d’aberrations, une dérive lente). CSV → NumPy/pandas.
• Description. Histogramme, moyenne, médiane, écart-type, quantiles, boîte à moustaches ; QQ-plot contre une normale (scipy.stats.probplot) : le bruit est-il gaussien ? Les aberrations apparaissent-elles ?
• Estimation. Pour chaque palier : moyenne avec IC à 95 % (formule et bootstrap) ; médiane avec IC bootstrap. Combien de lectures pour ±0,1 cm ?
• Test. Deux paliers ont-ils vraiment des valeurs différentes ? Test t (scipy.stats.ttest_ind) et test de permutation maison : comparez les p-valeurs. Puissance : simulez pour dimensionner.
• Modèle. Ajustez une chaîne de Markov à deux états (« calme » / « bruyant ») sur la variance glissante ; estimez la matrice de transition par comptage ; simulez 1000 secondes et comparez les durées de séjour.
• Rapport. 3 pages avec figures : chaque chiffre a son incertitude ; chaque affirmation (« le bruit est gaussien », « les paliers diffèrent ») a son test et sa p-valeur ; une section « limites ». C’est le format attendu en TIPE et en stage.

Exercices

Exercices auto-corrigés — probabilités

O4 = list(product(range(1, 7), repeat=4)); O3 = list(product(range(1, 7), repeat=3)); O2 = list(product(range(1, 7), repeat=2))
a = F(sum(len(set(w)) == 4 for w in O4), len(O4))
b = sum(F(max(w), len(O3)) for w in O3)
c = F(sum(6 in w for w in O4), len(O4))
pair = [w for w in O2 if any(x % 2 == 0 for x in w)]; d = F(sum(sum(w) == 9 for w in pair), len(pair))

def posterior(res):
    p6, p20 = F(1, 2), F(1, 2)
    for r in res:
        p6 *= F(1, 6) if r <= 6 else 0; p20 *= F(1, 20)
    return p6 / (p6 + p20) if p6 + p20 else F(0)
def nb_lancers_pour(seuil):
    n = 0
    while posterior([1] * n) < seuil: n += 1
    return n

Exercices

Exercices auto-corrigés — statistiques

def ic_moyenne(x, niveau=0.95):
    m, s = x.mean(), x.std(ddof=1); h = 1.96 * s / np.sqrt(len(x)); return m - h, m + h
def couverture(n, repetitions=4000):
    X = rng.normal(5, 2, (repetitions, n)); m = X.mean(1); s = X.std(1, ddof=1); h = 1.96 * s / np.sqrt(n)
    return np.mean((m - h <= 5) & (5 <= m + h))

def test_permutation(a, b, stat, n=5000):
    obs = abs(stat(a, b)); tout = np.concatenate([a, b]); k = len(a); compte = 0
    for _ in range(n):
        rng.shuffle(tout); compte += abs(stat(tout[:k], tout[k:])) >= obs
    return compte / n

05 / Défis

Défi ★ — Le capteur et ses statistiques

x = 50 + rng.normal(0, 2, 1000)
aberr = rng.random(1000) < 0.03
x[aberr] = rng.uniform(0, 400, aberr.sum())
print("moyenne", x.mean().round(2), "médiane", np.median(x).round(2))
def glissante(x, f, k=10): return np.array([f(x[max(0, i - k + 1):i + 1]) for i in range(len(x))])
m1, m2 = glissante(x, np.mean), glissante(x, np.median)
print("erreur RMS moyenne glissante :", np.sqrt(((m1 - 50)**2).mean()).round(2), "| médiane glissante :", np.sqrt(((m2 - 50)**2).mean()).round(2))
print("n pour ±0,2 :", int(np.ceil((1.96 * 2 / 0.2)**2)))

05 / Défis

Défi ★★ — Le bandit à deux bras et la loi de Bayes

def thompson(T=5000):
    s = np.zeros(2); e = np.zeros(2); regret = 0
    for t in range(T):
        bras = np.argmax(rng.beta(s + 1, e + 1))
        succes = rng.random() < p[bras]
        s[bras] += succes; e[bras] += not succes
        regret += p.max() - p[bras]
    return regret
def ab_test(T=5000, exploration=1000):
    s = np.zeros(2); n = np.zeros(2); regret = 0
    for t in range(T):
        bras = t % 2 if t < exploration else np.argmax(s / n)
        s[bras] += rng.random() < p[bras]; n[bras] += 1
        regret += p.max() - p[bras]
    return regret
print("regret A/B :", np.mean([ab_test() for _ in range(100)]).round(1))
print("regret Thompson :", np.mean([thompson() for _ in range(100)]).round(1))

05 / Défis

Défi ★★★ — Esprit prépa : analyse en espérance du tri rapide et du hachage

def tri_compte(t):
    c = 0
    def rec(t):
        nonlocal c
        if len(t) <= 1: return t
        p = random.choice(t); c += len(t) - 1
        return rec([x for x in t if x < p]) + [x for x in t if x == p] + rec([x for x in t if x > p])
    rec(t); return c
for n in (50, 200, 1000):
    moy = sum(tri_compte(random.sample(range(10**6), n)) for _ in range(20)) / 20
    theo = sum(2 / (j - i + 1) for i in range(n) for j in range(i + 1, n))
    print(n, round(moy), round(theo), round(2 * n * math.log(n)))

def collision(m):
    vus = set(); k = 0
    while True:
        h = random.randrange(m); k += 1
        if h in vus: return k
        vus.add(h)
for m in (365, 10**4, 10**6):
    print(m, sum(collision(m) for _ in range(500)) / 500, round(math.sqrt(math.pi * m / 2), 1))

Référence

Les mots à retenir

Pour continuer

Vous quantifiez l’incertitude

Module suivant : le calcul numérique — dérivées, intégrales, équations différentielles, optimisation par descente de gradient : les moteurs des simulateurs et de l’apprentissage.

À faire chez soi

• Refaire toutes les simulations du module 3e « probabilités » avec NumPy et des intervalles de confiance.
• Lire Think Stats chapitres 1-8 (gratuit) et refaire les exercices.
• Prouver que la médiane de n tirages a un point de rupture de 50 %.

← L10SommaireL12 : Calcul numérique et optimisation →