Número pseudoaleatorio

Un número pseudo-aleatorio es un número generado en un proceso que parece producir números al azar, pero no lo hace realmente. Las secuencias de números pseudo-aleatorios no muestran ningún patrón o regularidad aparente desde un punto de vista estadístico, a pesar de haber sido generadas por un algoritmo completamente determinista, en el que las mismas condiciones iniciales producen siempre el mismo resultado.

Casi Aleatorio

Una variable pseudoaleatoria es una variable que ha sido creada a través de un procedimiento determinista (por norma general un programa de ordenador o subrutina) el cual tiene como entrada dígitos realmente aleatorios. La cadena pseudoaleatoria resultante suele ser más larga que la cadena aleatoria original, pero menos aleatorio, es decir, con menos entropía.

Los mecanismos de generación de números aleatorios que se utilizan en la mayoría de los sistemas informáticos son en realidad procesos pseudo-aleatorios.

Campos de Aplicación

Los generadores de números pseudoaleatorios son ampliamente utilizados en campos tales como el modelado por computadora, estadística, diseño experimental, etc. Algunas de estas secuencias son lo suficientemente aleatorias para ser útiles en estas aplicaciones.

Una de las utilidades principales de los números pseudoaleatorios tiene lugar en los campos de la criptografía y de la esteganografía. Por ello se sigue investigando en la generación de dichos números, empleando por ejemplo medidores de ruido blanco o analizadores atmosféricos, ya que experimentalmente se ha comprobado que tienen una aleatoriedad bastante alta.

Asimismo, también destacan su uso en el llamado método de Montecarlo, con múltiples utilidades, por ejemplo para hallar áreas / volúmenes encerradas en una gráfica y cuyas integrales son muy difíciles de hallar o irresolubles; mediante la generación de puntos basados en estos números, podemos hacer una buena aproximación de la superficie /volumen total , encerrándolo en un cuadrado / cubo , aunque no lo suficientemente buena.

Un campo donde resulta imprescindible, es en la programación de juegos, donde a menudo se necesita disponer de series elegidas al azar. Por ejemplo para crear nubes con patrones diferentes según escenarios. Esto es aún más necesario en aquellos juegos donde el azar es primordial (como juegos donde el azar está implícito en la propia dinámica del juego, por ejemplo juegos de cartas, que necesitan ser barajadas) o incluso una cuestión que garantice la fiabilidad para dotar al juego de imparcialidad, como en los casos donde en esos juegos se realizan apuestas económicas. Y que suelen recurrir al algoritmo Fisher-Yates.

Secuencia Pseudoaleatoria

Por lo general, el interés no radica en generar un solo número aleatorio, sino muchos, reunidos en lo que se conoce como secuencia aleatoria.

Se llama secuencia pseudoaleatoria, sucesión de números pseudoaleatorios, secuencia de pseudo ruido o código de pseudo ruido a cualquier grupo de secuencias binarias que presentan propiedades aleatorias parecidas a las del ruido.

Las secuencias de pseudo ruido se distinguen de las secuencias aleatorias de verdad en que muestran una periodicidad. Es decir, están formadas por una serie periódica de números positivos y negativos, o bits, de longitud ${\displaystyle N}$ . A uno de estos bits de una secuencia de pseudo ruido se le llama chip. Por lo tanto, a la velocidad de la secuencia se le llama tasa chip, y se mide en chips por segundo (cps). Una secuencia de este tipo se puede representar de la siguiente manera:

${\displaystyle \dots ,a_{N-1},a_{N},a_{1},a_{2},\dots ,a_{N},a_{1},\dots }$ 

Los códigos de pseudo ruido deben satisfacer, entre otras, las siguientes condiciones:

1. En cada periodo la cantidad de números positivos tiene que diferir de la cantidad de números negativos en exactamente uno. Así pues, ${\displaystyle N}$  es un número impar:
2. En cada periodo la mitad de las secuencias del mismo signo han de tener longitud 1, un cuarto ha de tener longitud 2, un octavo ha de tener longitud 3, y así sucesivamente. Además el número de secuencias de números positivos tiene que ser igual al número de secuencias de números negativos.
3. La función de autocorrelación es periódica y presenta valor binario.

Sucesión de Números Pseudoaleatorios

La sucesión, supone en si una secuencia, pero como sucesión, ha sido obtenida mediante un proceso aritmético definido, efectiva para el propósito para el que se la requiere.

Si bien una sucesión de números pseudoaleatorios parece generalmente no obedecer a ningún patrón o ley de formación, todo generador de números pseudoaleatorios con un estado interior finito, se repetirá luego de una larga sucesión de números. Es posible demostrar esto mediante el principio del palomar.

Debe notarse que la sucesión, aun siendo una secuencia, guarda una periodicidad buscada de por sí o como consecuencia indeseable. Por lo general, al crear secuencias aleatorias se busca que la periodicidad sea la menor posible, salvo en sistemas donde sea requerido como parte del planteamiento concebido y esperado, de ahí la sucesión.

Historia

La generación de números tiene múltiples usos (principalmente en estadística, simulaciones y criptografía). Al principio los investigadores que necesitaban secuencias de números aleatorios tenían que generarlos ellos mismos mediante dados, monedas, cartas, etc. o utilizar tablas de números aleatorios existentes.

El primer intento de dotar a los investigadores con un suministro de dígitos aleatorios tuvo lugar en 1927, cuando la Cambridge University Press publicó una tabla de 41.600 dígitos desarrollada por Leonard H.C. Tippet. En 1947 la RAND Corporation generó una secuencia de números a partir de una simulación electrónica de una rueda de ruleta; los resultados fueron publicados en 1955 bajo el título A Million Random Digits with 100.000 Normal Deviates.

John von Neumann fue un pionero en la investigación de los generadores de números aleatorios implementados en computadoras. En 1951, Derrick Henry Lehmer inventó el Generador lineal congruencial, utilizado en un gran número de generadores pseudoaleatorios actuales. Con la proliferación de los ordenadores, los algoritmos de generación de números pseudoaleatorios fueron reemplazando las tablas de números aleatorios, y los generadores de números aleatorios "reales" (generadores de números aleatorios por hardware) son utilizados en muy raras ocasiones.

Periodo

Teorema 3.1 (Hull y Dobell, 1962)

Un generador congruencial tiene período máximo ${\displaystyle p=m}$  si y sólo si:

1. ${\displaystyle c}$  y ${\displaystyle m}$  son primos relativos, i.e. ${\displaystyle \operatorname {m.c.d.} (c,m)=1}$ .
2. ${\displaystyle a-1}$  es múltiplo de todos los factores primos de ${\displaystyle m}$  (i.e. ${\displaystyle a=1\operatorname {mod} m}$ , para todo ${\displaystyle q}$  factor primo de ${\displaystyle m}$ ).
3. Si ${\displaystyle m}$  es múltiplo de ${\displaystyle 4}$ , entonces ${\displaystyle a-1}$  también lo ha de ser (i.e. m≡0mod4⇒a≡1mod4).

Algunas consecuencias:

• Si ${\displaystyle m}$  primo entonces ${\displaystyle p=m\Longleftrightarrow a=1}$ 
• Un generador multiplicativo no cumple la condición 1.

Teorema 3.2 Un generador multiplicativo tiene período máximo ${\displaystyle p=m-1}$  si:

1. ${\displaystyle m}$  es primo.
2. ${\displaystyle a}$  es una raíz primitiva de ${\displaystyle m}$ , es decir, el menor entero ${\displaystyle q}$  tal que ${\displaystyle aq=1\operatorname {mod} m}$  es ${\displaystyle q=m-1}$ .

Además de preocuparse de la longitud del ciclo, las secuencias generadas deben aparentar muestras i.i.d. ${\displaystyle U(0,1)}$ . Por ejemplo, los valores generados pueden mostrar una estructura reticular.

• Marsaglia (1968): k-uplas de generadores multiplicativos contenidas en a lo sumo (k!m)1/khiperplanos paralelos.
• Generador RANDU de IBM (70’s):

library(rgl) system.time(u <- RANDCN(9999)) # Generar xyz <- matrix(u, ncol = 3, byrow = TRUE) plot3d(xyz) # rglwidget() 

Se han propuesto diversas pruebas (ver sección siguiente) para determinar si un generador tiene problemas de este tipo y se han realizado numerosos estudios para determinadas familias (e.g. Park y Miller, 1988, m=231−1).

• En cualquier caso, se recomienda considerar un “periodo de seguridad” ≈√p para evitar este tipo de problemas.
• Aunque estos generadores tiene limitaciones en su capacidad para producir secuencias muy largas de números ${\displaystyle \operatorname {IID} \;U(0,1)}$ , es un elemento básico en generadores más avanzados.

Algunos Generadores

Generador Congruencial Lineal Simple

Dada una semilla ${\displaystyle x_{0}}$ , un multiplicador ${\displaystyle a}$ , una constante ${\displaystyle c}$  llamada incremento y un módulo ${\displaystyle m}$ , se define

${\displaystyle x_{i}=(ax_{i-1}+c)\operatorname {mod} m}$ 

entonces ${\displaystyle 0\leq x_{i}\leq m-1}$  y para obtener una muestra ${\displaystyle u_{i}}$  en ${\displaystyle [0,1]}$  para ${\displaystyle i=1,2,3,\dots }$  se define

${\displaystyle u_{i}=x_{i}/m}$ 

Algunas Generalizaciones de LCGs

El Generador Congruencial Lineal Simple es un caso particular del Generador Congruencial Lineal (LCG) dado por

${\displaystyle x_{i}=g(x_{i-1},x_{i-2},\dots )\operatorname {mod} m}$ 

donde ${\displaystyle g}$  una función determinista de los ${\displaystyle x_{j}'s}$  con ${\displaystyle 0\leq x_{j}'s\leq m-1}$  y las muestras generadas a ${\displaystyle {\ce {U(0,1)}}}$  están dados por ${\displaystyle u_{i}=x_{i}/m}$ .

Algunos generadores son los siguientes:

• No lineal, por ejemplo, el generador congruencial cuadrático dado por ${\displaystyle x_{i}=(a_{1}x_{i-1}+a_{2}x_{i-1}^{2}+c)\operatorname {mod} m}$ 
• Generador Recursivo Múltiple: ${\displaystyle x_{i}=(a_{1}x_{i-1}+a_{2}x_{i-2}+\cdots +a_{q}x_{i-q})\operatorname {mod} m}$  donde ${\displaystyle a_{1},a_{2},\dots ,a_{q}\in \mathbb {R} }$ .
• Matricial: ${\displaystyle x_{i}=(A_{1}x_{i-1}+A_{2}x_{i-2}+\cdots +A_{k}x_{i-k})\operatorname {mod} m}$  (por ejemplo el generador por defecto de R).
• Generadores de registros desfasados: generadores de bits basados en el lineal múltiple ${\displaystyle m=2}$ ; ${\displaystyle a_{i}}$ , ${\displaystyle x_{i}\in (0,1)}$  (cálculos mediante operaciones lógicas).
• Combinación de generadores:
  • Combinación de salidas: ui=∑u(l)i mod1
  • Barajar salidas…

Análisis de la Calidad de un Generador

Para verificar si un generador tiene las propiedades estadísticas deseadas hay disponibles una gran cantidad de test de hipótesis y métodos gráficos:

• Contrastes genéricos de bondad de ajuste y aleatoriedad.
• Contrastes específicos para generadores aleatorios.

Se trata principalmente de contrastar si las muestras generadas son ${\displaystyle \operatorname {IID} \;U(0,1)}$  (análisis univariante).

Prueba ${\displaystyle \chi ^{2}}$ 

Se divide el intervalo ${\displaystyle [0,1]}$  en ${\displaystyle k}$  subintervalos de misma longitud y se generan ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$ . Para ${\displaystyle j=1,2,\dots ,k}$  sea ${\displaystyle f_{j}}$  el número de ${\displaystyle u_{i}'s}$  que están en el ${\displaystyle j}$ -ésimo subintervalo y sea

${\displaystyle \chi ^{2}={\frac {k}{n}}\sum _{j=1}^{k}\left(f_{j}-{\frac {n}{k}}\right)^{2}}$ 

si ${\displaystyle n}$  es un número muy grande (al menos debe ser mayor o igual a ${\displaystyle 100}$ ) entonces ${\displaystyle \chi ^{2}}$  tendrá aproximadamente una distribución ${\displaystyle \chi _{k-1}^{2}}$  bajo la hipótesis nula ${\displaystyle H_{0}:{\text{las muestras generadas son IID }}U(0,1)}$ . A un nivel ${\displaystyle (1-\alpha )100\%}$  de confianza rechazamos ${\displaystyle H_{0}}$  si ${\displaystyle \chi ^{2}>\chi _{k-1,1-\alpha }^{2}}$ , para valores de ${\displaystyle k}$  suficientemente grandes, se puede utilizar la aproximación

${\displaystyle \chi _{k-1,1-\alpha }^{2}\approx (k-1)\left[1-{\frac {2}{9(k-1)}}+z_{1-\alpha }{\sqrt {\frac {2}{9(k-1)}}}\right]}$ 

Los métodos más avanzados tratan normalmente de contrastar si las ${\displaystyle k}$ -uplas:

${\displaystyle (u_{t+1},u_{t+2},\dots ,u_{t+k-1})}$ , ${\displaystyle t=(i-1)k}$  con ${\displaystyle i=1,2,\dots ,m}$ 

son ${\displaystyle \operatorname {IID} \;U(0,1)}$  (uniformes independientes en el hipercubo; análisis multivariante).

Nos centraremos en los métodos genéricos. Pueden usarse en:

• Evaluación de generadores aleatorios
• Evaluación de generadores de variables aleatorias
• Modelado de entradas de modelos de simulación

Uno de los contrastes más conocidos es el test ji-cuadrado de bondad de ajuste . Aunque si la variable de interés es continua, habría que discretizarla (con la correspondiente perdida de información).

Importante: Empleando los métodos genéricos del modo habitual, desconfiamos del generador si la muestra/secuencia no se ajusta a la distribución teórica (${\displaystyle p}$ -valor ${\displaystyle \leq \alpha }$ ). En este caso además, también se sospecha si se ajusta demasiado bien a la distribución teórica (${\displaystyle p}$ -valor ${\displaystyle \geq 1-\alpha }$ ).

Repetición de Contrastes

Los contrastes se plantean habitualmente desde el punto de vista de la inferencia estadística en la práctica: se realiza una prueba sobre la única muestra disponible. Si se realiza una única prueba, en las condiciones de ${\displaystyle H_{0}}$  hay una probabilidad ${\displaystyle \alpha }$  de rechazarla. En simulación tiene mucho más sentido realizar un gran número de pruebas:

• La proporción de rechazos debería aproximarse al valor de α(se puede comprobar para distintos valores de ${\displaystyle \alpha }$ ).
• La distribución del estadístico debería ajustarse a la teórica bajo ${\displaystyle H_{0}}$ (se podría realizar un nuevo contraste de bondad de ajuste).
• Los ${\displaystyle p}$ -valores obtenidos deberían ajustarse a una ${\displaystyle U(0,1)}$  (se podría realizar también un contraste de bondad de ajuste).

Este procedimiento es también el habitual para validar un método de contraste de hipótesis por simulación.

Véase también

• Algoritmo Fisher-Yates
• Generador de números aleatorios
• Generador pseudoaleatorio de números
• Número aleatorio
• Sucesión de números reales

Referencias

Enlaces externos

• Calcular el área bajo la curva usando números aleatorios

•   Datos: Q12774855