Entropía de la información de los cerdos que beben agua venenosa
Uno de los 25 cubos de agua era venenoso Los cerdos morirían 15 minutos después de beber el agua. ¿Cuántos cerdos se necesitarán para encontrar este balde de agua venenosa en una hora?
Cuando vi esta pregunta, utilicé directamente la dicotomía. 25 barriles se dividen directamente en 12 barriles + 12 barriles + 1 barril, luego 12 minutos, 6 minutos, 3 minutos y 1 minuto. El resultado final del cálculo es que se necesitan 5 cerdos, lo que significa que ahora se necesitan 25 barriles de agua. Pero mi respuesta es incorrecta...
Después de buscar en Baidu, descubrí que es un tema de leecode. La respuesta correcta es 2. La solución también es fácil de entender. Aquí, tomo prestada una imagen de Baidu para ayudarme a comprender. Si no entiendo la explicación a continuación, también puedes leer el texto original del blogger: [código leet] - ¿Qué balde de agua es venenoso?
Como se muestra en la imagen, se dividen 25 cubos de agua en 5 filas y 5 columnas, y se envían dos cerdos, un cerdo bebe fila por fila (tenga en cuenta que se mezclan 5 cubos de agua en esta fila). a la vez), y el otro cerdo bebe fila por fila. Tomemos como ejemplo una hilera de cerdos. Si mueren después de 15 minutos, el agua envenenada está en la columna 1. Si están vivos, continúe bebiendo la segunda columna y luego espere 30 minutos, 45 minutos, 60 minutos para ver qué columna bloquean hasta morir. Si todavía están vivos después de 60 minutos, significa que no hay agua venenosa en las primeras cuatro columnas. Luego, mediante el método de eliminación, podemos saber que el agua venenosa solo puede estar en la quinta columna. De la misma manera, siempre que finalmente se bloquee el número de filas y columnas, la intersección debe ser donde está el agua venenosa.
Se puede observar que la clave de esta solución es que un cerdo aprovechó al máximo el intervalo de 15 minutos e identificó directamente si cinco cubos de agua (en realidad cinco cubos de agua mezclada) eran tóxicos en un plazo. hora. Si la pregunta se cambia a un intervalo de 10 minutos, entonces se pueden identificar 7 cubos de agua en 1 hora. En este momento, 7 elevado a la potencia 2 es 49 y se necesitan 2 cerdos.
Ampliándonos aún más, el intervalo sigue siendo de 15 minutos, pero ¿el total * * * es de 1.000 barriles de agua? De hecho, un cerdo solo puede distinguir 5. Las dos dimensiones solo pueden ser 5 por 5, y luego uno es el cubo de 5. Es fácil descubrir que la pregunta en realidad es cuántas veces encontrar 5. ¿Puede ser mayor? que 1000? La respuesta simple es 5 cerdos. De hecho, en este momento, la quinta potencia de 5 es 3125, lo que significa que aunque sean 3.000 barriles de agua, cinco cerdos son suficientes.
Ampliémoslo. ¿Qué pasa si el intervalo es de 15 minutos, pero el requisito es de 15 minutos, no de una hora? En este momento, encontrará que después de 15 minutos, el cerdo tiene solo dos estados, vivo o muerto. Es decir, cada fila o columna en realidad sólo puede contener 2 cubos de agua. Entonces la pregunta es cuántas potencias de 2 son mayores que 25. Bueno, la respuesta en este momento es exactamente la misma que la dicotomía que usé al principio. Sólo entonces me di cuenta de que mi método de dicotomía en realidad no me llevó una hora, sino sólo 15 minutos para identificar el agua venenosa. Debido a que la pregunta dice que cada balde de agua tiene una cantidad ilimitada, primero puedo desmantelar los 25 baldes de agua según el método de dicotomía y luego dar una orden para que 5 cerdos suban y beban el grupo correspondiente al mismo tiempo. Eso sí, tardaré 15 minutos en saber el resultado.
Sin embargo, hasta ahora, las cosas recién comienzan... Por ejemplo, este Zhihu responde con 30.000 me gusta:
1.000 barriles de agua, uno de los cuales es venenoso. Los cerdos que beben agua envenenada morirán en 15 minutos. ¿Cuántos cerdos se necesitarán para encontrar este balde de agua venenosa en una hora? ——La respuesta de Miao Huadong. - Zhihu
El autor descarta la definición y fórmula de la entropía de la información:
Entonces usar esta fórmula para calcularla me hace parecer estúpido. Se recomienda complementar primero los conocimientos básicos a través de otros enlaces.
¿Qué es la entropía de la información de referencia? ——La respuesta de la investigación de operaciones. -Zhihu
Entropía de la información, entropía de la información, ¿qué opinas? Si la palabra "entropía" no le sienta bien, no la lea todavía. Al menos sabemos que este concepto tiene que ver con la información. Además, es un concepto en un modelo matemático y generalmente puede cuantificarse. Entonces, aquí surge la primera pregunta: ¿Se puede cuantificar la información?
Al menos es intuitivamente posible. De lo contrario, ¿por qué pensaríamos que algunas personas dicen tonterías y "no tienen información", mientras que otras dan en el clavo y transmiten mucha información en una sola frase?
Algunas cosas son inciertas, como si las acciones subirán o bajarán mañana. Si me dice que las Finales de la NBA comienzan mañana, los dos parecen no tener nada que ver entre sí, entonces su información aporta poca información sobre si las acciones subirán o bajarán mañana. Pero si cuando comiencen las Finales de la NBA, todo el mundo ya no presta atención a las acciones y hay un 99% de posibilidades de que las acciones caigan, entonces sus palabras tendrán un gran valor de referencia, porque las cosas que originalmente eran inciertas se vuelven muy ciertas.
Y algunas cosas ya son ciertas, como que el sol sale por el este.
Si me dice que el sol sale por el este cien veces, su declaración no contendrá ninguna información, porque ya no puede ser seguro.
Así que la cantidad de información está relacionada con los cambios en la incertidumbre.
Primero, está relacionado con el número de resultados posibles de las cosas; segundo, está relacionado con la probabilidad.
Déjame hablar de uno primero. Por ejemplo, discutimos dónde sale el sol. Sólo hay un resultado, y hace tiempo que sabemos que no importa quién transmita un mensaje, no hay mensaje. Cuando el número de resultados posibles es relativamente grande, la nueva información que obtenemos tiene el potencial de ser informativa.
En segundo lugar, el número de resultados posibles no es suficiente y también depende de la distribución de probabilidad inicial. Por ejemplo, supe desde el principio que Xiao Ming estaba viendo una película en la Sala A con 15 * 15 asientos en el cine. Hay 225 asientos donde se sienta Xiao Mingcan, lo que puede generar demasiados asientos. Sin embargo, si sabemos desde el principio que la probabilidad de que Xiao Ming se siente en el extremo izquierdo de la primera fila es del 99% y que la probabilidad de sentarse en otras posiciones es muy pequeña, entonces, en la mayoría de los casos, no me dirás nada. información sobre Xiao Ming Qué útil, porque estamos casi seguros de que Xiao Ming está sentado en el extremo izquierdo de la primera fila. Entonces, ¿cómo se miden los cambios en la incertidumbre? ¿Cómo definir? Esta pregunta es difícil de responder, pero si ya sabemos que esta cantidad ya existe, también podríamos llamarla cantidad de información. Entonces, ¿qué características crees que debería cumplir al menos la cantidad de información?
¿Qué función puede satisfacer las cuatro condiciones anteriores?
La función logarítmica negativa, que es -log(x)! Tome una base mayor que 1 para asegurarse de que esta función no sea negativa. Simplemente multiplica el frente por un número normal.
R. ¿Por qué no es positivo? Porque si es un número positivo, debido a que x es un número menor o igual a 1, log(x) es menor o igual a 0. satisface la primera característica.
b. Verifiquemos otras funcionalidades. El tercero es el más fácil. Si x es una probabilidad, entonces log(x) depende continuamente de x.
¿Qué tal cuatro? Si hay n resultados posibles, la probabilidad de cualquiera de ellos es 1/n, y -log(1/n) es una función creciente de n, no hay problema.
d.Verificación final dos. Como -log(xy) = -log(x) -log(y), también es correcto. Los estudiantes de matemáticas deben tener en cuenta que aquí y puede ser la probabilidad condicional de un X dado o, por supuesto, puede ser independiente de X. Por cierto, esta función es única (excepto que puede multiplicarse por cualquier constante). Puedes comprobarlo tú mismo o consultar un libro si tienes tiempo.
Bien, entonces sabemos que el contenido de información de un evento es el logaritmo negativo de la probabilidad del evento. Finalmente, podemos volver a la entropía de la información. La entropía de la información está relacionada con todas las posibilidades. Todo evento posible tiene una probabilidad. La entropía de la información es la cantidad promedio de información que obtenemos cuando ocurre un evento. Entonces, matemáticamente hablando, la entropía de la información es en realidad la expectativa de información. (Ver otras respuestas o ver expresiones a continuación)
¿Qué es la entropía de información de referencia? -Respuesta de D.Han. - Zhihu
Hay cuatro caballos {A, B, C, D} en la competencia de carreras de caballos y la probabilidad de ganar es {1/2, 1/4, 1/8, 1/8} . A continuación, tratamos qué caballo gana como la variable aleatoria x.
Supongamos que necesitamos usar la menor cantidad posible de preguntas binarias para determinar el valor de la variable aleatoria x, como la pregunta 1: ¿Ganó A? Pregunta 2: ¿Ganó B? Pregunta 3: ¿Ganó C? Finalmente, podemos determinar el valor de X, es decir, qué caballo ganó la carrera, con hasta tres preguntas binarias.
Entonces es fácil de calcular, por lo que se puede determinar el valor de x.
Cuando utilizamos la fórmula de entropía de la información anterior, se ve así:
-1/2 * log(1/2)+-1/4 * log(1/ 4 )+-1/8 * log(1/8)+-1/8 * log(1/8)
Es fácil calcular el resultado aquí, por ejemplo: -1/2 * log (1/2)=-1/2 *(log 1-log2)= 1/2 * log2 = 1/2.
1/2+1/2+3/8+3/8 = 7/4
Se puede encontrar que el resultado del cálculo de la fórmula de entropía de la información es consistente con la cálculo previo. En una computadora binaria, un bit es 0 o 1 y en realidad representa la respuesta a una pregunta binaria. Es decir, en una computadora necesitamos una longitud de código promedio de 1,75 bits para codificar qué caballo ganó el campeonato.
Obviamente, para reducir la longitud del código tanto como sea posible, debemos asignar longitudes de código más cortas a eventos con mayor probabilidad. Después de una discusión en profundidad sobre este tema, podemos entender el concepto de codificación Huffman.
Para obtener más información, consulte la información de entropía termodinámica de la serie H264 nueve codificación de Huffman codificación Golomb. En este artículo hay otro ejemplo muy interesante:
Quiero tirar los dados una vez. Antes de observar el resultado, las seis caras del dado son posibles, con exactamente la misma probabilidad (todas 1/6). En este momento, la entropía de información del evento es. Este resultado también se calcula bien utilizando la fórmula de entropía de información anterior, que equivale a acumular -1/6 * log(1/6) 6 veces, es decir, -log(1/6)=-(log 1-log 6 )= log6. Tenga en cuenta que este algoritmo se utilizará más adelante para calcular cuándo el cerdo bebió el agua venenosa.
Ahora la Diosa Todopoderosa me dio una pista. El resultado de este dado debe ser un número par, por lo que los resultados posibles se reducen de 6 a 3, y la entropía del evento se vuelve. En otras palabras, cuando me preguntaron, me volví menos seguro sobre el resultado del evento. Definimos la cantidad de reducción de entropía de información como la cantidad de información I. La cantidad de información en el mensaje anterior es exactamente 1 bit, lo que equivale a la cantidad de información necesaria para emitir un juicio correcto o incorrecto sobre una proposición completamente desconocida. Y si quiero obtener el único resultado seguro, P (x) debe ser igual a 1 y la entropía de la información en este momento es cero. La información que necesitamos es entropía bruta.
Después de ver esto, debes poder sacar otra conclusión brillante: la información es entropía negativa. Cabe señalar que la "entropía" en esta oración se refiere y solo se refiere a la entropía de la información. Los intentos de ampliar esta conclusión a la explicación de la entropía termodinámica a menudo carecen de base fáctica suficiente y el significado suele ser ambiguo.
Es hora de volver a los 30.000 me gusta de Zhihu: 1.000 barriles de agua, uno de los cuales es venenoso. Los cerdos que beben el agua venenosa morirán en 15 minutos. ¿Cuántos cerdos se necesitarán para encontrar este balde de agua venenosa en una hora? ——La respuesta de Miao Huadong. -Zhihu
1.000 barriles de agua, uno de los cuales es venenoso. Los cerdos que beben agua envenenada morirán en 15 minutos. ¿Cuántos cerdos se necesitan para encontrar este balde de agua venenosa en 15 minutos?
En primer lugar, la entropía de información de la variable aleatoria X es: -(1/1000)* log(1/1000) acumulada 1000 veces. Esto es fácil de entender. La presencia de agua venenosa en cualquier balde es un evento igualmente probable. El resultado acumulativo es:
-log(1/1000)= log 1000 es aproximadamente 9,966.
Después de que un cerdo bebe agua, está vivo o muerto, un * * *, con dos estados, entonces la entropía de información de la variable aleatoria Y "después de que un cerdo bebe agua" es
Después de que N cerdos beban agua, habrá 2 N-ésimos estados de potencia, es decir, la entropía de información de la variable aleatoria Y es "el estado de N cerdos después de beber agua"
Entonces, según los requisitos de la pregunta, si se necesitan al menos N cerdos para encontrar este balde de agua venenosa, entonces la entropía de información de la variable aleatoria Y debe ser mayor que la entropía de información de la variable aleatoria X, es decir, H (y) >: = H (X), es decir, N >= 9.966, es decir, n = 10
Cuando usamos la entropía de la información para calcular el valor mínimo de n, podemos creer firmemente que n=10 debe ser el valor teórico solución óptima. Tratar de encontrar un valor menor que 10 es inútil.
De hecho, la versión simplificada del cálculo de entropía de la información anterior se puede escribir en la siguiente forma más comprensible y también se puede resolver como n = 10. Aunque la forma es simple, debes recordar que el principio detrás de esto es la entropía de la información.
En cuanto a qué plan adoptar, implica el nivel técnico. Incluso si no podemos resolverlo por el momento, todavía tendremos una dirección para nuestros esfuerzos, sabremos dónde están los límites de nuestros esfuerzos y no haremos cosas como buscar una máquina de movimiento perpetuo.
1000 barriles de agua, uno de los cuales es venenoso. Los cerdos que beben agua envenenada morirán en 15 minutos. ¿Cuántos cerdos se necesitarán para encontrar este balde de agua venenosa en una hora?
Uno de los 1.000 barriles de agua es venenoso. Es lo mismo que la primera pregunta, siguen siendo 9.966. Sin embargo, la entropía de la información de los cerdos es diferente. Podemos imaginar cuántos estados puede tener un cerdo en una hora.
Se puede ver que 1 cerdo tendrá cinco estados después de 1 hora, por lo que la entropía de información de la variable aleatoria Z de "1 cerdo después de 1 hora" es
Después de 1 hora , N cerdos tendrán 5 N-ésimos estados de potencia, es decir, la entropía de información de la variable aleatoria Y es "el estado de N cerdos después de 1 hora"
Entonces, de acuerdo con los requisitos de la pregunta, si al menos Se necesitan N cerdos para encontrar este balde de agua venenosa, entonces la entropía de información de la variable aleatoria Y debe ser mayor que la variable aleatoria.
La entropía de información de la cantidad, para n = 5, no hay problema en detectar no sólo 1.000 barriles de agua, sino incluso 3.000 barriles de agua. Zapatos para niños interesados
Puedes intentar calcularlo
En este punto, Shannon nos dio un límite teórico, pero el plan específico aún debemos construirlo nosotros mismos. n=5 lo decidimos nosotros.
La base teórica y el dibujo de planos específicos son nuestro nivel de ingeniería.
Sigue siendo el autor con 30.000 me gusta en Zhihu, refiriéndose a la teoría de la información de Shannon, ¿dónde está la vaca? - Respuesta de Miao Huadong - Zhihu, viejos hábitos, aquí solo presento las ideas, consulte el texto original del autor para conocer los planes específicos.
Una de las 12 bolas con la misma apariencia es una bola mala, que es más ligera que las otras 11 bolas buenas. Ahora hay una báscula sin peso. ¿Al menos cuántas veces tienes que pesarla antes de estar seguro de haber encontrado esa pelota mala?
Podemos pensar en ello. Pesar la balanza una vez tendrá tres resultados:
Por lo tanto, la entropía de información de la variable aleatoria z "el resultado después de pesar la balanza una vez" es
p>
Si se simplifica la fórmula anterior, es decir
Hay 1 bola mala entre 12 bolas con la misma apariencia y su peso es diferente de las otras 11. bolas. Ahora hay una báscula sin peso. ¿Al menos cuántas veces tienes que pesarla antes de estar seguro de haber encontrado esa pelota mala?
La diferencia entre esta pregunta y la anterior es que no sabemos el peso de la bola mala. ¿Qué efecto tiene esto sobre la entropía de la información en comparación con la bola mala conocida anteriormente como ligera?
Si hay dos bolas a ambos lados de la balanza. Si sé que la bola mala es más ligera, puedo saber inmediatamente que la bola mala está en el lado más claro cuando el cielo está desequilibrado. Cuando no sé si una pelota mala es liviana o pesada, si la balanza no está equilibrada, no puedo decir si una pelota mala es pesada o liviana. Sólo puedo decir si la bola mala es liviana o pesada. Por lo tanto, cuando no sabemos si una pelota mala es liviana o pesada, cada vez que medimos una pelota mala, existe incertidumbre sobre si la pelota mala es liviana o pesada. Según la pregunta anterior, agregue un número en la posición más alta para indicar el peso de la pelota. Entre ellos, 0 significa ligero y 1 significa pesado, como se muestra en la siguiente tabla. Entonces, aunque hay 12 bolas, hay 24 estados debido a la incertidumbre del peso.
Entonces la entropía de la información de la variable aleatoria Debido a que el equilibrio solo puede determinar tres estados a la vez, de manera similar, h (y) >: = H(X), es decir, n >; es n = 3. Se puede ver que la pregunta anterior no aprovechó al máximo la ventaja de información de la escala y aún pudo detectar tres bolas malas descuidadas. Éste es el beneficio de armar su mente con teoría. Encuentre primero la respuesta y luego piense en el plan. La ventaja de esta forma de pensar de arriba hacia abajo es que antes de pensar en el plan, tenemos una meta y una dirección para nuestro trabajo, en lugar de ser como una mosca sin cabeza.
Si lees los zapatos para niños titulados "Usar 1000 barriles de agua para encontrar veneno" al principio del artículo, es posible que descubras que las ideas para resolver este problema son casi las mismas que las ideas para resolverlo. ese problema. Aunque superficialmente parezca un tipo diferente de problema, debemos aprender de los antepasados de Citron y llegar a la esencia del problema a través de su apariencia.
La lógica subyacente de estos dos temas es la entropía de la información. Cuando dominamos las herramientas teóricas, la diferencia entre las personas radica en si tenemos la capacidad suficiente para abstraer problemas de la vida real en matemáticas u otros problemas, y luego usar las herramientas teóricas con las que estamos familiarizados para resolverlos. En este punto, las ecuaciones de resolución son las mismas. Resolver la ecuación en sí es muy simple. La parte difícil es cómo abstraer las preguntas reales en expresiones, definir variables y enumerar las ecuaciones. Puede encontrar una declaración detallada sobre este punto en mi otro artículo, ¿Qué utilidad tiene el pensamiento matemático en la vida? Hay una descripción más detallada en .
Hace referencia a 1.000 barriles de agua, uno de los cuales es venenoso. Los cerdos que beben agua envenenada morirán en 15 minutos.
¿Cuántos cerdos se necesitarán para encontrar este balde de agua venenosa en una hora? ——La respuesta de Prangel. - Zhihu
Considere este proceso: suponga que le dan dos números A y B. Solo puede compararlos una vez y ordenar los dos números de pequeño a grande. ¿No crees que esta pregunta es sencilla? Estos dos números solo deben compararse una vez y el número más pequeño ocupa el primer lugar.
Analicemos la esencia de esta pregunta aparentemente sencilla.
Si solo se puede comparar una vez, entonces, según esta comparación, en realidad solo podemos obtener dos tipos de información: o el primer número es más pequeño o el segundo número es más pequeño. Solo hay dos situaciones para la relación entre dos números de pequeño a grande: a, b o b, a. En otras palabras, podemos establecer un resultado basado en el resultado de esta comparación: la relación de permutación y biyección final. resultado de cada comparación Todos corresponden únicamente a la relación de tamaño final.
Considere ahora una versión mejorada de la pregunta anterior: si le dan cuatro números A, B, C y D, ¿puede ordenarlos de pequeño a grande mediante cuatro comparaciones? La respuesta es no, porque la información que podemos obtener a través de cuatro comparaciones es como máximo 2 elevado a la cuarta potencia, que son 16 tipos. ¡Y hay cuatro permutaciones de estos cuatro números! =24 especies. Por lo tanto, es imposible hacer corresponder los resultados de la consulta con la disposición final uno a uno. Probamos que 4 no puede ser el límite inferior de la respuesta.
Actualicémoslo nuevamente y consideremos la situación de ordenar n números. Si usamos k comparaciones en la solución final, entonces la información posible es 2 elevado a la k-ésima potencia, ¡y las permutaciones de n números son n! Amable. Para establecer una relación biyectiva entre el resultado y el arreglo final, se deben cumplir los siguientes requisitos:
Ahora pensamos en el problema original desde la perspectiva de la teoría de la información. De 1.000 barriles de agua, sólo uno es venenoso. En otras palabras, sólo hay 1.000 respuestas posibles.
Cada cerdo muere a los 15 minutos de ser envenenado, entonces podemos obtener cinco tipos de información de cada cerdo: en [0, 15] [15, 30] [30, 45] [45, 60] durante cuyo período de tiempo muere o finalmente sobrevive. Si al final hay K cerdos, hay varios tipos de información que podemos obtener. En otras palabras, K debe satisfacerse, es decir, el límite inferior de K es 5.