stringtranslate.com

Secuencia aleatoria

El concepto de secuencia aleatoria es esencial en la teoría de la probabilidad y la estadística . El concepto generalmente se basa en la noción de una secuencia de variables aleatorias y muchas discusiones estadísticas comienzan con las palabras "sea X 1 ,..., X n variables aleatorias independientes...". Sin embargo, como afirmó DH Lehmer en 1951: "Una secuencia aleatoria es una noción vaga... en la que cada término es impredecible para los no iniciados y cuyos dígitos pasan una cierta cantidad de pruebas tradicionales entre los estadísticos". [1]

La teoría de la probabilidad axiomática evita deliberadamente definir una secuencia aleatoria. [2] La teoría de la probabilidad tradicional no establece si una secuencia específica es aleatoria, pero generalmente procede a analizar las propiedades de las variables aleatorias y las secuencias estocásticas asumiendo alguna definición de aleatoriedad. La escuela Bourbaki consideró que la afirmación "consideremos una secuencia aleatoria" era un abuso del lenguaje . [3]

Historia temprana

Émile Borel fue uno de los primeros matemáticos en abordar formalmente la aleatoriedad en 1909. [4] En 1919, Richard von Mises dio la primera definición de aleatoriedad algorítmica , que se inspiró en la ley de los grandes números, aunque utilizó el término colectivo en lugar de secuencia aleatoria. Utilizando el concepto de la imposibilidad de un sistema de juego , von Mises definió una secuencia infinita de ceros y unos como aleatoria si no está sesgada por tener la propiedad de estabilidad de frecuencia, es decir, la frecuencia de ceros tiende a 1/2 y cada subsecuencia que podemos seleccionar de ella mediante un método "adecuado" de selección tampoco está sesgada. [5]

El criterio de selección de subsecuencias impuesto por von Mises es importante, porque aunque 0101010101... no está sesgado, al seleccionar las posiciones impares, obtenemos 000000... que no es aleatorio. Von Mises nunca formalizó totalmente su definición de una regla de selección adecuada para subsecuencias, pero en 1940 Alonzo Church la definió como cualquier función recursiva que, habiendo leído los primeros N elementos de la secuencia, decide si quiere seleccionar el elemento número  N  + 1. Church fue un pionero en el campo de las funciones computables, y la definición que hizo se basó en la Tesis de Church-Turing para la computabilidad. [6] Esta definición a menudo se llama aleatoriedad Mises-Church .

Enfoques modernos

Durante el siglo XX se desarrollaron varios enfoques técnicos para definir secuencias aleatorias y ahora se pueden identificar tres paradigmas distintos. A mediados de la década de 1960, AN Kolmogorov y DW Loveland propusieron de forma independiente una regla de selección más permisiva. [7] [8] En su opinión, la definición de función recursiva de Church era demasiado restrictiva porque leía los elementos en orden. En su lugar, propusieron una regla basada en un proceso parcialmente computable que, después de leer N elementos cualesquiera de la secuencia, decide si quiere seleccionar otro elemento que aún no se ha leído. Esta definición a menudo se denomina estocasticidad de Kolmogorov-Loveland . Pero Alexander Shen consideró que este método era demasiado débil y demostró que existe una secuencia estocástica de Kolmogorov-Loveland que no se ajusta a la noción general de aleatoriedad.

En 1966, Per Martin-Löf introdujo una nueva noción que hoy en día se considera generalmente la noción más satisfactoria de aleatoriedad algorítmica . Su definición original implicaba la teoría de la medida, pero más tarde se demostró que se puede expresar en términos de complejidad de Kolmogorov . La definición de Kolmogorov de una cadena aleatoria era que es aleatoria si no tiene una descripción más corta que ella misma a través de una máquina de Turing universal . [9]

Han surgido tres paradigmas básicos para tratar con secuencias aleatorias: [10]

  • El enfoque de la frecuencia/teoría de la medida . Este enfoque comenzó con el trabajo de Richard von Mises y Alonzo Church. En la década de 1960, Per Martin-Löf se dio cuenta de que los conjuntos que codifican dichas propiedades estocásticas basadas en la frecuencia son un tipo especial de conjuntos de medida cero , y que se puede obtener una definición más general y uniforme considerando todos los conjuntos de medida cero efectivos.
  • El enfoque de la complejidad/compresibilidad . Este paradigma fue defendido por AN Kolmogorov junto con las contribuciones de Leonid Levin y Gregory Chaitin . Para secuencias finitas, Kolmogorov define la aleatoriedad de una cadena binaria de longitud n como la entropía (o complejidad de Kolmogorov ) normalizada por la longitud n . En otras palabras, si la complejidad de Kolmogorov de la cadena es cercana a n , es muy aleatoria; si la complejidad es muy inferior a n , no es tan aleatoria. El concepto dual de aleatoriedad es la compresibilidad: cuanto más aleatoria es una secuencia, menos compresible es, y viceversa.
  • El enfoque de la predictibilidad . Este paradigma se debe a Claus P. Schnorr y utiliza una definición ligeramente diferente de las martingalas constructivas que las martingalas utilizadas en la teoría de la probabilidad tradicional. [11] Schnorr mostró cómo la existencia de una estrategia de apuestas selectivas implicaba la existencia de una regla de selección para una subsecuencia sesgada. Si uno solo requiere una martingala recursiva para tener éxito en una secuencia en lugar de tener éxito de manera constructiva en una secuencia, entonces se obtiene el concepto de aleatoriedad recursiva. [ se necesita más explicación ] Yongge Wang mostró [12] [13] que el concepto de aleatoriedad recursiva es diferente del concepto de aleatoriedad de Schnorr. [ se necesita más explicación ]

En la mayoría de los casos se han demostrado teoremas que relacionan los tres paradigmas (a menudo de equivalencia). [14]

Véase también

Referencias

Notas

  1. ^ "¿Qué se entiende por la palabra aleatorio?" en Matemáticas y sentido común de Philip J. Davis 2006 ISBN  1-56881-270-1 páginas 180-182
  2. ^ Aleatoriedad inevitable en las matemáticas discretas por József Beck 2009 ISBN 0-8218-4756-2 página 44 
  3. ^ Algoritmos: ideas principales y aplicaciones por Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X página 166 
  4. ^ E. Borel, Les probabilites denombrables et leurs apps arithmetique Rend. Circo. Estera. Palermo 27 (1909) 247–271
  5. ^ Laurant Bienvenido "Estocasticidad de Kolmogorov Loveland" en STACS 2007: 24º Simposio Anual sobre Aspectos Teóricos de la Ciencia de la Computación por Wolfgang Thomas ISBN 3-540-70917-7 página 260 
  6. ^ Church, Alonzo (1940). "Sobre el concepto de secuencia aleatoria". Bull. Amer. Math. Soc . 46 (2): 130–136. doi : 10.1090/S0002-9904-1940-07154-X .
  7. ^ AN Kolmogorov, Tres enfoques para la definición cuantitativa de la información , Problemas de información y transmisión, 1(1):1–7, 1965.
  8. ^ DW Loveland, Una nueva interpretación del concepto de secuencia aleatoria de von Mises Z. Math. Logik Grundlagen Matemáticas 12 (1966) 279–294
  9. ^ Introducción a la complejidad de Kolmogorov y sus aplicaciones por Ming Li, PMB Vitányi 1997 0387948686 páginas 149–151
  10. ^ R. Downey, Algunos avances recientes en la aleatoriedad algorítmica en los fundamentos matemáticos de la informática 2004: por Jiří Fiala, Václav Koubek 2004 ISBN 3-540-22823-3 página 44 
  11. ^ Schnorr, CP (1971). "Un enfoque unificado para la definición de una secuencia aleatoria". Teoría de sistemas matemáticos . 5 (3): 246–258. doi :10.1007/bf01694181. S2CID  8931514.
  12. ^ Yongge Wang: Aleatoriedad y complejidad. Tesis doctoral, 1996. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
  13. ^ Wang, Yongge (1999). "Una separación de dos conceptos de aleatoriedad". Information Processing Letters . 69 (3): 115–118. CiteSeerX 10.1.1.46.199 . doi :10.1016/S0020-0190(98)00202-6. 
  14. ^ Wolfgang Merkle, Kolmogorov Loveland Estocasticidad en autómatas, lenguajes y programación: 29.° coloquio internacional, ICALP 2002, por Peter Widmayer et al. ISBN 3-540-43864-5 página 391 

Enlaces externos