¿Cómo es aleatorio el generador de fibonacci retrasado?

Question

No consigo. Si tiene una longitud fija, elegir los retardos y la modificación una y otra vez dará el mismo número, ¿no?

Answer 1

Todo depende de la semilla. La mayoría de los generadores de números aleatorios dan la misma secuencia de números para un valor de semilla fijo.

Answer 2

Es aleatorio de la misma manera que cualquier generador de números pseudoaleatorios, es decir, nada.

Sin embargo, fibonacci retardado (y todos los PRNG de desplazamiento de realimentación lineal) mejoran en un generador congruente lineal básico al aumentar el tamaño del estado. Es decir, el siguiente valor depende de varios valores anteriores, en lugar de solo el anterior inmediato. Combinado con una semilla decente, debería poder obtener resultados bastante decentes.

Editar:

Desde su puesto, no está claro que entiende que el estado subyacente se almacena en un registro de desplazamiento, lo que significa que no es estático, sino actualizada (desplazando cada valor de un lugar a la izquierda, soltando el valor más a la izquierda y añadiendo el valor más reciente en el lado derecho) después de cada sorteo. De esta forma, se evita dibujar el mismo número sobre & una vez más (para la mayoría de los valores iniciales, al menos).

Answer 3

Para ser precisos, el Fibonacci rezagado es un pseudo-generador de números aleatorios. No es cierto al azar, pero es mucho mejor que, por ejemplo, el linear congruential generator (el generador estándar para C++, Java, etc.) más comúnmente utilizado. No estoy seguro de por qué crees que volverá a dar el mismo número, pero es verdad que como todos los generadores de números pseudoaleatorios, tiene un período después del cual la secuencia de números se repetirá nuevamente.

El multiplicador de GRS tiene un período de (2^k - 1)*2^(M-3). Para parámetros prácticos, esto es realmente bastante grande (el período de LCG es solo M).

La única pega con LFG es que el procedimiento de inicialización es muy complejo, y las matemáticas detrás de él están incompletas. Lo mejor es consultar la literatura para una buena elección de los parámetros y el procedimiento recomendado para la siembra adecuada.

Como ilustración, un LFG multiplicativo con los parámetros (j=31, k=52) y el módulo m=2^32 está sembrado con una matriz de 52 números de 32 bits.

---

referencias adicionales:

• http://sprng.fsu.edu/Version4.0/generators.html

  más detalles sobre este generador y los algoritmos de siembra se pueden encontrar en los documentos de Mascagni, et al.

Answer 4

No es al azar, su pseudorandom

De esta http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

generadores de Fibonacci rezagados tienen un plazo máximo de (2^k - 1) * 2^(M-1) si se usa la suma o la resta, y (2^k-1) si se usan operaciones exclusivas u para combinar los valores previos. Si, por otro lado, se usa la multiplicación, el período máximo es (2^k - 1) * 2^(M-3), o 1/4 del período del caso aditivo.

Por lo tanto, dado un cierto valor inicial, la secuencia de valores de salida es predecible y repetible, y tiene un ciclo. Se repetirá si espera lo suficiente, pero el ciclo es bastante grande.

Para un observador que no conoce el valor de inicialización, la secuencia parece ser bastante aleatoria, por lo que puede ser útil como fuente de "aleatoriedad" para simulaciones y otras situaciones donde no se requiere aleatoriedad real.

Answer 5

Los generadores de números aleatorios a menudo son funciones uno a uno donde para cada entrada hay una salida constante. Para hacerlo "aleatorio", debe alimentarlo con una semilla (que debe ser "aleatoria"), como la hora del sistema o los valores de las ubicaciones de la memoria de la computadora, por ejemplo.

Si se está preguntando por qué no usa directamente la semilla (el tiempo, etc.), es porque el tiempo es secuencial (1,2,3,4) mientras que la mayoría de los generadores de números pseudoaleatorios escupieron números que parecen aleatorios (8, 27, 13, 1). De esta forma, si está generando números pseudoaleatorios en un bucle (lo cual sucede muy rápido), no solo obtiene {1,2,3,4} ...