miércoles, 5 de septiembre de 2012

PRUEBAS ESTADÍSTICAS PARA LOS NÚMEROS PSEUDO ALEATORIOS

PRUEBAS ESTADÍSTICAS PARA LOS NÚMEROS PSEUDO ALEATORIOS


En la sección anterior se presentaron diversos algoritmos para construir un conjunto de números pseudo aleatorios, pero eso sólo es el primer paso, ya que el conjunto resultante debe ser sometido a una serie de pruebas para validar si los números que los integran son aptos para usarse en un estudio de simulación.
A continuación se presentan las pruebas estadísticas básicas que se emplean generalmente  para determinar si un conjunto de números pseudo aleatorios entre cero y uno cumplen con las  propiedades básicas de independencia y uniformidad. El objetivo es validar que el conjunto  realmente está conformado por números aleatorios.

Prueba de Medias 

Una de las propiedades que deben cumplir los números generados, es que el valor esperado  sea igual a 0.5. La prueba que busca determinar lo anterior es la llamada prueba de medias, en  la cual se plantean las siguientes hipótesis:

 y

La prueba de medias consiste en determinar el promedio de los  n números generados mediante la ecuación siguiente: 


Posteriormente, se calcula los límites inferior y superior con las ecuaciones siguientes:

y


Si el valor de −r se encuentra entre los límites de aceptación concluimos que no se puede  rechazar que el conjunto ir tiene un valor esperado de 0.5 con un nivel de aceptación de 1-α.  En caso contrario se rechaza que el conjunto ir tiene un valor esperado de 0.5. Para el cálculo de los límites de aceptación se utiliza el estadístico  Zα / 2, el cual se determina por medio de la tabla de distribución normal estándar.


Prueba de Varianza 

Otra de las propiedades que debe satisfacer el conjunto  ir , es que sus números tengan una varianza de 1/12. La prueba que busca determinar lo anterior es la prueba de varianza, que  establece las siguientes hipótesis: 



La prueba de varianza consiste en determinar la varianza de los  n números que contiene el  conjunto ir , mediante la ecuación siguiente: 




Después se calculan los límites de aceptación inferior y superior con las ecuaciones siguientes: 


y



Si el valor de  V(r) se encuentra entre los límites de aceptación, decimos que no se puede 
rechazar que el conjunto ir , tiene una varianza de 1/12, con un nivel de aceptación de 1-α; de 
lo contrario se rechaza que el conjunto ir tiene una varianza de 1/12. 








Prueba Chi-cuadrada


Una de las propiedades más importantes que debe cumplir un conjunto de números  ir es la uniformidad. Para comprobar su acatamiento se han desarrollado pruebas estadísticas como la prueba Chi-cuadrada. Para probar la uniformidad de los números de un conjunto bajo esta prueba es necesario formular las siguientes hipótesis:



y






La prueba Chi-cuadrada busca determinar si los números del conjunto
i
r se distribuyen
uniformemente en el intervalo  (0, 1). Para llevar a cabo esta prueba es necesario dividir el
intervalo en  m subintervalos en donde es recomendable que  m = n . Posteriormente se
clasifica cada número pseudo aleatorio del conjunto
i
r en los  m intervalos. A la cantidad de
números
i
r que se clasifican en cada intervalo se le denomina frecuencia observada  (0 )
i
, y a
la cantidad de números
i
r que se espera encontrar en cada intervalo se llama frecuencia
esperada  ( ) Ei
; teóricamente, la
i
r es igual a  n / m . A partir de los valores de  0i
y de  Ei
 se
determina el estadístico
2
χ 0
 mediante la ecuación:









Si el valor estadístico
2
χ 0
 es menor al valor de tablas
2
χα ,m−1
, entonces no se puede rechazar
que el conjunto de números
i
r sigue una distribución uniforme. En caso contrario, se rechaza
que
i
r sigue una distribución uniforme.





lunes, 3 de septiembre de 2012

LOS NÚMEROS PSEUDO ALEATORIOS

NÚMEROS ALEATORIOS


Algoritmos no congruenciales

Los algoritmos no congruenciales que se incluyen en este proyecto son cuadrados medios,
productos medios y multiplicador constante.


Algoritmo de cuadrados medios

Este algoritmo no congruencial fue propuesto en la década de los cuarenta del siglo XX por Von Neumann y Metropolis. Requiere un número entero detonador con D dígitos, el cual es elevado al cuadrado para seleccionar del resultado los D dígitos del centro; el primer número se determina simplemente anteponiendo el “0.” a esos dígitos. Para obtener el segundo número se sigue el mismo procedimiento, solo que ahora se eleva al cuadrado los D  dígitos del centro que se seleccionaron para obtener el primer número.
Este método se repite hasta obtener n números. A continuación se presentan con más detalle los pasos para generar números con el algoritmo de cuadrados medios.



1. Seleccionar la semilla ( X0)  con  D dígitos (D > 3).
2. Sea  Y0 = resultado de elevar  X0 al cuadrado; sea  X1 = los  D dígitos del centro y sea r1 = 0.D dígitos del centro.
3. Sea Yi = resultado de elevar  Xi al cuadrado; sea  Xi+1 = los  D dígitos del centro y sea ri+1 = 0. D dígitos del centro para toda i = 1, 2, 3,...,n .
4. Repetir el paso 3 hasta obtener los  n números ir deseados.



El algoritmo de cuadrados medios generalmente es incapaz de generar una secuencia de  números con período de vida  n grande. Además, en ocasiones solo es capaz de generar un  solo número. 

Algoritmo de productos medios 

La mecánica de generación de números pseudo aleatorios de este algoritmo no congruencial  es similar a la del algoritmo de cuadrados medios. La diferencia entre ambos radica en que el algoritmo de productos medios requiere dos semillas, ambas con  D dígitos; además, en lugar de elevarlas al cuadrado, las semillas se multiplican y del producto se seleccionan los  D dígitos del centro, los cuales formarán el primer número pseudo aleatorio ri = 0.D . Después se  elimina una semilla y la otra se multiplica por el primer número de  D dígitos, para luego seleccionar del producto los  D dígitos que conformarán un segundo número ir . Entonces se elimina la segunda semilla y se multiplican el primer número de  D dígitos por el segundo  número de  D dígitos; del producto se obtiene el tercer número ir . Siempre se irá eliminando el  número más antiguo, y el procedimiento se repetirá hasta generar los  n números pseudo  aleatorios. A continuación se presentan con más detalle los pasos del método para generar  números con el algoritmo de productos medios.


1. Seleccionar una semilla ( X0)  con  D dígitos.
2. Seleccionar una semilla (X1) con  D dígitos.
3. Sea Y0 = X0 * X1 ; sea  X 2  = los  D dígitos del centro y sea r1 = 0.D dígitos del centro.
4. Sea  Yi = Xi Xi+1 : sea  Xi+2 = los  D dígitos del centro y sea  r
i+1 = 0.D dígitos del centro para toda i = 1, 2, 3,..., n .
5. Repetir el paso 4 hasta obtener los  n números ir deseados.

Algoritmo de multiplicador constante

Este algoritmo no congruencial es similar al algoritmo de productos medios. Los siguientes son los pasos necesarios para generar números pseudo aleatorios con el algoritmo de multiplicador constante.
1. Selecciona una semilla (X0)  con  D dígitos (D > 3).
2. Seleccionar una constante (a) con  D dígitos (D > 3).
3. Sea Y0 = a * X0 ; sea  X1 = los  D dígitos del centro y sea r1 = 0.D dígitos del centro.
4. Sea  Yi = a * Xi ; sea  Xi+1 = los  D dígitos del centro y sea  ri+1 = 0. D dígitos del centro para toda i = 1, 2, 3,..., n .
5. Repetir el paso 4 hasta obtener los  n números ir deseados.




Algoritmos congruenciales

Entre los algoritmos congruenciales se encuentran los algoritmos congruenciales lineales y los  no lineales.


Algoritmos congruenciales lineales

En este trabajo abordaremos los algoritmos congruenciales lineales como el algoritmo congruencial lineal, el multiplicativo y el aditivo.


Algoritmo Lineal 

Este algoritmo congruencial fue propuesto por D. H. Lehmer en 1955. Según Law y Kelton, este  algoritmo ha sido el más utilizado. El algoritmo congruencial lineal genera una secuencia de números enteros por medio de la siguiente ecuación recursiva:



Con i = 1, 2, 3,...,n
Donde  X0 es la semilla,  a es la constante multiplicativa,  c es una constante aditiva y  m es el  módulo:    X0> 0 ,  a > 0 ,  c > 0 y  m > 0 deben ser números enteros. La operación              “ mod m ” significa multiplicar  Xi por  a , sumar  c y dividir el resultado entre  m para obtener el residuo  Xi+1. Es importante señalar que la ecuación recursiva del algoritmo congruencial lineal genera  una secuencia de números enteros y que para obtener números pseudo aleatorios en el  intervalo (0, 1) se requiere de la siguiente ecuación: 




Con i = 1,2,3,...,n
Para que el algoritmo sea capaz de lograr el máximo período de vida  n , es preciso que los  parámetros  X0 ,  a , y  m cumplan con ciertas condiciones. Banks, Carson, Nelson y Nicol 
sugieren lo siguiente:  m debe ser múltiplo de 2 , donde  g debe ser entero,  a = 1+ 4k , donde k debe ser entero y  c debe ser relativamente primo a  m. 
Bajo estas condiciones se obtiene un período de vida máximo: N = m = 2 . 



Algoritmo congruencial multiplicativo 

El algoritmo congruencial multiplicativo surge del algoritmo lineal cuando  c = 0 . Entonces la ecuación recursiva es:



Con i = 0, 1, 2, 3,..., n
En comparación con el algoritmo congruencial lineal, la ventaja del algoritmo multiplicativo es que implica una operación menos a realizar. Los parámetros de arranque de este algoritmo son  X0,  a y  m , los cuales deben ser enteros y mayores que cero. Para transformar los números Xi en el intervalo (0, 1) se usa la ecuación: 




Con i = 0, 1, 2, 3,..., n
De acuerdo con Banks, Carson, Nelson y Nicol, las condiciones que deben cumplir los parámetros para que el algoritmo congruencial multiplicativo alcance su máximo período son: 



m debe ser múltiplo de g 2 , donde  g debe ser entero,  a = 3 + 8k , donde  k = 0, 1, 2, 3,... ,   X0
debe ser un número impar. 
Bajo estas condiciones se logra un período de vida máximo: 
2 / 4 2−= =gN k . 


Algoritmo congruencial aditivo 

Este algoritmo requiere una secuencia previa de n números aleatorios  X X X X X n, , , ,... 1 2 3 4
para generar una secuencia de números enteros que empiezan en  , , , ,... X n+1 X n+2 X n+3
X n+4

Su ecuación recursiva es: