Voir la source de Loi de Bernoulli

{{Voir homonymes|Théorème de Bernoulli}}
{{Infobox Distribution statistiques
|   name       = Loi de Bernoulli
 | pmf_image   = 
 | pmf_légende = 
 | cdf_image   = 
 | cdf_légende = 
|   parameters = <math>0<p<1\,</math> ([[nombre réel]])<br /><math>q\equiv 1-p\,</math>
|   support    = <math>k=\{0,1\}\,</math>
|   pmf        = <math>
    \begin{matrix}
    q~~ & \mbox{pour }k=0 \\p~~ & \mbox{pour }k=1
    \end{matrix}
    </math>
|   cdf        = <math>
    \begin{matrix}
    0 & \mbox{pour }k<0 \\q & \mbox{pour }0 \leq k<1\\1 & \mbox{pour }k \geq 1
    \end{matrix}
    </math>
|   mean       = <math>p\,</math>
|   median     = non disponible
|   mode       = <math>
    \begin{matrix}
    0 & \text{si } p < q\\
    0, 1 & \text{si } p=q\\
    1 & \text{si } p > q
    \end{matrix}
    </math>
|   variance   = <math>pq\,</math>
|   skewness   = <math>\frac{q-p}{\sqrt{pq}}</math>
|   kurtosis   = <math>\frac{1-6pq}{pq}\,</math>
|   entropy    = <math>-q\ln(q)-p\ln(p)\,</math>
|   mgf        = <math>q+pe^t\,</math>
|   char       = <math>q+pe^{it}\,</math>
}}

En [[mathématiques]], la '''distribution de Bernoulli''' ou '''loi de Bernoulli''', du nom du mathématicien suisse [[Jacques Bernoulli]], est une [[Loi de probabilité|distribution]] discrète de [[probabilité]], qui prend la valeur 1 avec la probabilité ''p ''et 0 avec la probabilité ''q ''= 1 – ''p''. En d'autres termes,

<center><math>
\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.</math></center>

ou, de manière équivalente,

<center><math>
\mathbb{P}(X=x) = p^x (1-p)^{1-x} , x \in\{0,1\}</math></center>

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 ''p ''= 1/2 la distribution de Bernoulli a un kurtosis plus bas que toute autre distribution, c’est-à-dire 1.

== 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 qui n'admet que deux issues ([[épreuve de Bernoulli]]) : 1 pour « succès », 0 pour « échec », ou quel que soit le nom qu'on donne aux deux issues d'une telle expérience aléatoire.

Plus généralement, toute [[fonction mesurable|application mesurable]] à valeur dans {0,1} est une variable de Bernoulli. Autrement dit, toute [[Fonction caractéristique (théorie des ensembles)|fonction indicatrice]] d'un évènement suit une 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 ''X''{{ind|1}}, ''X''{{ind|2}}, … , ''X''{{ind|''n''}} sont des variables aléatoires de Bernoulli de paramètre ''p'', [[Indépendance (probabilités)#Cas des variables discrètes|indépendantes]] et identiquement distribuées, alors leur somme ''N'' est aussi une variable aléatoire, qui suit la [[loi binomiale]] :

<center><math>N = \sum_{k=1}^n X_k \sim \mathcal{B}(n,p).</math></center>

=== [[Loi de Poisson]] ===
Soit ''X''{{ind|1, ''n''}}, ''X''{{ind|2, ''n''}}, … , ''X''{{ind|''a{{ind|n}}'', ''n''}} un tableau de variables aléatoires de Bernoulli indépendantes, avec paramètres respectifs ''p''{{ind|''k'', ''n''}}. On note
:<math>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}.\ </math>
{{Théorème|[[Inégalité de Le Cam]]<ref>{{article|langue=en
 |nom1=Le Cam |prénom=L. |lien auteur=Lucien Le Cam
 |titre=An Approximation Theorem for the Poisson Binomial Distribution
 |journal=Pacific Journal of Mathematics
 |volume=10 |numéro=4 |pages=1181-1197 |année=1960
 |url=http://projecteuclid.org/euclid.pjm/1103038058 |consulté le=13 mai 2009
 |id={{MathSciNet|0142174}}. {{Zbl|0118.33601}}
}}</ref>|Pour tout ensemble ''A''  d'entiers naturels,
<center><math>\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.</math></center>
En particulier, si les deux conditions suivantes sont réunies :
* <math>\lim_n \lambda_n\,=\,\lambda>0,\ </math>
* <math>\lim_n \sum_{k=1}^{a_n}\,p_{k,n}^2\,=\,0,\  </math>
alors ''S{{ind|n}}''  [[Convergence de variables aléatoires#Convergence en loi|converge en loi]] vers la [[loi de Poisson]] de paramètre ''λ''.}}
Les deux conditions ci-dessus entrainent que
* <math>\lim_n  \max_{1\le k\le a_n}\,p_{k,n}\,=\,0,\  </math>
* <math>\lim_n a_n\,=\,+\infty.\  </math>
{{Théorème|Conséquence : paradigme de Poisson| La somme ''S{{ind|n}}'' d'un grand nombre de variables de Bernoulli indépendantes de petit paramètre [[Convergence de variables aléatoires#Convergence en loi|suit approximativement]] la loi de Poisson de paramètre <math>\mathbb{E}[S_n]. \ </math>}}
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 [[#Applications au comptage|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).
{{exemple|nom=Remarques|
* Un cas particulier célèbre du paradigme de Poisson est la [[Loi binomiale#Convergence vers la loi de Poisson|convergence de la loi binomiale]] de paramètres ''n'' et λ/''n'' vers la loi de Poisson de paramètre λ, qui correspond, dans l'[[inégalité de Le Cam]], aux choix  ''a{{ind|n}}'' {{=}} ''n'', ''p{{ind|k,n}}'' {{=}} λ/''n'', λ''{{ind|n}}'' {{=}} λ.
* Ce paradigme reste pertinent, dans certaines conditions, si l'on relaxe l'hypothèse d'indépendance<ref name="barbour">{{Ouvrage |langue=en |prénom1=A. D. |nom1=Barbour |prénom2=L. |nom2=Holst |prénom3=S. |nom3=Janson |titre=Poisson approximation |collection=Oxford Studies in Probability |éditeur=The Clarendon Press Oxford University Press |année=1992 |isbn=0198522355}}.</ref>.
** Un exemple frappant est le nombre de points fixes d'une permutation tirée au hasard.
** Un autre exemple est le [[Graphe aléatoire#Énumération des points isolés|nombre de points isolés]] du [[graphe aléatoire]], dont la convergence vers la loi de Poisson a permis à [[Paul Erdös|Erdös]] et [[Alfréd Rényi|Rényi]] de démontrer, en 1960, le [[Graphe aléatoire#Le théorème double-exponentiel|théorème double-exponentiel]].
* Le cas particulier ''a{{ind|n}}'' {{=}} ''n'', ''p{{ind|k,n}}'' {{=}} λ/''n'', λ''{{ind|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 λ : l'inégalité de Le Cam fournit alors une majoration de l'erreur par λ{{2}}/''n''.}}

== 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 :

<center><math>\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\}.</math></center>
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 :
<center><math>\mathbb{E}[X_i]\ =\ \mathbb{P}(X_i=1).</math></center>
Cette méthode simplifie aussi le calcul de la [[Variance (statistiques et probabilités)#Propriétés|variance]] de ''N'', dans certains cas :
<center><math>\textrm{Var}(N)=\sum_{(i,j)\in I^2} \big(\mathbb{P}(X_i=1\mathrm{~et~}X_j=1)-\mathbb{P}(X_i=1)\mathbb{P}(X_j=1)\big),</math></center>
et, lorsque ''I'' est ordonné, grâce à la propriété de symétrie de la [[covariance]],
<center><math>\textrm{Var}(N)=\sum_{i\in I}\mathbb{P}(X_i=1)(1-\mathbb{P}(X_i=1))+2\sum_{(i<j)\in I^2} \big(\mathbb{P}(X_i=1\mathrm{~et~}X_j=1)-\mathbb{P}(X_i=1)\mathbb{P}(X_j=1)\big).</math></center>
On trouvera ci-dessous quelques exemples, parmi les plus représentatifs, de cette méthode de comptage très répandue.
=== Sondage ===
{{article détaillé|Sondage (statistique)}}
On compte là, par exemple, le nombre ''N'' de réponses « oui » dans un [[Échantillon (statistiques)|é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
<center><math>N = \sum_{k=1}^n X_k,</math></center>
où ''X{{ind|1  }}'', ''X{{ind|2  }}'', ..., ''X{{ind|n }}'' sont définies par
<center><math>X_k\,=\, 1\!\!\!1_{\mathrm{la~r\acute eponse~du}\ k\mathrm{-\grave eme~individu~est}\ oui},</math></center>
i.e. ''X{{ind|k}}'' vaut 1 ou 0 selon que la réponse du ''k''-ème individu est « oui » ou « non ». Étant une fonction indicatrice, ''X{{ind|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
<center><math>\mathbb{E}[N]=\sum_{1\le i\le n} \mathbb{P}(X_i=1)\ =\ np,\qquad\text{et}\qquad\mathbb{E}[N/n]=p.</math></center>
D'où l'idée, proposée par [[Jacques Bernoulli|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)<ref>{{Ouvrage |langue=en|nom1=[[Stephen Stigler|Stephen M. Stigler]]|titre=The History of Statistics  |sous-titre=The Measurement of Uncertainty before 1900 |numéro d'édition=1 |éditeur=Belknap Press of Harvard University Press |lieu=Harvard |année=1990 |mois=mars |jour=1 |pages totales=432 |isbn=978-0674403413 |isbn10=067440341X |numéro chapitre=2 |titre chapitre=Probabilists and the measurement of uncertainty |passage=65-70}}.</ref>. 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 ''X{{ind|k}}'', et donne
<center><math>\text{Var}(N)=\sum_{1\le i\le n} \text{Var}(X_i)\ =\ np(1-p).</math></center>
: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{{ind|k}}'' ne sont pas indépendants. Alors
<center><math>\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).</math></center>
: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
<center><math>\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.</math></center>
:En effet la variable ''Z = X{{ind|i}}X{{ind|j}}'' vaut 0 ou 1, et est donc une variable de Bernoulli. Pour ''i < j'', on a alors
<center><math>\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},</math></center>
:puis, à l'aide des propriétés de la variance,
<center><math>\text{Var}(N)\ =\ \frac{p(1-p)n(T-n)}{T-1}.</math></center>

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 [[Loi de probabilité#Définition mathématique|théorème de transfert]] :
<center><math>\mathbb{E}[N]=\sum_{1\le k\le n}\ k\,\mathbb{P}(N=k).</math></center>
La même remarque vaut pour le calcul de la variance.

=== [[Fonction de répartition empirique]] ===
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 [[statistique]]s, la '''fonction de répartition empirique''' associée à un ''n''-[[Échantillon (statistiques)|é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 <math>\ X_1,X_2,\,\dots\,,X_n\ </math> un échantillon de [[Variable indépendante et identiquement distribuée|variables i.i.d.]] à valeurs dans <math>\ \mathbb{R}\ </math> ayant pour fonction de répartition commune ''F''(''x'') : la ''fonction de répartition empirique''
<math>\ F_n(x)\ </math> associée à l'échantillon <math>\ X_1,X_2,\,\dots\,,X_n\ </math> est une [[fonction en escalier]] définie par

<center><math>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}.</math></center>

Pour un ''x'' fixé, la variable <math>\ 1\!\!1_{X_i \le x}\ </math> est une variable de Bernoulli, de paramètre ''p'' = ''F''(''x''). Par conséquent, la variable <math>\ N=nF_n(x)\ </math> est distribuée selon une loi binomiale, avec pour [[moyenne]] ''nF''(''x'') et pour variance ''nF''(''x'')(1&nbsp;−&nbsp;''F''(''x'')).

Pour divers sens du mot « [[Convergence de variables aléatoires|convergence]] », la fonction de répartition empirique converge vers la fonction de répartition ''F'' des <math>\ X_i,\ </math> lorsque la taille de l'échantillon augmente<ref>voir {{Ouvrage
|langue=en
|prénom1=Galen R.
|nom1=Shorack
|prénom2=Jon A.
|nom2=Wellner
|titre=Empirical Processes With Applications to Statistics
|éditeur=Society for Industrial & Applied Mathematics
|jour=4
|mois=septembre
|année=2009
|pages totales=998
|isbn10=0898716845
|isbn=978-0898716849
}}, ou bien encore le [[Théorème de Glivenko-Cantelli]].</ref>. Par exemple, en vertu du calcul de la variance de ''F{{ind|n }}''(''x''), on a, pour tout ''x'' réel,
<center><math>\mathbb E\left[\left(F_n(x)-F(x)\right)^2\right]\ =\ \frac{F(x)(1-F(x))}{n}\ \longrightarrow\ 0,</math></center>
ce qui démontre la convergence de ''F{{ind|n }}''(''x'') vers ''F''(''x''), [[Convergence de variables aléatoires#Convergence en moyenne d'ordre r|dans ''L{{ind|2 }}'']].

=== [[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]] <math>\scriptstyle\ X=(X_n)_{n\ge 0}\quad</math> en un état <math>\scriptstyle\ i\ </math> est une variable aléatoire <math>\scriptstyle\ S(i)\ </math> à valeurs dans <math>\scriptstyle\ \overline{\mathbb{N}}=\mathbb{N}\cup\{+\infty\},\ </math> définie par
<center><math> S(i)\ =\ \sum_{k\ge 0}1\!\!1_{X_k=i}.</math></center>
L'état <math>\scriptstyle\ i\ </math> est dit transient ou récurrent, suivant que <math>\scriptstyle\ \mathbb{P}_{i}\left(S(i)=+\infty\right)</math> vaut 0 ou 1, ou encore suivant que le ''temps de séjour moyen'' en ''i'', partant de ''i'', <math>\scriptstyle\ \mathbb{E}_{i}\left[S(i)\right],</math> est fini ou infini. Comme <math>\scriptstyle\ S(i)\ </math> est une somme (infinie) de variables de Bernoulli, discuter ce dernier point revient à discuter la convergence de la série
<center><math>\ \mathbb{E}_{i}\left[S(i)\right]=\sum_{k\ge 0}p^{(k)}_{i,i},</math></center>
où <math>\scriptstyle\ p^{(k)}_{i,i}</math> est le paramètre de la variable de Bernoulli concernée, i.e.
<center><math>\ p^{(k)}_{i,i}=\mathbb{P}_i(X_k=i),</math></center>
lequel paramètre <math>\scriptstyle\ p^{(k)}_{i,i}</math> étant par ailleurs un terme diagonal de la puissance ''k''-ème de la [[Chaîne de Markov#Puissances de la matrice de transition|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'' boites, expérience probabiliste dont un événement élémentaire ''ω'' est une application de <math>\scriptstyle\ B=[\![1,m]\!]\ </math> dans <math>\scriptstyle\ A=[\![1,n]\!]\ </math> : ''ω''(''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 [[Loi uniforme discrète|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,
<center><math>N = \sum_{k=1}^n X_k,</math></center>
où ''X''{{ind|1}}, ''X''{{ind|2}}, … , ''X{{ind|n}}'' sont définies par
<center><math>X_k\,=\, 1\!\!1_{\mathrm{la}\ k\mathrm{-\grave eme~boite~est}\ vide},</math></center>
i.e. ''X{{ind|k}}'' vaut 1 ou 0 selon que la ''k''-ème boite est ''vide'' ou pas. Étant une fonction indicatrice d'événement, ''X{{ind|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
<center><math>\mathbb{E}[X_k]=\mathbb{P}(X_k=1)\ =\ \left(1-\tfrac1n\right)^m,</math></center>
puis
<center><math>\mathbb{E}[N]=\sum_{1\le k\le n} \mathbb{P}(X_k=1)\ =\ n\left(1-\tfrac1n\right)^m.</math></center>
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#Énoncé général|inégalité d'Azuma]]<ref>{{Randomized Algorithms (Motwani et Raghavan)|numéro chapitre=4 |titre chapitre=Tail inequalities |passage=94-95}}, Théorème 4.18.</ref>. Cette inégalité de concentration permet de justifier une [[Inégalité d'Azuma#Un problème de comptage approché|méthode statistique de comptage approximatif]]<ref>proposée par {{Article
| langue = en
| prénom1 = Kyu-Young
| nom1 = Whang
| prénom2 = Ravi
| nom2 = Krishnamurthy
| titre = Query optimization in a memory-resident domain relational calculus database system
| périodique = ACM Transactions on Database Systems (TODS)
| éditeur = ACM
| lieu = New York, NY, USA
| volume = 15
| numéro = 1
| mois = mars
| année = 1990
| pages = 67-95
| issn = 0362-5915
| url texte = http://doi.acm.org/10.1145/77643.77646
}}.</ref> 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 [[Nombre de Stirling#Nombre de Stirling de seconde espèce|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#Une inégalité de concentration|inégalité d'Azuma]].

=== [[Point fixe|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 <math>\omega</math> est une [[permutation]] des éléments de <math>[\![1,n]\!]</math> : <math>\omega(k)</math> 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 <math>\omega</math> de ''n'' boules dans ''n'' boites associe le nombre <math>N(\omega)</math> de boules portant le même numéro que la boite dans laquelle elles sont rangées à la fin de cette distribution <math>\omega</math> peut être vue comme une somme de variables de Bernoulli : en effet,
<center><math>N=\sum_{k=1}^n X_k</math>,</center>
où ''X''{{ind|1}}, ''X''{{ind|2}}, … , ''X{{ind|n}}'' sont définies par
<center><math>X_k\,=\, 1\!\!1_{k\text{ est un point fixe de }\omega}</math>,</center>
{{c.-à-d.}} ''X{{ind|k}}'' 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, ''X{{ind|k}}'' est donc une variable de Bernoulli. Son paramètre est ''1/n''. On obtient que
<center><math>\mathbb{E}[N]=\sum_{1\le k\le n} \ \tfrac1n\ =\ 1</math>.</center>
En suivant une démarche analogue à celle suivie pour un [[#Sondage|sondage (cas sans remise)]], on trouve que <center><math>\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</math>.</center>
Le [[principe d'inclusion-exclusion]] permet de [[Principe d'inclusion-exclusion#Dérangements et nombre de points fixes d'une permutation|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 <math>\mathbb{E}[N]</math> 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<ref name="barbour"/>. Là encore, un avantage de l'écriture de ''N'' comme somme de variables de Bernoulli est de permettre un calcul de l'[[espérance mathématique|espérance]] et de la [[variance (statistiques et probabilités)|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 savant|paradoxe du singe dactylographe]]) ===

On considère un texte ''ω = ω''{{ind|1}}''ω''{{ind|2}}''ω''{{ind|3}}…''ω{{ind|m}}'' constitué de ''m'' caractères d'imprimerie, notés ''ω{{ind|i}}'', 1 ≤ ''i ≤ m'', 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 <math>\scriptstyle\ \mathcal{A}\ </math> l'ensemble des caractères d'imprimerie, ''n'' le cardinal de <math>\scriptstyle\ \mathcal{A}.\ </math> Soit une suite ''a = a''{{ind|1}}''a''{{ind|2}}''a''{{ind|3}}…''a{{ind|r}}'' de caractères de <math>\scriptstyle\ \mathcal{A},\ </math> 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,
<center><math>N = \sum_{k=1}^{m-r+1} X_k,</math></center>
où ''X''{{ind|1}}, ''X''{{ind|2}}, … , ''X''{{ind|''m–r''+1}} sont définies par
<center><math>X_k\,=\, 1\!\!1_{\omega_k\omega_{k+1}\omega_{k+2}\dots\omega_{k+r-1}=a},</math></center>
i.e. ''X{{ind|k}}'' vaut 1 ou 0 suivant que la suite ''a'' apparaît 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{{ind|k}}'' est donc une variable de Bernoulli. Son paramètre est
<center><math>\mathbb{P}(\omega_k\omega_{k+1}\omega_{k+2}\dots\omega_{k+r-1}=a)\ =\ \frac1{n^{r}}.</math></center>
Ainsi
<center><math>\mathbb{E}[N]=\sum_{1\le k\le m-r+1}\ \mathbb{P}(X_k\,=\, 1)\ =\ \frac{m-r+1}{n^{r}}.</math></center>
L'intuition est alors qu'il faut un texte ''ω'' de longueur au moins ''m = n{{r}}'' pour que l'événement <math>\scriptstyle\ \{N\ge 1\}\ </math> (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
<center><math>\mathbb{P}(N\ge 1)\le\mathbb{E}[N].</math></center>
Le [[Paradoxe du singe savant|paradoxe du singe dactylographe]], popularisé par [[Émile Borel]]<ref>Voir {{Article|auteur=Émile Borel | titre=Mécanique Statistique et Irréversibilité | journal=J. Phys. {{5e|série}} | volume=3 | année=1913 | pages=189-196}}.</ref>, 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 [[Nombre normal|théorème du nombre normal]].

L'analyse statistique des suites de caractères tirés au hasard [[Indépendance (probabilités)|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 (mathématicien)|Andreï Markov]], de la notion de [[chaîne de Markov]].

=== Nombre de records et nombre de cycles des [[Permutation#Décomposition en produit de cycles à supports disjoints|permutations]] ===
{{Théorème|Définition|Dans une suite ''u ''{{=}} (''u{{ind|k}}''){{ind|1''≤k≤n''}}, il y a '''''[[Correspondance fondamentale de Foata#Applications|record vers le bas]]''''' (resp. '''''vers le haut''''') au rang ''k'' si ''u{{ind|k}}''  est strictement plus petit (resp. strictement plus grand) que chaque terme ''u{{ind|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 :
<center><math>\ \omega\ {=}\ (\underline{\textbf{13}},14,\underline{\textbf{11}},15,\underline{\textbf{7}},9,\underline{\textbf{4}},5,12,\underline{\textbf{3}},\underline{\textbf{1}},6,10,8,2).</math></center>}}

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 [[permutation]]s ''ω'' de <math>\scriptstyle\ \mathfrak{S}_n\ </math> pour lesquelles la suite (''ω''(1), ''ω''(2), ''ω''(3), ..., ''ω''(''n'')) présente un record vers le bas au rang ''k''. Ainsi le nombre ''N{{ind|b}}''(''ω'') (resp. ''N{{ind|h}}''(''ω'')) de records vers le bas (resp. vers le haut) de la permutation ''ω'' s'écrit comme une somme de variables de Bernoulli :
<center><math>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).</math></center>
En vertu des propriétés statistiques du [[Code de Lehmer#Indépendance des rangs relatifs|code de Lehmer]], ces variables de Bernoulli ont pour paramètres respectifs 1/''k'' :
<center><math>\mathbb{P}(B(k))=\mathbb{P}(H(k))=\tfrac1k.</math></center>
Ainsi
<center><math>\mathbb{E}[N_b]=\mathbb{E}[N_h]=\sum_{k=1}^n\frac{1}k=H_n\simeq \ln n,</math></center>
où ''H{{ind|n}}'' désigne le ''n''-ème [[nombre harmonique]]. Comme, toujours en vertu des propriétés statistiques du [[Code de Lehmer#Indépendance des rangs relatifs|code de Lehmer]], les variables de Bernoulli concernées sont indépendantes<ref>{{Knuth-TAOCPVol3}}, {{p.|13}}.</ref>, on a également
<center><math>\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,</math></center>
où ''H{{ind|n}}{{exp|(2)}}'' est le [[nombre harmonique]] défini par
<center><math>H_n^{(2)}=\sum_{k=1}^n\frac{1}{k^2},</math></center>
et converge vers [[Fonction zêta de Riemann#Valeurs de la fonction zêta pour s entier supérieur à 1|{{math|ζ(2)}}]], i.e. vers {{math|π{{2}}/6}}.

La [[correspondance fondamentale de Foata]] permet de montrer que les deux applications suivantes :
* le nombre ''N{{ind|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 [[Variable aléatoire réelle|variables aléatoires]] ayant même loi de probabilité. Cette loi de probabilité s'exprime en termes des [[Nombre de Stirling#Nombre de Stirling de première espèce|nombres de Stirling de première espèce]], notés <math>\left[\begin{matrix}\scriptstyle n \\\scriptstyle k \end{matrix}\right]\  </math> :
<center><math>\begin{array}{rcl}
\mathbb{P}\left(N_b=k\right)&=&\tfrac1{n!}\ \left[\begin{matrix} n \\ k \end{matrix}\right],\\
\mathbb{P}\left(x\le N_b\le y\right)&=&\sum_{k=x}^y\tfrac1{n!}\ \left[\begin{matrix} n \\ k \end{matrix}\right],\end{array}</math></center>
ce qui donne une formule exacte, mais peu explicite, pour <math>\scriptstyle\ \mathbb{P}\left(\left|N_b-\ln(n)\right|\le a\sqrt{\ln(n)}\right),\  </math> formule exacte dont il est alors difficile de déduire un calcul effectif de la probabilité en question.

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

<center><math>\begin{array}{rcl}\lim_n\,\mathbb{P}\left(\left|N_b-\ln(n)\right|\le a\sqrt{\ln(n)}\right)&=&\int_{-a}^a\,\tfrac{1}{\sqrt{2\pi}}\,e^{-x^2/2}\,{\rm d}x\\&=&0{,}999\end{array}</math></center>

pour ''{{math|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''{{ind|1}}, ''x''{{ind|2}}, ''x''{{ind|3}}, … , ''x{{ind|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''{{ind|1}} avec chacun des éléments de la liste (''x''{{ind|2}}, ''x''{{ind|3}}, … , ''x{{ind|n}}''), ce qui permet de constituer 2 sous-listes, la liste des ''ω''{{ind|1}} – 1 éléments plus petits (resp. des ''n – ω''{{ind|1}} éléments plus grands) que ''x''{{ind|1}}. Cela fournit le rang ''ω''{{ind|1}} que ''x''{{ind|1}} occupera dans la liste une fois que celle-ci sera bien rangée.
* on compare ''x''{{ind|2}} avec chacun des éléments de sa sous-liste, ce qui permet de trouver le rang de ''x''{{ind|2}} dans cette sous-liste, et finalement le rang ''ω''{{ind|2}} que ''x''{{ind|2}} 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''{{ind|1}} ou ''x''{{ind|2}} sont des éléments extrémaux de leur (sous-)liste).
* on compare ''x''{{ind|3}}, etc.

Une implémentation concrète de cet algorithme abstrait est décrite par [[Donald Knuth]] dans ''{{Lang|en|[[The Art of Computer Programming]]}}''<ref>{{Harvsp|Knuth|1998|loc=chap. 5.2.2}} (« Sorting by Exchanging »).</ref>.

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''{{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 ''ω ''= (''ω''(1), ''ω''(2), ''ω''(3), … , ''ω''(''n'')) les rangs respectifs des éléments (''x''{{ind|1}}, ''x''{{ind|2}}, ''x''{{ind|3}}, … , ''x{{ind|n}}'') de la liste désordonnée au préalable, une fois que ces éléments sont rangés en une liste croissante (''y''{{ind|1}} < ''y''{{ind|2}} < ''y''{{ind|3}} < … < ''y{{ind|n}}''), de sorte que ''x{{ind|i}} = y''{{ind|''ω''(''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''! [[permutation]]s possibles. On note ''N''(''ω'') le nombre de comparaisons effectuées par l'algorithme. Alors

<center><math>N(\omega)=\sum_{1\le i<j\le n}\ 1\!\!1_{A(i,j)}(\omega),</math></center>
où ''A(i,j)'' est l'événement « ''y{{ind|i}}'' et ''y{{ind|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]].
{{Théorème|Proposition|On a<ref>{{Ouvrage
|langue=en
|prénom1=Michael
|nom1=Mitzenmacher
|prénom2=Eli
|nom2=Upfal
|titre=Probability and Computing
|sous-titre=Randomized Algorithms and Probabilistic Analysis
|numéro d'édition=1
|éditeur= Cambridge University Press
|lieu= Cambridge
|mois=avril
|année=2005
|pages totales=368
|isbn=9780521835404
|isbn10=0521835402
|numéro chapitre=2
|titre chapitre=Discrete Random Variables and Expectation, Section 2.5
|passage=34-37
|lire en ligne=https://books.google.fr/books?id=0bAYl6d7hvkC
}}.</ref>
<center><math>\mathbb{P}\left(A(i,j)\right)\ = \ \frac2{j-i+1},</math></center>
et
<center><math>
\mathbb{E}[N]\ = \ 2(n+1)\,H_n\,-\,4n\ \simeq\ 2n\,\ln(n).
</math></center>
}}
{{Démonstration
| Il y a deux possibilités :
* si le terme, disons ''z'', de la liste ''L ''{{=}} (''y{{ind|i}} ''< ''y''{{ind|''i''+1}} < … < ''y''{{ind|''j''–1}} < ''y{{ind|j}}'') qui apparait le premier dans la liste (''x''{{ind|1}}, ''x''{{ind|2}}, ''x''{{ind|3}}, … , ''x{{ind|n}}'') est compris strictement entre  ''y{{ind|i }}'' et ''y{{ind|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{{ind|i }}'' et ''y{{ind|j }}'' sont placés dans deux sous-listes différentes (puisque ''y{{ind|i }} < z < y{{ind|j }}'') et ne seront plus jamais comparées :
<center><math>1\!\!1_{A(i,j)}(\omega)=0.</math></center>
* si ''z'' est l'un des deux éléments ''y{{ind|i }}'' et '' y{{ind|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{{ind|i }}, y{{ind|j }})'' :
<center><math>1\!\!1_{A(i,j)}(\omega)=1\ .</math></center>

La répartition des ''j – i ''+ 1 éléments de la liste ''L'' dans la liste ''x'' est aléatoire [[Loi uniforme discrète|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
<center><math>\begin{array}{rl}
\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{array}
</math></center>
et
<center><math>
\begin{array}{rl}
\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{array}
</math></center>
où ''H{{ind|n}}'' désigne le ''n''-ème [[nombre harmonique]]. La {{4e|égalité}} provient du changement de variables <math>\scriptstyle\ \ell=j-i+1,</math> la {{5e|égalité}} provient du changement de variables <math>\scriptstyle\ m=n-i+1,</math> et la {{6e|égalité}} découle d'une interversion de l'ordre de sommation entre les variables ''m'' et <math>\scriptstyle\ \ell.</math>}}
Ainsi la randomisation de la liste fournie en entrée permet de diminuer le coût de l'algorithme, de ''n''{{2}} à 2''n'' 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π{{2}}/3)) ''n''{{2}}, 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 ln(''n''!)/ln(2) qui, d'après la [[formule de Stirling]], vaut approximativement 1,4''n'' ln(''n'').

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Processus de Bernoulli]]
* [[Inégalité de Hoeffding]]
* [[Jacques Bernoulli]]

{{Palette|Lois de probabilités|Probabilités et statistiques}}
{{Portail|probabilités et statistiques}}

[[Catégorie:Loi de probabilité|Bernoulli]]
[[Catégorie:Jacques Bernoulli]]