Generador de números aleatorios

Dos dados rojos con números aleatorios.

Un generador de números aleatorios (RNG por sus siglas en inglés) es un dispositivo informático o físico diseñado para producir secuencias de números sin orden aparente.

Algoritmos

Los algoritmos para la generación de valores uniformemente distribuidos están presentes en todas las calculadoras y lenguajes de programación, y suelen estar basados en congruencias numéricas del tipo:

${\displaystyle x_{n+1}\equiv (ax_{n}+c){\pmod {m}}}$

El éxito de este tipo de generadores de valores de una variable aleatoria depende de la elección de los cuatro parámetros que intervienen inicialmente en la expresión anterior:

• El valor inicial o semilla: ${\displaystyle x_{0}}$
• La constante multiplicativa: ${\displaystyle a}$
• La constante aditiva: ${\displaystyle c}$
• El número ${\displaystyle m}$ respecto al cual se calculan los restos

Estos cuatro valores deben ser números enteros no negativos y que cumplan la siguiente condición: ${\displaystyle x_{0},a,c<m}$.

La mayor parte de los generadores de números aleatorios son, en realidad, pseudoaleatorios; se calcula (o introduce internamente) un valor x₀, que llamaremos semilla, y, a partir de él, se van generando x₁, x₂, x₃, ...

Siempre que se parta de la misma semilla, se obtendrá la misma secuencia de valores.

Por la condición anterior, es evidente que todos los valores generados por este procedimiento son números enteros entre 0 y ${\displaystyle m-1}$. El número máximo de cifras distintas que pueden obtenerse con el procedimiento descrito es ${\displaystyle m}$, así que llegará un momento en que el primer número generado se repetirá produciéndose un ciclo.

El ciclo dónde inevitablemente caerá el generador interesa que sea de la mayor longitud posible (como máximo ${\displaystyle m}$), para evitar que se repitan pronto los valores aleatorios. Por ejemplo, para los valores ${\displaystyle a=3}$, ${\displaystyle c=5}$, ${\displaystyle x_{0}=2}$ y ${\displaystyle m=32}$ se obtiene la siguiente secuencia de valores:

2-11-6-23-10-3-14-15-18-27-22-7-26-19-30-31-2-11-6

La secuencia generada tiene como longitud 16 números (el número generado en la decimoséptima posición es el 2 inicial, por lo que toda la secuencia se repite a partir de ahí), muy inferior a la longitud máxima que podría tener (${\displaystyle m}$=32). Determinadas elecciones de parámetros del generador (${\displaystyle x_{0}}$ , ${\displaystyle a}$ , ${\displaystyle c}$ y ${\displaystyle m}$) conducen a ciclos de amplitud máxima.

• Si c≠0:
  • ${\displaystyle m.c.d.(c,m)=1}$
  • ${\displaystyle a\equiv 1{\pmod {p}}}$ para cada primo p de m
  • ${\displaystyle a\equiv 1{\pmod {4}}}$ si 4 es divisor de m

• Si c=0:
  • m es primo
  • ${\displaystyle a^{m-1/p}\equiv 1{\pmod {m}}}$ La condición es que NO SEA congruente para cada factor primo p de m-1.

Por ejemplo, tomando como valores ${\displaystyle m=2^{5}=32}$, ${\displaystyle a=5}$, ${\displaystyle x_{0}=1}$ y ${\displaystyle c=3}$ se obtiene la siguiente secuencia de números, que tiene longitud máxima:

1-8-11-26-5-28-15-14-9-16-19-2-13-4-23-22-17-24-27-10-21-12-31-30-25-0-3-18-29-20-7-6-1

El estándar POSIX C define para la función de generación de números pseudoaleatorios los valores de ${\displaystyle c=12345}$, ${\displaystyle m=32768}$ y ${\displaystyle a=1103515245}$.

Hay quien dice que recientemente se ha descubierto que es posible generar verdaderos números aleatorios mediante software^[1]​^[2]​^[3]​, pero algunos expertos indican que, por mucho que estos números parezcan realmente aleatorios, en realidad no lo son^[4]​.

Referencias

1. True random numbers generator C++
2. CPU Time Jitter Based Non-Physical True Random Number Generator
3. Software Random Number Generation Based on Race Conditions
4. https://webs.um.es/mpulido/miwiki/lib/exe/fetch.php?media=wiki:simt1b.pdf, «El método más conveniente y más fiable de generar números aleatorios es utilizar algoritmos determinísticos que posean alguna base matemática solida. Estos algoritmos producen una sucesión de números que se asemeja a la de una sucesión de realizaciones de variables aleatorias iid U(0, 1), aunque realmente no lo sea. Es por ello que este tipo de números se denominan pseudo-aleatorios y el algoritmo que los produce se llama generador de números pseudo-aleatorios.» El concepto de iid U(0,1) está definido en el PDF.

Bibliografía

• Alberto, Marva; Schwer, Ingrid; Cámara, Viviana; Fumero, Yanina (2005). Matemática Discreta. Universidad Nac. del Litoral. p. 295. ISBN 9789875084315. 
• Blanco Castañeda, Liliana (2004). Probabilidad. textos. Univ. Nacional de Colombia. p. 295. ISBN 9789587014495. 

Enlaces externos

• Generador de números aleatorios en línea Archivado el 24 de febrero de 2011 en Wayback Machine.
• Generador simple de números aleatorios en línea
• Generador de números aleatorios

• Datos: Q61722412