Tasa de errores falsos en una prueba de Pearson, cuando la aproximación por $\chi^2$ ¿la distribución no es válida?

Question

La cuestión se plantea en un contexto criptográfico que implica una prueba reguladora de una fuente física o de bits aleatorios, con la hipótesis nula de que son independientes e insesgados. $n$ se extraen muestras de 4 bits ( $n=128$ o $80$ ), el número de muestras $O_i$ en cada una de las 16 franjas se cuenta, y se supone que la fuente es defectuosa si $$65.0<\sum\frac{(O_i-n/16)^2}{n/16}$$

El reglamento aprobado [KS2011] Una propuesta para: Clases de funcionalidad para generadores de números aleatorios, versión 2.0 , artículo 408 da una tasa de falsos errores de $3.8\cdot 10^{-7}$ para $n=128$ . El segundo refrendo [AIS31V1] Una propuesta para: Clases de funcionalidad y metodología de evaluación para generadores de números aleatorios verdaderos (físicos), versión 3.1 En el ejemplo E.6, se obtiene la misma tasa de errores falsos para $n=80$ . Tanto mi intento de cálculo exacto como la simulación de Monte-Carlo sugieren que el valor de la tasa de error falso es correcto sólo en [AIS31V1], y la justificación dada (aproximación por el $\chi^2$ lo que daría una tasa de falsos errores de $3.4\cdot 10^{-8}$ ) inutilizable para obtener el valor correcto.

Por lo tanto, pregunto cómo derivar directamente la tasa de error falso para esta prueba, preferiblemente con una referencia autorizada; entonces, con la esperanza de explicar una tasa de error mucho más alta observada en la práctica, el efecto esperado en la tasa de error falso de un ligero sesgo en los bits de origen (por ejemplo, si los bits se suponen independientes con media $0.5+\epsilon$ ).

---

Actualización: Entiendo por qué la aproximación por un $\chi^2$ no funciona; cómo puedo hacer simulaciones de Monte-Carlo; y cómo en principio puedo calcular exactamente las probabilidades de que la prueba falle (para $\epsilon=0$ mi código C que cuenta las probabilidades exactas de cada valor posible del resultado de la prueba es utilizable para $n$ múltiplo de $16$ hasta $160$ (con resultados que no se contradicen con las simulaciones). Los problemas son que me gustaría tener referencias; y este enfoque exacto choca con un muro computacional para $\epsilon\ne0$ .

Esto muestra mis resultados provisionales para la tasa de falsos errores (para $\epsilon=0$ ) en función del umbral, para diferentes $n$ y por el $\chi^2$ aproximación de la distribución.

Answer 1

Creo que la cuestión central de la discrepancia entre la tasa citada y la real (simulada) surge porque la asintótica $\chi^2_{15}$ es una pésima aproximación a las colas de la distribución muestral. Puede funcionar bien cerca de su centro (alrededor de 15, más o menos 5), pero llevarlo a probabilidades de cola muy pequeñas es sencillamente inapropiado. Por la ley de Murphy, las probabilidades se ponen en el lado malo, es decir, la aproximación te da algo que es demasiado pequeño. Tienes que tomar aproximaciones de orden superior, como las aproximaciones de punto de silla, para obtener mejor estas probabilidades de cola; estoy seguro de que existen algunas para esta prueba de Pearson, pero no puedo señalar ninguna de inmediato. Si tienes mucha potencia de cálculo a tu disposición (como podría ser), podrías intentar forzar el cálculo de la probabilidad multinomial que te daría la respuesta exacta.

Si los bits están fuera de lugar por $\epsilon$ , entonces la papelera con $k$ y $4-k$ ceros tiene la probabilidad de $(0.5+\epsilon)^k (0.5-\epsilon)^{4-k}$ . Con un poco de esfuerzo, probablemente se pueda derivar el parámetro de no centralidad para el correspondiente distribución chi-cuadrado no central . Mi conjetura, de la parte superior de mi cabeza, es que será la forma cuadrática con el vector dado por las diferencias de las medias "verdaderas" anteriores frente a 0,5, y la inversa de la matriz de covarianza multinomial en el medio. Este es un trabajo tedioso pero relativamente sencillo, típico del análisis de potencia. El chi-cuadrado no central tiene más masa a la derecha, por lo que la tasa de error subirá con estos $\epsilon$ sesgos. Actualización : Es aplicable para la situación desplazada siempre que el chi-cuadrado central sea aplicable para la situación central, pero también hay pruebas de que funciona un poco mejor en muestras finitas para la situación central, también, cuando el estadístico de prueba tiene un sesgo de $O(1/n)$ . Muchos de los estadísticos de las pruebas de relación de probabilidad tienen un sesgo de este tipo, que generalmente se rectifica con la corrección de Bartlett. La prueba de Pearson también puede tener este tipo de sesgo, y el chi-cuadrado no central podría ayudar, aunque de nuevo ayudará sobre todo en el centro de la distribución, y menos en las colas.

Perdona que sólo te dé indicaciones, no las respuestas definitivas. Estas últimas puede existen por ahí, pero si usted, que es el experto en su campo, no está familiarizado con ellas, lo más probable es que no haya ninguna.