proceso de Bernoulli

Los dos valores posibles de cada X _i se suelen denominar "éxito" y "fracaso". Por lo tanto, cuando se expresa como un número 0 o 1, el resultado puede denominarse 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 X _i pueden denominarse ensayos de Bernoulli con parámetro p.

En muchas aplicaciones, transcurre tiempo entre ensayos a medida que aumenta el índice i. En efecto, los ensayos X ₁ , X ₂ , ... X _i , ... ocurren en "momentos" 1, 2, ..., i , .... Sin embargo, ese transcurso del tiempo y las nociones asociadas de "pasado" y "futuro" no son necesarias. 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 solo dos resultados posibles, a menudo denominados "éxito" y "fracaso", generalmente codificados como 1 y 0, puede modelarse como una distribución de Bernoulli . ^{[ 1 ]} Varias variables aleatorias y distribuciones de probabilidad, además de las de Bernoulli, pueden derivarse 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 fallos necesarios para obtener r éxitos, que tiene una distribución binomial negativa NB( r , p ). 
• El número de fallos 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 .

Consideremos el producto directo infinitamente numerable de copias de${\displaystyle 2=\{H,T\}}$Es común examinar el conjunto unilateral${\displaystyle \Omega =2^{\mathbb {N} }=\{H,T\}^{\mathbb {N} }}$o el conjunto de dos caras${\displaystyle \Omega =2^{\mathbb {Z} }}$Existe una topología natural en este espacio, llamada topología 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), y el resto de la secuencia (infinitamente larga) se considera "indiferente". Estos conjuntos de secuencias finitas se denominan conjuntos cilíndricos en la topología producto. El conjunto de todas estas cadenas forma un álgebra sigma , específicamente, un álgebra de Borel . Esta álgebra se escribe comúnmente como${\displaystyle (\Omega,{\mathcal {B}})}$donde los elementos de${\displaystyle {\mathcal {B}}}$son las secuencias de longitud finita de lanzamientos de monedas (los conjuntos de cilindros).

Si las probabilidades de obtener cara o cruz están dadas por las probabilidades${\displaystyle \{p,1-p\}}$, entonces se puede definir una medida natural en el espacio producto, dada por${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$(o por${\displaystyle P=\{p,1-p\}^{\mathbb {Z} }}$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 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${\displaystyle [\omega _{1},\omega _{2},\cdots \omega _{n}]}$a veces${\displaystyle 1,2,\cdots ,n}$, la probabilidad de observar esta secuencia particular viene dada por

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

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 varias notaciones diferentes 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)^{nk}}$

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

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

Para concluir la definición formal, un proceso de Bernoulli viene dado por la tripleta de probabilidad.${\displaystyle (\Omega,{\mathcal {B}},P)}$, según se define anteriormente.

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 producto.${\displaystyle \Omega =2^{\mathbb {N} }}$proporcionado por el operador de turno

${\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${\displaystyle \sigma \in {\mathcal {B}}}$, uno tiene

${\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 producto.

En lugar de la medida de probabilidad${\displaystyle P:{\mathcal {B}}\to \mathbb {R} }$Consideremos en cambio alguna función arbitraria${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$El impulso hacia adelante

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

definido por${\displaystyle \left(f\circ T^{-1}\right)(\sigma )=f(T^{-1}(\sigma ))}$es de nuevo alguna función${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$Por lo tanto, el mapa${\displaystyle T}$induce otro mapa${\displaystyle {\mathcal {L}}_{T}}$en el espacio de todas las funciones${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$Es decir, dado que algunos${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$, uno define

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

El mapa${\displaystyle {\mathcal {L}}_{T}}$es un operador lineal , ya que (obviamente) se tiene${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$y${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$para funciones${\displaystyle f,g}$y constante${\displaystyle a}$Este operador lineal se denomina operador de transferencia u operador de Ruelle-Frobenius-Perron . Este operador tiene un espectro , es decir, una colección de autofunciones y autovalores correspondientes. El autovalor más grande es el autovalor de Frobenius-Perron , y en este caso, es 1. El autovector asociado es la medida invariante: en este caso, es la medida de Bernoulli. Es decir,${\displaystyle {\mathcal {L}}_{T}(P)=P.}$

Si uno restringe${\displaystyle {\mathcal {L}}_{T}}$para actuar sobre polinomios, entonces las funciones propias son (curiosamente) los polinomios de Bernoulli ! ^{[ 3 ] [ 4 ]} Es de suponer que Bernoulli desconocía esta coincidencia de nombres.

Lo anterior se puede precisar aún más. Dada una cadena infinita de dígitos binarios${\displaystyle b_{0},b_{1},\cdots }$escribir

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

El resultado${\displaystyle y}$es un número real en el intervalo unitario${\displaystyle 0\leq y\leq 1.}$El cambio${\displaystyle T}$induce un homomorfismo , también llamado${\displaystyle T}$, en el intervalo unitario. Dado que${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots ),}$uno puede ver que${\displaystyle T(y)=2y{\bmod {1}}.}$ Este mapa se denomina transformación diádica ; para la secuencia doblemente infinita de bits.${\displaystyle \Omega =2^{\mathbb {Z} },}$El homomorfismo inducido es el mapa de Baker .

Consideremos ahora el espacio de funciones en${\displaystyle y}$Dados algunos${\displaystyle f(y)}$uno puede encontrar que

${\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)}$

Restringir la acción del operador${\displaystyle {\mathcal {L}}_{T}}$Para funciones que están sobre polinomios, se encuentra que tiene un espectro discreto dado por

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

donde el${\displaystyle B_{n}}$son los polinomios de Bernoulli . En efecto, los polinomios de Bernoulli cumplen la identidad.

${\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)}$

Tenga en cuenta 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 razón por la que el conjunto${\displaystyle \{H,T\}^{\mathbb {N} }}$A veces se le llama el conjunto de Cantor .

Otra forma de crear un sistema dinámico es definir un odómetro . De manera informal, es exactamente lo que parece: simplemente "sumar uno" a la primera posición y dejar que el odómetro "reinicie" usando bits de acarreo a medida que avanza. Esto no es más que una suma en base dos sobre el conjunto de cadenas infinitas. Dado que la suma forma un grupo , y el proceso de Bernoulli ya recibió una topología, esto proporciona un ejemplo simple de un grupo topológico .

En este caso, la transformación${\displaystyle T}$es dado por

${\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${\displaystyle p=1/2}$(la "moneda justa"); de lo contrario, no. Por lo tanto,${\displaystyle T}$es un sistema dinámico que preserva medidas en este caso, de lo contrario, es simplemente un sistema conservador .

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

• Si los bits son iguales, descártalos;
• Si los bits no son iguales, imprime el primer bit.

Esta tabla resume el cálculo.

Por ejemplo, una secuencia 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 la secuencia de salida, 0 y 1 tienen la misma probabilidad, al igual que 10 y 01 en la secuencia original, ambas con probabilidad p (1− p )  =  (1− p ) p . Esta extracción de aleatoriedad uniforme no requiere que los ensayos de entrada sean independientes, solo que no estén correlacionados . En términos más generales, funciona para cualquier secuencia de bits intercambiable: todas las secuencias que son reordenamientos finitos tienen la misma probabilidad.

El extractor 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 una proporción p ²  +  (1  − p ) ² de los pares de entrada (00 y 11), que es cercana a uno cuando p es cercana a cero o uno, y se minimiza en 1/4 cuando p = 1/2 para el proceso original (en cuyo caso la secuencia de salida es 1/4 de la longitud de la secuencia de entrada en promedio).   

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

si (Bit1 ≠ Bit2) { Salida (bit 1) } 

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

La versión iterada del algoritmo de von Neumann, también conocida como estrategia multinivel avanzada (AMLS), ^{[ 6 ]} fue introducida por Yuval Peres en 1992. ^{[ 5 ]} Funciona recursivamente, 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, aptas para otra ronda de extracción. Si bien dicha generación de secuencias adicionales puede iterarse infinitamente para extraer toda la entropía disponible, se requiere una cantidad infinita de recursos computacionales; por lo tanto, el número de iteraciones suele fijarse a un valor bajo, ya sea fijado de antemano o calculado 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 del artículo AMLS:

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

Ejemplo: La secuencia de entrada del artículo de AMLS, 11001011101110 , donde 1 representa H y 0 representa 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 de 14 bits de entrada se generaron 10 bits de salida, en comparación con los 3 bits 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ásico) también permite implementaciones de tiempo constante que son resistentes a ataques de tiempo .

Pseudocódigo de la operación principal de Von Neumann-Peres (iterada):

si (Bit1 ≠ Bit2) { salida(1, Secuencia1) Salida (bit 1) } 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 de descartarlo antes a cambio de procesar más niveles de Sequence1. ^{[ 7 ]}