¿' (Pseudo)-funciones al azar ' por la siembra de PRNGs?

Question

Tengo una aplicación que quiere controlable funciones aleatorias de$\mathbb{Z}^2$$\mathbb{Z}^3$$2^{32}$, donde por controlable yo, básicamente, significa que seedable por algunos parámetros (por ejemplo, en el orden de 3 a 5 enteros de 32 bits) de tal manera que las mismas semillas se producen siempre las mismas funciones. La manera más obvia de hacerlo (para el caso bidimensional, dicen) parecen ser calcular el valor en algún punto de $(x,y)$ mediante el uso de $x$, $y$, y la semilla de parámetros como semillas para algo como un LFSR de generador o de un Mersenne Twister, a continuación, ejecutar el generador de números aleatorios para un número fijo de pasos y tomar el valor resultante como el valor de la función en ese punto.

Mi pregunta es, ¿cómo puedo estar seguro de que este procedimiento no mantener demasiado correlación entre los 'puntos semilla', y es que hay un análisis directo o incluso sólo algunos lineamientos generales para cuántas iteraciones sería necesario eliminar esa correlación? Mi primera vuelta-de-la-envoltura conjetura sería que en cada iteración aproximadamente duplica la descorrelación entre determinados valores de las semillas, por lo que el 32 iteraciones sería necesario para alcanzar el requisito de descorrelación en un rango de $2^{32}$ de los valores (y en la práctica probablemente me haga doble a 64 iteraciones), pero eso es estrictamente una conjetura y cualquier análisis adecuado sería bienvenida!

Editado por la aclaración: Para describir más a fondo el tema, puede ser de muestreo de esta función random $f$ (para algunos de semilla de parámetros) en valores arbitrarios, y la necesidad de las muestras a ser idénticos entre pasadas; así, por ejemplo, si la primera aplicación calcula $f(0, 0)$, $f(437, 61)$, $f(-23, 129)$, y, a continuación,$f(5,3)$, y una segunda (potencialmente concurrentes) de la aplicación calcula el $f(1,0)$ y, a continuación, $f(5,3)$tanto pasa necesidad de encontrar el mismo valor de $f$$(5,3)$. Yo también puede ser de muestreo $f$ en puntos arbitrarios, así que me gustaría que la evaluación toma constante de tiempo (y, en particular, la evaluación de $f(x,y)$ no debe tomar el tiempo lineal en $x+y$).

Answer 1

Tenga en cuenta que cuando un LFSR se utiliza para generar una secuencia de $+1\;/-1$ de los valores, la correlación entre la secuencia y en cualquier momento desplazado a la versión de que la secuencia está cerca de cero: (suma de$i = 0$$N-1$$a[i]a[i+k]$) $N$ si $k$ es un múltiplo de a $N$ o $-1$ lo contrario.

El estado inicial de un LFSR tiene un uno-a-uno de mapeo para el cambio de hora -- esto es análogo a un problema del logaritmo discreto en campos de Galois; dado un cambio de tiempo k, es fácil encontrar el estado inicial de un LFSR ($\mathcal{O}(log(k))$, creo que, como se acaba de informática de la exponenciación en el correspondiente campo de Galois), pero dado el estado inicial de un LFSR, es difícil encontrar el cambio de hora k en algo más corto de $\mathcal{O}(k)$. Por lo que su PRNG podría ser un LFSR con muy largo período, por ejemplo de 64 bits o mayor, y la "semilla" podría ser un cambio de tiempo utilizado para derivar un diferente estado inicial.

Tan lejos como $2$ - o $3$ - o $k$-dimensiones de asignación, intercalar los bits de las coordenadas, y el uso de una función de hash para asignar los bits de un número entero para su uso en la obtención de LFSR semillas.

No estoy seguro de qué tipo de correlación que usted está buscando para evitar que entre funciones. (por ejemplo, la correlación en un sentido estadístico, o de cifrado de la independencia, por ejemplo un PRNG no puede ser utilizado para predecir la futura salida de otro).

Answer 2

Esto no estrictamente responder a su pregunta, pero puede ser demasiado largo para un comentario. =)

Yo creo que usted debería reconsiderar su enfoque. La mayoría de los generadores de números aleatorios son diseñados para ser cabeza de serie de una vez, y que devuelva una secuencia de "al azar" de los números, tan cerca independientes y distribuidos de manera uniforme como sea posible. No creo que hay muchos resultados sobre la correlación de la 64ª elemento de la secuencia de las diferentes semillas.

También, (al menos en las implementaciones sé) el período de que el algoritmo es mucho mayor que el número de posibles semillas. Si usted tiene a la reutilización de las semillas en su caso, podría introducir correlaciones que son evitables.

En lugar de precomputing toda la cuadrícula, usted podría obtener un valor aleatorio just-in-time y guárdelo como referencia para el futuro, el ahorro de memoria si no el acceso a cada nodo.