美文网首页
数学中的熵-相关问题

数学中的熵-相关问题

作者: wale06 | 来源:发表于2018-12-22 17:59 被阅读0次

1. 猜数字游戏

A 写下一个数 x，其取值范围为 x\in [1,n]，B 来猜这个数字是多少，A 会告诉 B 猜的数字比 x 大了还是小了，问 B 最少猜多少次可以猜出这个数字？

把 x 看作一个随机数，他的取值范围是[1,n]，B 第一次任意猜一个数，猜中的概率是 P(x) = \frac{1}{n}。利用数学中的熵的定义，B 猜中的熵是
S_{x\in[1,n]} = -\Sigma_{x\in[1,n]}{P(x)\log_2 P(x)} = \log_2 n

假如 B 第一次猜的数是 y，则 P(x\in[1,y]) = \frac{y}{n}，P(x\in(y,n]) = \frac{n-y}{n}, 则 条件熵(给定条件下的熵)为 S_1 = P(x\in[1,y])S_{x\in[1,y]} + P(x\in(y,n])S_{x\in[y,n]}\\ =\frac{y}{n} \log_2 y +\frac{n-y}{n}\log_2 (n-y)

求 y 取何值时，熵最小？
\frac{dS_1}{dy} = 0\rightarrow y = \frac{n}{2}

所以每次都猜一个区间的中间值是最优的选择。由于 A 会告诉 B 两种状态，因此 B 只需要猜 \lceil\log_2 n \rceil 就可以猜出 A 给定的数。n 代表可取的状态数，2 代表给定信息的个数

2. 排序问题

有 n 个互不相等的数，需要通过多少次比较才可以将这些数从小到大排序？

比较两个数 a,b 的大小有两种状态，所以对数的底应取为 2，n 个数排序的方式，即可取的状态数为 A_n^n = n!，所以需要比较 \lceil(\log_2 n!)\rceil 次。

3. 猜球问题

有 n 个球，其中有一个球与其他 n-1 个球的重量不一样，现在有一个天平，问需要称多少次可以找出这个球？

天平有三种状态，故对数的底应为3，n 个球要么重了要么轻了，故有 2n 中状态数，所以需要称 (\lceil\log_3 2n\rceil) 次可以找出这个球。

相关文章

  • 数学中的熵-相关问题

    1. 猜数字游戏 A 写下一个数 ，其取值范围为 ，B 来猜这个数字是多少，A 会告诉 B 猜的数字比 大了还是...

  • 熵

    熵 又称信息熵 数学定义： 通俗解释：衡量变量分布不确定性的度量，不确定性越大则熵越大 条件熵 数学定义： 通俗解...

  • 05信息论

    信息熵——参看《数学之美》 第6章 86 最大熵——参看《数学之美》 第20章202

  • 交叉熵

    1.信息熵 1948年，香农在他著名的论文“通信的数学原理”中提高了“信息熵”的概念，解决了信息度量问题，同时量化...

  • 03 熵之殇

    1+1=2（代表了数学文明）E=mc²（爱因斯坦的质能方程）S=-∑PlnP(熵的定义)熵1 .熵是什么？ 熵是物...

  • 熵

    孤立系统的熵永不自动减少，熵在可逆过程中不变，在不可逆过程中增加。 今天看到一篇有意思的问题，问题是“为什么熵...

  • 最大熵模型中的数学推导

    注：此文非本人所写，来源于http://blog.csdn.net/u014114990/article/deta...

  • 熵的相关概念

    信息量（自信息） 信息的大小跟随机事件的概率有关。越小概率的事情发生了产生的信息量越大。 因此一个具体事件的信息量...

  • “熵”的理解

    01 什么是“信息熵” 香农提出“信息熵”的概念，解决了对信息的量化度量问题。热力学中的热熵是表示分子状态混乱程度...

  • 机器学习-面试总结

    决策树问题 1）各种熵的计算熵、联合熵、条件熵、交叉熵、KL散度（相对熵） 熵用于衡量不确定性，所以均分的时候熵最...

网友评论

      本文标题：数学中的熵-相关问题

      本文链接：https://www.haomeiwen.com/subject/yutwkqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数学中的熵-相关问题|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！