04 Numeros Aleatorios

Capítulo 4
Números
Aleatorios

Simulación/2002

Héctor

Números Aleatorios
• Elemento Central en la Simulación digital.
• Definición formal controvertida.
• Elemento esencial en muchas áreas del conocimiento
Ingeniería, Economía, Física, Estadística, etc.
• Definición intuitiva: Una sucesión de números
aleatorios puros, se caracteriza por que no existe
ninguna regla o plan que nos permitaconocer sus
valores.
• Los números aleatorios obtenidos a través de
algoritmos recursivos se llaman pseudoaleatorios.
Simulación/2002

Héctor

Números Aleatorios
Disponer de un buen generador de números
aleatorios es clave en:
•
•
•
•
•
•
•

Computación Aleatorizada
Computación Evolutiva
Algoritmos Aleatorizados
Verificación de Algoritmos
Validación de Algoritmos
Criptografía
etc.

Simulación/2002Héctor

Números Aleatorios
• La gran disponibilidad de generadores de números
aleatorios en muchos entornos y compiladores
puede llevarnos a pensar que para un usuario de
la simulación no sería necesario estudiar estas
cuestiones.
• Una lección del pasado reciente nos obliga a sacar
lecciones y actuar con mucho cuidado con dichos
generadores (RANDU - IBM).
• El Uso progresivo de modelos de simulacióncada
vez más detallados exige una mayor calidad de los
generadores de números aleatorios.
Simulación/2002

Héctor

Números Aleatorios
Algunas ideas o propiedades de los generadores
I. Lagarias (1993) publicó un trabajo titulado “Pseudo
Random Numbers” en Statistical Science. Donde
estudia algunas propiedades tales como:
2

Expansividad : Una aplicación d  [0,1] es expansiva
si | d ' ( x) |  1x  [0,1]
La idea es escoger “d” como una aplicación expansiva
de manera que la inestabilidad computacional
proporcione aleatoriedad.
Simulación/2002

Héctor

Números Aleatorios
No Linealidad: La composición de aplicaciones no
lineales
puede
conducir
a
comportamientos
crecientemente no lineales Ej: d(x) = x2; d(n)(x) = x2n
Complejidad Computacional: La aleatoriedad de
Kolmogorov, tambiéndenominada incomprensibilidad
computacional.
Consiste en constatar si la
aleatoriedad de una sucesión de números es
incomprensible (problema decidible).
Impredecibilidad

Simulación/2002

Héctor

Números Aleatorios
• DEF 1: Kolmogorov (1987) [Complejidad Algorítmica]
Una sucesión de números es aleatoria sino puede
producirse eficientemente de una manera más corta
que la propia serie.
• DEF 2: L’Ecuyer(1990) [Impredicibilidad] Una
sucesión de números es aleatoria si nadie que utilice
recursos computacionales razonables puede distinguir
entre la serie y una sucesión de números
verdaderamente aleatoria de una forma mejor que
tirando una moneda legal para decidir cuál es cuál.
Obs: Esta definición conduce a los denominados
generadores PT-perfectos usados en Criptografía.
Simulación/2002

HéctorNúmeros Aleatorios
• DEF 3: Un Número aleatorio es una realización de una
variable aleatoria que tiene asociada una ley de
probabilidades F, en un espacio o modelo de
Probabilidades (, , P).

Obs: Una particular Ley de Probabilidad base para la
generación de números pseudo-aleatorios es:
u1, u2,..., un : es la uniforme (0 ; 1) ui ~ U(0,1).
• DEF 4: Una sucesión de números aleatorios {u 1, u2,...,un} es una sucesión de números U(0;1), si tiene las
mismas propiedades estadísticas relevantes que dicha
sucesión de números aleatorios.
Simulación/2002

Héctor

Números Aleatorios
• DEF 5: Una sucesión de números aleatorios {ui}
es aleatorio si h-úplas de números sucesivos no
superpuestos se distribuyen aproximadamente.
como una [0,1]h, con h=1,2,..,n, para n
suficientemente grande.
• Obs: h=2tenemos (ui,ui+1) , i=1,2,..n , se distribuye
como una ley uniforme en [0,1]2.
• Existe una gran de métodos para generar
{ui} U(0,1) : -Uniformente distribuidas
- Independientes
- E[U]= ½ ; V[U]= 1/12
- Período largo
Simulación/2002

Héctor

Números Aleatorios
A las propiedades estadísticas anteriores se deben
agregar otras relativas a la eficiencia computacional:
• Velocidad de respuesta
•...