Monday, May 22, 2006

GENERACIÓN DE NÚMEROS ALEATORIOS (GNA's)


Por cierto, aprovecho para comentar aquí que estoy terminando un gran libro sobre programación para los amantes de las viejas computadoras en el que revelo todos mis "algoritmos de computación más preciados". Llevo trabajando más de dos años en el libro y ya os adelanto que tendrá unas 400 páginas y un precio aproximado de 40-50 euros. También os adelanto que la obra será personalizada para el lector, es decir, incluirá sus datos personales y en todo momento me dirigiré a él expresamente por su propio nombre para explicarle y detallarle la metodología de programación empleada en sus más de 60 aplicaciones prácticas. Sólo espero que sea una obra a tener en cuenta y que logre su principal objetivo que no es otro que introducir al lector en la apasionante aventura de la programación de computadoras.


Si bien existen diversos métodos para la generación de números aleatorios como por ejemplo el lanzamiento de monedas o dados, ruletas, etc., estos sistemas manuales resultan, por razones obvias, ineficaces en labores de investigación y aplicaciones informáticas, en cuyas tareas suelen emplearse métodos informáticos basados en hardware o software.
1) Hardware: entre los métodos hardware encontramos los sistemas basados en excitación de átomos radiactivos, el recuento de partículas emitidas, el ruido blanco producido por circuitos electrónicos, el ruido térmico de un diodo semiconductor, etc. Un buen ejemplo de ruido aleatorio pueden ser los puntos blancos y negros que muestra una televisión cuando no tiene sintonizado ningún canal, en tal caso, los puntos negros podrían equivaler a ceros y los puntos blancos a unos. En todos estos métodos, las salidas aleatorias suelen ser registradas por ordenador al objeto de poder recuperar la secuencia en un momento determinado, así como someterla a los tests pertinentes que certifiquen la validez de dichos sistemas. A pesar de poseer características propias inalcanzables por los generadores basados en algoritmos determinísticos (principalmente período infinito en las series e impredecibilidad absoluta) que le permiten rozar la aleatoriedad absoluta, sin embargo, y pese a que dichos fenómenos físicos puedan ser considerados como verdaderamente aleatorios e incluso superar cualquier prueba de contraste a la que se les someta, ¿creen realmente que dichos generadores pueden mostrarse absolutamente insensibles bajo cualquier circunstancia? Seguramente no, algo distinto es que los factores condicionantes escapen de nuestro control y la posibilidad de ser identificados. De hecho, existen trabajos en este sentido como “The Logic of Statistical Interference” (I. Hacking 1967) que revelan sesgos e irregularidades en algunos de estos mecanismos. Además, entre los principales inconvenientes para su uso en simulación, podemos destacar:
- Una considerable lentitud de generación que dificulta la simulación de procesos complejos en los que se requiera el cálculo con millones de variables aleatorias.
- La imposibilidad de reproducir la misma secuencia de variables en el caso que sea necesario para, por ejemplo, la corrección de errores en un algoritmo.
- Su absoluta impredecibilidad en cualquier circunstancia.
2) Software: Los generadores aleatorios basados en software utilizan algoritmos determinísticos para la generación de números “pseudoaleatorios” y constituyen un pilar básico en investigación, no en vano, el campo de la simulación (aplicable a multitud de disciplinas) se alimenta de dichos generadores al contar éstos con importantes ventajas frente a los generadores aleatorios basados en fenómenos físicos. Entre sus ventajas más destacables cabe citar la enorme velocidad de generación que ofrecen, limitada prácticamente a la capacidad de cálculo de los sistemas informáticos. Otra característica no menos baladí que ofrecen al investigador es la posibilidad de reproducir la misma secuencia cuantas veces sea necesario empleando el mismo algoritmo y la misma semilla. Las variables pseudoaleatorias generadas mediante algoritmos numéricos determinísticos plenamente previsibles simulan de algún modo el azar, sin embargo, y como era de esperar, los generadores algorítmicos no son perfectos: antes o después suelen caer en ciclos infinitos (periodo finito) de repetición de la serie, en otros casos, pueden caer en repetición periódica de un mismo número y en cualquier caso, podrían presentar sesgos y dependencias que les aleja de los criterios de calidad óptimos deseables para un generador aleatorio.
Algunos sencillos generadores de ejemplo muy empleados en calculadoras científicas pueden ser del tipo siguiente:
Ni+1 = FRC (Ni * 9281 + 0.211327)
Ni+1 = FRC (Ni * 2939 + Pi)
Ni+1 = FRC [ (Ni + Pi)5 ]
Ni+1 = FRC (Ni * 7 + 0.13)
* El comando FRC toma sólo la parte decimal ignorando la parte entera.
Pese a que pueden ser útiles en condiciones de poca exigencia, los algoritmos incluidos en los modernos lenguajes de programación suelen ser de mayor complejidad consiguiendo así un período mayor (el período es el tamaño máximo de la serie que puede ofrecer un determinado algoritmo determinístico antes de volver a repetir los valores).
Entre las principales ventajas de los generadores algorítmicos en simulaciones complejas destacan:
- La enorme velocidad de generación limitada únicamente por la capacidad del hardware empleado siendo posible la generación de series de millones de variables por segundo.
- La posibilidad de reproducir idéntica serie en cualquier circunstancia.
Existen al respecto numerosos modelos de pruebas de contraste encaminadas a evaluar la calidad del algoritmo, evidentemente, no basta con que la secuencia parezca aleatoria y deben cumplirse las leyes de la probabilidad. Los más sencillos tests que puedo ponerles como ejemplo, al margen de detectar el período máximo que nos llevaría a repetir la serie de nuevo, serían:
- Media aritmética de los valores de la serie: Por ejemplo, si simulamos el lanzamiento de un dado diez mil veces, debemos obtener una media global próxima a 3.5, que sería la media exacta de los seis valores posibles del espacio muestral (1,2,3,4,5,6) partiendo del enunciado:
Media = (1+2+3+4+5+6)/6
Así en nuestra prueba de contraste sumaríamos en un acumulador el valor de los diez mil lanzamientos y lo dividiríamos por 6.
- Regularidad comprobable en las frecuencias absolutas de cada uno de los valores posibles durante todo el período.
Continuando con el ejemplo anterior, en los diez mil lanzamientos del dado, comprobaríamos que cada uno de los valores posibles (1,2,3,4,5,6). En nuestro ejemplo, con 10000 lanzamientos simulados, la frecuencia absoluta esperada para cada uno de los valores posibles sería 10000/6.
Este podría ser más o menos el código en Basic de un sencillo test para comprobar si nuestro algoritmo cumple las leyes de la probabilidad:

dim f(7) : dim n,d as integer ‘ n -> bucles y d valores de 1 a 6
dim nl, media as double ‘ nl -> número de lanzamientos
? "SIMULADOR DE LANZAMIENTO DE DADOS"
? "================================="
input "NUMERO DE LANZAMIENTOS = "; nl
randomize (timer) ‘ altera semilla del algoritmo RND
for n=1 to nld=int(rnd(1)*6)+1 ‘ simula lanzamiento y almacena en d
f(d)=f(d)+1 ‘ acumula las frecuencias en vector f
media=media+d ‘ acumulador global para cálculo media
next
?:? "MEDIA ARITMETICA GLOBAL = "; media/(nl-1) ‘ imprime media
?
for n=1 to 6 ‘ bucle para imprimir contadores de frecuencia
? "frecuecia absoluta de "; n; " = "; f(n)
next
end


* Ejecutable disponible en: http://inicia.es/de/elpatron/hipotesis/dados.exe
Para ejecutar directamente seleccione ABRIR en el cuadro de diálogo que le muestre el sistema al hacer click! Sobre el enlace

Pero, tal y como anotábamos con anterioridad, la variables pseudoaleatorias no dejan de ser una solución a medias, por lo que a medida que aumenta la complejidad en los experimentos de simulación el investigador puede no disponer de mecanismos fiables que le permitan garantizar la normalidad de la simulación y la calidad suficiente del generador empleado.
Si bien en la actualidad existen diversos modelos de generación pseudoaleatoria empleados con cierto éxito en procesos de simulación, siguen siendo los obtenidos mediante generadores electrónicos los únicos procedimientos considerados puramente aleatorios, pese a que tampoco están exentos de inconvenientes como hemos detallado con anterioridad.
La generación aleatoria de variables para las matemáticas es hoy una asignatura pendiente en pleno vigor, una brecha abierta que probablemente jamás termine de cerrar. Como ustedes pueden ya imaginar la cuestión no es baladí y las soluciones actuales al problema distan bastante de alcanzar la “verdad absoluta” o un “estado definitivo”. Cualquier método conocido consiste en una solución a medias, un subterfugio transitorio que nos conduce a la generación de las denominadas variables “pseudoaleatorias” cuyo prefijo alude, de forma meridiana, a la falta de pureza en su génesis y a su predecibilidad.
Otras líneas de investigación han apuntado en sentidos distintos como por ejemplo la lista infinita de decimales del número PI ó E (que surgen al ampliar la precisión de estas constantes), que si bien pueden parecer aleatorias y podrían superar los test de probabilidad necesarios además de contar con un periodo infinito, no debemos olvidar que este tipo de series siempre serán predecibles mediante un sencillo cálculo.
El ingenio de ingenieros y matemáticos no cesa en la búsqueda de nuevas e inéditas fórmulas que nos acerquen un poco más al azar puro, prueba de ello son algunos de los destacados trabajos con que cada cierto tiempo nos sorprenden algunos expertos, como por ejemplo el trabajo conjunto de Pedro Mª Alcocer Garau, José Mª García Carrasco y Luis Hernández Encinas, desarrolladores de un ingenioso y efectivo generador de bits aleatorios basado en entradas por teclado. Sin embargo, y como ellos mismo llegan a afirmar en su trabajo, “no se dispone de ninguna prueba matemática que asegure de forma categórica la aleatoriedad de una secuencia de bits”.
Los interesados en este trabajo de investigación pueden encontrar más información sobre este generador aleatorio en:
http://inicia.es/de/evr2/novatica05.pdf

No comments: