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 "sean 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 un cierto número de pruebas tradicionales de los estadísticos". [1]

La teoría de la probabilidad axiomática evita deliberadamente una definición de secuencia aleatoria. [2] La teoría de probabilidad tradicional no establece si una secuencia específica es aleatoria, pero generalmente procede a discutir las propiedades de las variables aleatorias y las secuencias estocásticas asumiendo alguna definición de aleatoriedad. La escuela Bourbaki consideraba 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 aleatorio. secuencia. Utilizando el concepto de 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 va a 1/2 y cada subsecuencia poder seleccionarlo mediante un método de selección "adecuado" tampoco está sesgado. [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 sobre la computabilidad. [6] Esta definición a menudo se llama aleatoriedad de 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 en el sentido de que 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 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 ahora se considera generalmente la noción más satisfactoria de aleatoriedad algorítmica . Su definición original involucraba la teoría de la medida, pero luego se demostró que puede expresarse 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]

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

  • El enfoque de la teoría de la frecuencia/medida . Este enfoque comenzó con el trabajo de Richard von Mises y Alonzo Church. En la década de 1960, Per Martin-Löf notó que los conjuntos que codifican tales propiedades estocásticas basadas en frecuencia son un tipo especial de conjuntos de ceros de medidas , y que se puede obtener una definición más general y suave considerando todos los conjuntos de ceros de medidas efectivas.
  • El enfoque de complejidad/compresibilidad . Este paradigma fue defendido por AN Kolmogorov junto con 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 Kolmogorov de la cadena es cercana a n , es muy aleatoria; si la complejidad está muy por debajo de n , no es tan aleatorio. El concepto dual de aleatoriedad es el de compresibilidad: cuanto más aleatoria es una secuencia, menos compresible y viceversa.
  • El enfoque de la previsibilidad . Este paradigma se debe a Claus P. Schnorr y utiliza una definición de martingalas constructivas ligeramente diferente a la utilizada en la teoría de probabilidad tradicional. [11] Schnorr demostró cómo la existencia de una estrategia de apuestas selectiva implicaba la existencia de una regla de selección para una subsecuencia sesgada. Si solo se 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 demostró [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]

Ver 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 Bienvenu "Kolmogorov Loveland Stocasticity" en STACS 2007: 24º Simposio anual sobre aspectos teóricos de la informática por Wolfgang Thomas ISBN 3-540-70917-7 página 260 
  6. ^ Iglesia, Alonso (1940). "Sobre el concepto de secuencia aleatoria". Toro. América. Matemáticas. Soc . 46 (2): 130-136. doi : 10.1090/S0002-9904-1940-07154-X .
  7. ^ AN Kolmogorov, Tres enfoques para la definición cuantitativa de 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. ^ Una 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". Cartas de Procesamiento de Información . 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