Estrategia más eficiente para adivinar el resultado de (feria) tirada de dados?

Question

Estoy empezando a aprender acerca de la teoría de la información y estoy un poco pegado en esto. he aquí lo que tengo hasta ahora:

1 estrategia posible es simplemente preguntar " ¿resultado 1 se producen?' si sí, entonces tenemos nuestra respuesta, si no nos vuelva a preguntar '¿resultado 2' etc. para un dado, el número máximo de preguntas con esta estrategia sería 5, ya que si, por 1 - 5 la respuesta es no, eso debe significar que el resultado 6 debe ser positivo. Basado en mi cálculo, el número medio de preguntas a través de esta estrategia es de 2,5 (suma de 1 a 5 de $Q/6$, donde Q es el número de preguntas y 1/6 es el probabilty de rodar alguna de las caras de los dados).

Otra estrategia pensé sería dividir la probabilties – es decir, es el resultado? si sí, podríamos preguntar a 'es mayor que 3?' y, a continuación, o tenemos el resultado (6) o le pedimos '4?' y desde aquí tenemos una respuesta definitiva. Asimismo, para el caso de la primera respuesta no es decir, el número es impar.

Luché para calcular el número medio de preguntas para esto. Mi lógica era que nos debe hacer al menos 2 preguntas para que la respuesta sea totalmente determinado. Así, nos debemos preguntar: 1 pregunta y, a continuación, el resultado de la segunda pregunta está sujeto a probabilty. Por lo tanto, el número medio de preguntas es: $1+(2/6)+(3/6)=1.83333...$

Esto es correcto? Es mi lógica correcta? Hay otras estrategias que vale la pena mirar?

Estoy disfrutando mucho de la información teoría y estoy realmente interesado en aprender más más más!

Answer 1

Cada respuesta sí-no pregunta puede proporcionar más de un bit de información. Una feria de la tirada de dados tiene seis resultados igualmente probables, por lo $\log_26=2.585$ bits de entropía. Cualquier estrategia de adivinar correctamente el rollo de dados puede utilizar menos de esto muchas preguntas en promedio.

Una estrategia que reduce el espacio de búsqueda con cada nueva pregunta tan uniformemente como sea posible tendrá dos preguntas para adivinar correctamente para dos rollos (por ejemplo, 1, 6) y tres preguntas para los otros cuatro rollos, con lo que un promedio de $\frac83=2.667$ preguntas. Esta es la óptima, ya que si tres rollos sólo se requiere de dos preguntas, el número medio de preguntas sería de 2.5 por debajo de la teórica límite inferior.

La estrategia que se pregunta si la tirada es 1, luego 2, luego 3 y así sucesivamente requiere 5 preguntas si la tirada fue de 5 o 6, por lo que requieren $\frac{1+2+3+4+5+5}6=\frac{10}3=3.333$ preguntas en promedio; es sub-óptima.

Answer 2

Su pregunta es, esencialmente, un problema de codificación. Cuando usted haya decidido sobre su estrategia, cada resultado es una serie de sí-no-respuestas. Mediante la codificación de las respuestas "sí" como $1$ y respuestas "no" como $0$, se obtiene un binario de la palabra para cada uno de los resultados.

El conjunto de los codewords debe ser un prefijo de código, es decir, ninguna palabra es un prefijo de otra. Eso es porque, por ejemplo, si uno de los resultados corresponde a la secuencia de respuesta de "sí-no-sí", que claramente no puede tener un resultado que corresponde a la secuencia de respuesta de "sí-no". (De lo contrario sabrías la respuesta después de 2 preguntas, pero todavía le pregunte a una tercera pregunta que iba a cambiar la respuesta, lo cual es claramente imposible.)

Por otro lado, puede transformar un prefijo de código a una pregunta de la estrategia; usted acaba de formular su $k$th pregunta como "el Uso de esta codificación, es el $k$th bits de la palabra $1$?" y se detiene cuando usted sabe la respuesta.

Así que tu pregunta es exactamente equivalente a "¿Cuál es el más eficiente prefijo de código para lanzar un dado resultado?" Aquí, la eficiencia es el valor esperado de la longitud de la palabra.

Dado un conocido conjunto de resultados con una distribución de probabilidad, la más eficiente prefijo de código es el código Huffman. Voy a dejar de construir el código como un ejercicio para el lector, pero el óptimo de la longitud esperada en este caso es $2+\frac{2}{3}$.

Answer 3

Para su primera idea no estoy seguro de que la estimación es correcta. $1$ toma una suposición, $2$ dos, y así sucesivamente, hasta que $5$ toma cinco, y $6$ también lleva cinco. Por lo que la estimación será:

$\frac 16 +\frac 26 + \frac 36 +\frac 46 + \frac 56 +\frac 56 = 3 \frac 13.$

Para el segundo método que ya ha dicho que debe haber al menos $2$ conjeturas, así que ¿cómo puede el promedio de los ser $1.8333...$? Si se elimina la mitad en la primera pregunta se puede obtener dos números en el segundo intento, y los otros cuatro en la tercera pregunta. Para su estimación se

$2 \times \frac 26 + 4 \times \frac 36 = 2 \frac 23.$

Desde aquí se puede ver que esta es la mejor estrategia de los dos que has mencionado.

Answer 4

Veamos este problema desde el puro punto de vista probabilístico.

Usted tiene un espacio probabilístico $\Omega = \{1, 2, 3, 4, 5, 6\}$ con $\sigma\text{-set}$ $P=2^{\Omega}$ (por lo que cualquier subconjunto de a$\Omega$ es en su $P$ y discretas de probabilidad con $p(n)=p(\{n\})=\frac{1}{6}$.

Ahora para cada estrategia tiene un conjunto finito de preguntas. Para cada uno de los 1-elemento de los conjuntos de $P$ puede definir cuál será la respuesta a su conjunto de pregunta y como resultado, usted verá cómo muchas de las respuestas fueron proporcionadas. Su variable aleatoria $X$ es el número de preguntas para un determinado resultado y el valor esperado $E|X$ es un producto de la suma de la variable aleatoria y la correspondiente probabilidad de que, en su caso es $\Sigma_{i=1}^6p(i)\cdot X(i)=\frac16\Sigma_{i=1}^6X(i)$

Nota, los términos abstractos son útiles para cualquier espacio probabilístico y estrategia, usted sólo tenga que adaptar algunas de las fórmulas.

Ahora para que sus ejemplos, la estrategia donde usted preguntar "Es 1, que es a las 2..." etc su variable aleatoria $X_1$ es como sigue (las respuestas a las preguntas en paréntesis): $$X_1(1)=1\text{ \{y\}}$$ $$X_1(2)=2\text{ \{ny\}}$$ $$X_1(3)=3\text{ \{nny\}}$$ $$X_1(4)=4\text{ \{nnny\}}$$ $$X_1(5)=5\text{ \{nnnny\}}$$ $$X_1(6)=5\text{ \{nnnnn\}}$$ Por lo que su valor esperado es $$E_1=\frac16\Sigma_{i=1}^6 X_1(i)=\frac{20}6=3\frac13$$

La diferencia en comparación con el resultado de la $2.5$ proviene del hecho de que usted no hizo caso de que usted necesita preguntarse a 5 preguntas dos veces tan a menudo como usted hacer otras preguntas.

Su segunda estrategia de recortes de la mitad de sus números restantes (en promedio). Digamos que las dos primeras preguntas son siempre "Es" y "Es mayor que 3". Si esos dos no proporcionan un resultado definido usted tiene dos opciones y necesita hacer una pregunta más (vamos a suponer que siempre vas a preguntar sobre el menor número posible).

Con esta estrategia de su variable aleatoria $X_2$ y el valor esperado $E_2$ son como: $$X_1(1)=3\text{ \{nny\}}$$ $$X_1(2)=2\text{ \{yn\}}$$ $$X_1(3)=3\text{ \{nnn\}}$$ $$X_1(4)=3\text{ \{yyy\}}$$ $$X_1(5)=2\text{ \{ny\}}$$ $$X_1(6)=3\text{ \{yyn\}}$$ $$E_2=\frac16\Sigma_{i=1}^6 X_1(i)=\frac{16}6=2\frac23$$

Realmente no puedo adivinar ¿cómo calcular su segundo resultado así que no soy capaz de responder a lo que hiciste mal.

Como se puede ver, la segunda estrategia es mejor.

También verá cómo calcular correctamente para cualquier otro ejemplo.

Answer 5

Secuencial de preguntas, de hecho, requieren en promedio $$\frac{1+2+3+4+5+5}6=\frac{10}3$$ ensayos.

Si usted se divide en dos sets iguales de $3$, no hay mejor opción que la secuencial de preguntas entre los $3$, y en total que se lleva a

$$1+\frac{1+2+2}3=\frac83$$ ensayos.

De manera más general, la estrategia óptima es de dos siempre dividir la actual subconjunto en dos mitades (lazos rotos de forma arbitraria).