Entre las diferentes formalizaciones de la aleatoriedad que se
pueden proponer, la noción de sucesión uniforme es la única que se
puede emplear en la práctica: es la única que puede ser comprobada
por un test para un generador dado, y ella es suficiente para
justificar todas las aplicaciones de la función
Random. Una
``verdadera'' sucesión aleatoria debe ser uniforme. Pero, ¿podemos
considerar como aleatoria a toda sucesión uniforme? Vamos a ver,
lamentablemente, que no.
Vamos a limitarnos a las sucesiones de bits en . Esperamos que una sucesión de este tipo sea el resultado típico de lanzar una moneda, Cara o Cruz. Veamos tres sucesiones particulares:
La tercera presenta mejor aspecto que las dos primeras. Sin
embargo ella tiene las mismas probabilidades de salir así en el
juego de Cara o Cruz: . Entre las -tuplas de bits,
todos tienen, a priori, la misma probabilidad de salir:
. Toda
sucesión aleatoria de bits debe contener,
necesariamente, una infinidad de veces ceros uno detrás del
otro. ¿Aceptaríamos que un generador aleatorio de bits nos dé como
resultado solamente ceros en sucesión? Esto parece poco
verosímil.
De los ejemplos anteriores, descartaríamos el primero pues parece violar la -uniformidad. Descartaríamos el segundo en nombre de la -uniformidad. Pero, ¿qué decir entonces de la sucesión concatenada de todos los enteros en base ? (sucesión de Champernowne)
Se puede demostrar que ella es -uniforme. Pero ¿cómo
calificar de aleatoria una sucesión tan perfectamente previsible?
La definición mas intuitiva de azar, la de los diccionarios, no tiene ninguna relación con la uniformidad. Es aleatorio lo que es imprevisible. Una sucesión sería aleatoria, si no pudiésemos prever su término conociendo los primeros. La sucesión
no es aleatoria porque sin haber escrito los primeros términos, sabemos que el -ésimo será y el siguiente 0. Por el contrario, la sucesión
Ejemplo:
Repetir veces
escribir 0, luego
finRepetir.
La codificación binaria de este algoritmo es una sucesión cuya longitud depende de la expresión de . El número de bits necesarios para escribir , más o menos , es el logaritmo de en base : . El resto de la cadena no depende de y es un número constante de bits, digamos . En total, una cadena de bits de longitud, engendrará al ejecutarse una cadena de longitud . Denotemos por al conjunto de todas las cadenas de bits, de longitud finita. Si , denotaremos su longitud (número de bits) por . Un algoritmo es una aplicación de en sí mismo.
input | output |
En otras palabras es la cantidad de información que hace falta para producir empleando el algoritmo . En el ejemplo anterior, una cadena de bits bastaba para producir la siguiente cadena de longitud .
Observación :
Aunque
estas páginas no tienen la pretensión de ser un curso sobre
complejidad, debemos al menos señalar que las definiciones
anteriores no tienen sentido si no restringimos un poco la noción
de algoritmo. Si nos mantenemos en el campo de las aplicaciones
cualesquiera en , podemos llegar a paradojas del tipo de la
de R. Berry :
Para generar una sucesión dada de bits, el algoritmo a lo ``bruto'' consiste en escribirlos todos en el orden correspondiente. Esto corresponde a la aplicación identidad de en símismo, con respecto a este algoritmo la complejidad de cualquier sucesión de bits es . Por tanto la complejidad de toda sucesión está mayorada por su longitud:
Decir que una sucesión es aleatoria es decir que no se puede mejorar el algoritmo a lo bruto para generarla.
Según la proposición siguiente, la mayor parte de las sucesiones son aleatorias.
Demostración : Entre los inputs susceptibles de generar a las sucesiones de longitud , solamente nos interesan aquellos cuya longitud es inferior a . Hay a lo sumo:
Concretamente, entre todas las sucesiones de longitud ,
solamente una proporción de
entre ellas
es de complejidad .
Debe ser, por tanto, fácil encontrar sucesiones aleatorias, puesto que la mayor parte de ellas lo son. Paradójicamente, el problema de demostrar que una sucesión en particular es aleatoria es, en general, irresoluble.