De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

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 están idénticamente distribuidas e independiente . Prosaicamente, un proceso de Bernoulli es un lanzamiento repetido de una moneda , posiblemente con una moneda injusta (pero con una injusticia constante). Cada variable X i en la secuencia está asociada con un ensayo de Bernoullio experimentar. Todos tienen la misma distribución de Bernoulli . Mucho 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 [ editar ]

Un proceso de Bernoulli es una secuencia finita o infinita de variables aleatorias independientes X 1X 2X 3 , ..., 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 sea 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 juicios 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. (Si p es desconocido, sin embargo, 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 a todo el proceso, la propiedad de nuevo comienzo.

Interpretación [ editar ]

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 se puede llamar 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 X i pueden denominarse ensayos de Bernoulli con el parámetro p.

En muchas aplicaciones, el tiempo pasa entre ensayos, a medida que aumenta el índice i. En efecto, los ensayos X 1X 2 , ...  X i , ... ocurren 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. Más 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 casos infinitos.

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

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

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

Definición formal [ editar ]

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

Álgebra de Borel [ editar ]

Considere el producto directo infinito contable de copias de . Es común examinar el conjunto de un solo lado o el conjunto de dos lados . Existe una topología natural en este espacio, denominada topología de producto . Los conjuntos en esta topología son secuencias finitas de lanzamientos de monedas, es decir, cadenas de H y T de longitud finita ( H significa cara y T significa cruz), y el resto de la secuencia (infinitamente larga) se toma 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 se escribe comúnmente como donde los elementos de son las secuencias de longitud finita de lanzamientos de monedas (los conjuntos de cilindros).

Medida de Bernoulli [ editar ]

Si las probabilidades de que salga cara o cruz están dadas por las probabilidades , entonces se puede definir una medida natural en el espacio del producto, dada por (o por para el proceso de dos caras). 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

y .

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

Dado un juego de cilindros, es decir, una secuencia específica de lanzamiento de una moneda resulta a veces , la probabilidad de observar esta secuencia particular viene dada por

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; uno común es escribir

donde cada uno es un binario de valor variable aleatoria con en soporte Iverson notación, es decir, ya sea si o si . Esta probabilidad se denomina comúnmente medida de Bernoulli . [3]

Tenga en cuenta que la probabilidad de cualquier secuencia infinitamente larga de lanzamientos de monedas es exactamente cero; esto se debe a que , para cualquiera . 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 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 la probabilidad triple , como se definió anteriormente.

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

Asumamos el proceso canónico con representado por y representado por . La ley de los números grandes establece que, en 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 las cabezas giratorias , que se supone que está representado por 1, viene dado por . De hecho, uno tiene

para cualquier variable aleatoria dada 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 monedas. 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 apariciones de H viene dado por el coeficiente binomial

Si la probabilidad de voltear caras viene dada por p , entonces la probabilidad total de ver una cadena de longitud n con k caras es

donde . 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 para una secuencia suficientemente larga de lanzamientos de monedas, es decir, para el límite . En este caso, se puede hacer uso de la aproximación de Stirling al factorial y escribir

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 . Dicho de manera informal, uno observa que, sí, en muchos lanzamientos de monedas, se observará H exactamente una p fracción del tiempo, y que esto se corresponde exactamente con el pico de la Gauss. La propiedad de equipartición asintótica esencialmente establece 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 Tque 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 divisió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 cadenas de longitud n . El tamaño de este conjunto es . De estos, es probable que sólo un cierto subconjunto; el tamaño de este conjunto es para . Al usar la aproximación de Stirling, poniéndola en la expresión de P ( k , n ), resolviendo la ubicación y el ancho del pico, y finalmente tomando uno, se encuentra que

Este valor es la entropía de Bernoulli de un proceso de Bernoulli. Aquí, H significa 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 alguna vez 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 fue finalmente y completamente respondida 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 uno debe tener cuidado con esta declaración informal; ciertamente, los sistemas que están mezclandoson, en cierto sentido, "más fuertes" que el proceso de Bernoulli, que es simplemente ergódico pero no mezcla. Sin embargo, tales procesos no consisten en variables aleatorias independientes: de hecho, muchos sistemas puramente deterministas y no aleatorios pueden mezclarse).

Sistemas dinámicos [ editar ]

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 , en una de varias formas diferentes. Una forma es como un espacio de turno y la otra es como un odómetro . Estos se revisan a continuación.

Cambio de Bernoulli [ editar ]

Una forma de crear un sistema dinámico a partir del proceso de Bernoulli es como un espacio de cambio . Existe una simetría de traslación natural en el espacio del producto dada por el operador de turno

La medida de Bernoulli, definida anteriormente, es invariante en la traducción; es decir, dado cualquier juego de cilindros , uno tiene

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 , considere en cambio alguna función arbitraria . El empujón

definido por es de nuevo alguna función Por lo tanto, el mapa induce otro mapa en el espacio de todas las funciones Es decir, dado algunos , uno define

El mapa es un operador lineal , como (obviamente) uno tiene y para funciones y constante . Este operador lineal se denomina operador de transferencia o 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,

Si uno se limita a actuar sobre polinomios, entonces las funciones propias son (curiosamente) ¡los polinomios de Bernoulli ! [4] [5] Esta coincidencia de nombres presumiblemente no era conocida por Bernoulli.

El mapa 2x mod 1 [ editar ]

El mapa T  : [0,1) → [0,1), conserva la medida de Lebesgue .

Lo anterior se puede hacer más preciso. Dada una cadena infinita de dígitos binarios, escriba

El resultado es un número real en el intervalo unitario. El desplazamiento induce un homomorfismo , también llamado , en el intervalo unitario. Dado que uno puede ver fácilmente que este mapa se llama transformación diádica ; para la secuencia doblemente infinita de bits, el homomorfismo inducido es el mapa de Baker .

Considere ahora el espacio de funciones en . Dado que alguien puede encontrar fácilmente que

Restringiendo la acción del operador a funciones que están en polinomios, se encuentra que tiene un espectro discreto dado por

donde son los polinomios de Bernoulli . De hecho, los polinomios de Bernoulli obedecen a la identidad

El conjunto de Cantor [ editar ]

Tenga en cuenta que la suma

da la función de Cantor , como se define convencionalmente. Ésta es una de las razones por las que el conjunto a veces se denomina conjunto de Cantor .

Odómetro [ editar ]

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

En este caso, la transformación viene dada por

Deja la medida de Bernoulli invariante sólo para el caso especial de (la "moneda justa"); de otra forma no. Por tanto, es una medida que preserva el sistema dinámico en este caso, de lo contrario, es meramente un sistema conservador .

Secuencia de Bernoulli [ editar ]

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 a la que se da a continuación.

Suponga un proceso de Bernoulli definido formalmente como una única variable aleatoria (consulte la sección anterior). Por cada secuencia infinita x de lanzamientos de moneda, hay una secuencia de enteros

llamada secuencia de Bernoulli [ verificación necesaria ] asociada con el proceso de Bernoulli. Por ejemplo, si x representa una secuencia de lanzamientos de la moneda, a continuación, la secuencia de Bernoulli asociado es la lista de números naturales o puntos de tiempo para el que el sorteo resultado es cabezas .

Así definida, una secuencia de Bernoulli es también un subconjunto aleatorio del conjunto de índices, los números naturales .

Casi todas las secuencias de Bernoulli son secuencias ergódicas . [ verificación necesaria ]

Extracción de aleatoriedad [ editar ]

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 primer extractor de aleatoriedad , que en realidad extrae aleatoriedad uniforme.

Extractor básico de von Neumann [ editar ]

Represente el proceso observado como una secuencia de ceros y unos, o bits, y agrupe 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, envíe 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, de acuerdo con la tabla anterior, estos pares se traducen en 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, y ambos tienen 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 utiliza dos bits de entrada para producir cero o uno de salida, por lo que la salida es más corta que la entrada en un factor de al menos 2. En promedio, el cálculo descarta la proporción p 2  + (1 -  p ) 2 de la 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 flujo de entrada en promedio).

Von Neumann (clásica) principal operación pseudocódigo :

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

Extractor de von Neumann iterado [ editar ]

Esta disminución en la eficiencia, o desperdicio de aleatoriedad presente en el flujo de entrada, puede mitigarse iterando el algoritmo sobre los datos de entrada. De esta manera, se puede hacer que la salida esté "arbitrariamente cerca del límite de entropía". [6]

La versión iterada del algoritmo de von Neumann, también conocida como estrategia avanzada multinivel (AMLS), [7] fue introducida por Yuval Peres en 1992. [6]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). 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, son 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 salida junto con dos nuevas secuencias:

(Si la longitud de la entrada es impar, el último bit se descarta por completo). Luego, el algoritmo se aplica de forma recursiva 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:


A partir del paso de 1 en adelante, 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, en contraposición a los tres bits a través 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 el VN clásico) también permite implementaciones de tiempo constante que son resistentes a los ataques de tiempo .

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

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

Se presentó otro ajuste 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. [8]

Referencias [ editar ]

  1. ^ Una introducción moderna a la probabilidad y la estadística . págs. 45–46. ISBN 9781852338961.
  2. ^ Una introducción moderna a la probabilidad y la estadística . págs. 45–46. ISBN 9781852338961.
  3. ^ Klenke, Achim (2006). Teoría de la probabilidad . Springer-Verlag. ISBN 978-1-84800-047-6.
  4. ^ Pierre Gaspard, "mapas unidimensionales r -adic y la fórmula de suma de Euler", Journal of Physics A , 25 (carta) L483-L485 (1992).
  5. ^ Dean J. Driebe, Mapas completamente caóticos y simetría del tiempo roto, (1999) Editores académicos Kluwer, Dordrecht Países Bajos ISBN 0-7923-5564-4 
  6. ↑ a b Peres, Yuval (marzo de 1992). "Iterando el procedimiento de Von Neumann para extraer bits aleatorios" (PDF) . The Annals of Statistics . 20 (1): 590–597. doi : 10.1214 / aos / 1176348543 . Archivado desde el original (PDF) el 18 de mayo de 2013 . Consultado el 30 de mayo de 2013 .
  7. ^ "Lanzar una moneda sesgada" (PDF) . eecs.harvard.edu . Consultado el 28 de julio de 2018 .
  8. Rožić, Vladimir; Yang, Bohan; Dehaene, Wim; Verbauwhede, Ingrid (3-5 de mayo de 2016). Iterando el posprocesamiento de Von Neumann bajo restricciones de hardware (PDF) . 2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST). Maclean, VA, Estados Unidos. doi : 10.1109 / HST.2016.7495553 \ .

Lectura adicional [ editar ]

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

Enlaces externos [ editar ]

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