Dado un acotado número de morir rollos siguientes unif{1,6}, producir unif{1,7}

Question

Este es un giro en el tradicional problema de la transformación entre el uniforme de distribuciones discretas de diferentes tamaños.

Para este ejemplo, se puede tirar el dado dos veces y conseguir uno de 36 posibilidades. La solución habitual dice que los primeros 35 puede ser distribuida equitativamente entre las salidas 1..7, y el último puede ser rechazado, lo que resulta en una nueva tirada. Esto, sin embargo, no está limitado en el número de morir rollos, ya que usted puede seguir recibiendo rechazos de forma indefinida. Mi pregunta es, ¿ un delimitada algoritmo de existir?

Un poco de boceto argumento dice que no, como sigue. La cantidad de información de cada uno tirada de dados es $\log_2 6$ bits, y necesitamos un múltiplo de $\log_2 7$ bits. $\frac{\log_2 7}{\log_2 6}$ lamentablemente es irracional, por lo que no podemos perfectamente utilizar la información - siempre estamos a la pérdida de información. Esta pérdida de información implica que usted está rechazando algunos números. Y así nunca vas a ser capaz de limitar el número de morir rollos de que el algoritmo requiere.

Este argumento es super boceto para un montón de razones, y probablemente equivocada, pero la orientación general del argumento parece correcto. Estoy en lo correcto, y si es así ¿cómo puedo mejorar esta "prueba"?

Answer 1

El argumento está muy bien. Creo que se puede destilar a algo más simple, sin embargo.

Una secuencia de rollos determina una probabilidad de ramificación del árbol con seis sucursales en cada nodo. Debido a que los rollos son independientes y cada uno de los resultados ha de probabilidad $6^{-1}$, la posibilidad de llegar a un determinado nodo en el nivel de $n$ (es decir, una secuencia particular de $n$ rollos) es $6^{-n}$. Deje $N$ ser cualquier obligado por el número de rollos. Entonces la probabilidad de cualquier evento en absoluto es la suma de los números de la forma $6^{-n}$ donde $0 \le n \le N$. Una suma que, obviamente, es un múltiplo de a $6^{-N}$. Desde $1/7$ no es tan múltiples, que no se dio cuenta de que la probabilidad de cualquier evento, no importa cuán grande $N$ puede ser.

---

He aquí una alternativa exposición de la misma idea. La probabilidad de cualquier evento después de $N$ rollos, cuando se escribe en la base de las $6$, puede ser escrito utilizando en la mayoría de las $N$ dígitos después de la "seximal", en base a $6$. Desde $1/7 = 0.050505\ldots_{[6]}$ requiere una infinita expansión, no puede surgir como la probabilidad de que dicho evento.

Si usted se siente incómodo usar la base de $6$, entonces (por analogía) contemplar un (hipotético) de diez caras de morir, cada resultado con una probabilidad de $1/10$. Después de $N$ rollos, todas las probabilidades puede ser expresado como decimal con exactamente $N$ dígitos. Los números como $1/3 = 0.333\ldots$, $1/7=0.142857\,142857\ldots$, etc., no puede surgir ninguna probabilidad.

Answer 2

Si sigo tu línea, podemos observar que a lo $\frac{log_2{7}}{log_2{6}}=log_6{7}$, que está destinado a ser irracional, por lo que siempre vamos a perder algo de información (lo cual es cierto, como 5 diferentes resultados están representados por un número y el 36º resultado se descarta).

Yo creo, sin embargo, que por la definición de caso de un re-roll y su probabilidad, usted puede obtener un límite en el número de re-rolls, utilizando la desigualdad de Markov. La probabilidad de tener k re-rolls decae rápidamente a 0 por lo que para algunos grandes k a su gusto, usted puede comenzar a utilizar de cero probabilidad de teoremas.