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.