Comptez les arrivées avec le processus de Poisson

Une API de prédiction reçoit en moyenne 4 requêtes par seconde. Mais « en moyenne » cache beaucoup de choses : certaines secondes, elle n’en reçoit aucune ; d’autres, elle en reçoit 8 ou 10. Pour dimensionner le service, il faut connaître la loi du nombre de requêtes, pas seulement sa moyenne.

Quand les arrivées proviennent d’un grand nombre d’utilisateurs indépendants, qui agissent chacun rarement, un modèle s’impose presque toujours : le processus de Poisson. C’est le processus d’arrivée de référence des files d’attente, et c’est aussi le plus simple des processus de naissance et de mort. Nous suivrons cette API tout au long du chapitre.

Compter des événements au fil du temps

Un processus de comptage $(N_t)_{t \geq 0}$ compte le nombre d’événements survenus dans l’intervalle $[0, t]$ : ici, le nombre de requêtes reçues depuis l’instant 0. Il part de 0, ne prend que des valeurs entières et ne décroît jamais. Le nombre d’événements dans un intervalle $]s, t]$ est l’accroissement $N_t - N_s$.

Une trajectoire simulée de l'API sur 3 secondes : le compteur N_t monte d'une marche à chaque requête et ne redescend jamais. Il fluctue autour de la droite de moyenne 4t, parfois au-dessus, parfois en dessous.

Un processus de comptage est un processus de Poisson de taux (ou d’intensité) $\lambda > 0$ si :

1. $N_0 = 0$ ;
2. ses accroissements sont indépendants : les nombres d’arrivées sur des intervalles disjoints sont des variables aléatoires indépendantes (ce qui arrive entre 10 h et 10 h 01 ne dit rien sur ce qui arrive entre 11 h et 11 h 01) ;
3. ses accroissements sont stationnaires : la loi de $N_{t+s} - N_s$ ne dépend que de la durée $t$, pas de l’instant $s$ ;
4. sur un petit intervalle de durée $h$, il arrive une requête avec probabilité $\lambda h + o(h)$ et deux ou plus avec probabilité $o(h)$ : les arrivées sont isolées.

La dernière condition dit exactement qu’on a un processus de naissance et de mort de naissance pure : $\lambda_n = \lambda$ pour tout $n$ et $\mu_n = 0$. Le graphe est une ligne où l’on ne fait que monter :

      λ        λ        λ               λ
  0 ─────► 1 ─────► 2 ─────► 3  ···  n ─────► n+1  ···

Attention

Avec des taux de mort nuls, aucun état n’est récurrent : on quitte chaque état pour ne jamais y revenir. Le processus de Poisson n’a donc pas de régime stationnaire, et c’est normal : le nombre total d’arrivées croît sans limite. Ce qui nous intéresse, c’est son régime transitoire.

Le nombre d’arrivées suit une loi de Poisson

Écrivons les équations du régime transitoire du chapitre 6 avec $\lambda_n = \lambda$ et $\mu_n = 0$ :

$$p_0'(t) = -\lambda\, p_0(t), \qquad p_n'(t) = \lambda\, p_{n-1}(t) - \lambda\, p_n(t) \quad (n \geq 1).$$

La première donne, avec $p_0(0) = 1$, $p_0(t) = e^{-\lambda t}$. La deuxième, pour $n = 1$, est une équation linéaire dont la solution avec $p_1(0) = 0$ est $p_1(t) = \lambda t\, e^{-\lambda t}$. En continuant par récurrence (méthode de variation de la constante), on obtient

$$P(N_t = n) = e^{-\lambda t}\, \frac{(\lambda t)^n}{n!}, \qquad n = 0, 1, 2, \dots$$

Le nombre d’arrivées sur une durée $t$ suit une loi de Poisson de paramètre $\lambda t$. Grâce à la stationnarité des accroissements, c’est vrai sur n’importe quel intervalle de longueur $t$ : $N_{s+t} - N_s$ suit la même loi. On en déduit

$$E[N_t] = \lambda t, \qquad \operatorname{Var}(N_t) = \lambda t.$$

Le taux $\lambda$ est donc le nombre moyen d’événements par unité de temps, ce qui justifie son nom.

Exemple

Pour notre API, $\lambda = 4$ requêtes par seconde. Sur une seconde, $N_1$ suit une loi de Poisson de paramètre 4 :

• aucune requête : $e^{-4} \approx 0{,}018$, soit environ une seconde sur 55 ;
• exactement 4 requêtes (la moyenne) : $e^{-4}\,4^4/4! \approx 0{,}195$, moins d’une chance sur cinq ;
• au moins 8 requêtes (le double de la moyenne) : environ 0,051, soit une seconde sur 20.

Si le service ne peut absorber que 7 requêtes par seconde, il sera débordé environ 5 % des secondes, alors que sa capacité moyenne est presque le double de la demande. Voilà pourquoi la moyenne ne suffit pas.

La loi de Poisson de paramètre 4 : la valeur moyenne n'arrive qu'une seconde sur cinq, et la queue au-delà de 7 (en rose) pèse encore 5 % des secondes.

Les temps entre deux arrivées sont exponentiels

Regardons maintenant le processus autrement : non plus « combien d’arrivées ? », mais « quand ? ». Notons $T_1$ l’instant de la première requête. Attendre plus de $t$ secondes, c’est n’avoir reçu aucune requête dans $[0, t]$ :

$$P(T_1 > t) = P(N_t = 0) = e^{-\lambda t}.$$

$T_1$ suit donc une loi exponentielle de paramètre $\lambda$. Grâce à l’indépendance et à la stationnarité des accroissements, le processus « repart à zéro » après chaque arrivée : les temps inter-arrivées successifs sont indépendants et de même loi $\mathcal E(\lambda)$, de moyenne $1/\lambda$ (ici 0,25 seconde).

La réciproque est vraie et très utile : si l’on place des événements séparés par des durées indépendantes de loi $\mathcal E(\lambda)$, on obtient un processus de Poisson de taux $\lambda$. C’est ainsi qu’on le simule.

L’instant $S_n$ de la $n$-ième arrivée est la somme de $n$ exponentielles indépendantes. Sa loi s’appelle la loi d’Erlang de paramètres $(n, \lambda)$ (c’est une loi Gamma), de moyenne $n/\lambda$. Pour calculer sa fonction de répartition, on utilise l’équivalence $\lbrace S_n \leq t \rbrace = \lbrace N_t \geq n \rbrace$ : la $n$-ième requête est arrivée avant $t$ si et seulement si on a reçu au moins $n$ requêtes dans $[0, t]$.

Les durées entre requêtes suivent une exponentielle de moyenne 0,25 s : les petits écarts sont les plus fréquents. L'instant de la n-ième arrivée (loi d'Erlang) se décale à la moyenne n/4 et s'étale quand n grandit.

À retenir

Deux visages du même processus de Poisson de taux $\lambda$ : le nombre d’arrivées sur une durée $t$ suit une loi de Poisson de paramètre $\lambda t$, et les durées entre arrivées sont des exponentielles indépendantes de moyenne $1/\lambda$.

Piège

Vous arrivez à un arrêt de bus où les bus passent selon un processus de Poisson, en moyenne toutes les 10 minutes. Combien de temps attendrez-vous en moyenne ? Pas 5 minutes, mais 10 : par l’absence de mémoire, le temps restant jusqu’au prochain bus est encore exponentiel de moyenne 10 minutes, quel que soit le temps écoulé depuis le précédent. L’intuition « j’arrive au milieu d’un intervalle » ne vaut que pour des passages réguliers.

Superposer et décomposer des flux

Deux propriétés rendent le processus de Poisson très commode pour modéliser des réseaux de files d’attente.

Superposition. Si deux flux indépendants sont des processus de Poisson de taux $\lambda_1$ et $\lambda_2$, leur réunion est un processus de Poisson de taux $\lambda_1 + \lambda_2$. Supposons que l’API reçoive 3 requêtes par seconde du site web et 1 de l’application mobile, de façon indépendante : au total, c’est bien un Poisson de taux 4. C’est la même propriété que « le minimum d’exponentielles est exponentiel » (chapitre 5).

Décomposition. Inversement, si chaque arrivée d’un Poisson de taux $\lambda$ est aiguillée vers la destination $i$ avec probabilité $p_i$, indépendamment des autres, alors les flux obtenus sont des processus de Poisson indépendants de taux $p_i\,\lambda$. Si l’API envoie 70 % des requêtes vers un modèle A et 30 % vers un modèle B (un test A/B, par exemple), le modèle A reçoit un Poisson de taux 2,8 et le modèle B un Poisson de taux 1,2. La probabilité que le modèle B ne reçoive aucune requête pendant une seconde vaut $e^{-1{,}2} \approx 0{,}30$.

Superposition : le flux de l'API est la simple réunion des deux flux (taux 3 + 1 = 4). Décomposition : chaque requête est ensuite aiguillée au hasard, ce qui donne deux flux de Poisson plus clairsemés, de taux 2,8 et 1,2.

L’indépendance des deux flux décomposés est un résultat étonnant : savoir que le modèle A vient de recevoir un pic de requêtes ne dit rien sur ce qu’a reçu le modèle B.

Simuler et vérifier les hypothèses

La simulation découle directement de la propriété des temps inter-arrivées :

import numpy as np

rng = np.random.default_rng(42)
lam, duree = 4.0, 10_000.0                           # 4 requêtes/s pendant 10 000 s

# Inter-arrivées exponentielles de moyenne 1/lam, puis instants d'arrivée cumulés
inter = rng.exponential(1 / lam, size=int(lam * duree * 1.2))
arrivees = np.cumsum(inter)
arrivees = arrivees[arrivees < duree]

# Nombre de requêtes dans chaque seconde
comptes = np.bincount(arrivees.astype(int), minlength=int(duree))
print(comptes.mean(), comptes.var())                 # tous deux proches de 4
print((comptes == 0).mean(), (comptes >= 8).mean())  # proches de 0.018 et 0.051

# Décomposition : chaque requête va vers A avec probabilité 0.7
vers_A = rng.random(arrivees.size) < 0.7
print(vers_A.sum() / duree)                          # proche de 2.8 requêtes/s

La dernière vérification est aussi la plus utile sur des données réelles : pour un processus de Poisson, la variance du nombre d’arrivées par intervalle égale sa moyenne. Si vous observez une variance bien plus grande que la moyenne, les arrivées arrivent en rafales (un utilisateur qui envoie un lot de requêtes, un pic à la sortie d’une newsletter) et le modèle de Poisson sous-estimera les pics. De même, si le taux varie au cours de la journée, les accroissements ne sont plus stationnaires : on découpe alors la journée en tranches où le taux est à peu près constant.

Même moyenne, 4 requêtes par seconde, mais pas la même variance : pour un flux de Poisson elle vaut aussi environ 4, alors que des rafales la triplent et produisent des secondes à 15 ou 20 requêtes que le modèle de Poisson jugerait presque impossibles.

En entretien

« Un processus de Poisson de taux $\lambda$ modélise des arrivées indépendantes et isolées : le nombre d’arrivées sur une durée $t$ suit une loi de Poisson de moyenne $\lambda t$, et les inter-arrivées sont exponentielles de moyenne $1/\lambda$. Pour le tester sur des données, je compare la variance et la moyenne des comptes par intervalle. »

En résumé

• Un processus de Poisson de taux $\lambda$ est un processus de comptage avec $N_0 = 0$, des accroissements indépendants et stationnaires, et des arrivées isolées ($P(N_h = 1) = \lambda h + o(h)$). C’est un processus de naissance pure.
• $N_{s+t} - N_s$ suit une loi de Poisson de paramètre $\lambda t$ : $P = e^{-\lambda t}(\lambda t)^n/n!$, avec moyenne et variance $\lambda t$.
• Les inter-arrivées sont indépendantes de loi $\mathcal E(\lambda)$ ; l’instant de la $n$-ième arrivée suit une loi d’Erlang $(n, \lambda)$ de moyenne $n/\lambda$. On simule un Poisson en cumulant des exponentielles.
• Superposition : Poisson($\lambda_1$) + Poisson($\lambda_2$) indépendants = Poisson($\lambda_1 + \lambda_2$). Décomposition aléatoire avec probabilités $p_i$ : Poisson indépendants de taux $p_i\lambda$.
• Sur des données réelles, vérifiez que la variance des comptes est proche de leur moyenne et que le taux est stable dans le temps.

Exercices

Exercice · Tickets au support

facile

Un service de support reçoit des tickets selon un processus de Poisson de taux 6 par heure.

1. Quelle est la probabilité de ne recevoir aucun ticket pendant 20 minutes ?
2. Combien de tickets reçoit-on en moyenne sur une journée de 8 heures ? Avec quel écart-type ?
3. Quelle est la durée moyenne entre deux tickets ?

Voir la solution

1. Sur 20 minutes, soit $1/3$ d’heure, le nombre de tickets suit une loi de Poisson de paramètre $6 \times \tfrac13 = 2$. La probabilité de n’en recevoir aucun vaut $e^{-2} \approx 0{,}135$.
2. Sur 8 heures, le paramètre vaut $6 \times 8 = 48$ : 48 tickets en moyenne, avec une variance de 48, donc un écart-type de $\sqrt{48} \approx 6{,}9$.
3. Les inter-arrivées sont exponentielles de moyenne $1/6$ d’heure, soit 10 minutes.

En code

Python

import numpy as np
from scipy.stats import poisson

taux = 6                                  # tickets par heure
print(poisson.pmf(0, taux / 3))           # 0.1353 : aucun ticket en 20 minutes
jour = poisson(taux * 8)                  # journée de 8 heures
print(jour.mean(), jour.std())            # 48.0 6.93
print(60 / taux)                          # 10.0 minutes entre deux tickets

R

taux <- 6                               # tickets par heure
dpois(0, taux / 3)                      # 0.1353 : aucun ticket en 20 minutes
c(moyenne = taux * 8, ecart_type = sqrt(taux * 8))   # 48 6.93
60 / taux                               # 10 minutes entre deux tickets

Exercice · Test A/B sur une API

moyen

L’API du chapitre reçoit un Poisson de taux 4 requêtes par seconde, aiguillées à 70 % vers le modèle A et à 30 % vers le modèle B.

1. Quelle est la probabilité que le modèle A reçoive au moins une requête pendant une seconde donnée ?
2. Quelle est la probabilité que l’API reçoive au plus 5 requêtes en 2 secondes ?
3. Pendant une seconde, le modèle A a reçu 6 requêtes, bien plus que sa moyenne. Quelle est la loi du nombre de requêtes reçues par B pendant cette même seconde ?

Voir la solution

1. A reçoit un Poisson de taux 2,8 : $P(\text{au moins une}) = 1 - e^{-2{,}8} \approx 0{,}939$.
2. Sur 2 secondes, le nombre total suit une loi de Poisson de paramètre 8. $P(N \leq 5) = e^{-8}\sum_{k=0}^{5} 8^k/k! \approx 0{,}191$.
3. Par la propriété de décomposition, les flux vers A et vers B sont indépendants. Le nombre de requêtes de B suit donc toujours une loi de Poisson de paramètre 1,2, quoi qu’ait reçu A.

En code

Python

import numpy as np
from scipy.stats import poisson

print(1 - poisson.pmf(0, 0.7 * 4))        # 0.9392 : A reçoit au moins une requête
print(poisson.cdf(5, 4 * 2))              # 0.1912 : au plus 5 requêtes en 2 s

# Indépendance des flux décomposés : simulation seconde par seconde
rng = np.random.default_rng(0)
total = rng.poisson(4, 200_000)
vers_A = rng.binomial(total, 0.7)
vers_B = total - vers_A
print(np.corrcoef(vers_A, vers_B)[0, 1])  # -0.0005, corrélation nulle
print(vers_B[vers_A == 6].mean(), vers_B.mean())   # 1.195 1.201 : B garde sa moyenne 1.2

R

1 - dpois(0, 0.7 * 4)                   # 0.9392 : A reçoit au moins une requête
ppois(5, 4 * 2)                         # 0.1912 : au plus 5 requêtes en 2 s

# Indépendance des flux décomposés : simulation seconde par seconde
set.seed(0)
total <- rpois(2e5, 4)
vers_A <- rbinom(length(total), total, 0.7)
vers_B <- total - vers_A
cor(vers_A, vers_B)                     # 0.0005, corrélation nulle
c(mean(vers_B[vers_A == 6]), mean(vers_B))   # 1.200 1.197 : B garde sa moyenne 1.2

Exercice · L'instant de la troisième requête

difficile

Toujours avec $\lambda = 4$ requêtes par seconde, on note $S_3$ l’instant d’arrivée de la troisième requête.

1. Quelle est sa moyenne ?
2. Calculez $P(S_3 \leq 1)$, la probabilité que la troisième requête arrive dans la première seconde.
3. Le serveur met 1 seconde à démarrer et ne commence à traiter qu’à partir de là. Quelle est la probabilité qu’au moins trois requêtes l’attendent à son démarrage ?

Voir la solution

1. $S_3$ est la somme de trois inter-arrivées exponentielles de moyenne 0,25 s : $E[S_3] = 3/4 = 0{,}75$ s.
2. On utilise $\lbrace S_3 \leq 1 \rbrace = \lbrace N_1 \geq 3 \rbrace$, avec $N_1$ de loi de Poisson de paramètre 4 :

$$P(S_3 \leq 1) = 1 - e^{-4}\left(1 + 4 + \frac{4^2}{2}\right) = 1 - 13\,e^{-4} \approx 0{,}762.$$

3. C’est exactement la même question, formulée autrement : au moins trois requêtes attendent si et seulement si la troisième est arrivée avant 1 s. La probabilité vaut environ 0,762.

En code

Python

import numpy as np
from scipy.stats import gamma, poisson

lam = 4
S3 = gamma(a=3, scale=1 / lam)            # loi d'Erlang(3, lam)
print(S3.mean())                          # 0.75
print(S3.cdf(1), 1 - poisson.cdf(2, lam), 1 - 13 * np.exp(-4))   # 0.7619 (trois fois)

# Simulation : somme de trois inter-arrivées exponentielles
rng = np.random.default_rng(0)
s3 = rng.exponential(1 / lam, (500_000, 3)).sum(axis=1)
print(s3.mean(), (s3 <= 1).mean())        # 0.7498 0.7621

R

lam <- 4
3 / lam                                 # 0.75, moyenne d'une Erlang(3, lam)
c(pgamma(1, shape = 3, rate = lam),     # P(S3 <= 1)
  1 - ppois(2, lam),                    # = P(N1 >= 3)
  1 - 13 * exp(-4))                     # 0.7619 (trois fois)

# Simulation : somme de trois inter-arrivées exponentielles
set.seed(0)
s3 <- rowSums(matrix(rexp(3 * 5e5, lam), ncol = 3))
c(mean(s3), mean(s3 <= 1))              # 0.7506 0.7615