secuencia aleatoria

El concepto de secuencia aleatoria es fundamental en la _teoría de la probabilidad y la estadística . Este 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₁ , ..., Xn variables aleatorias independientes...". Sin embargo, como _afirmó D.H. Lehmer en 1951: "Una secuencia aleatoria es una noción vaga... en la que cada término es impredecible para quienes no están familiarizados con el tema y cuyos dígitos superan una serie de pruebas tradicionales entre los estadísticos". ^{[ 1 ]}

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

É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 , inspirada en la ley de los grandes números, aunque utilizó el término secuencia colectiva 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 de selección "apropiado" 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ó completamente 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 se denomina a menudo aleatoriedad de Mises-Church .   

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, A. N. Kolmogorov y D. W. Loveland propusieron independientemente 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, ya que leía los elementos en orden. En su lugar, propusieron una regla basada en un proceso parcialmente computable que, después de leer cualesquiera N elementos de la secuencia, decide si quiere seleccionar otro elemento que aún no se haya leído. Esta definición se suele llamar estocasticidad de Kolmogorov-Loveland . Pero este método fue considerado demasiado débil por Alexander Shen , quien 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 más satisfactoria de aleatoriedad algorítmica . Su definición original implicaba la teoría de la medida, pero posteriormente se demostró que puede expresarse en términos de la 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 mediante una máquina de Turing universal . ^{[ 9 ]}

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

• El enfoque basado en la frecuencia y la teoría de la medida . Este enfoque se originó con el trabajo de Richard von Mises y Alonzo Church. En la década de 1960, Per Martin-Löf observó 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 fluida considerando todos los conjuntos de medida cero efectivos.

• El enfoque de complejidad/compresibilidad . Este paradigma fue impulsado por A. N. Kolmogorov, 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 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 predictibilidad . Este paradigma se debe a Claus P. Schnorr y utiliza una definición ligeramente diferente de martingalas constructivas que las martingalas utilizadas 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 que una martingala recursiva tenga éxito en una secuencia en lugar de tener éxito constructivo en una secuencia, entonces se obtiene el concepto de aleatoriedad recursiva. Yongge Wang demostró ^{[ 12 ] [ 13 ]} que el concepto de aleatoriedad recursiva es diferente del concepto de aleatoriedad de Schnorr.

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

• Aleatoriedad
• Historia de la aleatoriedad
• generador de números aleatorios
• Siete estados de aleatoriedad
• Aleatoriedad estadística

• Sergio B. Volchan ¿Qué es una secuencia aleatoria? Archivado el 27 de abril de 2021 en Wayback Machine The American Mathematical Monthly , vol. 109, 2002, págs. 46–63 

• "Secuencia aleatoria" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Video sobre la estabilidad de la frecuencia. Por qué los humanos no pueden "adivinar" al azar.
• Pruebas de aleatoriedad de Terry Ritter