Loi de Bernoulli

Pour les articles homonymes, voir Théorème de Bernoulli.

Bernoulli
Paramètres	$p>0\,$ (nombre réel) $q\equiv 1-p\,$
Support	$k=\{0,1\}\,$
Densité de probabilité (fonction de masse)	$\begin{matrix} q & \mbox{pour }k=0 \\p~~ & \mbox{pour }k=1 \end{matrix}$
Fonction de répartition	$\begin{matrix} 0 & \mbox{pour }k<0 \\q & \mbox{pour }0<k<1\\1 & \mbox{pour }k>1 \end{matrix}$
Espérance	$p\,$
Médiane (centre)	non disponible
Mode	$\textrm{max}(p,q)\,$
Variance	$pq\,$
Asymétrie	$\frac{q-p}{\sqrt{pq}}$
Kurtosis normalisé	$\frac{1-6pq}{pq}\,$
Entropie	$-q\ln(q)-p\ln(p)\,$
Fonction génératrice des moments	$q+pe^t\,$
Fonction caractéristique	$q+pe^{it}\,$
modifier

En mathématiques, la distribution de Bernoulli ou loi de Bernoulli, du nom du mathématicien suisse Jacques Bernoulli, est une distribution discrète de probabilité, qui prend la valeur 1 avec la probabilité p et 0 avec la probabilité $\scriptstyle\ q = 1 - p.$

$\mathbb{P}(X=x) = \left\{\begin{array}{ll} p &\quad\mbox {si }x=1, \\ 1-p &\quad\mbox {si }x=0, \\ 0 &\quad\mbox {sinon.}\end{array}\right.$

L'espérance mathématique d'une variable aléatoire de Bernoulli vaut p et la variance vaut p(1-p).

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

Sommaire

1 Variable de Bernoulli
2 Distributions liées
- 2.1 Loi binomiale
- 2.2 Loi de Poisson
3 Applications au comptage
4 Voir aussi
- 4.1 Notes
- 4.2 Pages liées

Variable de Bernoulli

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

La loi de Bernoulli est la loi de la variable aléatoire qui code le résultat d'une épreuve de Bernoulli de la manière suivante : 1 pour "succès", 0 pour "échec", ou quel que soit le nom qu'on donne aux deux issues d'une épreuve de Bernoulli.

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

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

Distributions liées

Loi binomiale

Si $\scriptstyle\ X_1,\dots,X_n\$ sont des variables aléatoires de Bernoulli avec paramètre p, indépendantes et identiquement distribuées, alors leur somme N suit la loi binomiale :

$N = \sum_{k=1}^n X_k \sim \mathcal{B}(n,p).$

Loi de Poisson

Soit $\scriptstyle\ X_{1,n}, X_{2,n},\dots, X_{a_n,n}\$ un tableau de variables aléatoires de Bernoulli indépendantes, avec paramètres respectifs $\scriptstyle\ p_{k,n}.\$ On note

$S_n=\sum_{k=1}^{a_n}\,X_{k,n}\quad\text{et}\quad\lambda_n\ =\ \mathbb{E}[S_n]=\sum_{k=1}^{a_n}\,p_{k,n}.\$

Inégalité de Le Cam^[1] — Pour tout ensemble A d'entiers naturels,

$\left|\mathbb{P}\left(S_n\in A\right)-\sum_{k\in A}\,\frac{\lambda_n^k\,e^{-\lambda_n}}{k!}\right|\ \le\ \sum_{k=1}^{a_n}\,p_{k,n}^2.$

En particulier, si les deux conditions suivantes sont réunies :

$\lim_n \lambda_n\,=\,\lambda>0,\$
$\lim_n \sum_{k=1}^{a_n}\,p_{k,n}^2\,=\,0,\$

alors S_n converge en loi vers la loi de Poisson de paramètre λ.

Les deux conditions ci-dessus entrainent que

$\lim_n \max_{1\le k\le a_n}\,p_{k,n}\,=\,0,\$
$\lim_n a_n\,=\,+\infty.\$

Conséquence : paradigme de Poisson — La somme S_n d'un grand nombre de variables de Bernoulli indépendantes de petit paramètre suit approximativement la loi de Poisson de paramètre $\scriptstyle\ \mathbb{E}[S_n]. \$

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).

Remarques :

Ce paradigme reste pertinent, dans certaines conditions, si l'on relaxe l'hypothèse d' indépendance^[2].
- Un exemple frappant est le nombre de points fixes d'une permutation tirée au hasard.
- Un autre exemple est le nombre de points isolés du graphe aléatoire, dont la convergence vers la loi de Poisson a permis à Erdös et Rényi de démontrer, en 1960, le théorème double-exponentiel.
Le cas particulier a_n=n, p_k,n=λ/n, λ_n=λ, de l'inégalité de Le Cam, précise la rapidité de convergence de la loi binomiale de paramètres n et λ/n vers la loi de Poisson de paramètre λ.

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:

$\left\{N=\sum_{i\in I} X_i\right\}\quad\Rightarrow\quad\left\{\mathbb{E}[N]=\sum_{i\in I} \mathbb{P}(X_i=1)\right\}.$

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 :

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

Cette méthode simplifie aussi le calcul de la variance de N, dans certains cas. On trouvera ci-dessous quelques exemples, parmi les plus représentatifs, de cette méthode de comptage très répandue.

Sondage

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ù X₁ , X₂ , ... , X_n sont définies par

$X_k\,=\, 1\!\!1_{\mathrm{la~r\acute eponse~du}\ k\mathrm{-\grave eme~individu~est}\ oui},$

i.e. X_k vaut 1 ou 0 selon que la réponse du k-ème individu est "oui" ou "non". Étant une fonction indicatrice, X_k 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

$\mathbb{E}[N]=\sum_{1\le i\le n} \mathbb{P}(X_i=1)\ =\ np,\qquad\text{et}\qquad\mathbb{E}[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)^[3]. 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. A 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 X_k, 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 X_k 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)=\mathbb{E}[X_iX_j]-\mathbb{E}[X_i]\mathbb{E}[X_j]=\mathbb{P}(X_iX_j=1)-p^2.$

En effet la variable Z=X_iX_j vaut 0 ou 1, et est donc une variable de Bernoulli. On a alors

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

puis

$\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 :

$\mathbb{E}[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

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 $\scriptstyle\ X_1,X_2,\,\dots\,,X_n\$ un échantillon de variables i.i.d. à valeurs dans $\scriptstyle\ \mathbb{R}\$ ayant pour fonction de répartition commune F(x) : la fonction de répartition empirique $\scriptstyle\ F_n(x)\$ associée à l'échantillon $\scriptstyle\ X_1,X_2,\,\dots\,,X_n\$ est une fonction en escalier définie par

$F_n(x)\ =\ \frac{\mathrm{nombre~d'\acute el \acute ements~inf\acute erieurs~\grave a}\ x\ \mathrm{dans~ l'\acute echantillon}}{n}\ =\ \frac{1}{n}\ \sum_{i=1}^n\ 1\!\!1_{X_i \le x}.$

Pour un x fixé, la variable $\scriptstyle\ 1\!\!1_{X_i \le x}\$ est une variable de Bernoulli, de paramètre p = F(x). Par conséquent, la variable $\scriptstyle\ nF_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 $\scriptstyle\ X_i,\$ lorsque la taille de l'échantillon augmente^[4]. Par exemple, en vertu du calcul de la variance de F_n (x), on a, pour tout x réel,

$\mathbb E\left[\left(F_n(x)-F(x)\right)^2\right]\ =\ \tfrac{F(x)(1-F(x))}{n}\ \longrightarrow\ 0,$

ce qui démontre la convergence de F_n (x) vers F(x), dans L₂ .

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

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

$S(i)\ =\ \sum_{k\ge 0}1\!\!1_{X_k=i}.$

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

$\ \mathbb{E}_{i}\left[S(i)\right]=\sum_{k\ge 0}p^{(k)}_{i,i},$

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

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

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

Problèmes d'allocation : urnes et boules

On jette m boules au hasard dans n boites, expérience probabiliste dont un évènement élémentaire ω est une application de $\scriptstyle\ B=[\![1,m]\!]\$ dans $\scriptstyle\ A=[\![1,n]\!]\$ : ω(k) est le numéro de la boite 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 boites associe le nombre N(ω) de boites vides à la fin de cette distribution ω, peut être vue comme une somme de variables de Bernoulli : en effet,

$N = \sum_{k=1}^n X_k,$

où X₁ , X₂ , ... , X_n sont définies par

$X_k\,=\, 1\!\!1_{\mathrm{la}\ k\mathrm{-\grave eme~boite~est}\ vide},$

i.e. X_k vaut 1 ou 0 selon que la k-ème boite est vide ou pas. Étant une fonction indicatrice d'évènement, X_k 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 n°k. 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

$\mathbb{E}[X_k]=\mathbb{P}(X_k=1)\ =\ \left(1-\tfrac1n\right)^m,$

puis

$\mathbb{E}[N]=\sum_{1\le k\le n} \mathbb{P}(X_k=1)\ =\ n\left(1-\tfrac1n\right)^m.$

Grace à 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^[5]. Cette inégalité de concentration permet de justifier une méthode statistique de comptage approximatif^[6] 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 terme 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 $\scriptstyle\ \omega\$ est une permutation des éléments de $\scriptstyle\ [\![1,n]\!]\$ : $\scriptstyle\ \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 $\scriptstyle\ \omega\$ de n boules dans n boites associe le nombre $\scriptstyle\ N(\omega)\$ de boules portant le même numéro que la boite dans laquelle elles sont rangées à la fin de cette distribution $\scriptstyle\ \omega,\$ peut être vue comme une somme de variables de Bernoulli : en effet,

$N = \sum_{k=1}^n X_k,$

où X₁ , X₂ , ... , X_n sont définies par

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

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

$\mathbb{E}[N]=\sum_{1\le k\le n} \ \tfrac1n\ =\ 1.$

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

$\mathbb{P}(X_iX_j=1)\,=\,\tfrac1{n(n-1)},\quad\text{Cov}(X_i,X_j)=\tfrac{1}{n^2(n-1)},\quad\text{puis}\quad\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. Cet exemple est représentatif : en général, la loi de Poisson de paramètre $\scriptstyle\ \mathbb{E}[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^[2]. Là encore, un avantage de l'écriture de N comme somme de variables de Bernoulli est de permettre un calcul rapide de l'espérance et de la variance de N, ce que l'expression explicite de la loi de N ne permet pas.

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

On considère un texte ω=ω₁ω₂ω₃ ... ω_m constitué de m caractères d'imprimerie tous tirés au hasard, avec remise, d'un sac contenant exactement une fois chaque caractère d'imprimerie. On note $\scriptstyle\ \mathcal{A}\$ l'ensemble des caractères d'imprimerie, n le cardinal de $\scriptstyle\ \mathcal{A}.\$ Soit une suite a=a₁a₂a₃ ... a_r de caractères de $\scriptstyle\ \mathcal{A},\$ par exemple un mot, comme Wikipedia (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ù X₁ , X₂ , ... , X_m-r+1 sont définies par

$X_k\,=\, 1\!\!1_{\omega_k\omega_{k+1}\omega_{k+2}\dots\omega_{k+r-1}=a},$

i.e. X_k vaut 1 ou 0 suivant que la suite a apparait dans le texte ω, juste après le k-1-ème caractère de ce texte ω, ou pas. Étant une fonction indicatrice d'évènement, X_kest 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)\ =\ \frac1{n^{r}}.$

Ainsi

$\mathbb{E}[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=n^r pour que l'évènement $\scriptstyle\ \{N\ge 1\}\$ (autrement dit l'évènement "le mot a apparait au moins une fois dans le texte ω") devienne probable. En effet, l'inégalité de Markov entraine que

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

Le paradoxe du singe dactylographe, popularisé par Émile Borel^[7], 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 d'une permutation

Définition — Dans une suite u=(u_k)_1≤k≤n, il y a record vers le bas (resp. vers le haut) au rang k si u_k est strictement plus petit (resp. strictement plus grand) que chaque terme u_i tel que i<k, c'est-à-dire strictement plus petit (resp. strictement plus grand) que chacun des termes qui le précèdent.

Exemple. Les records vers le bas de la suite ω ci-dessous sont en gras et soulignés :

$\ \omega\ {=}\ (\underline{\bold{13}},14,\underline{\bold{11}},15,\underline{\bold{7}},9,\underline{\bold{4}},5,12,\underline{\bold{3}},\underline{\bold{1}},6,10,8,2).$

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 $\scriptstyle\ \mathfrak{S}_n\$ pour lesquelles la suite (ω(1), ω(2), ω(3), ... , ω(n)) présente un record vers le bas au rang k. Ainsi le nombre N_b(ω) (resp. N_h(ω)) 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}\ 1\!\!1_{B(k)}(\omega)\quad\text{et}\quad N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{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))=\tfrac1k.$

Ainsi

$\mathbb{E}[N_b]=\mathbb{E}[N_h]=\sum_{k=1}^n\frac{1}k=H_n\simeq \ln n,$

où H_n désigne le n-è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^[8], on a également

$\text{Var}(N_b)=\text{Var}(N_h)=\sum_{1\le k\le n}\ \text{Var}\left(1\!\!1_{B(k)}\right)=H_n-H_n^{(2)}\simeq \ln n,$

où H_n⁽²⁾ est le nombre harmonique défini par

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

et converge vers ζ(2), i.e. vers π²/6.

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

le nombre N_b(ω) 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 terme des nombres de Stirling de première espèce, notés $\left[\begin{matrix}\scriptstyle n \\\scriptstyle k \end{matrix}\right]\$ :

$\begin{align} \mathbb{P}\left(N_b=k\right)&=\tfrac{(-1)^{n-k}}{n!}\ \left[\begin{matrix} n \\ k \end{matrix}\right], \\\mathbb{P}\left(x\le N_b\le y\right)&=\sum_{k=x}^y\tfrac{(-1)^{n-k}}{n!}\ \left[\begin{matrix} n \\ k \end{matrix}\right],\end{align}$

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

En revanche, l'écriture de N_b comme somme de variables de Bernoulli permet d'appliquer à N_b 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 :

Erreur math (La conversion en PNG a échoué ; vérifiez l’installation de latex et dvipng (ou dvips + gs + convert)): \lim_n\,\mathbb{P}\left(\left|N_b-\ln(n)\right|\le a\sqrt{\ln(n)}\right)\ =\ \int_{-a}^a\ \tfrac1\sqrt{2\pi}\ e^{-x^2/2}\ dx\ =\ 0,999,

pour a=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= (x₁ , x₂ , x₃ , ... , x_n ) 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 x₁ avec chacun des éléments de la liste (x₂ , x₃ , ... , x_n ), ce qui permet de constituer 2 sous-listes, la liste des ω₁-1 éléments plus petits (resp. des n-ω₁ éléments plus grands) que x₁ . Cela fournit le rang ω₁ que x₁ occupera dans la liste une fois que celle-ci sera bien rangée.

on compare x₂ avec chacun des éléments de sa sous-liste, ce qui permet de trouver le rang de x₂ dans cette sous-liste, et finalement le rang ω₂ que x₂ 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 x₁ ou x₂ sont des éléments extrémaux de leur (sous-)liste).

on compare x₃ etc ...

Une implémentation concrète de cet algorithme abstrait est décrite par Don Knuth dans The art of computer programming^[9].

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 n² 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 ω=(ω(1), ω(2), ω(3), ... , ω(n)) les rangs respectifs des éléments (x₁ , x₂ , x₃ , ... , x_n ) de la liste désordonnée au préalable, une fois que ces éléments sont rangés en une liste croissante (y₁ < y₂ < y₃ < ... < y_n ), de sorte que x_i =y_ω(i) . 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}\ 1\!\!1_{A(i,j)}(\omega),$

où A(i,j) est l'évènement "y_i et y_j 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.

Proposition — On a^[10]

$\mathbb{P}\left(A(i,j)\right)\ =\ \frac2{j-i+1},$

$\mathbb{E}[N]\ =\ 2(n+1)\,H_n\,-\,4n\ \simeq\ 2n\,\ln(n).$

Démonstration

Il y a deux possibilités :

si le terme, disons z, de la liste L=(y_i < y_i+1 < ... < y_j-1 < y_j ) qui apparait le premier dans la liste (x₁ , x₂ , x₃ , ... , x_n ) est compris strictement entre y_i et y_j , alors, juste avant qu'on commence à comparer z avec les éléments de sa sous-liste, cette sous-liste contient la liste L, et aucun des éléments de L n'a encore été comparé avec un autre élément de L (puisque z est le premier). Après qu'on a comparé z avec tous les autres éléments de L, y_i et y_j sont placés dans deux sous-listes différentes (puisque y_i < z < y_j ) et ne seront plus jamais comparées :

$1\!\!1_{A(i,j)}(\omega)=0\ ;$

si z est l'un des deux éléments y_i et y_j de la liste L, comme on compare z à tous les autres éléments de sa sous-liste, laquelle contient intégralement la liste L, alors z va, en particulier, être comparé à l'autre élément du couple (y_i , y_j ) :

$1\!\!1_{A(i,j)}(\omega)=1\ .$

La répartition des j-i+1 éléments de la liste L dans la liste x est aléatoire uniforme, donc la probabilité qu'un élément particulier z de la liste L apparaisse le premier dans la liste x est 1/(j-i+1). Ainsi

$\begin{align} \mathbb{P}\left(A(i,j)\right)&=\mathbb{P}\left(\mathrm{le~1er~\acute el\acute ement~de~la~liste}\ L\ \mathrm{dans~la~liste}\ x\ \mathrm{est~soit}\ y_i,\ \text{soit}\ y_j\right) \\ &=\frac2{j-i+1}, \end{align}$

$\begin{align} \mathbb{E}[N]&=\sum_{1\le i<j\le n}\ \mathbb{P}\left(A(i,j)\right)\\ &=\sum_{1\le i<j\le n}\ \frac2{j-i+1}\\ &=2\sum_{1\le i\le n-1}\ \left(\sum_{i+1\le j\le n}\frac1{j-i+1}\right)\\ &=2\sum_{1\le i\le n-1}\ \left(\sum_{2\le \ell\le n-i+1}\frac1{\ell}\right)\\ &=2\sum_{2\le m\le n}\ \left(\sum_{2\le \ell\le m}\frac1{\ell}\right)\\ &=2\sum_{2\le \ell\le n}\ \frac1{\ell}\left(\sum_{\ell\le m\le n}\,1\right)\\ &=2\ \sum_{2\le \ell\le n}\ \frac{n+1-\ell}{\ell}\\ &=2(n+1)\ \sum_{2\le \ell\le n}\ \frac{1}{\ell}\ -\ 2\ \sum_{2\le \ell\le n}\ \frac{\ell}{\ell}\\ &=2\left((n+1)(H_n-1)-(n-1)\right) \\ &=2(n+1)\,H_n\,-\,4n \\ &\simeq 2n\,\ln(n). \end{align}$

où H_n désigne le n-ème nombre harmonique. La 4ème égalité provient du changement de variables $\scriptstyle\ \ell=j-i+1,$ la 5ème égalité provient du changement de variables $\scriptstyle\ m=n-i+1,$ et la 6ème égalité découle d'une interversion de l'ordre de sommation entre les variables m et $\scriptstyle\ \ell.$

Ainsi la randomisation de la liste fournie en entrée permet de diminuer le coût de l'algorithme, de n² à 2n ln(n). Une analyse plus poussée permet de démontrer que N est très concentré autour de sa moyenne 2n ln(n). Plus précisément, la variance de N est asymptotiquement (7-(2π²/3)) 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 ln(n!)/ln(2) qui, d'après la formule de Stirling, vaut approximativement 1,4... n ln(n).

Voir aussi

Notes

↑ L. Le Cam, « An Approximation Theorem for the Poisson Binomial Distribution », dans Pacific Journal of Mathematics, vol. 10, n^o 4, 1960, p. 1181–1197 [texte intégral (page consultée le 2009-05-13)]
↑ ^{a et b} (en) A. D. Barbour, L. Holst et S. Janson, Poisson approximation, The Clarendon Press Oxford University Press, 1992 (ISBN 0198522355) .
↑ (en) Stephen M. Stigler, The History of Statistics : The Measurement of Uncertainty before 1900, Harvard, Belknap Press of Harvard University Press, 1^er mars 1990, 1^re éd., 432 p. (ISBN 978-0674403413 et 067440341X), chap. 2 (« Probabilists and the measurement of uncertainty »), p. 65-70 .
↑ (en) Galen R. Shorack et Jon A. Wellner, Empirical Processes With Applications to Statistics, Society for Industrial & Applied Mathematics, 4 septembre 2009, 998 p. (ISBN 0898716845 et 978-0898716849)
↑ (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge ; New York, [University Press], août 1995, 1^re éd., 476 p. (ISBN 9780521474658), chap. 4 (« Tail inequalities »), p. 94–95 , Théorème 4.18.
↑ proposée par (en) Kyu-Young Whang et Ravi Krishnamurthy, « Query optimization in a memory-resident domain relational calculus database system », dans ACM Transactions on Database Systems (TODS), New York, NY, USA, ACM, vol. 15, n^o 1, mars 1990, p. 67–95 (ISSN 0362-5915) [texte intégral] .
↑ Voir Émile Borel, « Mécanique Statistique et Irréversibilité », dans J. Phys. 5e série, vol. 3, 1913, p. 189–196 .
↑ (en) Don Knuth, The art of computer programming : Sorting and Searching, t. 3, Reading, Addison-Wesley, 1981, 2^e éd., p. 13 .
↑ (en) Don Knuth, The art of computer programming : Sorting and Searching, t. 3, Reading, Addison-Wesley, 1997, 3^e éd. (ISBN 0-201-89685-0), « Sorting by Exchanging », p. 113–122 .
↑ (en) Michael Mitzenmacher et Eli Upfal, Probability and Computing : Randomized Algorithms and Probabilistic Analysis, Cambridge, Cambridge University Press, avril 2005, 1^re éd., 368 p. (ISBN 9780521835404 et 0521835402) [lire en ligne], chap. 2 (« Discrete Random Variables and Expectation, Section 2.5 »), p. 34-37 .

Pages liées

v · Lois de probabilités

Lois discrètes

à support fini	Loi de Bernoulli • Loi uniforme discrète • Loi binomiale • Loi hypergéométrique • Loi de Benford
à support dénombrable	Loi géométrique • Loi de Poisson • Loi binomiale négative • Loi logarithmique

Lois continues

à support compact	Loi uniforme continue • Loi triangulaire • Loi bêta
à support semi-infini	Loi exponentielle • Loi Gamma • Loi du χ² • Loi de Fisher • Loi de Weibull • Loi de Rayleigh • Loi de Rice • Loi d'Erlang • Loi de Lévy • Loi inverse-gamma • Loi log-normale
à support infini	Loi normale • Loi normale asymétrique • Loi de Cauchy • Loi de Laplace • Loi logistique • Loi de Student • Loi stable • Loi de Gumbel

v · Probabilités et statistiques

Théorie des probabilités

Axiomes des probabilités • Espace probabilisable • Probabilité • Événement • Tribu • Indépendance

Probabilités élémentaires	Moyenne • Espérance • Médiane • Variance • Écart type
Loi de probabilité	Variable aléatoire • Loi de Bernoulli • Loi de Poisson • Loi uniforme • Loi normale • Loi de Student • Loi de Fisher • Variables iid
Convergence de lois	Théorème central limite • Loi des grands nombres
Calcul stochastique	Marche aléatoire • Chaîne de Markov • Processus stochastique • Processus de Markov • Martingale • Mouvement brownien • Équation différentielle stochastique

Statistiques

Statistique descriptive	Échantillon • Quantile • Intervalle de confiance • Représentations de données • Histogramme • Diagramme circulaire • Boîte à moustaches • Régression linéaire • Méthode des moindres carrés
Statistique mathématique	Fonction de répartition empirique • Théorème de Glivenko-Cantelli • Inférence bayésienne
Tests statistiques	Test d'hypothèse • Hypothèse statistique • Estimateur • Test du χ² • Test t • Test de Fisher

Applications

Économétrie • Mécanique statistique • Jeu de hasard • Biomathématique • Mathématiques financières

Portail des probabilités et des statistiques

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Loi de Bernoulli de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

Loi De Bernoulli — Pour les articles homonymes, voir Théorème de Bernoulli. Bernoulli Densité de probabilité / Fonction de masse Fonction de répartition … Wikipédia en Français
Loi de bernoulli — Pour les articles homonymes, voir Théorème de Bernoulli. Bernoulli Densité de probabilité / Fonction de masse Fonction de répartition … Wikipédia en Français
Loi de Bernouilli — Loi de Bernoulli Pour les articles homonymes, voir Théorème de Bernoulli. Bernoulli Densité de probabilité / Fonction de masse Fonction de répartition … Wikipédia en Français
Loi De Probabilité — Une loi de probabilité ou distribution de probabilité a commencé par décrire les répartitions typiques des fréquences d apparition des résultats d un phénomène aléatoire. Dans le dernier quart du XXe siècle, on a largement étendu le concept… … Wikipédia en Français
Loi de probabilite — Loi de probabilité Une loi de probabilité ou distribution de probabilité a commencé par décrire les répartitions typiques des fréquences d apparition des résultats d un phénomène aléatoire. Dans le dernier quart du XXe siècle, on a largement … Wikipédia en Français
Loi Binomiale — Binomiale Densité de probabilité / Fonction de masse Fonction de répartition … Wikipédia en Français
Loi binômiale — Loi binomiale Binomiale Densité de probabilité / Fonction de masse Fonction de répartition … Wikipédia en Français
Loi Des Grands Nombres — En statistiques, la loi des grands nombres indique que lorsque l on fait un tirage aléatoire dans une série de grande taille, plus on augmente la taille de l échantillon, plus les caractéristiques statistiques de l échantillon se rapprochent des… … Wikipédia en Français
Loi faible des grands nombres — Loi des grands nombres En statistiques, la loi des grands nombres indique que lorsque l on fait un tirage aléatoire dans une série de grande taille, plus on augmente la taille de l échantillon, plus les caractéristiques statistiques de l… … Wikipédia en Français
Loi log-normale — Densité de probabilité / Fonction de masse μ=0 Fonction de répartition μ=0 … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Loi de Bernoulli

Sommaire

Variable de Bernoulli

Distributions liées

Loi binomiale

Loi de Poisson

Applications au comptage

Sondage

Fonction de répartition empirique

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

Problèmes d'allocation : urnes et boules

Points fixes d'une permutation tirée au hasard

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

Nombre de records et nombre de cycles d'une permutation

Coût moyen de l'algorithme de tri rapide

Voir aussi

Notes

Pages liées

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Loi de Bernoulli

Sommaire

Variable de Bernoulli

Distributions liées

Loi binomiale

Loi de Poisson

Applications au comptage

Sondage

Fonction de répartition empirique

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

Problèmes d'allocation : urnes et boules

Points fixes d'une permutation tirée au hasard

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

Nombre de records et nombre de cycles d'une permutation

Coût moyen de l'algorithme de tri rapide

Voir aussi

Notes

Pages liées

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link