Proceso de Bernoulli

Proceso aleatorio de variables aleatorias binarias (booleanas)

En probabilidad y estadística , un proceso de Bernoulli (llamado así por Jacob Bernoulli ) es una secuencia finita o infinita de variables aleatorias binarias , por lo que es un proceso estocástico de tiempo discreto que toma solo dos valores, canónicamente 0 y 1. Las variables de Bernoulli componentes X _i están distribuidas de manera idéntica y son independientes . Prosaicamente, un proceso de Bernoulli es un lanzamiento repetido de moneda , posiblemente con una moneda injusta (pero con injusticia consistente). Cada variable X _i en la secuencia está asociada con un ensayo o experimento de Bernoulli. Todos tienen la misma distribución de Bernoulli . Gran parte de lo que se puede decir sobre el proceso de Bernoulli también se puede generalizar a más de dos resultados (como el proceso para un dado de seis caras); esta generalización se conoce como el esquema de Bernoulli .

El problema de determinar el proceso, dada sólo una muestra limitada de ensayos de Bernoulli, puede llamarse el problema de comprobar si una moneda es justa .

Definición

Un proceso de Bernoulli es una secuencia finita o infinita de variables aleatorias independientes X ₁ ,  X ₂ ,  X ₃ , ..., tales que

• para cada i , el valor de _Xi es 0 o 1;
• para todos los valores de , la probabilidad p de que X _i  = 1 es la misma. ${\textstyle i}$

En otras palabras, un proceso de Bernoulli es una secuencia de ensayos de Bernoulli independientes distribuidos de forma idéntica .

La independencia de los ensayos implica que el proceso no tiene memoria . Dado que se conoce la probabilidad p , los resultados pasados ​​no brindan información sobre los resultados futuros. (Sin embargo, si se desconoce p , el pasado informa sobre el futuro indirectamente, a través de inferencias sobre  p ).

Si el proceso es infinito, entonces desde cualquier punto los ensayos futuros constituyen un proceso de Bernoulli idéntico al proceso completo, la propiedad de nuevo comienzo.

Interpretación

Los dos valores posibles de cada X _i se denominan a menudo "éxito" y "fracaso". Por lo tanto, cuando se expresa como un número 0 o 1, el resultado puede denominarse el número de éxitos en el i- ésimo "ensayo".

Otras dos interpretaciones comunes de los valores son verdadero o falso y sí o no. Bajo cualquier interpretación de los dos valores, las variables individuales Xi pueden llamarse ensayos de Bernoulli _con parámetro p.

En muchas aplicaciones, el tiempo pasa entre los ensayos, a medida que el índice i aumenta. En efecto, los ensayos X ₁ ,  X ₂ , ...  X _i , ... ocurren en "puntos en el tiempo" 1, 2, ...,  i , .... Sin embargo, ese paso del tiempo y las nociones asociadas de "pasado" y "futuro" no son necesarios. En general, cualquier X _i y X _j en el proceso son simplemente dos de un conjunto de variables aleatorias indexadas por {1, 2, ...,  n }, los casos finitos, o por {1, 2, 3, ...}, los casos infinitos.

Un experimento con sólo dos resultados posibles, a menudo denominados "éxito" y "fracaso", normalmente codificados como 1 y 0, se puede modelar como una distribución de Bernoulli . ^[1] Varias variables aleatorias y distribuciones de probabilidad además de las de Bernoulli se pueden derivar del proceso de Bernoulli:

• El número de éxitos en los primeros n ensayos, que tiene una distribución binomial B( n ,  p )
• El número de fracasos necesarios para obtener r éxitos, que tiene una distribución binomial negativa NB( r ,  p )
• El número de fracasos necesarios para obtener un éxito, que tiene una distribución geométrica NB(1,  p ), un caso especial de la distribución binomial negativa

Las variables binomiales negativas pueden interpretarse como tiempos de espera aleatorios .

Definición formal

El proceso de Bernoulli se puede formalizar en el lenguaje de los espacios de probabilidad como una secuencia aleatoria de realizaciones independientes de una variable aleatoria que puede tomar valores de cara o cruz. El espacio de estados para un valor individual se denota por ${\displaystyle 2=\{H,T\}.}$

Álgebra de Borel

Considere el producto directo infinito numerable de copias de . Es común examinar el conjunto unilateral o el conjunto bilateral . Existe una topología natural en este espacio, llamada topología del producto . Los conjuntos en esta topología son secuencias finitas de lanzamientos de moneda, es decir, cadenas de longitud finita de H y T ( H representa cara y T representa cruz), con el resto de la secuencia (infinitamente larga) tomada como "no importa". Estos conjuntos de secuencias finitas se conocen como conjuntos cilíndricos en la topología del producto. El conjunto de todas esas cadenas forma un álgebra sigma , específicamente, un álgebra de Borel . Esta álgebra se escribe entonces comúnmente como donde los elementos de son las secuencias de longitud finita de lanzamientos de moneda (los conjuntos cilíndricos). ${\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}}}$

Medida de Bernoulli

Si las posibilidades de obtener cara o cruz están dadas por las probabilidades , entonces se puede definir una medida natural en el espacio de producto, dada por (o por para el proceso bilateral). En otras palabras, si una variable aleatoria discreta X tiene una distribución de Bernoulli con parámetro p , donde 0 ≤ p ≤ 1, y su función de masa de probabilidad está dada por ${\displaystyle \{p,1-p\}}$ ${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$ ${\displaystyle P=\{p,1-p\}^{\mathbb {Z} }}$

${\displaystyle pX(1)=P(X=1)=p}$y . ${\displaystyle pX(0)=P(X=0)=1-p}$

Denotamos esta distribución por Ber( p ). ^[1]

Dado un conjunto de cilindros, es decir, una secuencia específica de resultados de lanzamiento de moneda en momentos , la probabilidad de observar esta secuencia particular está dada por ${\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)^{n-k}}$

donde k es el número de veces que H aparece en la secuencia, y n − k es el número de veces que T aparece en la secuencia. Hay varios tipos diferentes de notaciones para lo anterior; una común es escribir

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

donde cada una es una variable aleatoria de valor binario con notación de corchetes de Iverson , es decir, si o si . Esta probabilidad se denomina comúnmente medida de Bernoulli . ^[2] ${\displaystyle X_{i}}$ ${\displaystyle x_{i}=[\omega _{i}=H]}$ ${\displaystyle 1}$ ${\displaystyle \omega _{i}=H}$ ${\displaystyle 0}$ ${\displaystyle \omega _{i}=T}$ ${\displaystyle P}$

Nótese que la probabilidad de cualquier secuencia específica infinitamente larga de lanzamientos de moneda es exactamente cero; esto se debe a que , para cualquier . Una probabilidad igual a 1 implica que cualquier secuencia infinita dada tiene medida cero . Sin embargo, todavía se puede decir que algunas clases de secuencias infinitas de lanzamientos de moneda son mucho más probables que otras, esto se da por la propiedad de equipartición asintótica . ${\displaystyle \lim _{n\to \infty }p^{n}=0}$ ${\displaystyle 0\leq p<1}$

Para concluir la definición formal, un proceso de Bernoulli viene dado por el triple de probabilidad , como se definió anteriormente. ${\displaystyle (\Omega ,{\mathcal {B}},P)}$

Ley de los grandes números, distribución binomial y teorema del límite central

Supongamos el proceso canónico con representado por y representado por . La ley de los grandes números establece que el promedio de la secuencia, es decir, , se acercará al valor esperado casi con certeza, es decir, los eventos que no satisfacen este límite tienen probabilidad cero. El valor esperado de sacar cara , que se supone que está representado por 1, está dado por . De hecho, uno tiene ${\displaystyle H}$ ${\displaystyle 1}$ ${\displaystyle T}$ ${\displaystyle 0}$ ${\displaystyle {\bar {X}}_{n}:={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$ ${\displaystyle p}$

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

para cualquier variable aleatoria dada de la secuencia infinita de ensayos de Bernoulli que componen el proceso de Bernoulli. ${\displaystyle X_{i}}$

A menudo nos interesa saber con qué frecuencia observaremos H en una secuencia de n lanzamientos de moneda. Esto se obtiene simplemente contando: Dados n lanzamientos de moneda sucesivos, es decir, dado el conjunto de todas las cadenas posibles de longitud n , el número N ( k , n ) de tales cadenas que contienen k ocurrencias de H está dado por el coeficiente binomial

${\displaystyle N(k,n)={n \choose k}={\frac {n!}{k!(n-k)!}}}$

Si la probabilidad de obtener cara está dada por p , entonces la probabilidad total de ver una cadena de longitud n con k caras es

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

donde . La medida de probabilidad así definida se conoce como distribución binomial . ${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}$

Como podemos ver en la fórmula anterior, si n = 1, la distribución binomial se convertirá en una distribución de Bernoulli . Por lo tanto, podemos saber que la distribución de Bernoulli es exactamente un caso especial de distribución binomial cuando n es igual a 1.

De particular interés es la cuestión del valor de para una secuencia suficientemente larga de lanzamientos de moneda, es decir, para el límite . En este caso, se puede hacer uso de la aproximación de Stirling al factorial y escribir ${\displaystyle S_{n}}$ ${\displaystyle n\to \infty }$

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

Insertando esto en la expresión para P ( k , n ), se obtiene la distribución normal ; este es el contenido del teorema del límite central , y este es el ejemplo más simple del mismo.

La combinación de la ley de los grandes números, junto con el teorema del límite central, conduce a un resultado interesante y quizás sorprendente: la propiedad de equipartición asintótica . Expresado de manera informal, se observa que, sí, a lo largo de muchos lanzamientos de moneda, se observará H exactamente p fracción del tiempo, y que esto corresponde exactamente con el pico de la gaussiana. La propiedad de equipartición asintótica establece esencialmente que este pico es infinitamente agudo, con una caída infinita en ambos lados. Es decir, dado el conjunto de todas las posibles cadenas infinitamente largas de H y T que ocurren en el proceso de Bernoulli, este conjunto se divide en dos: las cadenas que ocurren con probabilidad 1 y las que ocurren con probabilidad 0. Esta partición se conoce como la ley de Kolmogorov 0-1 .

El tamaño de este conjunto también es interesante y se puede determinar explícitamente: su logaritmo es exactamente la entropía del proceso de Bernoulli. Una vez más, considere el conjunto de todas las cuerdas de longitud n . El tamaño de este conjunto es . De estos, solo un cierto subconjunto es probable; el tamaño de este conjunto es para . Al usar la aproximación de Stirling, poniéndola en la expresión para P ( k , n ), resolviendo para la ubicación y el ancho del pico y finalmente tomando , se encuentra que ${\displaystyle 2^{n}}$ ${\displaystyle 2^{nH}}$ ${\displaystyle H\leq 1}$ ${\displaystyle n\to \infty }$

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

Este valor es la entropía de Bernoulli de un proceso de Bernoulli. Aquí, H representa la entropía; no debe confundirse con el mismo símbolo H que representa las cabezas .

John von Neumann planteó una pregunta sobre el proceso de Bernoulli en relación con la posibilidad de que un proceso dado sea isomorfo a otro, en el sentido del isomorfismo de los sistemas dinámicos . La pregunta desafió el análisis durante mucho tiempo, pero finalmente fue respondida por completo con el teorema de isomorfismo de Ornstein . Este avance resultó en la comprensión de que el proceso de Bernoulli es único y universal ; en cierto sentido, es el proceso más aleatorio posible; nada es "más" aleatorio que el proceso de Bernoulli (aunque hay que tener cuidado con esta afirmación informal; ciertamente, los sistemas que se mezclan son, en cierto sentido, "más fuertes" que el proceso de Bernoulli, que es meramente ergódico pero no mixto. Sin embargo, tales procesos no consisten en variables aleatorias independientes: de hecho, muchos sistemas puramente deterministas, no aleatorios, pueden ser mixtos).

Sistemas dinámicos

El proceso de Bernoulli también puede entenderse como un sistema dinámico , como un ejemplo de un sistema ergódico y, específicamente, un sistema dinámico que preserva la medida , de varias maneras diferentes. Una de ellas es como un espacio de desplazamiento y la otra como un odómetro . Estas se analizan a continuación.

Cambio de Bernoulli

Una forma de crear un sistema dinámico a partir del proceso de Bernoulli es como un espacio de desplazamiento . Existe una simetría de traslación natural en el espacio del producto dada por el operador de desplazamiento. ${\displaystyle \Omega =2^{\mathbb {N} }}$

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

La medida de Bernoulli, definida anteriormente, es invariante a la traslación; es decir, dado cualquier conjunto de cilindros , se tiene ${\displaystyle \sigma \in {\mathcal {B}}}$

${\displaystyle P(T^{-1}(\sigma ))=P(\sigma )}$

y por lo tanto la medida de Bernoulli es una medida de Haar ; es una medida invariante en el espacio del producto.

En lugar de la medida de probabilidad , considere una función arbitraria . ${\displaystyle P:{\mathcal {B}}\to \mathbb {R} }$ ${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$

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

definida por es nuevamente alguna función Por lo tanto, la función induce otra función en el espacio de todas las funciones Es decir, dada alguna , se define ${\displaystyle \left(f\circ T^{-1}\right)(\sigma )=f(T^{-1}(\sigma ))}$ ${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$ ${\displaystyle 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 función es un operador lineal , como (obviamente) se tiene y para funciones y constantes . Este operador lineal se llama operador de transferencia u operador de Ruelle–Frobenius–Perron . Este operador tiene un espectro , es decir, una colección de funciones propias y valores propios correspondientes. El valor propio más grande es el valor propio de Frobenius–Perron y, en este caso, es 1. El vector propio asociado es la medida invariante: en este caso, es la medida de Bernoulli. Es decir, ${\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)}$ ${\displaystyle f,g}$ ${\displaystyle a}$ ${\displaystyle {\mathcal {L}}_{T}(P)=P.}$

Si uno se limita a actuar sobre polinomios, entonces las funciones propias son (curiosamente) ¡los polinomios de Bernoulli ! ^{[3] [4]} Esta coincidencia de nombres presumiblemente no era conocida por Bernoulli. ${\displaystyle {\mathcal {L}}_{T}}$

El mapa 2x mod 1

El mapa T  : [0,1) → [0,1), conserva la medida de Lebesgue . ${\displaystyle x\mapsto 2x{\bmod {1}}}$

Lo anterior se puede hacer más preciso. Dada una cadena infinita de dígitos binarios, escriba ${\displaystyle b_{0},b_{1},\cdots }$

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

El resultado es un número real en el intervalo unitario . El desplazamiento induce un homomorfismo , también llamado , en el intervalo unitario. Como se puede ver, este mapa se llama transformación diádica ; para la secuencia doblemente infinita de bits, el homomorfismo inducido es el mapa de Baker . ${\displaystyle y}$ ${\displaystyle 0\leq y\leq 1.}$ ${\displaystyle T}$ ${\displaystyle 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} },}$

Consideremos ahora el espacio de funciones en . Dado que se puede encontrar que ${\displaystyle y}$ ${\displaystyle f(y)}$

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

Restringiendo la acción del operador a funciones que son polinomios, se encuentra que tiene un espectro discreto dado por ${\displaystyle {\mathcal {L}}_{T}}$

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

donde son los polinomios de Bernoulli . En efecto, los polinomios de Bernoulli obedecen a la identidad ${\displaystyle 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)}$

El conjunto de Cantor

Nótese que la suma

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

da la función de Cantor , tal como se define convencionalmente. Esta es una de las razones por las que el conjunto a veces se denomina conjunto de Cantor . ${\displaystyle \{H,T\}^{\mathbb {N} }}$

Cuentakilómetros

Otra forma de crear un sistema dinámico es definir un odómetro . De manera informal, esto es exactamente lo que parece: simplemente "agrega uno" a la primera posición y deja que el odómetro "gire" utilizando bits de acarreo a medida que el odómetro gira. Esto no es nada más que una adición en base dos en el conjunto de cadenas infinitas. Dado que la adición forma un grupo (matemáticas) , y al proceso de Bernoulli ya se le dio una topología, arriba, esto proporciona un ejemplo simple de un grupo topológico .

En este caso, la transformación viene dada por ${\displaystyle 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).}$

Deja la medida de Bernoulli invariante solo para el caso especial de (la "moneda justa"); de lo contrario, no. Por lo tanto, es un sistema dinámico que preserva la medida en este caso; de lo contrario, es simplemente un sistema conservativo . ${\displaystyle p=1/2}$ ${\displaystyle T}$

Secuencia de Bernoulli

El término secuencia de Bernoulli se suele utilizar de manera informal para referirse a la realización de un proceso de Bernoulli. Sin embargo, el término tiene una definición formal completamente diferente, como se indica a continuación.

Supongamos un proceso de Bernoulli definido formalmente como una única variable aleatoria (véase la sección anterior). Para cada secuencia infinita x de lanzamientos de moneda, existe una secuencia de números enteros

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

llamada secuencia de Bernoulli ^{[ se necesita verificación ]} asociada con el proceso de Bernoulli. Por ejemplo, si x representa una secuencia de lanzamientos de moneda, entonces la secuencia de Bernoulli asociada es la lista de números naturales o puntos de tiempo para los cuales el resultado del lanzamiento de moneda es cara .

Así definida, una secuencia de Bernoulli es también un subconjunto aleatorio del conjunto índice, los números naturales . ${\displaystyle \mathbb {Z} ^{x}}$ ${\displaystyle \mathbb {N} }$

Casi todas las secuencias de Bernoulli son secuencias ergódicas . ^{[ verificación necesaria ]} ${\displaystyle \mathbb {Z} ^{x}}$

Extracción de aleatoriedad

De cualquier proceso de Bernoulli se puede derivar un proceso de Bernoulli con p  = 1/2 mediante el extractor de von Neumann , el primer extractor de aleatoriedad , que en realidad extrae aleatoriedad uniforme.

Extractor básico de von Neumann

Representar el proceso observado como una secuencia de ceros y unos, o bits, y agrupar ese flujo de entrada en pares no superpuestos de bits sucesivos, como (11)(00)(10)... . Luego, para cada par,

• si los bits son iguales, descartar;
• Si los bits no son iguales, muestra el primer bit.

Esta tabla resume el cálculo.

Por ejemplo, un flujo de entrada de ocho bits 10011011 se agruparía en pares como (10)(01)(10)(11) . Luego, según la tabla anterior, estos pares se traducen en la salida del procedimiento: (1)(0)(1) (= 101 ).

En el flujo de salida, 0 y 1 tienen la misma probabilidad, como 10 y 01 tienen la misma probabilidad en el original, y ambos tienen una probabilidad p (1− p ) = (1− p ) p . Esta extracción de aleatoriedad uniforme no requiere que los ensayos de entrada sean independientes, solo no correlacionados . En términos más generales, funciona para cualquier secuencia intercambiable de bits: todas las secuencias que son reordenamientos finitos tienen la misma probabilidad.

El extractor de von Neumann utiliza dos bits de entrada para producir cero o un bit de salida, por lo que la salida es más corta que la entrada por un factor de al menos 2. En promedio, el cálculo descarta la proporción p ²  + (1 −  p ) ² de los pares de entrada (00 y 11), que es cercana a uno cuando p es cercano a cero o uno, y se minimiza en 1/4 cuando p  = 1/2 para el proceso original (en cuyo caso el flujo de salida es 1/4 de la longitud del flujo de entrada en promedio).

Pseudocódigo de operación principal de Von Neumann (clásico) :

si (Bit1 ≠ Bit2) { salida(Bit1)}

Extractor de von Neumann iterado

Esta disminución de la eficiencia, o el desperdicio de aleatoriedad presente en el flujo de entrada, se puede mitigar iterando el algoritmo sobre los datos de entrada. De esta manera, se puede lograr que la salida sea "arbitrariamente cercana al límite de entropía". ^[5]

La versión iterada del algoritmo de von Neumann, también conocido como estrategia multinivel avanzada (AMLS), ^[6] fue introducido por Yuval Peres en 1992. ^[5] Funciona de forma recursiva, reciclando la "aleatoriedad desperdiciada" de dos fuentes: la secuencia de descarte-no descarte y los valores de los pares descartados (0 para 00 y 1 para 11). Se basa en el hecho de que, dada la secuencia ya generada, ambas fuentes siguen siendo secuencias de bits intercambiables y, por lo tanto, elegibles para otra ronda de extracción. Si bien dicha generación de secuencias adicionales se puede iterar infinitamente para extraer toda la entropía disponible, se requiere una cantidad infinita de recursos computacionales, por lo tanto, el número de iteraciones generalmente se fija en un valor bajo; este valor se fija de antemano o se calcula en tiempo de ejecución.

Más concretamente, en una secuencia de entrada, el algoritmo consume los bits de entrada en pares, generando una salida junto con dos nuevas secuencias, () da la notación en papel AMLS:

(Si la longitud de la entrada es impar, el último bit se descarta por completo). Luego, el algoritmo se aplica recursivamente a cada una de las dos nuevas secuencias, hasta que la entrada esté vacía.

Ejemplo: El flujo de entrada del documento AMLS, 11001011101110, que utiliza 1 para H y 0 para T, se procesa de esta manera:

A partir del paso 1, la entrada es una concatenación de la secuencia 2 y la secuencia 1 del paso anterior (el orden es arbitrario pero debe ser fijo). La salida final es ()()(1)()(1)(1)(1)()()(0)(0)()(0)(1)(1)()(1) (= 1111000111 ), por lo que a partir de 14 bits de entrada se generaron 10 bits de salida, en lugar de 3 bits a través del algoritmo de von Neumann solo. La salida constante de exactamente 2 bits por ronda por par de bits (en comparación con una variable de ninguno a 1 bit en VN clásica) también permite implementaciones de tiempo constante que son resistentes a ataques de tiempo .

Pseudocódigo de operación principal de Von Neumann–Peres (iterado):

si (Bit1 ≠ Bit2) { salida(1, Secuencia1) salida(Bit1)} demás { salida(0, secuencia1) salida(Bit1, Secuencia2)}

En 2016 se presentó otro ajuste basado en la observación de que el canal Sequence2 no proporciona mucho rendimiento y una implementación de hardware con un número finito de niveles puede beneficiarse al descartarlo antes a cambio de procesar más niveles de Sequence1. ^[7]

Referencias

1. Dekking, FM; Kraaikamp, ​​C.; Lopuhaä, HP; Meester, LE (2005). Una introducción moderna a la probabilidad y la estadística . págs. 45–46. ISBN 9781852338961.
2. Klenke, Achim (2006). Teoría de la probabilidad . Springer-Verlag. ISBN 978-1-84800-047-6.
3. Pierre Gaspard, " Mapas unidimensionales r -ádicos y la fórmula de suma de Euler", Journal of Physics A , 25 (carta) L483-L485 (1992).
4. Dean J. Driebe, Mapas completamente caóticos y simetría temporal rota, (1999) Kluwer Academic Publishers, Dordrecht, Países Bajos ISBN 0-7923-5564-4 
5. Peres, Yuval (marzo de 1992). "Iteración del procedimiento de von Neumann para extraer bits aleatorios". Anales de estadística . 20 (1): 590–597. doi : 10.1214/aos/1176348543 .
6. "Lanzar una moneda sesgada" (PDF) . eecs.harvard.edu. Archivado (PDF) desde el original el 2010-03-31 . Consultado el 2018-07-28 .
7. Rožić, Vladimir; Yang, Bohan; Dehaene, Wim; Verbauwhede, Ingrid (3–5 de mayo de 2016). Iteración del posprocesamiento de Von Neumann bajo restricciones de hardware (PDF) . Simposio internacional IEEE 2016 sobre seguridad y confianza orientadas al hardware (HOST). Maclean, VA, EE. UU. doi :10.1109/HST.2016.7495553. Archivado (PDF) desde el original el 12 de febrero de 2019.

Lectura adicional

• Carl W. Helstrom, Probabilidad y procesos estocásticos para ingenieros , (1984) Macmillan Publishing Company, Nueva York ISBN 0-02-353560-1 . 

Enlaces externos

• Uso de un diagrama de árbol binario para describir un proceso de Bernoulli