¿Cuántas veces tiro un dado injusto para determinar su sesgo?

Question

Esta pregunta proviene de la seguridad informática, pero la destilaré en una pregunta de probabilidad:

Tengo un troquel sesgado con 96 caras. 95 caras son equiprobables, cada una tiene un 1% de posibilidades de salir hacia arriba. El lado restante, el lado X, tiene una probabilidad del 5%.

Todos los lados mira idéntico; quiero identificar el lado X. Mi mejor estrategia es, obviamente, tirar un montón de veces y tomar la mayoría, pero mi pregunta es la siguiente: ¿cuántas tiradas son necesarias hasta que Pr{X sea el resultado mayoritario} > p para cualquier p > 1/2 dado?

Answer 1

Hay una forma de aproximar la respuesta utilizando la teoría de la información. Dejemos que $X$ sea la variable que representa el lado, y que $D$ ser el resultado de una tirada. Cada tirada te dice que mucha información sobre $X$ : $$ I(X;D) = H(D) - H(D|X) = \log 96 + 95 \cdot 0.01 \log 0.01 + 0.05 \log 0.05. $$ Como aproximación, la información obtenida de las diferentes tiradas es aditiva; ciertamente, como mucho es aditiva. Dado que $H(X) = \log 96$ (ya que no tiene ninguna creencia a priori sobre $X$ ), el número de rollos necesarios es al menos $$ \frac{H(X)}{I(X;D)} \approx 115. $$

---

Otra forma de enfocar la misma cuestión es la siguiente. Supongamos que se lanza el dado $N$ tiempos. El lado bueno surgió aproximadamente $N/20$ veces, y todos los demás subieron $\mathrm{Bin}(N,0.01) \approx \mathcal{N}(0.01N,0.0099N)$ . Así que queremos que la probabilidad de que dicha variable normal sea mayor que $N/20$ sea menor que $1/95$ (ya que hay $95$ tales variables; estamos ignorando su dependencia). Esto es $$\frac{0.05N - 0.01N}{\sqrt{0.0099N}} \approx 0.4\sqrt{N}$$ desviaciones estándar. Mirando una tabla, necesitamos aproximadamente $2.3$ desviaciones estándar para obtener una probabilidad de $1/95$ , por lo que necesitamos $$N \approx (2.3/0.4)^2 = 33. $$ Por supuesto, esta estimación es bastante aproximada (ni siquiera coincide con nuestro supuesto límite inferior anterior).

---

La estimación del párrafo anterior es particularmente problemática ya que en este rango la convergencia a la distribución normal es bastante mala (la expectativa es muy pequeña, aproximadamente $1$ ). En este régimen, la probabilidad es en realidad aproximadamente poissoniana. Estimemos la probabilidad de éxito cuando $N=100$ utilizando esta aproximación. El lado correcto va a aparecer aproximadamente $5$ tiempos. Cada lado va a aparecer $P(1)$ veces, por lo que va a ser tan grande como $4$ con probabilidad $$ 1 - e^{-1} \sum_{t=0}^4 \frac{1^t}{t!} \approx 0.00366. $$ Así que el número esperado de "contendientes" es $$ 0.00366 \cdot 95 \approx 0.35.$$ Asumiendo la independencia, la probabilidad de que no haya contendientes es aproximadamente $$ (1 - 0.00366)^{95} \approx 0.706. $$ Esta aproximación sólo se ve reivindicada a grandes rasgos por los experimentos que se realizan a continuación.

Para encontrar una mejor aproximación, vamos a tener en cuenta el $P(5)$ distribución del histograma de $X$ : $$ e^{-5} \sum_{H=0}^\infty \frac{5^H}{H!} \left(e^{-1} \sum_{t=0}^{H-1} \frac{1}{t!} \right)^{95} \approx 0.527. $$ Esto se ajusta mucho mejor a los resultados que aparecen a continuación.

---

Por último, aquí están los resultados experimentales de un millón de ensayos, junto con la aproximación de Poisson:

$$ \begin{array}{r|c|c} N & \text{Experiment} & \text{Approx} \\\hline 50 & 0.272323 & 0.274900 \\ 100 & 0.526765 & 0.527424 \\ 150 & 0.718004 & 0.714956 \\ 200 & 0.840143 & 0.836808 \\ 250 & 0.912917 & 0.910115 \\ 300 & 0.954097 & 0.951953 \end{array}$$

Los resultados apoyan el límite teórico de la información, así como nuestras estimaciones obtenidas utilizando la aproximación de Poisson.

Nota: Cuando la probabilidad de éxito es $p$ y hay $T$ ensayos, la desviación estándar es $$\sqrt{\frac{p(1-p)}{T}} \leq \frac{1}{2\sqrt{T}}.$$ En nuestro caso, $T = 10^6$ y por lo tanto una desviación estándar es como máximo $0.5\cdot 10^{-3}$ . Con probabilidad $95\%$ el error es como máximo de dos desviaciones estándar, es decir $\pm 0.001$ . Por tanto, los resultados experimentales son correctos hasta aproximadamente el tercer dígito (que puede estar ligeramente desviado).

Answer 2

Como muestra la otra respuesta, la respuesta no es sencilla. Esto se debe a que depende de la secuencia exacta de las tiradas. Puedes ver esto usando el razonamiento bayesiano. Sea $X$ sea una v.r. que indique el lado sesgado. Denotemos el valor de la $i^\mathrm{th}$ papel de $Y_i$ . Entonces,

$$p(Y_1, \cdots, Y_n|X=x) = \left(\frac{1}{20}\right)^{m_x} \left(\frac{1}{100}\right)^{n-m_x}$$

où

$$m_x = \sum_{i=1}^n \mathbf{1}\left(Y_i = x\right)$$

y $\mathbf{1}$ es la función indicadora. Entonces, podemos utilizar la regla de Bayes para calcular la probabilidad de $X=x$ dada una secuencia de tiradas.

$$p(X=x|Y_1, \cdots, Y_n) = \frac{p(Y_1, \cdots, Y_n|X=x)p(X=x)}{P(Y_1, \cdots, Y_n)} = \frac{p(Y_1, \cdots, Y_n|X=x)p(X=x)}{\sum_{x'} P(Y_1, \cdots, Y_n | X=x')p(X=x')}$$

Sustituyendo desde arriba y asumiendo que todos los lados son uniformemente iguales

$$=\frac{\left(\frac{1}{20}\right)^{m_x} \left(\frac{1}{100}\right)^{n-m_x} \frac{1}{96}}{\sum_{x'=1}^{96}\left[ \left(\frac{1}{20}\right)^{m_{x'}} \left(\frac{1}{100}\right)^{n-m_{x'}}\right] \frac{1}{96}}$$

Así que, básicamente, es difícil saber a priori cuántas tiradas porque depende de cuántas "repeticiones" en todos los lados salgan. Pero se puede calcular fácilmente la probabilidad de que $X=x$ donde $x$ es cualquier lado que desee y se detiene después de suficientes rollos.

Answer 3

Acordemos que la primera parte tiene $5\%$ oportunidad, y permaneciendo $95$ lados cada uno tiene $1\%$ de ocurrencia. Después de $n$ rollos, que $N_k$ denotan la variable aleatoria para el número de ocurrencias de $k$ -a la derecha. Entonces el vector aleatorio $(N_1,\ldots, N_{96})$ , con la condición de que $\sum_{k=1}^{96} N_k = n$ sigue una distribución multinomial.

Yo interpretaría su pregunta como una búsqueda para determinar, por $p > \frac{1}{2}$ : $$ n_\mathrm{min} = \operatorname{arg min}_n \mathbb{P}(N_1 > N_2 \land N_1 > N_3 \land \ldots \land N_1 > N_{96} ) > p $$

Esta probabilidad es igual: $$ \begin{eqnarray} \mathbb{P}\left( \land_{k=2}^{96} N_1 > N_k \right) &=& \sum_{n_1=1}^n \mathbb{P}\left( \land_{k=2}^{96} N_k \le n_1 -1 ; N_1 = n_1 \right) \mathbb{P}\left( N_1 = n_1 \right) \\ &=& \sum_{k=0}^{n-1} \left( F\left( k+1,k,\ldots,k \right) - F\left( k,k,\ldots,k \right) \right) \end{eqnarray} $$ donde $F(n_1,\ldots,n_k,\ldots,n_{96}) = \mathbb{P}\left( N_1 \le n_1, \ldots, N_k \le n_k,\ldots, N_{96} \le n_{96} \right)$ .

Incluso cuando se aplica la aproximación normal o de Poisson a la función de distribución acumulativa multinomial, no simplifica mucho la cuestión.

Como aproximación $F$ puede sustituirse por el producto de las funciones de distribución acumulativa marginal, ya que los coeficientes de correlación son del orden de $0.01$ es decir, pequeño: $$ \mathbb{P}\left( \land_{k=2}^{96} N_1 > N_k \right) = \sum_{k=0}^{n-1} f_{\mathrm{Bi}\left(n, \frac{1}{20}\right)}(k+1) \left( F_{\mathrm{Bi}\left(n, \frac{1}{95}\right)}(k) \right)^{95} $$

Hice una simulación, y tracé la probabilidad $\mathbb{P}(\land_{k=2}^{96} N_k < N_1)$ en función de $n$ y en comparación con esta aproximación, el acuerdo es bastante bueno: