Proceso de Bernoulli

Compartir Imprimir Citar

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. El componente Variables de Bernoulli X _i son idénticamente distribuidos e independientes. Prosaicamente, un proceso de Bernoulli es un lanzamiento de moneda repetido, posiblemente con una moneda injusta (pero con una injusticia constante). Cada variable X _ien la secuencia está asociado 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 de un dado de seis caras); esta generalización se conoce como el esquema de Bernoulli.

El problema de determinar el proceso, dada solo una muestra limitada de ensayos de Bernoulli, puede llamarse el problema de verificar si una moneda es justa.

Definición

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

para cada i, el valor de X _i es 0 o 1;
para todos los valores de i, la probabilidad p de que X _i = 1 es la misma.

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 proporcionan información sobre los resultados futuros. (Sin embargo, si se desconoce p, el pasado informa indirectamente sobre el futuro, 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 a menudo se denominan "éxito" y "fracaso". Por lo tanto, cuando se expresa como un número 0 o 1, el resultado puede llamarse 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 ensayos, a medida que aumenta el índice i. En efecto, los ensayos X ₁, X ₂,... X _i,... suceden en "puntos en el tiempo" 1, 2,..., i,.... Ese paso del tiempo y las nociones asociadas de Sin embargo, "pasado" y "futuro" no son necesarios. Generalmente, 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 infinitos casos.

Un experimento con solo dos resultados posibles, a menudo denominado "éxito" y "fracaso", generalmente codificado como 1 y 0, se puede modelar como una distribución de Bernoulli. Varias variables aleatorias y distribuciones de probabilidad además de Bernoulli se pueden derivar del proceso de Bernoulli:

El número de éxitos en los primeros n intentos, que tiene una distribución binomial B(n, p)
El número de fallas necesarias para obtener r éxitos, que tiene una distribución binomial negativa NB(r, p)
El número de fallas necesarias 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.

Definicion 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 estado para un valor individual se denota por $2={H,T}.$

álgebra de borel

Considere el producto directo contablemente infinito de copias de $2={H,T}$ . Es común examinar el conjunto de una cara $Omega =2^{{mathbb {N}}}={H,T}^{{mathbb {N}}}$ o el conjunto de dos caras $Omega =2^{{mathbb {Z}}}$ . Hay una topología natural en este espacio, llamada topología del producto. Los conjuntos en esta topología son secuencias finitas de lanzamientos de monedas, 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". cuidado". Estos conjuntos de secuencias finitas se denominan conjuntos de cilindros en la topología del producto. El conjunto de todas esas cadenas forma un álgebra sigma, específicamente, un álgebra de Borel. Esta álgebra entonces se escribe comúnmente como ${displaystyle (Omega,{mathcal {B}})}$ donde los elementos de ${ matemáticas {B}}$ son las secuencias de longitud finita de lanzamientos de monedas (los juegos de cilindros).

Medida de Bernoulli

Si las posibilidades de sacar cara o cruz están dadas por las probabilidades ${p,1-p}$ , entonces se puede definir una medida natural en el espacio del producto, dada por $P={p,1-p}^{{mathbb {N}}}$ (o por $P={p,1-p}^{{mathbb {Z}}}$ para el proceso de dos lados). 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 ${ estilo de visualización pX (1) = P (X = 1) = p}$ y ${displaystyle pX(0)=P(X=0)=1-p}$ .

Denotamos esta distribución por Ber(p).

Dado un conjunto de cilindros, es decir, una secuencia específica de resultados de lanzamiento de moneda $[omega _{1},omega _{2},cdots omega _{n}]$ a veces $1,2,cpuntos,n$ , la probabilidad de observar esta secuencia particular está dada por $P([omega _{1},omega _{2},cdots,omega _{n}])=p^{k}(1-p)^{{nk}}$

donde k es el número de veces que aparece H en la secuencia, y n − k es el número de veces que aparece T en la secuencia. Hay varios tipos diferentes de notaciones para lo anterior; uno 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 each $X_{yo}$ es una variable aleatoria de valor binario con una ${displaystyle x_{i}=[omega_{i}=H]}$ notación de paréntesis de Iverson, lo que significa $1$ si ${ estilo de visualización omega _ {i} = H}$ o ${ estilo de visualización 0}$ si ${ estilo de visualización omega _ {i} = T}$ . Esta probabilidad $PAG$ se denomina comúnmente medida de Bernoulli.

Tenga en cuenta que la probabilidad de cualquier secuencia infinitamente larga de lanzamientos de monedas es exactamente cero; esto se debe a que $lim _{{nto infty}}p^{n}=0$ , para cualquier <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ddd9ada1b1951e8892f14b77b1398bda4ee4451e" alt="0leq p. Una probabilidad igual a 1 implica que cualquier sucesión infinita dada tiene medida cero. Sin embargo, todavía se puede decir que algunas clases de secuencias infinitas de lanzamientos de monedas 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 el triple de probabilidad ${displaystyle (Omega,{mathcal {B}},P)}$ , como se definió anteriormente.

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

Supongamos el proceso canónico con $H$ representado por $1$ y $T$ representado por ${ estilo de visualización 0}$ . La ley de los grandes números establece que, en el promedio de la secuencia, es decir, ${displaystyle {bar {X}}_{n}:={frac {1}{n}}sum_{i=1}^{n}X_{i}}$ , se aproximará casi con certeza al valor esperado, es decir, los eventos que no satisfagan este límite tienen probabilidad cero. El valor esperado de voltear cabezas, que se supone representado por 1, viene dado por $pag$ . De hecho, uno tiene ${displaystyle mathbb {E} [X_{i}]=mathbb {P} ([X_{i}=1])=p,}$

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

A menudo, uno está interesado en saber con qué frecuencia observará 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 viene dado por el coeficiente binomial $N(k,n)={n elegir k}={frac {n!}{k!(nk)!}}$

Si la probabilidad de lanzar caras viene 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 elegir k}p^{k}(1-p)^{nk},}$

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

Como podemos ver en la fórmula anterior, si n=1, la distribución binomial se convertirá en una distribución de Bernoulli. Entonces 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 $S_{n}$ para una secuencia suficientemente larga de lanzamientos de monedas, es decir, para el límite $ntoinfty$ . En este caso, se puede hacer uso de la aproximación de Stirling al factorial y escribir $n!={sqrt {2pi n}};n^{n}e^{{-n}}left(1+{mathcal {O}}left({frac {1}{ n}}derecho)derecho)$

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 informalmente, uno nota que, sí, en muchos lanzamientos de moneda, uno 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 nítido, con una caída infinita en cada lado. Es decir, dado el conjunto de todas las posibles cadenas infinitamente largas de H y Tque ocurre 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 puede determinarse explícitamente: su logaritmo es exactamente la entropía del proceso de Bernoulli. Una vez más, considere el conjunto de todas las cadenas de longitud n. El tamaño de este conjunto es $2^{n}$ . De estos, solo un cierto subconjunto es probable; el tamaño de este conjunto es $2^{{nH}}$ para $H leq 1$ . Usando la aproximación de Stirling, poniéndola en la expresión para P (k, n), resolviendo la ubicación y el ancho del pico, y finalmente tomando $ntoinfty$ se encuentra que $H=-plog _{2}p-(1-p)log _{2}(1-p)$

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

John von Neumann planteó una pregunta curiosa sobre el proceso de Bernoulli: ¿es posible que un proceso determinado sea isomorfo a otro, en el sentido del isomorfismo de los sistemas dinámicos? La pregunta desafió durante mucho tiempo el análisis, pero finalmente se respondió por completo con el teorema del 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 procesos puramente deterministas,

Sistemas dinámicos

El proceso de Bernoulli también puede entenderse como un sistema dinámico, como ejemplo de un sistema ergódico y, específicamente, un sistema dinámico que conserva la medida, en una de varias formas diferentes. Una forma es como un espacio de cambio y la otra es como un odómetro. Estos se revisan 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 cambio. Hay una simetría de traslación natural en el espacio del producto ${displaystyle Omega =2^{mathbb {N} }}$ dado por el operador de cambio ${displaystyle T(X_{0},X_{1},X_{2},cdots)=(X_{1},X_{2},cdots)}$

La medida de Bernoulli, definida anteriormente, es invariante traslacional; es decir, dado cualquier conjunto de cilindros ${displaystyle sigma in {mathcal {B}}}$ , se tiene ${displaystyle P(T^{-1}(sigma))=P(sigma)}$

y así 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 ${displaystyle P:{mathcal {B}}to mathbb {R} }$ , considere alguna función arbitraria ${displaystyle f:{mathcal {B}}to mathbb {R} }$ . el impulso ${displaystyle fcirc T^{-1}}$

definido por ${displaystyle left(fcirc 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 $T$ induce otro mapa ${displaystyle {mathcal {L}}_{T}}$ en el espacio de todas las funciones ${displaystyle {mathcal {B}}to mathbb {R}.}$ Es decir, dado algunos ${displaystyle f:{mathcal {B}}to mathbb {R} }$ , uno define ${displaystyle {mathcal {L}}_{T}f=fcirc T^{-1}}$

El mapa ${displaystyle {mathcal {L}}_{T}}$ es un operador lineal, como (obviamente) uno 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 $f, g$ y constantes $un$ . 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}(P)=P.}$

Si uno se limita ${displaystyle {mathcal {L}}_{T}}$ a actuar sobre polinomios, entonces las funciones propias son (curiosamente) ¡los polinomios de Bernoulli! Presumiblemente, Bernoulli no conocía esta coincidencia de nombres.

El mapa 2x mod 1

Lo anterior se puede hacer más preciso. Dada una cadena infinita de dígitos binarios, ${displaystyle b_{0},b_{1},cdots}$ escriba ${displaystyle y=sum _{n=0}^{infty}{frac {b_{n}}{2^{n+1}}}.}$

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

Considere ahora el espacio de funciones en $y$ . Dado $f(y)$ que alguien puede encontrar fácilmente que ${displaystyle left[{mathcal {L}}_{T}fright](y)={frac {1}{2}}fleft({frac {y}{2}} derecha)+{frac {1}{2}}fizquierda({frac {y+1}{2}}derecha)}$

Restringiendo la acción del operador ${displaystyle {mathcal {L}}_{T}}$ a 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 $B_{n}$ son los polinomios de Bernoulli. De hecho, los polinomios de Bernoulli obedecen a 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)}$

El conjunto de Cantor

Tenga en cuenta que la suma ${displaystyle y=sum _{n=0}^{infty }{frac {b_{n}}{3^{n+1}}}}$

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

Cuentakilómetros

Otra forma de crear un sistema dinámico es definir un odómetro. Informalmente, esto es exactamente lo que parece: simplemente "agregue uno" a la primera posición y deje que el odómetro "se desplace" usando bits de acarreo a medida que el odómetro se desplace. Esto no es más que una suma de base dos en el conjunto de cadenas infinitas. Dado que la suma forma un grupo (matemáticas), y el proceso de Bernoulli ya recibió una topología, arriba, esto proporciona un ejemplo simple de un grupo topológico.

En este caso, la transformación $T$ está dada por ${displaystyle Tleft(1,dots,1,0,X_{k+1},X_{k+2},dots right)=left(0,dots,0,1,X_{ k+1},X_{k+2},puntosderecha).}$

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

Secuencia de Bernoulli

El término secuencia de Bernoulli se usa a menudo 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.

Suponga que un proceso de Bernoulli se define formalmente como una sola variable aleatoria (consulte la sección anterior). Por cada secuencia infinita x de lanzamientos de monedas, hay una secuencia de números enteros ${mathbb {Z}}^{x}={nin {mathbb {Z}}:X_{n}(x)=1},$

llamada secuencia de Bernoulli asociada con el proceso de Bernoulli. Por ejemplo, si x representa una secuencia de lanzamientos de monedas, 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 la moneda es cara.

Así definida, una sucesión de Bernoulli ${matemáticas {Z}}^{x}$ es también un subconjunto aleatorio del conjunto índice, los números naturales $matemáticas {N}$ .

Casi todas las secuencias de Bernoulli ${matemáticas {Z}}^{x}$ son secuencias ergódicas.

Extracción de aleatoriedad

A partir de cualquier proceso de Bernoulli, se puede derivar un proceso de Bernoulli con p = 1/2 mediante el extractor de von Neumann, el extractor de aleatoriedad más antiguo, que en realidad extrae aleatoriedad uniforme.

Extractor von Neumann básico

Represente el proceso observado como una secuencia de ceros y unos, o bits, y agrupe ese flujo de entrada en pares de bits sucesivos que no se superpongan, como (11)(00)(10).... Luego, para cada par,

si los bits son iguales, descartar;
si los bits no son iguales, emite el primer bit.

Esta tabla resume el cálculo.

aporte	producción
00	desechar
01	0
10	1
11	desechar

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

En el flujo de salida, 0 y 1 son igualmente probables, ya que 10 y 01 son igualmente probables en el original, ambos 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. De manera más general, funciona para cualquier secuencia intercambiable de bits: todas las secuencias que son reordenamientos finitos son igualmente probables.

El extractor de von Neumann usa dos bits de entrada para producir uno o cero bits 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 está cerca de uno cuando p está cerca de 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 proceso original). 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 desperdicio de aleatoriedad presente en el flujo de entrada, se puede mitigar iterando el algoritmo sobre los datos de entrada. De esta forma, se puede hacer que la salida sea "arbitrariamente cercana al límite de entropía".

La versión iterada del algoritmo de von Neumann, también conocida como estrategia multinivel avanzada (AMLS), fue presentada por Yuval Peres en 1992. 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). Intuitivamente, 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, la cantidad 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:

aporte	producción	nueva secuencia 1	nueva secuencia 2
00	ninguna	0	0
01	0	1	ninguna
10	1	1	ninguna
11	ninguna	0	1

(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 de arriba, 10011011, se procesa de esta manera:

número de paso	aporte	producción	nueva secuencia 1	nueva secuencia 2
0	(10)(01)(10)(11)	(1)(0)(1)()	(1)(1)(1)(0)	()()()(1)
1	(11)(10)	()(1)	(0)(1)	(1)()
1.1	(01)	(0)	(1)	()
1.1.1	1	ninguna	ninguna	ninguna
1.2	1	ninguna	ninguna	ninguna
2	1	ninguna	ninguna	ninguna

A partir del paso 1, la entrada se convierte en la nueva secuencia1 del último paso para avanzar en este proceso. Por lo tanto, la salida es (101)(1)(0)()()() (= 10110), de modo que a partir de los ocho bits de entrada se generaron cinco bits de salida, a diferencia de los tres bits del algoritmo básico anterior. La salida constante de exactamente 2 bits por ronda (en comparación con una variable de 0 a 1 bits en VN clásico) también permite implementaciones de tiempo constante que son resistentes a los 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)
}

Otro ajuste se presentó en 2016, 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.