¿Qué es exactamente una semilla en un generador de números aleatorios?

Intenté algunas búsquedas habituales en Google, etc., pero la mayoría de las respuestas que encuentro son algo ambiguas o específicas del idioma / biblioteca, como Python o C ++, stdlib.hetc. Estoy buscando una respuesta matemática agnóstica del lenguaje, no los detalles de una biblioteca.

Como ejemplo, muchos dicen que la semilla es un punto de partida del generador de números aleatorios y la misma semilla siempre produce el mismo número aleatorio. Qué significa eso? ¿Significa que el número de salida es una función determinista de una semilla específica y que la aleatoriedad proviene del valor de la semilla? Pero si ese es el caso, al suministrar la semilla, ¿no estamos nosotros, los programadores, creando la aleatoriedad en lugar de dejar que la máquina lo haga?

Además, ¿qué significa un punto de partida en este contexto? ¿Es esta una forma no rigurosa de decir un elemento del dominio de un mapa ? ¿O estoy haciendo algo mal? $x\in\mathfrak{X}$ $f:\mathfrak{X}\rightarrow\mathfrak{Y}$

random-generation Della
fuente

No me siento calificado para escribir una respuesta, pero es posible que el artículo de Wikipedia sobre Mersenne Twister sea esclarecedor, especialmente la sección sobre inicialización . En resumen, un generador de números pseudoaleatorios como el Mersenne Twister eventualmente repetirá su salida. En el caso de la MT, el período tiene duración 2^19937 − 1. La semilla es el punto de esta secuencia extremadamente larga donde comienza el generador. Entonces sí, es determinista.

IonicSolutions

Un generador de números pseudoaleatorios es una lista fija de números que se repite sin cesar. Donde comienza Tienes que decirlo.

whuber

@whuber Realmente creo que tu comentario sería una gran respuesta.

David Z

Respuestas:

La mayoría de los generadores de números pseudoaleatorios (PRNG) se basan en algoritmos que involucran algún tipo de método recursivo a partir de un valor base que está determinado por una entrada llamada "semilla". El PRNG predeterminado en la mayoría del software estadístico (R, Python, Stata, etc.) es el algoritmo Mersenne Twister MT19937, que se establece en Matsumoto y Nishimura (1998) . Este es un algoritmo complicado, por lo que sería mejor leer el documento en él si desea saber cómo funciona en detalle. En este algoritmo particular, existe una relación de recurrencia de grado , y su semilla de entrada es un conjunto inicial de vectores . El algoritmo utiliza una relación de recurrencia lineal que genera: $n$ $\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}$

x_{n + k} = f (x_{k}, x_{k + 1}, x_{k + m}, r, A),

$\mathbf{x}_{n+k} = f(\mathbf{x}_k, \mathbf{x}_{k+1}, \mathbf{x}_{k+m}, r, \mathbf{A}),$

donde y y son objetos que se pueden especificar como parámetros en el algoritmo. Como la semilla proporciona el conjunto inicial de vectores (y se le dan otros parámetros fijos para el algoritmo), la serie de números pseudoaleatorios generados por el algoritmo es fija. Si cambia la semilla, entonces cambia los vectores iniciales, lo que cambia los números pseudoaleatorios generados por el algoritmo. Esta es, por supuesto, la función de la semilla. $1 \leqslant m \leqslant n$ $r$ $\mathbf{A}$

Ahora, es importante tener en cuenta que este es solo un ejemplo, utilizando el algoritmo MT19937. Hay muchos PRNG que se pueden usar en software estadístico, y cada uno de ellos involucra diferentes métodos recursivos, por lo que la semilla significa algo diferente (en términos técnicos) en cada uno de ellos. Puede encontrar una biblioteca de PRNG Ren esta documentación , que enumera los algoritmos disponibles y los documentos que describen estos algoritmos.

El propósito de la semilla es permitir al usuario "bloquear" el generador de números pseudoaleatorios, para permitir un análisis replicable. A algunos analistas les gusta establecer la semilla utilizando un verdadero generador de números aleatorios (TRNG) que usa entradas de hardware para generar un número inicial de semilla, y luego informa esto como un número bloqueado. Si el usuario original establece e informa la semilla, un auditor puede repetir el análisis y obtener la misma secuencia de números pseudoaleatorios que el usuario original. Si la semilla no está configurada, el algoritmo usualmente usará algún tipo de semilla predeterminada (por ejemplo, del reloj del sistema), y generalmente no será posible replicar la aleatorización.

Reinstalar a Mónica
fuente

+1. Sería bueno agregar lo que (generalmente) sucede si uno no proporciona explícitamente la semilla.

ameba dice Reinstate Monica

@amoeba: El cuarto párrafo de mi respuesta, discute esto brevemente.

BruceET

Si bien esto responde a los conceptos básicos de la pregunta, no toca el hecho de por qué necesitamos esto en las simulaciones. Es muy difícil producir una aleatoriedad VERDADERA, ¡y cuando lo tienes no puedes reproducir la respuesta original! Ingrese el PNRG ... con todos sus problemas.

Paul Palmpje

@amoeba: Según lo solicitado, he agregado un párrafo adicional para desarrollar esto.

Vuelva a instalar Mónica

Gracias. "Semilla predeterminada" suena un poco como si siempre fuera el mismo valor predeterminado de semilla; lo que quise decir es que generalmente la semilla se toma del reloj del sistema. Esto creo que es bueno saberlo.

ameba dice Reinstate Monica

Primero, no hay aleatoriedad verdadera en los "números aleatorios" generados por computadora de hoy. Todos los generadores pseudoaleatorios usan métodos deterministas. (Posiblemente, las computadoras cuánticas cambiarán eso).

La tarea difícil es idear algoritmos que produzcan resultados que no puedan distinguirse significativamente de los datos que provienen de una fuente verdaderamente aleatoria.

Tiene razón en que establecer una semilla lo inicia en un punto de partida conocido particular en una larga lista de números pseudoaleatorios. Para los generadores implementados en R, Python, etc., la lista es enormemente larga. El tiempo suficiente para que ni siquiera el proyecto de simulación factible más grande exceda el "período" del generador para que los valores comiencen a reciclarse.

En muchas aplicaciones ordinarias, la gente no establece una semilla. Luego, una semilla impredecible se recoge automáticamente (por ejemplo, de los microsegundos en el reloj del sistema operativo). Los generadores pseudoaleatorios en uso general han sido sometidos a baterías de pruebas, en gran parte consistentes en problemas que han resultado ser difíciles de simular con generadores insatisfactorios anteriores.

Usualmente, la salida de un generador consiste en valores que no son, para propósitos prácticos, distinguibles de números elegidos verdaderamente al azar de la distribución uniforme enLuego, esos números pseudoaleatorios se manipulan para que coincidan con lo que uno obtendría al azar de otras distribuciones como binomial, Poisson, normal, exponencial, etc. $(0,1).$

Una prueba de un generador es ver si sus pares sucesivos en 'observaciones' simuladas como realmente parecen estar llenando el cuadrado de la unidad al azar. (Hecho dos veces a continuación). El aspecto ligeramente veteado es el resultado de la variabilidad inherente. Sería muy sospechoso obtener una trama que se viera perfectamente uniformemente gris. [En algunas resoluciones, puede haber un patrón de muaré regular; cambie la ampliación hacia arriba o hacia abajo para deshacerse de ese efecto falso si ocurre.] $\mathsf{Unif}(0,1)$

set.seed(1776);  m = 50000
par(mfrow=c(1,2))
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
par(mfrow=c(1,1))

A veces es útil establecer una semilla. Algunos de estos usos son los siguientes:

Al programar y depurar es conveniente tener resultados predecibles. Muchos programadores ponen una set.seeddeclaración al comienzo de un programa hasta que se escriben y se depuran.
Al enseñar sobre simulación. Si quiero mostrarles a los estudiantes que puedo simular tiradas de un dado justo usando la samplefunción en R, podría hacer trampa, ejecutar muchas simulaciones y elegir la que más se acerque a un valor teórico objetivo. Pero eso daría una impresión poco realista de cómo funciona realmente la simulación.

Si configuro una semilla al comienzo, la simulación obtendrá el mismo resultado cada vez. Los estudiantes pueden corregir su copia de mi programa para asegurarse de que proporcione los resultados previstos. Luego pueden ejecutar sus propias simulaciones, ya sea con sus propias semillas o dejando que el programa elija su propio punto de partida.

Por ejemplo, la probabilidad de obtener el total de 10 al tirar dos dados justos esCon un millón de experimentos de 2 dados, debería obtener una precisión de dos o tres lugares. El margen de error de simulación del 95% es de aproximadamente
$3 / 36 = 1 / 12 = 0.08333333.$
$2 \sqrt{(1 / 12) (11 / 12) / 10^{6}} = 0.00055.$
```
set.seed(703);  m = 10^6
s = replicate( m, sum(sample(1:6, 2, rep=T)) )
mean(s == 10)
[1] 0.083456         # aprx 1/12 = 0.0833
2*sd(s == 10)/sqrt(m)
[1] 0.0005531408     # aprx 95% marg of sim err.
```
Al compartir análisis estadísticos que implican simulación. Hoy en día, muchos análisis estadísticos implican alguna simulación, por ejemplo, una prueba de permutación o una muestra de Gibbs. Al mostrar la semilla, permite a las personas que leen el análisis replicar los resultados exactamente, si así lo desean.
Al escribir artículos académicos relacionados con la aleatorización. Los artículos académicos generalmente pasan por múltiples rondas de revisión por pares. Un diagrama puede usar, por ejemplo, puntos aleatorizados aleatoriamente para reducir el trazado excesivo. Si los análisis deben modificarse ligeramente en respuesta a los comentarios de los revisores, es bueno que una fluctuación de fase particular no relacionada no cambie entre las rondas de revisión, lo que puede ser desconcertante para los revisores particularmente quisquillosos, por lo que debe establecer una semilla antes de la fluctuación.

BruceET
fuente

Muy bien, +1. Me tomé la libertad de agregar un cuarto punto.

S. Kolassa - Restablece a Mónica el

Entonces, ¿quiere decir que un generador de números de pseudodrom básicamente almacena una secuencia periódica de números aleatorios (distribuidos uniformemente en [0, 1]) y una semilla es simplemente un índice de la secuencia? Entonces, ¿significa que el número aleatorio generado es una función determinista de la semilla?

Della

No necesita una computadora cuántica para usar fenómenos cuánticos para tener un generador aleatorio ( en.wikipedia.org/wiki/Hardware_random_number_generator )

Guiroux

@Della. Tienes esencialmente la idea correcta. Pero, por favor, comprenda que en la práctica el "período" tiene que ser realmente enorme. (No importa qué tan grande sea su proyecto de simulación, no desea que se repita). Por ejemplo, IonicSolutions comenta después de la Q que el generador Mersenne Twilster tiene un período algo más grande de lo que puedo visualizar fácilmente. // Si conoce la semilla, puede producir la secuencia pseudoaleatoria desde allí. // Se han usado generadores para encriptar mensajes. Pero los estándares para generadores seguros para encriptación son diferentes de los estándares para generadores para simulación de probabilidad.

2^{19937} - 1,

$2^{19937}-1,$

BruceET

@Guiroux. La posibilidad de que intentara mencionar las computadoras cuánticas era tener verdaderos generadores de números aleatorios tan rápido como los generadores pseudoaleatorios de hoy. En la década de 1950, se utilizaron fuentes de números aleatorios "verdaderos" para la aleatorización en el diseño experimental y para simulaciones de problemas (lentas, limitadas). Quizás vea Million Random Digits .

BruceET

TL; DR;

Una semilla generalmente le permite reproducir la secuencia de números aleatorios. En ese sentido, no son números aleatorios verdaderos, sino "números pseudoaleatorios", por lo tanto, un generador de PNR (PNRG). ¡Son una ayuda real en la vida real!

Un poco más de detalle:

Prácticamente todos los generadores de números "aleatorios" implementados en lenguajes de computadora son generadores de números pseudoaleatorios. Esto se debe a que dado un valor inicial (===> la semilla) siempre proporcionarán la misma secuencia de resultados pseudoaleatorios. Un buen generador producirá una secuencia que no se puede distinguir, en términos estadísticos, de una secuencia aleatoria verdadera (lanzar un dado verdadero, una moneda verdadera, etc.).

En muchos casos de simulación, desea tener una verdadera experiencia "aleatoria". Sin embargo, también desea poder reproducir sus resultados. ¿Por qué? Bueno, al menos los reguladores están interesados en esa cosa peculiar.

Hay mucho para sumergirse. Las personas incluso analizan la "mejor" semilla aleatoria. En mi opinión, esto invalida su modelo ya que no pueden manejar el comportamiento aleatorio "verdadero", o su PRNG no es apto para su implementación. La mayoría de las veces simplemente no hacen suficientes simulaciones, pero toman tiempo.

Ahora imagine un "verdadero" RNG. Uno podría implementar esto basado en un tipo de aleatoriedad en la máquina. Si solo toma una semilla aleatoria (por ejemplo, el tiempo ahora), crea una especie de punto de partida aleatorio, pero la aleatoriedad de la secuencia aún depende del algoritmo para determinar los siguientes números. Esto es más importante que el punto de partida en la mayoría de los casos, ya que la distribución de resultados determina el "resultado" real. Si su secuencia fuera verdaderamente aleatoria, ¿cómo implementaría esto? Se puede decir que los tics de reloj de una computadora son deterministas y, de lo contrario, probablemente mostrarán mucha autocorrelación. ¿Entonces que puedes hacer? La mejor apuesta hasta ahora es implementar un PNRG sólido.

¿Computación cuántica? No estoy seguro de que eso lo arregle.

Paul Palmpje
fuente