Procédé Bernoulli - Bernoulli process

Fait partie d'une série sur les statistiques
Théorie des probabilités
Probabilité Axiomes Déterminisme Système Indéterminisme Aléatoire
Espace de probabilité Espace d'échantillon Événement Des événements collectivement exhaustifs Événement élémentaire Exclusivité mutuelle Résultat Singleton Expérience Procès Bernoulli Distribution de probabilité Distribution de Bernoulli Distribution binomiale Distribution normale Mesure de probabilité Variable aléatoire procédé Bernoulli Continu ou discret Valeur attendue chaîne de Markov Valeur observée Marche aléatoire Processus stochastique
Événement complémentaire Probabilité conjointe Probabilité marginale Probabilite conditionnelle
Indépendance Indépendance conditionnelle Loi de probabilité totale Loi des grands nombres théorème de Bayes L'inégalité de Boole
Diagramme de Venn Diagramme d'arbre
v t e

En probabilités et statistiques , un processus de Bernoulli (du nom de Jacob Bernoulli ) est une séquence finie ou infinie de variables aléatoires binaires , il s'agit donc d'un processus stochastique à temps discret qui ne prend que deux valeurs, canoniquement 0 et 1. La composante des variables de Bernoulli X _i sont équidistribuées et indépendants . Prosaïquement, un processus de Bernoulli est un retournement répété de pièces , éventuellement avec une pièce injuste (mais avec une injustice constante). Chaque variable X _i dans la séquence est associée à un essai ou à une expérience de Bernoulli . Ils ont tous la même distribution de Bernoulli . Une grande partie de ce qui peut être dit sur le processus de Bernoulli peut également être généralisé à plus de deux résultats (comme le processus pour un dé à six faces) ; cette généralisation est connue sous le nom de schéma de Bernoulli .

Le problème de déterminer le processus, étant donné seulement un échantillon limité d'essais de Bernoulli, peut être appelé le problème de vérifier si une pièce est juste .

Définition

Un processus de Bernoulli est finie ou infinie de séquence indépendantes variables aléatoires X ₁ ,  X ₂ ,  X ₃ , ..., de telle sorte que

• pour chaque i , la valeur de X _i est soit 0, soit 1 ;
• pour toutes les valeurs de i , la probabilité p que X _i  = 1 soit la même.

En d'autres termes, un processus de Bernoulli est une séquence d' essais de Bernoulli indépendants répartis de manière identique .

L'indépendance des épreuves implique que le processus est sans mémoire . Étant donné que la probabilité p est connue, les résultats passés ne fournissent aucune information sur les résultats futurs. (Si p est inconnu, cependant, le passé informe sur le futur indirectement, par le biais d'inférences sur  p .)

Si le processus est infini, alors les essais futurs constituent en tout point un processus de Bernoulli identique à l'ensemble du processus, la propriété du nouveau départ.

Interprétation

Les deux valeurs possibles de chaque X _i sont souvent appelées "succès" et "échec". Ainsi, exprimée en nombre 0 ou 1, le résultat peut être appelé le nombre de succès sur le i e « procès ».

Deux autres interprétations courantes des valeurs sont vraies ou fausses et oui ou non. Quelle que soit l'interprétation des deux valeurs, les variables individuelles X _i peuvent être appelées essais de Bernoulli avec le paramètre p.

Dans de nombreuses applications, le temps s'écoule entre les essais, à mesure que l'indice i augmente. En effet, les essais X ₁ ,  X ₂ , ...  X _i , ... se produisent à des "points dans le temps" 1, 2, ...,  i , .... Ce passage du temps et les notions associées de "passé" et "futur" ne sont cependant pas nécessaires. Plus généralement, tout X _i et X _j dans le processus sont simplement deux d'un ensemble de variables aléatoires indexées par {1, 2, ...,  n }, les cas finis, ou par {1, 2, 3, .. .}, les cas infinis.

Une expérience avec seulement deux résultats possibles, souvent appelée "succès" et "échec", généralement codée par 1 et 0, peut être modélisée comme une distribution de Bernoulli . Plusieurs variables aléatoires et distributions de probabilité à côté du Bernoullis peuvent être dérivées du processus de Bernoulli :

• Le nombre de succès dans les n premiers essais, qui a une distribution binomiale B( n ,  p )
• Le nombre d'échecs nécessaires pour obtenir r succès, qui a une distribution binomiale négative NB( r ,  p )
• Le nombre d'échecs nécessaires pour obtenir un succès, qui a une distribution géométrique NB(1,  p ), un cas particulier de la distribution binomiale négative

Les variables binomiales négatives peuvent être interprétées comme des temps d'attente aléatoires .

Définition formelle

Le processus de Bernoulli peut être formalisé dans le langage des espaces de probabilité comme une séquence aléatoire de réalisations indépendantes d'une variable aléatoire qui peut prendre des valeurs de pile ou face. L'espace d'état pour une valeur individuelle est désigné par${\displaystyle 2=\{H,T\}.}$

Algèbre de Borel

Considérez le produit direct dénombrable infini de copies de . Il est courant d'examiner soit l'ensemble unilatéral, soit l'ensemble recto-verso . Il existe une topologie naturelle sur cet espace, appelée topologie produit . Les ensembles de cette topologie sont des séquences finies de lancers de pièces, c'est-à-dire des chaînes de longueur finie de H et T ( H signifie face et T signifie pile ), le reste de la séquence (infiniment longue) étant considéré comme « ne pas se soucier". Ces ensembles de séquences finies sont appelés ensembles de cylindres dans la topologie du produit. L'ensemble de toutes ces chaînes forme une algèbre sigma , en particulier une algèbre de Borel . Cette algèbre est alors communément écrite comme où les éléments de sont les séquences de longueur finie de lancers de pièces (les ensembles de cylindres). ${\displaystyle 2=\{H,T\}}$${\displaystyle \Omega =2^{\mathbb {N} }=\{H,T\}^{\mathbb {N} }}$${\displaystyle \Omega =2^{\mathbb {Z} }}$${\displaystyle (\Omega ,{\mathcal {B}})}$${\displaystyle {\mathcal {B}}}$

mesure de Bernoulli

Si les chances de renverser pile ou face sont données par les probabilités , alors on peut définir une mesure naturelle sur l'espace produit, donnée par (ou par pour le processus bilatéral). En d'autres termes, si une variable aléatoire discrète X a une distribution de Bernoulli de paramètre p , où 0 p 1, et sa fonction de masse de probabilité est donnée par ${\style d'affichage \{p,1-p\}}$${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$${\displaystyle P=\{p,1-p\}^{\mathbb {Z} }}$

${\style d'affichage pX(1)=P(X=1)=p}$et .${\style d'affichage pX(0)=P(X=0)=1-p}$

On note cette distribution par Ber( p ).

Étant donné un jeu de cylindres, c'est-à-dire une séquence spécifique de tirages au sort à certains moments , la probabilité d'observer cette séquence particulière est donnée par ${\displaystyle [\omega _{1},\omega _{2},\cdots \omega _{n}]}$${\displaystyle 1,2,\cdots ,n}$

${\displaystyle P([\omega _{1},\omega _{2},\cdots ,\omega _{n}])=p^{k}(1-p)^{nk}}$

où k est le nombre de fois que H apparaît dans la séquence, et n − k est le nombre de fois que T apparaît dans la séquence. Il existe plusieurs types de notations pour ce qui précède ; un commun est d'écrire

${\displaystyle P(X_{1}=x_{1},X_{2}=x_{2},\cdots ,X_{n}=x_{n})=p^{k}(1-p)^ {nk}}$

où chacun est une valeur binaire variable aléatoire avec en support Iverson notation, ce qui signifie soit si ou si . Cette probabilité est communément appelée la mesure de Bernoulli . ${\style d'affichage X_{i}}$${\displaystyle x_{i}=[\omega _{i}=H]}$${\style d'affichage 1}$${\displaystyle \omega _{i}=H}$${\style d'affichage 0}$${\displaystyle \omega _{i}=T}$${\style d'affichage P}$

Notez que la probabilité d'une séquence spécifique et infiniment longue de lancers de pièces est exactement de zéro ; c'est parce que , pour tout . Une probabilité égale à 1 implique que toute séquence infinie donnée a pour mesure zéro . Néanmoins, on peut toujours dire que certaines classes de séquences infinies de lancers de pièces sont beaucoup plus probables que d'autres, cela est donné par la propriété d'équipartition asymptotique . ${\displaystyle \lim _{n\to \infty }p^{n}=0}$${\style d'affichage 0\leq p<1}$

Pour conclure la définition formelle, un processus de Bernoulli est alors donné par le triplet de probabilité , tel que défini ci-dessus. ${\displaystyle (\Omega ,{\mathcal {B}},P)}$

Loi des grands nombres, distribution binomiale et théorème central limite

Supposons le processus canonique avec représenté par et représenté par . La loi des grands nombres stipule que, sur la moyenne de la séquence, c'est-à-dire , s'approchera presque certainement de la valeur attendue , c'est-à-dire que les événements qui ne satisfont pas cette limite ont une probabilité nulle. La valeur attendue des têtes retournées , supposée être représentée par 1, est donnée par . En fait, on a ${\style d'affichage H}$${\style d'affichage 1}$${\style d'affichage T}$${\style d'affichage 0}$${\displaystyle {\bar {X}}_{n} :={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$${\style d'affichage p}$

${\displaystyle \mathbb {E} [X_{i}]=\mathbb {P} ([X_{i}=1])=p,}$

pour toute variable aléatoire donnée de la séquence infinie d' essais de Bernoulli qui composent le processus de Bernoulli. ${\style d'affichage X_{i}}$

On s'intéresse souvent à savoir à quelle fréquence on observera H dans une séquence de n lancers de pièces. Ceci est donné en comptant simplement : étant donné n lancers de pièces successifs, c'est-à-dire étant donné l'ensemble de toutes les chaînes possibles de longueur n , le nombre N ( k , n ) de telles chaînes qui contiennent k occurrences de H est donné par le coefficient binomial

${\displaystyle N(k,n)={n \choisissez k}={\frac {n!}{k!(nk)!}}}$

Si la probabilité de retourner les têtes est donnée par p , alors la probabilité totale de voir une chaîne de longueur n avec k têtes est

${\displaystyle \mathbb {P} ([S_{n}=k])={n \choose k}p^{k}(1-p)^{nk},}$

où . La mesure de probabilité ainsi définie est connue sous le nom de distribution binomiale . ${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}$

Comme nous pouvons le voir d'après la formule ci-dessus, si n=1, la distribution binomiale se transformera en une distribution de Bernoulli . Nous pouvons donc savoir que la distribution de Bernoulli est exactement un cas particulier de distribution binomiale lorsque n est égal à 1.

La question de la valeur de pour une séquence suffisamment longue de lancers de pièces est particulièrement intéressante , c'est-à-dire pour la limite . Dans ce cas, on peut utiliser l'approximation de Stirling à la factorielle, et écrire ${\style d'affichage S_{n}}$${\style d'affichage n\à \infty }$

${\displaystyle n!={\sqrt {2\pi n}}\;n^{n}e^{-n}\left(1+{\mathcal {O}}\left({\frac {1} {n}}\droit)\droit)}$

En insérant ceci dans l'expression pour P ( k , n ), on obtient la distribution Normale ; c'est le contenu du théorème central limite , et c'est l'exemple le plus simple de celui-ci.

La combinaison de la loi des grands nombres, avec le théorème central limite, conduit à un résultat intéressant et peut-être surprenant : la propriété d'équipartition asymptotique . En termes informels, on note que, oui, sur de nombreux lancers de pièces, on observera H exactement p fraction du temps, et que cela correspond exactement au pic de la gaussienne. La propriété d'équipartition asymptotique indique essentiellement que ce pic est infiniment net, avec une chute infinie de chaque côté. Autrement dit, étant donné l'ensemble de toutes les chaînes infiniment longues possibles de H et T apparaissant dans le processus de Bernoulli, cet ensemble est partitionné en deux : la loi Kolmogorov 0-1 .

La taille de cet ensemble est également intéressante et peut être explicitement déterminée : son logarithme est exactement l' entropie du processus de Bernoulli. Encore une fois, considérons l'ensemble de toutes les chaînes de longueur n . La taille de cet ensemble est . Parmi ceux-ci, seul un certain sous-ensemble est probable ; la taille de cet ensemble est pour . En utilisant l'approximation de Stirling, en la mettant dans l'expression de P ( k , n ), en résolvant l'emplacement et la largeur du pic, et enfin en prenant on trouve que ${\style d'affichage 2^{n}}$${\style d'affichage 2^{nH}}$${\displaystyle H\leq 1}$${\style d'affichage n\à \infty }$

${\displaystyle H=-p\log _{2}p-(1-p)\log _{2}(1-p)}$

Cette valeur est l' entropie de Bernoulli d'un processus de Bernoulli. Ici, H signifie entropie; ne le confondez pas avec le même symbole H pour têtes .

John von Neumann a posé une curieuse question sur le processus de Bernoulli : est-il jamais possible qu'un processus donné soit isomorphe à un autre, au sens de l' isomorphisme des systèmes dynamiques ? La question a longtemps défié l'analyse, mais a finalement trouvé une réponse complète avec le théorème d'isomorphisme d'Ornstein . Cette percée a permis de comprendre que le processus de Bernoulli est unique et universel ; en un certain sens, c'est le processus le plus aléatoire possible ; rien n'est « plus » aléatoire que le processus de Bernoulli (bien qu'il faille être prudent avec cette affirmation informelle ; certes, les systèmes qui se mélangent sont, dans un certain sens, « plus forts » que le processus de Bernoulli, qui est simplement ergodique mais ne se mélange pas. Cependant, de tels processus ne sont pas constitués de variables aléatoires indépendantes : en effet, de nombreux systèmes purement déterministes et non aléatoires peuvent se mélanger).

Systèmes dynamiques

Le processus de Bernoulli peut également être compris comme un système dynamique , en tant qu'exemple de système ergodique et plus précisément, un système dynamique préservant la mesure , de plusieurs manières différentes. Une façon est comme un espace de changement , et l'autre est comme un odomètre . Ceux-ci sont examinés ci-dessous.

Changement de Bernoulli

Une façon de créer un système dynamique à partir du processus de Bernoulli est un espace de décalage . Il existe une symétrie de translation naturelle sur l'espace produit donnée par l' opérateur de décalage${\displaystyle \Omega =2^{\mathbb {N} }}$

${\displaystyle T(X_{0},X_{1},X_{2},\cdots )=(X_{1},X_{2},\cdots )}$

La mesure de Bernoulli, définie ci-dessus, est invariante par translation ; c'est-à-dire que, étant donné n'importe quel ensemble de cylindres , on a ${\displaystyle \sigma \in {\mathcal {B}}}$

${\style d'affichage P(T^{-1}(\sigma ))=P(\sigma )}$

et ainsi la mesure de Bernoulli est une mesure de Haar ; c'est une mesure invariante sur l'espace produit.

Au lieu de la mesure de probabilité , considérons plutôt une fonction arbitraire . La poussée${\displaystyle P:{\mathcal {B}}\to \mathbb {R} }$${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$

${\displaystyle f\circ T^{-1}}$

défini par est à nouveau une fonction Ainsi, l'application induit une autre application sur l'espace de toutes les fonctions C'est-à-dire que, étant donné certaines , on définit ${\displaystyle \left(f\circ T^{-1}\right)(\sigma )=f(T^{-1}(\sigma ))}$${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$${\style d'affichage T}$${\displaystyle {\mathcal {L}}_{T}}$${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$

${\displaystyle {\mathcal {L}}_{T}f=f\circ T^{-1}}$

La carte est un opérateur linéaire , comme (évidemment) on a et pour les fonctions et constante . Cet opérateur linéaire est appelé opérateur de transfert ou opérateur de Ruelle-Frobenius-Perron . Cet opérateur a un spectre , c'est-à-dire une collection de fonctions propres et de valeurs propres correspondantes. La plus grande valeur propre est la valeur propre de Frobenius-Perron , et dans ce cas, elle vaut 1. Le vecteur propre associé est la mesure invariante : dans ce cas, c'est la mesure de Bernoulli. C'est-à-dire,${\displaystyle {\mathcal {L}}_{T}}$${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$${\style d'affichage f,g}$${\style d'affichage a}$${\displaystyle {\mathcal {L}}_{T}(P)=P.}$

Si l'on se limite à agir sur les polynômes, alors les fonctions propres sont (curieusement) les polynômes de Bernoulli ! Cette coïncidence de dénomination n'était probablement pas connue de Bernoulli. ${\displaystyle {\mathcal {L}}_{T}}$

La carte 2x mod 1

L'application T  : [0,1) → [0,1), conserve la mesure de Lebesgue .${\displaystyle x\mapsto 2x{\bmod {1}}}$

Ce qui précède peut être rendu plus précis. Étant donné une chaîne infinie de chiffres binaires, écrivez ${\displaystyle b_{0},b_{1},\cdots }$

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

Le résultat est un nombre réel dans l'intervalle unitaire. Le décalage induit un homomorphisme , également appelé , sur l'intervalle unitaire. Puisqu'on peut facilement voir que cette carte s'appelle la transformation dyadique ; pour la séquence doublement infinie de bits, l'homomorphisme induit est l'application de Baker . ${\style d'affichage y}$${\style d'affichage 0\leq y\leq 1.}$${\style d'affichage T}$${\style d'affichage T}$${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots ),}$${\displaystyle T(y)=2y{\bmod {1}}.}$${\displaystyle \Omega =2^{\mathbb {Z} },}$

Considérons maintenant l'espace des fonctions dans . Étant donné que quelqu'un peut facilement trouver que ${\style d'affichage y}$${\style d'affichage f(y)}$

${\displaystyle \left[{\mathcal {L}}_{T}f\right](y)={\frac {1}{2}}f\left({\frac {y}{2}}\ droite)+{\frac {1}{2}}f\gauche({\frac {y+1}{2}}\droite)}$

En restreignant l'action de l'opérateur aux fonctions qui sont sur des polynômes, on trouve qu'il a un spectre discret donné par ${\displaystyle {\mathcal {L}}_{T}}$

${\displaystyle {\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}}$

où sont les polynômes de Bernoulli . En effet, les polynômes de Bernoulli obéissent à l'identité ${\style d'affichage B_{n}}$

${\displaystyle {\frac {1}{2}}B_{n}\left({\frac {y}{2}}\right)+{\frac {1}{2}}B_{n}\left ({\frac {y+1}{2}}\right)=2^{-n}B_{n}(y)}$

L'ensemble Cantor

Notez que la somme

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{3^{n+1}}}}$

donne la fonction de Cantor , telle que définie par convention. C'est l'une des raisons pour lesquelles l'ensemble est parfois appelé ensemble de Cantor . ${\displaystyle \{H,T\}^{\mathbb {N} }}$

Odomètre

Une autre façon de créer un système dynamique est de définir un odomètre . De manière informelle, c'est exactement ce à quoi cela ressemble: il suffit d'en "ajouter un" à la première position et de laisser l'odomètre "rouler" en utilisant des bits de report pendant que l'odomètre roule. Ce n'est rien de plus qu'une addition de base deux sur l'ensemble des chaînes infinies. Puisque l'addition forme un groupe (mathématiques) et que le processus de Bernoulli a déjà reçu une topologie, ci-dessus, cela fournit un exemple simple de groupe topologique .

Dans ce cas, la transformation est donnée par ${\style d'affichage T}$

${\displaystyle T\left(1,\dots ,1,0,X_{k+1},X_{k+2},\dots \right)=\left(0,\dots ,0,1,X_{ k+1},X_{k+2},\dots \right).}$

Il ne laisse invariante la mesure de Bernoulli que pour le cas particulier de (la "juste pièce"); sinon non. Ainsi, est une mesure préservant le système dynamique dans ce cas, sinon, c'est simplement un système conservateur . ${\style d'affichage p=1/2}$${\style d'affichage T}$

séquence de Bernoulli

Le terme séquence de Bernoulli est souvent utilisé de manière informelle pour désigner une réalisation d'un processus de Bernoulli. Cependant, le terme a une définition formelle entièrement différente, comme indiqué ci-dessous.

Supposons un processus de Bernoulli formellement défini comme une variable aléatoire unique (voir la section précédente). Pour chaque séquence infinie x de lancers de pièces, il existe une séquence d'entiers

${\displaystyle \mathbb {Z} ^{x}=\{n\in \mathbb {Z} :X_{n}(x)=1\}\,}$

appelée séquence de Bernoulli associée au processus de Bernoulli. Par exemple, si x représente une séquence de pièces flips, la séquence Bernoulli associée est la liste des nombres naturels ou points de temps pour lesquels la pièce Toss résultat est la tête .

Ainsi définie, une séquence de Bernoulli est également un sous-ensemble aléatoire de l'ensemble d'indices, les nombres naturels . ${\displaystyle \mathbb {Z} ^{x}}$${\displaystyle \mathbb {N} }$

Presque toutes les séquences de Bernoulli sont des séquences ergodiques . ${\displaystyle \mathbb {Z} ^{x}}$

Extraction aléatoire

De n'importe quel processus de Bernoulli, on peut dériver un processus de Bernoulli avec p  = 1/2 par l' extracteur de von Neumann , le premier extracteur d'aléatoire , qui extrait en fait l'aléatoire uniforme.

Extracteur de base von Neumann

Représentez le processus observé sous la forme d'une séquence de zéros et de uns, ou de bits, et groupez ce flux d'entrée en paires de bits successifs ne se chevauchant pas, telles que (11)(00)(10)... . Puis pour chaque paire,

• si les bits sont égaux, rejeter ;
• si les bits ne sont pas égaux, sortir le premier bit.

Ce tableau résume le calcul.

Par exemple, un flux d'entrée de huit bits 10011011 serait groupé par paires sous la forme (10)(01)(10)(11) . Ensuite, selon le tableau ci-dessus, ces paires sont traduites en sortie de la procédure : (1)(0)(1)() (= 101 ).

Dans le flux de sortie, 0 et 1 sont également probables, comme 10 et 01 sont également probables dans l'original, les deux ayant une probabilité p (1− p ) = (1− p ) p . Cette extraction de l'aléa uniforme ne nécessite pas que les essais d'entrée soient indépendants, seulement non corrélés . Plus généralement, cela fonctionne pour toute séquence de bits échangeable : toutes les séquences qui sont des réarrangements finis sont également probables.

L'extracteur de von Neumann utilise deux bits d'entrée pour produire zéro ou un bit de sortie, de sorte que la sortie est plus courte que l'entrée d'un facteur d'au moins 2. En moyenne, le calcul rejette la proportion p ²  + (1 −  p ) ² du paires d'entrée (00 et 11), qui est proche de un lorsque p est proche de zéro ou un, et est minimisé à 1/4 lorsque p  = 1/2 pour le processus d'origine (auquel cas le flux de sortie est 1/4 de la longueur du flux d'entrée en moyenne).

Von Neumann opération principale (classique) pseudocode :

if (Bit1 ≠ Bit2) {
   output(Bit1)
}

Extracteur de von Neumann itéré

Cette diminution de l'efficacité, ou le gaspillage du caractère aléatoire présent dans le flux d'entrée, peut être atténué en itérant l'algorithme sur les données d'entrée. De cette façon, la sortie peut être rendue "arbitrairement proche de la limite d'entropie".

La version itérée de l'algorithme de von Neumann, également connue sous le nom de Advanced Multi-Level Strategy (AMLS), a été introduite par Yuval Peres en 1992. Elle fonctionne de manière récursive, en recyclant le « gâché aléatoire » à partir de deux sources : la séquence de rejet/non-rejet , et les valeurs des paires rejetées (0 pour 00 et 1 pour 11). Intuitivement, il repose sur le fait que, compte tenu de la séquence déjà générée, ces deux sources sont toujours des séquences de bits échangeables, et donc éligibles pour un autre tour d'extraction. Alors qu'une telle génération de séquences supplémentaires peut être itérée à l'infini pour extraire toute l'entropie disponible, une quantité infinie de ressources de calcul est requise, donc le nombre d'itérations est généralement fixé à une valeur faible - cette valeur soit fixée à l'avance, soit calculée au moment de l'exécution.

Plus concrètement, sur une séquence d'entrée, l'algorithme consomme les bits d'entrée par paires, générant une sortie avec deux nouvelles séquences :

(Si la longueur de l'entrée est impaire, le dernier bit est complètement ignoré.) Ensuite, l'algorithme est appliqué de manière récursive à chacune des deux nouvelles séquences, jusqu'à ce que l'entrée soit vide.

Exemple : Le flux d'entrée ci-dessus, 10011011 , est traité de cette façon :

A partir du pas de 1, l'entrée devient la nouvelle séquence1 du dernier pas pour avancer dans ce processus. La sortie est donc (101)(1)(0)()()() (= 10110 ), de sorte qu'à partir des huit bits d'entrée, cinq bits de sortie ont été générés, par opposition à trois bits via l'algorithme de base ci-dessus. La sortie constante d'exactement 2 bits par tour (par rapport à une variable de 0 à 1 bits dans le VN classique) permet également des implémentations à temps constant qui résistent aux attaques de synchronisation .

Pseudo-code d'opération principale de Von Neumann-Peres (itéré) :

if (Bit1 ≠ Bit2) {
   output(1, Sequence1)
   output(Bit1)
} else {
   output(0, Sequence1)
   output(Bit1, Sequence2)
}

Un autre ajustement a été présenté en 2016, basé sur l'observation que le canal Sequence2 ne fournit pas beaucoup de débit, et une implémentation matérielle avec un nombre fini de niveaux peut bénéficier de son élimination plus tôt en échange du traitement de plus de niveaux de Sequence1.

Les références

Lectures complémentaires

• Carl W. Helstrom, Probabilité et processus stochastiques pour les ingénieurs , (1984) Macmillan Publishing Company, New York ISBN  0-02-353560-1 .

Liens externes

• Utilisation d'un arbre binaire pour décrire un processus de Bernoulli