数学系专业课程——《数学模型》 离散模型补充材料 刘云 玉溪师范学院数学系.

Presentation on theme: "数学系专业课程——《数学模型》 离散模型补充材料 刘云 玉溪师范学院数学系."— Presentation transcript:

1 数学系专业课程——《数学模型》 离散模型补充材料 刘云 玉溪师范学院数学系

2 §1 从游戏说起  Dürer魔方（或幻方）问题
德国著名的艺术家Albrecht Dürer( )于1514年曾铸造了一枚名为“Melencotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题

3 什么是Dürer魔方 所谓的魔方是指由1~n2这n2个正整数按一定规则排列成的一个n行n列的正方形 。n称为此魔方的阶 。 多么奇妙的魔方！
铜币铸造时间：1514年

4 构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯·阿格里帕（ ）先后构造出了3~9阶的魔方 。

5 如何构造魔方 奇数（不妨n=5）阶的情况 Step1: 在第一行中间写1
Step2: 每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完 偶数阶的情况 偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法 ，这里不作详细介绍 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9

6 魔方数量随阶数n增长的速度实在是太惊人了！
同阶魔方的个数 五阶 没人知道有多少个！！！ 三阶 个 反射和中心旋转生成8个 四阶 个 反射和中心旋转生成7040个 魔方数量随阶数n增长的速度实在是太惊人了！

7 松驰问题的讨论 允许构成魔方的数取任意实数 问题已发生了实质性变化 n阶魔方A、B，任意实数α、β αA+βB是n阶魔方 允许取实数
具有指定性质的魔方全体构成一个线性空间 注：刻画一个线性空间只需指出它的维数并求出此线性空间的一组基底

8 仍以4阶方阵为例。 令R为行和，C为列和，D为对角线和，S为小方块和 定义0-方：R=C=D=S=0 定义1-方：R=C=D=S=1 R=C=D=S=1的方阵构成的线性空间具有什么样的性质？ 类似于构造n维欧氏空间的标准基，利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。 1在第一行中共有4种取法，为保持上述性质的成立，第二行中的1还有两种取法。当第二行的1也取定后，第三行与第四行的1就完全定位了，故一共可作出8个不同的最简方阵，称之为基本魔方并记之为Q1，… ，Q8

9 显然， Dürer空间（简称D空间）中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，但它们能否构成D空间的一组基呢？
显然， Dürer空间（简称D空间）中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，但它们能否构成D空间的一组基呢？

10 容易看出： Q1，…，Q8这8个基本方是线性相关的，即至少存在一个Qj，可以通过其它7个基本方的线性组合得到。这8个基本方的地位是等同的，故可不妨设j=8。下面验证Q1，Q2，…，Q7是否线性相关。 令： ，即 =

11 = 等号两边对应元素相比较，得r1=r2=…=r7=0， 所以 是线性无关 是D空间的最小生成集。
所以 是线性无关 是D空间的最小生成集。 研究Albrecht Dürer铸造的铜币 令D 即解方程组： = 解得 D=

12 进一步讨论 D空间的子空间和D空间的扩展 （1）要求魔方的所有数都相等 这是集合G={rE,r∈R}， G是以βG={E}为基的一维向量空间 （2）要求列、行及每条主、附对角线上各和都相等。 得到5维泛对角方的向量空间B。例如： 它的基BB为： H=N=R=C=46 其中H为主对角线和，N为附对角线和。

13 （3）要求行和，列和及两条对角线上的元素和相等
得到8维向量空间Q。 基向量QB={Q1，Q2，…，Q7，N0}， 其中Q1，Q2，…，Q7是D的基，而 例如： R=C=D=30

14 （4）仅要求行和与列和相等 得到10维向量空间ψ 基向量ψB={Q1，Q2，…，Q7，N1，N2，N3} 其中Q1，Q2，…，Q7是D的基，而 Botsch（1976年）证明了对于1与16之间的每一个数K，都存在K维的4×4方的向量空间 （5）对数字没任何要求 所有4×4数字方组成16维向量空间M 基向量MB的元素应是标准基（即仅有一个 元素为1，其余元素均为0的阵）。 由上可知，有下式成立 ： （向量空间） （维数）

15 拼方问题  什么是拼方问题 在H.E.Dudeney所写的《Cantebury难题》一书中有一个正方形的图案，这个正方形图案是由一个小长方形和若干个边长各异的小正方形组成的。小长方形的长为 ，宽为 ，要求求出所有正方形的边长和拼接方法。这种拼接过程称为拼方，而这种类型的问题称为拼方问题。 12 8 5 3 2 7 21/4 11/4 5/2 31/4 1

16 受上一问题的启示，加拿大数学家W.T.Tutte, A.Stone等人考虑了如下问题：
怎样的长方形可以剖分成若干个边长各异的小正方形？ 正方形能否剖分成边长各异的小正方形？ 称具有上述性质的长方形为完美长方形，正方形为完美正方形。 波兰数学家Z.Moron 的工作 Z.Moron 在W.T.Tutte等之前已经作出了一个9阶完美长方形，见右图 18 14 4 10 15 7 9 8 1 Z.Moron的完美长方形很接近完美正方形

17 Tutte等人用来分析Moron给出例子的 奇特方法：
用点表示水平边，用边表示小正方形。边长即小正方形之边长，方向规定由上到下。于是一个剖分好的完美长方形被十分巧妙地转化成了一个有向图网络，见下图 A B C D E F 除表示上、下两底边的顶点以外，其余顶点处指入边边长之和应等于指出边边长之和

18 分析Moron给出的完美长方形，取高为32，则相应电网络中的电流强度xi(i=1,…,9)应满足：
其解为： （x1,x2,x3,x4,x5,x6,x7,x8,x9)=(18,15,4,7,8,1,14,10,9)， 恰为相应小正方形的边长。此外，由x1+x2=33可知，长方形的宽应为33。 若将每边看成一个单位电阻，在给出正极A与负极F之间的电势差后（相当于给出长方形的高），即可求出每条边上的电流强度（等于两顶点间的电势差），而这些数恰好就是小正方形的边长。 由上面说明：假如我们把得到的有向图网络看作电网络，则所述性质恰好就是电学中的基尔霍夫定律。 此外还可看出，解应当是唯一的，因为在给定A、F间的电势差后，各边上的电流强度是唯一确定的。

19 可以不管长方形的剖分，直接根据图的各种情况利用计算机来搜查 前面分析是在对完美长方形作了剖分的前提下作出的，不知道剖分情况怎么办？
几种最简单的情况及寻查过程的简要说明 可以不管长方形的剖分，直接根据图的各种情况利用计算机来搜查 前面分析是在对完美长方形作了剖分的前提下作出的，不知道剖分情况怎么办？ 有向图只有三条边的图见图1。 由x1= x3可知不存在3阶完美长方形。 由四条边组成的有向图可以有两种形式， 见图2中的（a）、(b)，它们均不可能对 应完美长方形。 图1 图2（a） 图2（b）

20 逐阶寻查下去可发现，完美长方形对应的电网络必有以下性质
(性质1) 除两端顶点外，其余各项点的进出边之和至少为3。 (性质2) 电网络不具有对称性。 几点说明： 对一个指定的有向图求相应的完美长方形时，高可以先随意选取一个整数。求出所有小正方形的边长后再将所有数据同乘一个适当的数，使所有有数据均化为整数。显然，变动长方形的高所得到的剖分是相似的，在将相似看作等同的意义下，这种剖分是唯一的。 当然，随着阶数增大，计算量将按指数增长，因为相应电网络的数目是按指数增长的。 根据这两条性质，可以发现完美长方形的最小阶数为9，进而可作出各种9阶、10阶、11阶…完美长方形。 Tutte等人将他们用人工方法得到的完美长方形列成了一个表，其中包括有二百多个完美长方形。1960年，人们用电子计算机求得了9至15阶的全部完美长方形，可其中没有一个是完美正方形！

21 是否存在完美正方形？ 当求得的完美长方形的长恰好等于宽的十分巧合的情况下，我们才能得到一个正方形的剖分。由于计算量过大，在计算机上寻查并未获得成功，最早作出的正方形的剖分是基于非常复杂的图形并用对称性人工凑出来的，它具有69阶。后来又作出了39阶和38阶的完美正方形。接着Tutte等人利用他们获得的完美长方形表又拼凑出一个26阶的完美正方形，它是由一个边长为231的正方形和两个完美长方形拼合而成的，如图所示。 完美长方形 正方形 在此之前，人们对图论还没有多少研究。Tutte等人在引入网络图方法后，十分自然地将兴趣转向了对图论的研究，并因此而获得了许多具有重大意义的开创性结果，直接促进了图论的发展。

22 对偶理论  两个有向图是由同一个完美长方形得出的，它们之间必然存在着某种密切的关系，这种关系被称为对偶关系。在A、F和a、f之间各添加一条线段，对偶关系就显示出来，添线后的网络称为拼方完美长方形的完全网或C-网。每一个C-网将平面分割成若干个区域（称为面），而两个互为对偶的C-网是指具有如下性质的两个C-网：可以把它们画在平面上使任一个C-网的每一面中有且仅有另一个C-网的一个顶点，见图。 A B C D E F a b c d e f 对一个完美长方形也可用垂直线代替水平线，用类似方法作出另一个有向图。所以对一个确定的完美长方形，我们可以获得的两个不同的有向图。 c a b d e f D E A B C F 添加 添加

23 3-连通理论  前面我们已经看到，由几个完美长方形可以拼出一个新的完美长方形。相应地，新网络图与原有的完美长方形的网络之间存在着十分密切的联系。应当看到这种拼合而成的完美长方形是比较特殊的，它们与那些非拼合而成的（基本）完美长方形有着重大的区别，这些区别必然会在图论中反映出来。例如，考察由两个完美长方形拼接成的完美长方形，可以导出下述定义： 定义11.1 一个连通图如可分成两部分，这两部分只有一个公共顶点，且每一部分均含有另一部分所没有的顶点，则称此图为可分离的。不可分离的图称为2-连通图。 定义11.2 一个2-连通图若可被分成两部分，这两部分恰有两个公共顶点，且每一部分均含有另一部分所没有的顶点，则称此图为2-可分离的，2-连通但非2-可分离的图称为3-连通图。 Tutte等人从一个数学游戏开始，而最终却成了研究图论问题的专家创建了图的对偶理论、3-连通理论等。在他们取得的极其丰硕的研究成果中，人们可以清晰地看到丰富的想象力、敏锐的洞察力和严密的逻辑推理能力得到了巧妙的结合。 可分离图 2-可分离图

24 §2 公平选举问题 什么是选举 所谓选举，其实质就是在评选人对候选人先后（优劣）次序排队的基础上，根据某一事先规定的选举规则决定出候选人的一个先后次序，即得出选举结果。现用I={1,2,…,n}表示评选人集合，用有限集A={x,y,…}表示候选人集合，用>,=,<分别表示优于、等于、劣于，用(x>y)i表示评选人i认为x优于y，用(x>y)表示选举结果为x优于y并用pi表示评选人i的排序，p表示选举结果。 A的排序应满足以下性质： (1)择一性 关系式(x>y)、(x=y)、(x<y)有且仅有一个成立 (2)传递性 若x≥y, y≥z,则必有x≥z

25 简单多数规则的主要优点是简单易行，使用方便。但可惜的是这一规则有时会违反传递性
几种选举规则  简单多数规则 它规定当且仅当(x>y)i的评选人超过半数时选举结果才为(x>y)。 简单多数规则的主要优点是简单易行，使用方便。但可惜的是这一规则有时会违反传递性 例1 设I={1,2,3},A={x,y,u,v}，三位评选人的选票为 p1: x>y>u=v p2: y>x>u>v p3: x=u>v>y 有时要超过2/3多数等 根据选举规则，结果应为 P: x>y>u>v 违反传递性（2） 例2 设I={1,2,3}, A={x,y,z} p1: x>y>z p2: y>z>x p3: z>x>y 根据规则，自然应有 (x>y), (y>z)和(z>x)

26 例3 I={1,2,3,4}, A={x,y,z,u,v}，选票情况为
 Borda数规则 记Bi(x)为pi中劣于x的候选人数目，记 ，称B(x)为x的Borda数，Borda数规则规定按Borda数大小排列候选人的优劣次序，即当B(x)≥B(y)时有(x≥y)，两关系式中的等号必须同时成立。 用Borda数规则得出 的结果未必合理 对于例2，计算出B(x)=B(y)=B(z)=3 故选举结果为 x=y=z 但有三人认为x优于y 例3 I={1,2,3,4}, A={x,y,z,u,v}，选票情况为 p1p2p3: x>y>z>u>v P : y>z>u>v>x 用Borda数规则得出 的结果更合乎常理 计算得 B(x)=12，B(y)=13 故选举结果为 y>x

27 什么是“公平”的选举规则 能找到一种在任何情况下都“公平”的选举规则吗 “公平”的选举规则应当满足以下公理 公理1 公理2
投票人对候选人排出的所有可能排列都是可以实现的。 公理2 如果对所有的i，有(x≥y)i，则必须有(x≥y)。 公理3 如果在两次选举中，对任意i，由 必可得出 ，则由 必可得出 。 公理4 如果两次选举中，每个投票人对x、y的排序都未改变，则对x、y的排序两次结果也应相同。

28 公理5 有满足上述公理的选举规则吗 Arrow不可能性定理使上述想法终结 定理1 证： 首先引入决定性集合的概念。
不存在这样的投票人i，使得对任意一对候选人x、y，只要 有(x≥y)i,，就必有(x≥y)。 有满足上述公理的选举规则吗 Arrow不可能性定理使上述想法终结 定理1 如果至少有三名候选人，则满足公理1~公理5的选举规划 事实上是不可能存在的。 证： 将证明由公理1~公理4必可导出存在一个独裁者，从而违反了公理5 首先引入决定性集合的概念。 称I的子集Vxy为候选人x、y的决定性集合，如果由所有Vxy中的I 有(x≥y)i必可导出(x≥y)。 显然决定性集合是必定存在，由公理2或实际一次选举得到。 找出所有决定性集合中含元素最少的一个，不妨仍记为Vxy 。

29 证明 Vxy只能含有一个元素——某评选人i 。
反证 假定Vxy至少含有两个元素，则Vxy必可分解为两个非空集合的和 即 与 非空且不相交 ，且均不可能是任一对候选人的决定性集合 假设 根据公理1，以下选举是允许的： 当 时， （x≥y≥z）i 当 时， （z≥x≥y）i 当 时， （y＞z＞x）i 其中z是任一另外的候选人 考察选举结果 (x≥z)是不可能，否则 是x、z的决定性集合，故必 有(z＞x)。又Vxy是x、y的决定性能合，故必有(x≥y)。 由传递性(z＞x)。得 是y、z的决定性集合，从而导出矛盾。 以上证明说明Vxy不能分解，即Vxy={i}，i为某一投票人。

30 进一步说明：对于任意另外的候选人z，V={i}也是x、z的决定性集合。
考虑另一次选举：(x＞y≥z)i，而（y≥z≥x）j≠I 显然，由于全体一致意见，（y≥z）必成立。又{i}是x、y的决定性集合，故应有（x＞y）。于是，由传递性，必有（x＞z）。再由公理4，y的插入不应影响x、z的排序，故{i}也是x、z的决定性集合。类似还可证明，如果ω是异议于x、z的任一候选人，{i}也是w、z的决定性集合，这就是说，评选人i是选举的独裁者。 Arrow的公理系统隐含矛盾

31 例4 设I={1,2}, A={x,y,z}，考察如下的四次选举：
（第一次） x＞y＞z （第三次） y＞z＞x x＞y＞z z＞y＞x 结果应有 x＞y 合理结果 y=z （第二次） x＞z＞y （第四次） x＞y＞z z＞x＞y z＞x＞y 合理结果 x=z 结果？？？ x＞y，x=z与y=z 居然同时成立！ 由公理1，第四次的选举应当是有效的 由公理2，必须有（x＞y）(4) 再与第二次选举比较并根据公理3，则应有（x=z）(4) 与第三次比较并根据公理3，应有（y=z）(4)

32 改进方案 解决这一问题的另一途径是事先适当限制评选人的排序方式，使得可能出现的情况数减少，以便保证一个合理的选举规则的存在。
一个可以考虑的改进方案为要求评选人给出他对每一候选人优劣程度的评价，然后按定量方式决定候选人的顺序，但矛盾仍然不能避免，总可以构造出类似于Borda数规则中例那样的例子来。 解决这一问题的另一途径是事先适当限制评选人的排序方式，使得可能出现的情况数减少，以便保证一个合理的选举规则的存在。 由于本节的主要目的是介绍利用逻辑方法讨论实际问题的Arrow不可能性定理，关于选举问题我们就不再讨论下去了。

33 §3 信息的度量与应用 有12个外表相同的硬币，已知其中有一个是假的，可能轻些也可能重些。现要求用没有砝码的天平在最少次数中找出假币，问应当怎样称法。

34 对于系统，可以利用守恒关系有A+I=B，得I=B-A。
§3 信息的度量与应用 怎么度量信息 对于系统，可以利用守恒关系有A+I=B，得I=B-A。 首先分析一下问题的认识过程 1.对一问题毫无了解，对它的认识是不确定的 可否用消除不确定性的多少来度量信息！ 2. 通过各种途径获得信息，逐渐消除不确定性 3. 对这一问题非常的了解，不确定性很小 白箱 不确定度C 黑箱 不确定度A 灰箱 不确定度B 信息II 信息I

35 例6 假如在盛夏季节气象台突然预报“明天无雪”的消息。在明天是否下雪的问题上，根本不存在不确定性，所以这条消息包含的信息量为零。
几个例子： 例5 当你要到大会堂去找某一个人时，甲告诉你两条消息：（1）此人不坐在前十排，（2）他也不坐在后十排；乙只告诉你一条消息：此人坐在第十五排。问谁提供的信息量大？ 乙虽然只提供了一条消息，但这一条消息对此人在什么位置上这一不确定性消除得更多，所以后者包含的信息量应比前者提供的两条消息所包含的总信息量更大 例6 假如在盛夏季节气象台突然预报“明天无雪”的消息。在明天是否下雪的问题上，根本不存在不确定性，所以这条消息包含的信息量为零。

36 "I just wondered how things were put together."
是否存在信息量的度量公式 基于前面的观点，美国贝尔实验室的学者香农（Shannon）应用概率论知识和逻辑方法推导出了信息量的计算公式 In his words "I just wondered how things were put together." Claude Elwood Shannon (April 30, February 24, 2001) has been called "the father of information theory".

37 Shannon提出的四条基本性质 （不妨称它们为公理 ）
公理1 信息量是该事件发生概率的连续函数 公理2 如果事件A发生必有事件B发生，则得知事件A发生的信息量大于或等于得知事件B发生的信息量。 公理3 如果事件A和事件B的发生是相互独立的，则获知 A、B事件将同时发生的信息量应为单独获知两事件发生的信息量之和。 公理4 任何信息的信息量均是有限的。 上述公理怎样推出信息量的计算公式呢 将某事件发生的信息记为M，该事件发生的概率记为p，记M的信息量为I（M）。

38 定理2 证明: 满足公理1—公理4的信息量计算公式为I(M)=－Clogap，其中C是任意正常数，对数之底a可取任意为不为1的正实数。
由公理1 I(M)=f(p)，函数f连续。 由公理2 若A发生必有B发生，则pA≤pB， 有f(pA)≥f(PB) ，故函数f是单调不增的。 由公理3 若A、B是两个独立事件，则A、B同时发生 的概率为pApB，有f(PAPB)=f(pA)+f(pB)。 先作变量替换 令p=a-q，即q=－logaP 记 ，又 有： ，g亦为连续函数。

39 g(x+y)=g(x)+g(y)的连续函数有怎样的性质
首先，由g(0)=g(0+0)=2g(0)得出g(0)=0或g(0)=∞。 但由公理4，后式不能成立，故必有g(0)=0。 记g(1)=C，容易求得g(2)=2C,g(3)=3C,…,一般地， 有g(n)=nC。进而 ，可得 。 于是对一切正有理数 m/n，g(m/n) =(m/n)C。 由连续性可知：对一切非负实数x，有g(x)=Cx 当x取负实数时，由g(x)+g(－x)=g(0)=0，可得 出g(x)=―g(―x)=cx也成立，从而对一切实数x，g(x)=Cx, 故g(q)=Cq。 现作逆变换q=－logap， 得I(M)=f(P)=－ClogaP 证毕。

40 各种信息量单位 若取a=2,C=1，此时信息量单位称为比特 若取a=10,C=1，此时信息量单位称为迪吉特
若取a=e,C=1，此时信息量单位称为奈特

41 解： 在未知任何信息的情况下， 此人在各排的概率可以认为是相等的，他坐在各座号上的概率也可以认为是相等的，故
例7 设剧院有1280个座位，分为32排，每排40座。现欲从中找出某人，求以下信息的信息量。（i）某人在第十排；（ii）某人在第15座；（iii）某人在第十排第15座。 这一例子反映了对完全独立的几条信息，其总信息量等于各条信息的信息量之和。 对于相应不独立的信息，要计算在已获得某信息后其余信息的信息量时，需要用到条件概率公式，可以参阅信息论书籍。 解： 在未知任何信息的情况下， 此人在各排的概率可以认为是相等的，他坐在各座号上的概率也可以认为是相等的，故 （i）“某人在第十排”包含的信息量为 （比特） （ii）“某人在第15座”包含的信息量为 （比特） 5bit+5.32bit=10.32bit （iii）“某人在第十排第15座”包含的信息量为 （比特）

42 至此，我们已经引入了信息度量的定量公式。如前所述，它是信息对消除问题的不确定性的度量。这种讲法似乎有点难以为人们所接受，其实，这只是人们的习惯在起作用。这里，我们不妨来作一比较。在人们搞清热的奥秘以前，温度也是一个较为抽象的概念，因它实质上是物体分子运动平均速度的一种映。人们天生就知道冷和热，但如何来度量它却曾经是一个难题。只有在解决了这一问题以后，以定量分析为主的热力学才能得到飞速的发展。信息问题也是这样，人们对各种信息包含的实质“内容”究竟有多少往往也有一个直观的感觉，但用什么方法来度量它，却比“今天15度”这样的讲法更不易理解，因为它是通过较为抽象的概率来计算的。

43 例8 投掷一枚骼子的结果有六种，即出现1—6点、出现每 种情况的概率均为1/6，故熵 H=log26≈2.585（比特）。
平均信息量（熵）问题 设某一实验可能有N种结果，它们出现的概率分别为p1,…,pN,则事先告诉你将出现第i种结果的信息，其信息量为－log2pi，而该实验的不确定性则可用这组信息的平均信息量（或熵） 来表示 例8 投掷一枚骼子的结果有六种，即出现1—6点、出现每 种情况的概率均为1/6，故熵 H=log26≈2.585（比特）。 投掷一枚硬币的结果为正、反面两种，出现的概率均为1/2，故熵 H=log22=1（比特）。 向石块上猛摔一只鸡蛋，其结果必然是将鸡蛋摔破，出现的概率为1，故熵H=log21=0 从例子可以看出，熵实质上反映的是问题的“模糊度”，熵为零时问题是完全清楚的，熵越大则问题的模糊程度也越大

44 此定理既可化为条件极值问题证明之，也可以利用凸函数性质来证明，请大家自己去完成
离散型概率分布的随机试验，熵的定义为 ： 此定理既可化为条件极值问题证明之，也可以利用凸函数性质来证明，请大家自己去完成 连续型概率分布的随机试验，熵的定义为 : 熵具有哪些有趣的性质 定理3 若实验仅有有限结果S1,…,Sn，其发生的概率分别为 P1,…,Pn，则当 时，此实验具有最大熵。

45 定理4 定理5 定理6 若实验是连续型随机试验，其概率分布P(x)在[a,b]区间以外均为零，则当 P(x)为均匀分布时具有最大熵。
对于一般连续型随机试验，在方差一定的前提下，正态分布具有最大的熵。 定理6 最大熵原理，即受到相互独立且均匀而小的随机因素影响的系统，其状态的概率分布将使系统的熵最大。 上述结果并非某种巧合。根据概率论里的中心极限定理，若试验结果受到大量相互独立的随机因素的影响，且每一因素的影响均不突出时，试验结果服从正态分布。最大熵原理则说明，自然现象总是不均匀逐步趋于均匀的，在不加任何限止的情况下，系统将处于熵最大的均匀状态。

46 英文的熵是多少呢？ 例9 在人类活动中，大量信息是通过文字或语言来表达的，而文学或语言则是一串符号的组合。据此，我们可以计算出每一语种里每一符号的平均信息量。例如，表1、表2、表3分别是英语、德语和俄语中每一符号（字母与空格，标点符号不计）在文章中出现的概率的统计结果（汉语因符号繁多，难以统计）

47 表1（英语） 符号 Pi 空格 E T O A N I 0.2 0.105 0.072 0.0654 0.063 0.059 0.065 R S H D L C F 0.054 0.052 0.047 0.035 0.029 0.023 0.0225 U M P Y W G V 0.021 0.0175 0.012 0.011 0.008 B K X J Q Z 0.005 0.003 0.002 0.001

48 表2（德语） 符号 Pi 空格 E N S I R A 0.144 0.0865 0.0646 0.0628 0.0622 0.0594 D T U H L C G 0.0546 0.0536 0.0422 0.0361 0.0345 0.0255 0.0236 O M B W Z V F 0.0211 0.0172 0.0138 0.0113 0.0092 0.0079 0.0078 K P J Q Y 0.0071 0.0067 0.0028 0.0008 0.0005 0.0000

49 表3（俄语） 符号 Pi 空格 O E Ё A И T H C 0.175 0.090 0.072 0.062 0.053 0.045 P
B Л К М Д П у 0.040 0.038 0.035 0.028 0.026 0.025 0.023 0.021 Я Ы э ъь Б Г Ч й 0.018 0.016 0.014 0.013 0.012 0.010 Х Ж Ю Щ Ц Ш Э Ф 0.009 0.007 0.006 0.004 0.003 0.002

50 英文的多余度 以英文为例，可计算得： （比特/每符号） 对于有27个符号的信息源，可能达到的最大平均信息量为： （比特/每符号）
由此可计算出英语表达的多余度为： （即15%）

51 事实上，英语在表达意思上的确存在着富余。例如Q后出现U的概率几乎是1，T后出现H的概率也很大，等等。这种多余是完全必要的，没有多余度的语言是死板的，没有文采的，它是存在语法的必要条件。但对于电报编码、计算机文字处理来讲，这种多余度的存在常常会造成浪费。有人在上述讨论的基础上研究了符号编码问题，使得每一符号的平均信息量达到十分接近Hmax的程度，但由于译电过于复杂，这种方法尚未实际应用。

52 信息通道的容量问题 问题背景： 信息的传递是需要时间的。用n个符号S1、…、Sn来表达信息，各符号传递所需时间是各不相同的，设分别为t1、…、tn，并设各符号出现的概率分别为p1、…、pn。这样，就出现了两方面的问题。 一、pi是确定的，如何缩短传递确定信息所需的时间。 二、ti是确定的，如何使单位时间传递的平均信息量最大。 单位时间内信息通道能够传递的最大平均信息量称为此信息通道的容量

53 如何求信息通道的容量？ 每一符号的平均信息量为： 每一符号所需的平均时间为： 故单位时间内传递的平均信息量应为：

54 问题化为： 利用拉格朗日乘子法，上式可化为无约束极值问题： 记此式的目标函数为f(p,λ)，即求解方程组：

55 上述方程组的解为： 由于 是与pi有关的量，方程组的解仍无法算出 为此，记 则 ，又 得方程 记 ，g（0+）=+∞，g（+∞）=0及g’（A）＜0， 知上式有且仅有一个正根，此根容易用牛顿法求 出，进而求出最佳的 。

56 例10 为简单起见，设符号只有四种：S1、S2、S3和S4，在利用这些符号传递信息时，这些符号分别需要1、2、3、4单位传递时间，试求出此信息通道的容量及相应的最佳pi值。
解： 求解方程 ，得唯一正根A=1.92。 由A的定义可以求出此信息通道容量 ： （比特/单位时间） 而

57 货币是人们拥有财富的一种信息，它具有各种面值（相当于例10中的符号），各种面值的平均花费时间是不等的（相当于例10中的时间），于是，如何控制各种面值的比例以便使货币流通的容量最大显然是一个十分有意义的问题。日本东京工业大学的国泽清典教授基于上述方法计算了100日元与500日元信用券应保持的比例，并与市场实际调查作了对比，发现两者完全一致。市场多次调查结果均为100日元占75%，500日元占25%，而计算结果如下：以百元为单位，令t1=1,t2=5，求解方程 求得正根A≈1.327 信息通道容量为log2A≈0.408（比特/每单位）

58 练习 任意选取黑白两种颜色的小球共8个排在如下图所示的圆圈上，然后执行如下操作：
在两个颜色相同的小球中间放一个黑色小球，在两个颜色不同的小球中间放一个白色小球，放完后撤掉原来所放的小球。 重复以上的过程。证明最多经过8次变换，圆圈上的小球都会变成黑色。如果小球个数为n，结论又如何？