Tengo una pregunta acerca de mi comprensión de un artículo de B. D. McCullough (2008) acerca de Excel es la aplicación de la Wichmann-Hill generador de números aleatorios (1982).
Primero, un poco de contexto
El Wichmann-Hill algoritmo es dado en 183 aquí. Como se puede ver en el programa de los comentarios, es simplemente tres lineal congruential generadores (LCG) se combinan para formar una sola RNG:
$$ix = 171 \times ix \mod p\\ iy = 172 \times iy \mod q\\ iz = 170 \times iz \mod r$$
Con $p=30269, q=30307, r=30323$
A continuación, los tres valores enteros se combinan para producir un (pseudo-aleatorio) número real $x$$[0,1]$, con
$$x=\frac{ix}{p}+\frac{iy}{q}+\frac{iz}{r} \mod 1$$
El programa es un poco más complicado debido a que está diseñada para ejecutarse en máquinas que no pueden representar a $172\times30306=5212632$ (por ejemplo, máquinas de 16 bits, que donde no es raro entonces), pero es el equivalente a las fórmulas anteriores.
En un posterior artículo (1986), H. Zeisel señaló que las tres LCG puede reducirse a una sola, gracias al teorema del resto chino:
$$u = a \times u \mod m$$
Con $a=16555425264690$$m=pqr=27817185604309$, e $a$ se encuentran resolviendo la siguiente (que es donde teorema del resto chino):
$$a\equiv171\pmod{30269}\\ un\equiv172\pmod{30307}\\ un\equiv170\pmod{30323}$$
Observe que $30269$, $30307$ y $30323$ son todos números primos.
La reclamación
Ahora, la demanda en McCullough del artículo es que Microsoft no implementar el Wichmann-Hill correctamente, y para demostrar esto, uno tiene que mostrar los sucesivos valores calculados mediante Excel no están de acuerdo con los valores calculados mediante una implementación de referencia de la WH RNG.
Desde Excel no dar acceso a la semilla, la semilla se calcula mediante la multiplicación de un número aleatorio devuelve Excel, por $m$, para obtener la semilla (véase la sección 3 del artículo).
No entiendo esto.
Si he entendido bien, si se supone que el WH RNG ha sido implementado de acuerdo con el algoritmo original 183, uno no puede recuperar la semilla por simplemente multiplicar por $m$. Imagine, por ejemplo, la semilla es $u=1$ en Zeisel de la formulación. Entonces trivialmente, la semilla es $ix=iy=iz=1$ en TAN 183 de la formulación. Pero el número aleatorio, entonces debe ser
$$x=\frac1p+\frac1q+\frac1r\simeq0.000099011$$
Observe el "módulo 1" no tiene ningún efecto en este caso.
Y multiplicando $x$$m$, se encuentra
$$mx=pqr\left(\frac1p+\frac1q+\frac1r\right)=2754208631\neq1$$
Así que en realidad no recuperar la semilla.
La razón no es el mismo es que, mientras que uno puede cambiar de ida y vuelta desde 183 a Zeisel las semillas por el resto chino thorem, la combinación en el último paso (dividir cada una de las $ix, iy, iz$ por los correspondientes módulos, y tomar la suma modulo $1$), no es equivalente a dividir el Zeisel semilla $u$ por el "combinado" módulo de $m=pqr$. Habría que recuperar primero $ix, iy, iz$, tomando respectivamente
$$ix=u\mod p\\iy=u \mod q\\iz=u \mod r$$
Y sólo entonces para terminar con 183 combinación. Pero esto no es fácil de revertir, como es necesario para el propósito de la comprobación de la conformidad de Excel del RNG.
Mi pregunta
En primer lugar, me gustaría saber si mi razonamiento es correcto, lo que significaría que hay un error en el artículo. No estoy acostumbrado a "atacar" a un artículo publicado, y en la mayoría de los casos, no iba a encontrar este agradable a todos. Sin embargo, dado el tono irónico del artículo, me gustaría encontrar lugar encantador que se basa en una suposición equivocada. Eso es la "lengua en la mejilla", parte de la situación.
Más en serio, me gustaría saber si hay alguna manera sencilla de encontrar la semilla de $(ix,iy,iz)$, dado a uno o varios de los sucesivos valores aleatorios de la (correcta) Wichmann-Hill. No parece obvio, como McCullough él mismo comentó en la misma sección 3 de su artículo. Que me permitiría evaluar la exactitud de Excel RNG (no estoy seguro de Excel utiliza todavía el Wichmann-Hill, de todos modos).
Observe que Wichmann y Hill, han publicado una versión revisada del generador (2005), disponible de forma gratuita en la MOROSIDAD del sitio web. De acuerdo con el enlace al sitio de Microsoft anteriormente, Excel aplicado a la anterior, en Excel 2003.
Reflexión: el problema es aún más difícil de lo esperado. En el artículo se establece en la sección 2 de Excel se produce al azar los números reales de precisión simple, por lo tanto hay una pérdida de precisión. Sin embargo, es bien sabido que un buen generador de números aleatorios satisface una propiedad importante: dos casi iguales las semillas dan números aleatorios que pueden ser muy diferentes. Por lo tanto, a sabiendas de que sólo un único aproximado del número al azar del generador puede no ser suficiente para recuperar la semilla, por lo que podemos esperar que vamos a necesitar varios en una fila.
Editar
Como sucede, Ronald A. Thisted, de la universidad de Chicago, se ha trabajado en un segundo volumen de sus Elementos de Computación Estadística. El proyecto de notas, de fecha de enero de 2005, se puede encontrar aquí. El Wichmann-Hill generador es evocado en la página 9, que termina con
Sin embargo, el uniforme número aleatorio devuelto por el Wichmann-Hill el algoritmo no es simplemente el cociente de la única salida del generador a su módulo. Mientras que las propiedades de éste sería fácilmente estudiado, no ha habido estudios analíticos de la real Wichmann-Hill generador. Sin embargo, parece funcionar muy bien en en la práctica.
Esa es una respuesta definitiva a mi primera pregunta, pero yo ya estaba bastante seguro de esto. Sin embargo, todavía estoy perdido en la segunda pregunta, acerca de la realidad "invertir" el generador.
