Loi de Bernoulli

La loi de Bernoulli, du nom du mathématicien suisse Jacques Bernoulli, désigne en théorie des probabilités la loi de probabilité d'une variable aléatoire discrète qui prend la valeur 1 (représentant la réalisation du succès de l'événement) avec la probabilité p, et 0 (respectivement la réalisation de l'échec) avec la probabilité q = 1 – p.

La variable aléatoire associée au nombre de piles obtenues au cours d'une partie de pile ou face suit une loi de Bernoulli de paramètre 0,5.

Définition

Une variable aléatoire suivant la loi de Bernoulli est appelée variable de Bernoulli.

Une variable aléatoire Modèle:Mvar suit la loi de Bernoulli de paramètre Modèle:Mvar si les seules valeurs prises par Modèle:Mvar sont 0 ou 1, avec Modèle:Mvar la probabilité que Modèle:Mvar prenne pour valeur 1, et q = 1 – p la probabilité qu'elle prenne pour valeur 0 (avec p et q non nuls)Modèle:,.

De manière formelle :

$X\sim ℬ(p)⟺\mathbb{P}(X=k)=\{\begin{array}{cc}p& \text{si }k=1,\\ 1-p& \text{si }k=0,\\ 0& \text{sinon}\end{array}$

ou, de manière équivalente,

$\mathbb{P}(X=k)=p^k(1-p{)}^{1-k},k\in \{0;1\}$

Propriétés

Généralités

L'espérance mathématique d'une variable aléatoire de Bernoulli vaut p et la variance vaut p(1 – p). Le support d'une telle variable est : $X(\mathrm{\Omega })=\{0,1\}$.

Le kurtosis tend vers l'infini pour des valeurs hautes et basses de p, mais pour p = 1/2 la distribution de Bernoulli a un kurtosis plus bas que toute autre distribution, c’est-à-dire 1.

Plus généralement, toute application mesurable à valeur dans {0,1} est une variable de Bernoulli. Autrement dit, toute fonction indicatrice d'un évènement suit une loi de Bernoulli.

Réciproquement, pour toute variable de Bernoulli Modèle:Mvar définie sur (Ω, A, P), on peut trouver un ensemble mesurable B tel que Modèle:Mvar et la fonction indicatrice de B soient presque sûrement égales : toute variable de Bernoulli est presque sûrement égale à une fonction indicatrice.

Moments

Moments ordinaires et variance

Le premier moment ordinaire, soit l'espérance, d'une loi de Bernoulli se calcule comme suit :

$\begin{array}{cc}𝔼(X)& =\sum _{k=0}^{1}kP(X=k)\\ & =0\times P(X=0)+1\times P(X=1)\\ & =p\\ \end{array}$

De même, pour tout entier naturel non nul n, le moment ordinaire d'ordre n d'une loi de Bernoulli est donné par :

$𝔼(X^n)=p$

Les moments d'ordre 1 et 2 permettent ainsi de retrouver la variance d'une loi de Bernoulli. Par théorème de König-Huygens :

$\begin{array}{cc}\text{V}(X)& =𝔼(X^2)-(𝔼(X){)}^2\\ & =p-p^2\\ & =p(1-p)\\ \end{array}$

Moments centrés

Les trois premiers moments centrés d'une loi de Bernoulli sont donnés par :

$\begin{array}{ccc}𝔼[(X-p{)}^2]& =& p(1-p)\\ 𝔼[(X-p{)}^3]& =& p(1-p)(1-2p)\\ 𝔼[(X-p{)}^4]& =& p(1-p)(3p^2-3p+1)\end{array}$

Fonction génératrice des probabilités

La fonction génératrice des probabilités d'une loi de Bernoulli est :

Fonction génératrice des moments

La fonction génératrice des moments d'une loi de Bernoulli est donné par :

$𝔼(e^{tX})=p{e}^t+1-p$

Distributions liées

Loi binomiale

Modèle:Article détaillé Si XModèle:Ind, XModèle:Ind, … , XModèle:Ind sont des variables aléatoires de Bernoulli de probabilité p et indépendantes, alors leur somme $N$ est une variable aléatoire, qui suit une loi binomiale de paramètres (n, p) :

$N=\sum _{k=1}^n{X}_k\sim ℬ(n,p)$

En particulier, une variable aléatoire de Bernoulli de paramètre p suit une loi binomiale

$ℬ(1,p)$

.

Par indépendance des variables aléatoires XModèle:Ind, cette relation avec la loi de Bernoulli permet d'aisément trouver l'espérance et la variance d'une variable aléatoire suivant une loi binomiale :

Son espérance est donnée par : $𝔼(N)=𝔼(\sum _{k=1}^n{X}_k)=\sum _{k=1}^n𝔼(X_k)=\sum _{k=1}^{n}p=np$ ;

et sa variance par : $\text{V}(N)=\text{V}(\sum _{k=1}^n{X}_k)=\sum _{k=1}^n\text{V}(X_k)=\sum _{k=1}^{n}p(1-p)=np(1-p)$.

Loi de Poisson

Modèle:Article détaillé Soit XModèle:Ind, XModèle:Ind, … , XModèle:Ind un tableau de variables aléatoires de Bernoulli indépendantes, avec paramètres respectifs pModèle:Ind. On note

$S_n=\sum _{k=1}^{a_n}{X}_{k,n}\text{et}{\lambda }_n=𝔼[S_n]=\sum _{k=1}^{a_n}{p}_{k,n}$

Modèle:Théorème Les deux conditions ci-dessus entrainent que

• $\underset{n}{\lim }\underset{1\le k\le a_n}{\max }{p}_{k,n}=0,$
• $\underset{n}{\lim }{a}_n=+\mathrm{\infty }.$

Modèle:Théorème La loi de Poisson intervient souvent lorsqu'on compte des événements rares comme les suicides d'enfants, les arrivées de bateaux dans un port ou les accidents dus aux coups de pied de cheval dans les armées (étude de Ladislaus Bortkiewicz). Le décompte des événements rares se fait souvent au travers d'une somme de variables de Bernoulli, et la rareté des événements se traduit par le fait que les paramètres de ces variables de Bernoulli sont petits (ainsi, la probabilité que chaque événement survienne est faible). Modèle:Exemple

Simulation

Un algorithme simple pour simuler la loi de Bernoulli consiste à utiliser le théorème suivant :Modèle:ThéorèmeModèle:Démonstrationoù $𝒰([0,1])$ est une loi uniforme continue de paramètre $[0,1]$ et $\mathrm{𝟏}$ est la fonction indicatrice.

L'algorithme peut ainsi se simplifier en :

• on tire Modèle:Mvar selon un tirage aléatoire uniforme sur $[0,1]$
• si Modèle:Mvar
  • on renvoie 1
• sinon
  • on renvoie 0

Applications au comptage

Écrire une variable aléatoire N, comptant un nombre d'événements dans une situation donnée, comme la somme d'une famille de variables de Bernoulli, permet souvent de calculer simplement l'espérance de N, comme étant la somme des paramètres de ces variables de Bernoulli :

$\{N=\sum _{i\in I}{X}_i\}\Rightarrow \{𝔼[N]=\sum _{i\in I}\mathbb{P}(X_i=1)\}.$

On utilise le fait que, pour une variable de Bernoulli, le paramètre p est à la fois l'espérance et la probabilité de la valeur 1 :

$𝔼[X_i]=\mathbb{P}(X_i=1).$

Cette méthode simplifie aussi le calcul de la variance de N, dans certains cas :

$\text{Var}(N)=\sum _{(i,j)\in I^2}(\mathbb{P}(X_i=1\mathrm{e}\mathrm{t}{X}_j=1)-\mathbb{P}(X_i=1)\mathbb{P}(X_j=1)),$

et, lorsque I est ordonné, grâce à la propriété de symétrie de la covariance,

$\text{Var}(N)=\sum _{i\in I}\mathbb{P}(X_i=1)(1-\mathbb{P}(X_i=1))+2\sum _{(i<j)\in I^2}(\mathbb{P}(X_i=1\mathrm{e}\mathrm{t}{X}_j=1)-\mathbb{P}(X_i=1)\mathbb{P}(X_j=1)).$

On trouvera ci-dessous quelques exemples, parmi les plus représentatifs, de cette méthode de comptage très répandue.

Sondage

Modèle:Article détaillé On compte là, par exemple, le nombre N de réponses « oui » dans un échantillon de population, lors d'un sondage, afin d'en déduire la proportion de « oui ». On effectue une série de n tirages au hasard dans une population. On pose la même question à chacun des n individus tirés au hasard. Le but est d'estimer la proportion p d'individus de la population totale qui auraient répondu « oui » (si on leur avait posé la question) à l'aide du nombre N d'individus qui ont effectivement répondu « oui » parmi les n individus interrogés. On remarque que N peut s'écrire

$N=\sum _{k=1}^n{X}_k,$

où XModèle:Ind, XModèle:Ind, ..., XModèle:Ind sont définies par

$X_k={\mathrm{𝟏}}_{\mathrm{l}\mathrm{a}\mathrm{r}\acute{\mathrm{e}}\mathrm{p}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{e}\mathrm{d}\mathrm{u}k\mathrm{-}\mathrm{i}\stackrel{`}{\mathrm{e}}\mathrm{m}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{d}\mathrm{u}\mathrm{e}\mathrm{s}\mathrm{t}oui},$

i.e. XModèle:Ind vaut 1 ou 0 selon que la réponse du k-ième individu est « oui » ou « non ». Étant une fonction indicatrice, XModèle:Ind est donc une variable de Bernoulli. Son paramètre est « la probabilité de répondre « oui » », à savoir la proportion de « oui » dans la population totale, c'est-à-dire p. On a donc

$𝔼[N]=\sum _{1\le i\le n}\mathbb{P}(X_i=1)=np,\text{et}𝔼[N/n]=p$

D'où l'idée, proposée par Bernoulli dans son ouvrage fondateur Ars Conjectandi, d'estimer cette proportion p a priori inconnue à l'aide de la proportion N/n de « oui » dans l'échantillon, qui est, elle, connue. Dans le but de déterminer la précision de cette estimation, Bernoulli a proposé dans le même ouvrage les premières inégalités de concentration (pour la loi binomiale). Une approche plus simple (mais produisant des inégalités de concentration plus grossières) que celle de Bernoulli, serait de calculer la variance de N, dans l'idée d'appliquer l'inégalité de Bienaymé-Tchebychev. À ce stade, il est nécessaire de préciser

• si les tirages ont eu lieu avec remise (i.e. il est possible que la même personne soit interrogée plusieurs fois), ce qui implique l'indépendance des XModèle:Ind, et donne

$\text{Var}(N)=\sum _{1\le i\le n}\text{Var}(X_i)=np(1-p).$

Dans le cas « avec remise », N suit la loi binomiale.

• si les tirages ont eu lieu sans remise (i.e. en évitant d'interroger 2 fois la même personne), auquel cas les XModèle:Ind ne sont pas indépendants. Alors

$\text{Var}(N)=\sum _{1\le i\le n}\text{Var}(X_i)+2\sum _{1\le i<j\le n}\text{Cov}(X_i,X_j).$

En ce cas N suit la loi hypergéométrique, et les calculs requièrent de connaître la taille totale de la population, qu'on notera T dans la suite. On a

$\text{Cov}(X_i,X_j)=𝔼[X_i{X}_j]-𝔼[X_i]𝔼[X_j]=\mathbb{P}(X_i{X}_j=1)-p^2.$

En effet la variable Z = XModèle:IndXModèle:Ind vaut 0 ou 1, et est donc une variable de Bernoulli. Pour i < j, on a alors

$\mathbb{P}(X_i{X}_j=1)=\frac{pT}{T}\frac{pT-1}{T-1}\text{et}\text{Cov}(X_i,X_j)=-\frac{p(1-p)}{T-1},$

puis, à l'aide des propriétés de la variance,

$\text{Var}(N)=\frac{p(1-p)n(T-n)}{T-1}.$

Dans les deux cas considérés ci-dessus, la loi de N est connue explicitement. Cependant, le calcul de l'espérance de N utilisant la décomposition de N en somme de variables de Bernoulli, présenté ci-dessus, est plus simple que le calcul de l'espérance de N utilisant le théorème de transfert :

$𝔼[N]=\sum _{1\le k\le n}k\mathbb{P}(N=k).$

La même remarque vaut pour le calcul de la variance.

Fonction de répartition empirique

Modèle:Loupe On compte là le nombre N d'éléments inférieurs au nombre réel x dans un échantillon de nombres aléatoires, afin d'en déduire la proportion de tels nombres, qui est appelée fonction de répartition empirique. En statistiques, la fonction de répartition empirique associée à un n-échantillon est la fonction de répartition de la loi de probabilité qui attribue la probabilité 1/n à chacun des n nombres de cet échantillon.

Soit $X_1,X_2,\dots ,X_n$ un échantillon de variables i.i.d. à valeurs dans $ℝ$ ayant pour fonction de répartition commune F(x) : la fonction de répartition empirique $F_n(x)$ associée à l'échantillon $X_1,X_2,\dots ,X_n$ est une fonction en escalier définie par

$F_n(x)=\frac{\mathrm{n}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{r}\mathrm{e}{\mathrm{d}}^{\prime }\acute{\mathrm{e}}\mathrm{l}\acute{\mathrm{e}}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{f}\acute{\mathrm{e}}\mathrm{r}\mathrm{i}\mathrm{e}\mathrm{u}\mathrm{r}\mathrm{s}\stackrel{`}{\mathrm{a}}x\mathrm{d}\mathrm{a}\mathrm{n}\mathrm{s}{\mathrm{l}}^{\prime }\acute{\mathrm{e}}\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{n}}{n}=\frac{1}{n}\sum _{i=1}^n{\mathrm{𝟏}}_{X_i\le x}.$

Pour un x fixé, la variable ${\mathrm{𝟏}}_{X_i\le x}$ est une variable de Bernoulli, de paramètre p = F(x). Par conséquent, la variable $N=n{F}_n(x)$ est distribuée selon une loi binomiale, avec pour moyenne nF(x) et pour variance nF(x)(1 − F(x)).

Pour divers sens du mot « convergence », la fonction de répartition empirique converge vers la fonction de répartition F des $X_i,$ lorsque la taille de l'échantillon augmente. Par exemple, en vertu du calcul de la variance de FModèle:Ind(x), on a, pour tout x réel,

$𝔼\left[{(F_n(x)-F(x))}^2\right]=\frac{F(x)(1-F(x))}{n}⟶0,$

ce qui démontre la convergence de FModèle:Ind(x) vers F(x), [[Convergence de variables aléatoires#Convergence en moyenne d'ordre r|dans LModèle:Ind]].

Récurrence et transience d'une chaîne de Markov

Modèle:Loupe Le temps de séjour (ou nombre de passages) d'une chaîne de Markov $X=(X_n{)}_{n\ge 0}$ en un état $i$ est une variable aléatoire $S(i)$ à valeurs dans $\bar{\mathbb{N}}=\mathbb{N}\cup \{+\mathrm{\infty }\}$, définie par

$S(i)=\sum _{k\ge 0}{\mathrm{𝟏}}_{X_k=i}.$

L'état $i$ est dit transitoire ou récurrent, suivant que ${\mathbb{P}}_i(S(i)=+\mathrm{\infty })$ vaut 0 ou 1, ou encore suivant que le temps de séjour moyen en i, partant de i, ${𝔼}_i[S(i)]$, est fini ou infini. Comme $S(i)$ est une somme (infinie) de variables de Bernoulli, discuter ce dernier point revient à discuter la convergence de la série

${𝔼}_i[S(i)]=\sum _{k\ge 0}{p}_{i,i}^{(k)}$,

où $p_{i,i}^{(k)}$ est le paramètre de la variable de Bernoulli concernée, i.e.

$p_{i,i}^{(k)}={\mathbb{P}}_i(X_k=i)$,

lequel paramètre $p_{i,i}^{(k)}$ étant par ailleurs un terme diagonal de la puissance k-ième de la matrice de transition de la chaîne de Markov considérée.

Problèmes d'allocation : boîtes et boules

On compte ici le nombre N de boîtes vides, dans une expérience aléatoire faisant intervenir boîtes et boules, avec de nombreuses interprétations. On jette m boules au hasard dans n boîtes, expérience probabiliste dont un événement élémentaire ω est une application de $B=[[1,m]]$ dans $A=[[1,n]]$ : ω(k) est le numéro de la boîte dans laquelle est rangée la boule numéro k. Ainsi les ω(k) sont des variables aléatoires indépendantes et uniformes sur A. L'application N, qui à une distribution ω de m boules dans n boîtes associe le nombre N(ω) de boîtes vides à la fin de cette distribution ω, peut être vue comme une somme de variables aléatoires de Bernoulli : en effet,

$N=\sum _{k=1}^n{X}_k,$

où XModèle:Ind, XModèle:Ind,…, XModèle:Ind sont définies par

$X_k={\mathrm{𝟏}}_{\mathrm{l}\mathrm{a}k\mathrm{-}\mathrm{i}\stackrel{`}{\mathrm{e}}\mathrm{m}\mathrm{e}\mathrm{b}\mathrm{o}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{e}\mathrm{s}\mathrm{t}vide}$

i.e. XModèle:Ind vaut 1 ou 0 selon que la k-ième boîte est vide ou pas à la fin de la distribution ω. Étant une fonction indicatrice d'événement, XModèle:Ind est donc une variable de Bernoulli. Son paramètre est « la probabilité d'être vide », i.e. la probabilité que chacune des m boules ait évité la boîte Modèle:N°. Chacune des m boules ayant une probabilité 1/n de tomber dans la boîte n°k, et les allocations des m boules étant indépendantes, on obtient

$𝔼[X_k]=\mathbb{P}(X_k=1)={(1-\frac{1}{n})}^m,$

puis

$𝔼[N]=\sum _{1\le k\le n}\mathbb{P}(X_k=1)=n{(1-\frac{1}{n})}^m.$

Grâce à cette décomposition en somme de variables de Bernoulli, on peut obtenir une inégalité de concentration précise pour N, en appliquant l'inégalité d'Azuma. Cette inégalité de concentration permet de justifier une méthode statistique de comptage approximatif basée sur la statistique N, et pouvant servir, par exemple, à déceler une attaque de virus informatique.

Remarque : La loi de probabilité de N s'exprime explicitement en termes des nombres de Stirling de seconde espèce, mais les expressions obtenues sont peu propices au calcul numérique, d'où la nécessité d'une approximation via l'inégalité d'Azuma.

Points fixes d'une permutation tirée au hasard

On jette n boules numérotées au hasard dans n boites numérotées, chacune de ces boites contenant au plus une boule, expérience probabiliste dont un événement élémentaire $\omega$ est une permutation des éléments de $[[1,n]]$ : $\omega (k)$ est, là encore, le numéro de la boite dans laquelle est rangée la boule numéro k. On suppose que les différentes distributions (permutations) possibles sont équiprobables. L'application N, qui à une distribution $\omega$ de n boules dans n boites associe le nombre $N(\omega )$ de boules portant le même numéro que la boite dans laquelle elles sont rangées à la fin de cette distribution $\omega$ peut être vue comme une somme de variables de Bernoulli : en effet,

$N=\sum _{k=1}^n{X}_k$,

où XModèle:Ind, XModèle:Ind, … , XModèle:Ind sont définies par

$X_k={\mathrm{𝟏}}_{k\text{ est un point fixe de }\omega }$,

Modèle:C.-à-d. XModèle:Ind vaut 1 ou 0 selon que la k-ième boite contient la k-ième boule ou pas. Étant une fonction indicatrice d'événement, XModèle:Ind est donc une variable de Bernoulli. Son paramètre est 1/n. On obtient que

$𝔼[N]=\sum _{1\le k\le n}\frac{1}{n}=1$.

En suivant une démarche analogue à celle suivie pour un sondage (cas sans remise), on trouve que

$\mathbb{P}(X_i{X}_j=1)=\frac{1}{n(n-1)},\text{Cov}(X_i,X_j)=\frac{1}{n^2(n-1)},\text{puis}\text{Var}(N)=1$.

Le principe d'inclusion-exclusion permet de calculer exactement la loi de N, et de constater que cette loi converge, lorsque n tend vers l'infini, vers la loi de Poisson de paramètre 1 (qui, incidemment, a 1 pour espérance, et a aussi 1 pour variance). Cet exemple est représentatif : en général, la loi de Poisson de paramètre $𝔼[N]$ est une bonne approximation de la loi de la somme N d'un grand nombre de variables de Bernoulli de petit paramètre et peu corrélées. Là encore, un avantage de l'écriture de N comme somme de variables de Bernoulli est de permettre un calcul de l'espérance et de la variance de N plus rapide qu'à partir de l'expression explicite de la loi de N.

Nombre d'occurrences d'un mot dans un texte (paradoxe du singe dactylographe)

Modèle:Loupe On considère un texte ω = ωModèle:IndωModèle:IndωModèle:Ind…ωModèle:Ind constitué de m caractères d'imprimerie, notés Modèle:Nobr, lesquels caractères d'imprimerie sont tous tirés au hasard, avec remise, d'un sac contenant exactement une fois chaque caractère d'imprimerie. On note $𝒜$ l'ensemble des caractères d'imprimerie, n le cardinal de $𝒜$. Soit une suite a = aModèle:IndaModèle:IndaModèle:Ind…aModèle:Ind de caractères de $𝒜$, par exemple un mot, comme Wikipédia (r = 9 dans ce cas particulier). L'application N, qui à un texte ω associe le nombre N(ω) d'occurrences de la suite a dans le texte ω peut être vue comme une somme de variables de Bernoulli : en effet,

$N=\sum _{k=1}^{m-r+1}{X}_k,$

où XModèle:Ind, XModèle:Ind, … , XModèle:Ind sont définies par

$X_k={\mathrm{𝟏}}_{{\omega }_k{\omega }_{k+1}{\omega }_{k+2}\dots {\omega }_{k+r-1}=a},$

i.e. XModèle:Ind vaut 1 ou 0 suivant que la suite a apparaît dans le texte ω, juste après le (k – 1)-ième caractère de ce texte ω, ou pas. Étant une fonction indicatrice d'événement, XModèle:Ind est donc une variable de Bernoulli. Son paramètre est

$\mathbb{P}({\omega }_k{\omega }_{k+1}{\omega }_{k+2}\dots {\omega }_{k+r-1}=a)=\frac{1}{n^r}.$

Ainsi

$𝔼[N]=\sum _{1\le k\le m-r+1}\mathbb{P}(X_k=1)=\frac{m-r+1}{n^r}.$

L'intuition est alors qu'il faut un texte ω de longueur au moins m = nModèle:R pour que l'événement $\{N\ge 1\}$ (autrement dit l'événement « le mot a apparaît au moins une fois dans le texte ω ») devienne probable. En effet, l'inégalité de Markov entraîne que

$\mathbb{P}(N\ge 1)\le 𝔼[N].$

Le paradoxe du singe dactylographe, popularisé par Émile Borel, exploite les propriétés de N lorsque la longueur r de la séquence de caractères a est très grande. Dans l'exemple donné par Émile Borel, la séquence a est un texte classique de la littérature française, par exemple le texte intégral de La Comédie humaine. La même démarche conduit le même Émile Borel à démontrer le théorème du nombre normal.

L'analyse statistique des suites de caractères tirés au hasard indépendamment, ou tirés au hasard suivant des modèles plus sophistiqués, a de nombreuses applications, comme l'analyse des performances de différentes méthodes de compression de données, ou encore l'étude du génome, et est à l'origine de la formalisation, par Andreï Markov, de la notion de chaîne de Markov.

Nombre de records et nombre de cycles des permutations

Soit B(k) (resp. H(k)) l'événement « il y a record vers le bas (resp. vers le haut) au rang k ». Autrement dit, B(k) est l'ensemble des permutations ω de ${𝔖}_n$ pour lesquelles la suite (ω(1), ω(2), ω(3), ..., ω(n)) présente un record vers le bas au rang k. Ainsi le nombre NModèle:Ind(ω) (resp. NModèle:Ind(ω)) de records vers le bas (resp. vers le haut) de la permutation ω s'écrit comme une somme de variables de Bernoulli :

$N_b(\omega )=\sum _{1\le k\le n}{\mathrm{𝟏}}_{B(k)}(\omega )\text{et}{N}_b(\omega )=\sum _{1\le k\le n}{\mathrm{𝟏}}_{H(k)}(\omega ).$

En vertu des propriétés statistiques du code de Lehmer, ces variables de Bernoulli ont pour paramètres respectifs 1/k :

$\mathbb{P}(B(k))=\mathbb{P}(H(k))=\frac{1}{k}.$

Ainsi

$𝔼[N_b]=𝔼[N_h]=\sum _{k=1}^n\frac{1}{k}=H_n\simeq \ln n,$

où HModèle:Ind désigne le n-ième nombre harmonique. Comme, toujours en vertu des propriétés statistiques du code de Lehmer, les variables de Bernoulli concernées sont indépendantes, on a également

$\text{V}(N_b)=\text{V}(N_h)=\sum _{1\le k\le n}\text{V}\left({\mathrm{𝟏}}_{B(k)}\right)=H_n-H_n^{(2)}\simeq \ln n,$

où HModèle:IndModèle:Exp est le nombre harmonique défini par

$H_n^{(2)}=\sum _{k=1}^n\frac{1}{k^2},$

et converge vers [[Fonction zêta de Riemann#Valeurs de la fonction zêta pour s entier supérieur à 1|Modèle:Math]], i.e. vers Modèle:Math.

La correspondance fondamentale de Foata permet de montrer que les deux applications suivantes :

• le nombre NModèle:Ind(ω) de records d'une permutation ω tirée au hasard,
• le nombre C(ω) de cycles de la décomposition d'une permutation ω tirée au hasard,

sont deux variables aléatoires ayant même loi de probabilité. Cette loi de probabilité s'exprime en termes des nombres de Stirling de première espèce, notés $\left[\begin{array}{c}n\\ k\end{array}\right]$ :

$\begin{array}{ccc}\mathbb{P}(N_b=k)& =& \frac{1}{n!}\left[\begin{array}{c}n\\ k\end{array}\right],\\ \mathbb{P}(x\le N_b\le y)& =& \sum _{k=x}^y\frac{1}{n!}\left[\begin{array}{c}n\\ k\end{array}\right],\end{array}$

ce qui donne une formule exacte, mais peu explicite, pour $\mathbb{P}(|N_b-\ln (n)|\le a\sqrt{\ln (n)}),$ formule exacte dont il est alors difficile de déduire un calcul effectif de la probabilité en question.

En revanche, l'écriture de NModèle:Ind comme somme de variables de Bernoulli permet d'appliquer à NModèle:Ind le théorème central limite. Ainsi, on constate que le nombre de cycles d'une permutation tirée au hasard, comme son nombre de records, sont très concentrés autour leur espérance, qui vaut approximativement ln n. Plus précisément :

$\begin{array}{ccc}\underset{n}{\lim }\mathbb{P}(|N_b-\ln (n)|\le a\sqrt{\ln (n)})& =& \underset{-a}{\overset{a}{\int }}\frac{1}{\sqrt{2\pi }}{e}^{-x^2/2}\mathrm{d}x\\ & =& 0,999\end{array}$

pour Modèle:Math = 3,3.

Coût moyen de l'algorithme de tri rapide

L'algorithme de tri rapide, également appelé Quicksort, est un des algorithmes les plus utilisés pour ranger, dans l'ordre croissant, une liste désordonnée x = (xModèle:Ind, xModèle:Ind, xModèle:Ind, … , xModèle:Ind) de n articles, à l'aide d'un petit nombre de comparaisons deux à deux. En effet, Quicksort est réputé à la fois simple et efficace. Quicksort se déroule de la manière suivante :

• on compare xModèle:Ind avec chacun des éléments de la liste (xModèle:Ind, xModèle:Ind, … , xModèle:Ind), ce qui permet de constituer 2 sous-listes, la liste des ωModèle:Ind – 1 éléments plus petits (resp. des n – ωModèle:Ind éléments plus grands) que xModèle:Ind. Cela fournit le rang ωModèle:Ind que xModèle:Ind occupera dans la liste une fois que celle-ci sera bien rangée.
• on compare xModèle:Ind avec chacun des éléments de sa sous-liste, ce qui permet de trouver le rang de xModèle:Ind dans cette sous-liste, et finalement le rang ωModèle:Ind que xModèle:Ind occupera dans la liste complète une fois que celle-ci sera bien rangée. Par ailleurs cela scinde une des deux sous-listes constituées à l'étape précédente en deux, constituant ainsi 3 sous-listes, dont certaines, éventuellement, peuvent être vides (si xModèle:Ind ou xModèle:Ind sont des éléments extrémaux de leur (sous-)liste).
• on compare xModèle:Ind, etc.

Une mise en œuvre concrète de cet algorithme abstrait est décrite par Donald Knuth dans Modèle:Lang.

La performance de Quicksort, dans le pire des cas (pire des cas qui correspond à une liste déjà bien rangée, dans l'ordre croissant ou décroissant), est de l'ordre de nModèle:2 comparaisons deux à deux. Pour cette raison, une liste constituée de concaténations de listes bien rangées (configuration fréquente en pratique) coûtera cher à ranger, en nombre de comparaisons effectuées. Le remède souvent adopté pour pallier cette faiblesse de Quicksort est de désordonner artificiellement la liste avant de la traiter : on note Modèle:Nobr les rangs respectifs des éléments Modèle:Nobr de la liste désordonnée au préalable, une fois que ces éléments sont rangés en une liste croissante Modèle:Nobr, de sorte que Modèle:Nobr. On suppose donc que la liste a été prétraitée de sorte que ω soit une permutation tirée au hasard avec équiprobabilité parmi les n! permutations possibles. On note N(ω) le nombre de comparaisons effectuées par l'algorithme. Alors

$N(\omega )=\sum _{1\le i<j\le n}{\mathrm{𝟏}}_{A(i,j)}(\omega )\text{,}$

où A(i,j) est l'événement « yModèle:Ind et yModèle:Ind sont comparés une fois au cours de l'algorithme ». En découle une analyse élémentaire du coût moyen de Quicksort, plus simple que la méthode classique utilisant une formule de récurrence et un calcul de fonction génératrice. Modèle:Théorème Modèle:Démonstration Ainsi la randomisation de la liste fournie en entrée permet de diminuer le coût de l'algorithme, de nModèle:2 à Modèle:Nobr. Une analyse plus poussée permet de démontrer que N est très concentré autour de sa moyenne Modèle:Nobr. Plus précisément, la variance de N est asymptotiquement Modèle:Nobr, d'où on déduit que l'écart-type de N est de l'ordre de n, c'est-à-dire négligeable devant l'espérance de N. Notons que le coût (coût moyen ou coût dans le pire des cas) de n'importe quel algorithme de tri utilisant des comparaisons 2 à 2 est minoré par Modèle:Nobr qui, d'après la formule de Stirling, vaut approximativement Modèle:Nobr.

Voir aussi

Articles connexes

• Processus de Bernoulli
• Inégalité de Hoeffding
• Jacques Bernoulli