• Author / Uploaded
• Elizabeth Naranjo Ordoñez

• Categories
• Aleatoriedad
• Número primo
• Secuencia
• Simulación
• Algoritmos

Citation preview

Generación de Números Aleatorios ESCUELA POLITÉCNICA NACIONAL FACULTAD DE CIENCIAS ADMINISTRATIVAS

INGENIERÍA EMPRESARIAL SIMULACIÓN DE NEGOCIOS

El uso del concepto de aleatoriedad es empleado en Simulación para modelar dos tipos de situaciones:

*Fenómenos que se aprecian “realmente” como aleatorios. • el resultado de tirar un dado o girar la rueda de una ruleta, etc.

*Situaciones que se asumen como aleatorias por falta de mayor información, a fin de simplificar la lógica del modelo de simulación.

Números Aleatorios: HISTORIA FORMAL Antes del advenimiento de las computadoras, los números aleatorios eran generados por dispositivos físicos

Kendall y Babington-Smith (1939) publicaron 100.000 dígitos aleatorios obtenidos en un disco giratorio iluminado con una lámpara relámpago.

Década de los 40: método Simulación de Montecarlo

John Von Neumann conjeturó el potencial de los computadores para tratar problemas estocásticos en 1945.

En 1955, la Rand Corporation publicó un millón de dígitos producidos controlando una fuente de pulsos de frecuencia aleatoria.

1951 D.H.Lehmer propuso el generador lineal de congruencia.

Números Aleatorios

Los números aleatorios son la base esencial para la simulación.

Secuencia de variables aleatorias independientes e idénticamente distribuidas U (0,1).

Simulan las diferentes distribuciones de probabilidad que se requieran en el modelo.

Números aleatorios: Definición Informal Una sucesión de números aleatorios es aquella secuencia caracterizada por la nula existencia de una regla que permita conocer sus valores.

Números Aleatorios: Definiciones formales Una sucesión de números aleatorios (R1,R2…Rn ) es un sucesión de números U(0,1), si tiene las mismas propiedades estadísticas relevantes que dicha sucesión de números aleatorios.

L´ecuver (1990): 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 monde legal para decidir cuál es cuál.

Números Aleatorios: Áreas de campo

Ingeniería

Economía

Física

Estadística

Computación

Propiedades de Números Aleatorios Una secuencia R1, R2, ..., de números aleatorios debe satisfacer dos propiedades fundamentales:

UNIFORMIDAD

los números de la secuencia siguen una distribución continua uniforme con valores comprendidos entre 0 y 1. 𝑋~𝑈 0,1 .

INDEPENDENCIA

Cada valor Ri de la secuencia es independiente de los restantes valores Rj de la secuencia.

Función de Densidad

𝑓 𝑥 ={

1, 0,

0≤𝑥≤1 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜

Números pseudo-aleatorios: Son aquellos que tienen un comportamiento similar a la naturaleza aleatoria, pero están ceñidos a un patrón, generalmente de naturaleza matemática, que hace que su comportamiento sea determinístico.

Generación de Números Pseudo aleatorios El simple hecho de generar números aleatorios mediante un método conocido, remueve el verdadero potencial de la aleatoriedad.

La meta es simular o “imitar” las propiedades ideales de números aleatorios.

Si el método es conocido, la secuencia de números aleatorios puede ser repetido.

Propiedades de los Generadores Secuencias no correlacionadas • En una sucesión de números aleatorios:

X  X 0 , X 1 , X 2 ,..., X i 1 , X i , X i 1 ,..., X  ( m1) , X  ( m ) ,...

• Una subsecuencia de números aleatorios no debe estar relacionada con ninguna otra.

Independencia estadística y equiprobabilidad • Igual probabilidad de ocurrencia.

Período máximo: • El período y las propiedades de la secuencia no deben depender del valor inicial.

Impredecibilidad • Incorpora el azar en su andamiaje.

Eficiencia • Producir los mismos resultados independientemente de la plataforma computacional que se esté utilizando.

Problemas en la generación de Números Pseudo aleatorios No estar uniformemente distribuidos.

Existencia de autocorrelación.

Tener una varianza muy alta o muy baja.

Ser valores discretos en lugar de valores continuos.

Tener una media muy alta o muy baja.

Métodos para Generar Números Aleatorios

Son programas determinísticos que – a través del uso de algoritmos y con una base matemática sólida- intentan reproducir una sucesión de valores que parezca aleatoria.

Métodos para Generar Números Aleatorios: Consideraciones Ser rápidos. Reproducibles en diferentes computadoras. Tener un ciclo de repetición/período lo suficientemente largo. Números repetibles.

Cumplir el ideal de uniformidad e independencia.

Métodos para Generar Números Aleatorios Método de los Cuadrados Medios

Método Congruencia Lineal

Métodos para Generar Números Aleatorios Estructura:

I.

Determinar una semilla (valor inicial)

II.

Aplicación del algoritmo respectivo.

III.

Validación de la secuencia generada.

Método de los Cuadrados Medios Definición: Consiste en que cada secuencia de número es calculado mediante la toma de los dígitos medios de un número obtenido a través de su elevación al cuadrado.

Determinar la semilla (valor inicial).

Elevar al cuadrado los dígitos medios.

Validar la secuencia obtenida.

Método de los Cuadrados Medios: Consideraciones La semilla debe ser un número al azar 𝑋0 de 2n cifras que al elevarlo al cuadrado es de 4n cifras. De ser necesario, se añaden ceros a la izquierda para que tenga 4n cifras. El número aleatorio 𝑅𝑛 se obtiene de anteponer el punto decimal a las 2n cifras de 𝑋1 .

Métodos de los Cuadrados Medios Ejemplo: Consideremos la semilla 445

X

X2

N° Aleatorio

445

1| 9802 | 5

0,9802

9802

96| 0792 | 04

0,0792

792

6 | 2726 | 4

0,2726

2726

...............

...............

Método de los Cuadrados Medios: Inconvenientes

Fuerte tendencia a degenerar a cero rápidamente (ej. 𝑋0 = 10009). El tiempo de ciclo/período es muy corto.

Ejemplo 1: Realizar una secuencia de números aleatorios mediante el método de los cuadrados medios. Considere el valor de la semilla 8756.

Método Congruencia Lineal EXPRESIÓN ENTEROS

EXPRESIÓN ALEATORIO

Propuesto por Lehmer (1951), produce una secuencia de enteros, 𝑋1 , 𝑋2 , … entre 0 y 𝑚 − 1 mediante la siguiente relación:

Para generar números aleatorios en función de los enteros aleatorios entregados:

𝑋𝑖+1 = 𝑎𝑋𝑖 + 𝑐 𝑚𝑜𝑑 𝑚

𝑋𝑖 𝑅𝑖 = 𝑚

Donde 𝑖 = 0,1,2, …

Método Congruencia Lineal: Parámetros Variable

Denominación

𝑋0

Semilla (Valor inicial)

𝑎

Multiplicador (α)

𝑐

Incremento (β)

𝑚

Módulo

Método Congruencia Lineal: Observaciones Método Congruencial Mixto • Se denomina así cuando c0

Método Congruencial Multiplicativo • Se denomina así cuando c=0

Ejemplo 2: Tomando en consideración los siguientes datos, genere una secuencia de números aleatorios.

𝑋0 =27 𝑎= 17

𝑿𝒊+𝟏 = 𝒂𝑿𝒊 + 𝒄 𝒎𝒐𝒅 𝒎

𝑐= 43

𝒂 𝒂 𝒎𝒐𝒅 𝒃: = 𝒄 ∗ 𝒃 𝒃

𝑚= 100

c:decimales resultantes de a/b

𝑿𝒊 𝑹𝒊 = 𝒎

Método Congruencia Lineal: Consideraciones Otra manera de calcular 𝑋𝑛 es mediante la fórmula:

𝑋𝑛+1 = 𝛼 ∗ 𝑋𝑛 + 𝛽 − 𝑀

𝐴𝑙𝑓𝑎 ∗ 𝑋𝑛 + 𝑏𝑒𝑡𝑎 𝑀

Ejemplo 3: Con los siguientes datos, genere una secuencia de números aleatorios. 𝑋0 =13 𝑎= 7 𝑐= 3

𝑚= 100

𝑋𝑛+1 = 𝛼 ∗ 𝑋𝑛 + 𝛽 − 𝑀

𝑿𝒊 𝑹𝒊 = 𝒎

𝐴𝑙𝑓𝑎 ∗ 𝑋𝑛 + 𝑏𝑒𝑡𝑎 𝑀

Método Congruencia Lineal: Teoremas Teorema 1: Un generador Congruencial tiene periodo completo si y sólo si se cumplen las siguientes condiciones: 1. m y c son primos entre sí. 2. a-1 es divisible para cada primo que divide a m.

3. Si m es múltiplo de 4, entonces a-1 es múltiplo de 4.

Corolario: Un generador Congruencial multiplicativo no puede tener periodo completo.

Siempre que c = 0, el generador posee la siguiente forma: 𝑋𝑖+1 = 𝑎𝑋𝑖 𝑚𝑜𝑑 𝑚

i=0, 1, …, n

• Para asegurar la máxima longitud periódica de la secuencia, m y X0 deben ser primos entre sí. • La forma más sencilla de asegurar esto para cualquier semilla X0 es utilizar un número primo para m.

Ejemplo 4 Genere 100 números aleatorios distintos. m=100

Ejemplo 5 Genere 84 números aleatorios distintos. m=84