Algoritmos

Tema 1
Generaci´
on de n´
umeros aleatorios

1.1.

Introducci´
on

Los n´
umeros aleatorios son la base esencial de la simulaci´on. Usualmente, toda la
aleatoriedad involucrada en el modelo se obtiene a partir de un generador de n´
umeros
aleatorios que produce una sucesi´on de valores que supuestamente son realizaciones
de una secuencia de variables aleatorias independientes e id´enticamentedistribuidas
(i.i.d.) U (0, 1). Posteriormente estos n´
umeros aleatorios se transforman convenientemente para simular las diferentes distribuciones de probabilidad que se requieran en el
modelo. En general, la validez de los m´etodos de transformaci´on dependen fuertemente
de la hip´otesis de que los valores de partida son realizaciones de variables aleatorias
iid U (0, 1), pero esta suposici´onrealmente no se cumple, puesto que los generadores
de n´
umeros aleatorios son simplementes programas determin´ısticos que intentan reproducir una sucesi´on de valores que parezca aleatoria.

1

2

Tema 1. Generaci´on de n´
umeros aleatorios

N´
umeros pseudoaleatorios
Si decidi´esemos realizar el sorteo de Navidad de Loter´ıa Nacional mediante ordenador, seguramente la gente no confiar´ıa en laaleatoriedad del ordenador y se quejar´ıa.
En su lugar, se prefiere un m´etodo f´ısico y sencillo de entender, como extraer bolas de
un bombo. Incluso este tipo de m´etodos requiere tomar ciertas precauciones: todas las
bolas debe tener id´entico peso, deben de estar bien mezcladas en el bombo y se deben
cambiar regularmente para reducir las posibilidades de que unas aparezcan m´as que
otras.Claramente este procedimiento no es pr´actico para una simulaci´on computacional
que requiere la generaci´on de cientos de miles de n´
umeros aleatorios.
El m´etodo m´as conveniente y m´as fiable de generar n´
umeros aleatorios es utilizar
algoritmos determin´ısticos que posean alguna base matem´atica solida. Estos algoritmos
producen una sucesi´on de n´
umeros que se asemeja a la de una sucesi´on derealizaciones
de variables aleatorias iid U (0, 1), aunque realmente no lo sea. Es por ello que este tipo
de n´
umeros se denominan pseudo-aleatorios y el algoritmo que los produce se llama
generador de n´
umeros pseudo-aleatorios.
Definici´
on 1.1. Un generador de n´
umeros (pseudo)aleatorios es una estructura G =
(X, x0 , T, U, g), donde X es un conjunto finito de estados, x0 ∈ X es el estadoinicial
(semilla), la aplicaci´on T : X → X es la funci´on de transici´on, U es el conjunto finito
de posibles observaciones, y G : X → U es la funci´on de salida.

B´asicamente, el funcionamiento de un generador de n´
umeros pseudo-aleatorios es
el siguiente. Se elige una semilla inicial cualquiera x0 , y se genera una sucesi´on de
valores xn mediante una relaci´on de recurrencia xn = T (xn−1 ). Cadauno de estos
valores proporciona un n´
umero pseudo-aleatorio un definido a trav´es de alguna relaci´on
un = g(xn ). Claramente, la sucesi´on de estados es peri´odica, puesto que X es finito.
En alg´
un momento, ocurrir´a que xj = xi para alg´
un j > i, y a partir de ese instante,

1.2. M´etodos de generaci´
on de n´
umeros pseudo-aleatorios

3

xj+k = xi+k , y por lo tanto, uj+k = ui+k , paratodo k ≥ 0. El periodo es el menor entero
ρ > 0 tal que para alg´
un entero τ ≥ 0, se verifica que xρ+k = xk , para todo k ≥ τ .
Claramente, el periodo de un generador no puede exceder el cardinal del espacio de
estados. Una buena propiedad para un generador es que su periodo est´e cercano a |X|.
Un buen generador de n´
umeros pseudo-aleatorios deber´ıa tener las siguientes propiedades:

Por encimade todo, la sucesi´on de valores que proporcione deber´ıa asemejarse a
una sucesi´on de realizaciones independientes de una variable aleatoria U (0, 1).
Los resultados deben ser reproducibles, en el sentido de que comenzando con las
mismas condiciones iniciales debe ser capaz de reproducir la misma sucesi´on. Esto
nos puede permitir depurar fallos del modelo o simular diferentes alternativas...