Une marche aléatoire, et la loi exacte de sa position

Ce qu'on montre. Qu'une marche se ramène à une binomiale par un changement de variable, que la loi binomiale se calcule par une récurrence évitant tout coefficient binomial explicite, et que la simulation confirme le calcul.

La loi de $S_n$. Notons $K$ le nombre de pas valant $+1$ : les pas étant indépendants et chacun égal à $+1$ avec la probabilité $\frac{1}{2}$, on a $K\hookrightarrow \mathcal{B}\left(n,\frac{1}{2}\right)$. Les $n-K$ autres pas valent $-1$, donc $$S_n=K-(n-K)=2K-n.$$ Par conséquent $$P(S_n=2k-n)=P(K=k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)\frac{1}{2^n},k\in [[0,n]].$$ On en déduit aussi $E(S_n)=2\times \frac{n}{2}-n=0$ et $V(S_n)=4V(K)=4\times \frac{n}{4}=n$.

La récurrence sur la loi. Plutôt que de calculer $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ — nombre gigantesque pour $n=100$ — on part de $P(K=0)=2^{-n}$ et l'on utilise $$\frac{P(K=k+1)}{P(K=k)}=\frac{\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}=\frac{n-k}{k+1},$$ identité qui se vérifie en écrivant les deux coefficients avec des factorielles. Toutes les valeurs restent alors de l'ordre de $10^{-30}$ à $10^{-1}$, sans débordement.

Le programme.

import numpy as np
import numpy.random as rd

def loi_binomiale_demi(n):
    """p[k] = P(K = k) pour K binomiale(n, 1/2), par recurrence."""
    p = np.zeros(n + 1)
    p[0] = 0.5 ** n
    for k in range(n):
        p[k + 1] = p[k] * (n - k) / (k + 1)
    return p

def proba_exacte(n, seuil):
    """P(S_n >= seuil), avec S_n = 2K - n."""
    p = loi_binomiale_demi(n)
    total = 0.0
    for k in range(n + 1):
        if 2 * k - n >= seuil:
            total = total + p[k]
    return total

def simule(n, M):
    """M positions finales d'une marche de n pas."""
    pas = 2 * rd.binomial(1, 0.5, [M, n]) - 1     # +1 ou -1
    return np.sum(pas, axis=1)

print(np.sum(loi_binomiale_demi(100)))            # 1.0 : controle
print(proba_exacte(100, 10))                      # 0.1841
S = simule(100, 10 ** 5)
print(np.mean(S >= 10), np.mean(S), np.var(S))    # ~0.184, ~0, ~100

Les résultats. Le calcul exact donne $P(S_{100}\ge 10)=P(K\ge 55)\approx 0,184$, et la simulation sur $10^5$ marches affiche une fréquence voisine de $0,184$. La moyenne empirique de $S$ est proche de $0$ et sa variance proche de $100$, conformément à $E(S_{100})=0$ et $V(S_{100})=100$.

Point délicat. $S_n$ a la parité de $n$ : pour $n=100$, seules les valeurs paires sont atteintes, et $P(S_{100}=9)=0$. Un histogramme de pas $1$ montrerait donc une barre vide sur deux, qu'on prendrait à tort pour un défaut de la simulation.