概述 在一群人面对威胁或损失时，“第一个采取行动”的决定是很难做出的，因为它意味着将付出惨重代价。这个困境便就叫做人质困境。 枪打出头鸟，人质联合固然可以制服歹徒，但是谁愿出头。这一点给了无数处于劫持者地位的一方以机会，类似于秦的远交近攻、各个击破的策略，将最终全盘赢下。人质可有反制的策略，当然有，不过艰难至极。人质可以选择沉默，这样他有一定时间苟延残喘；或者联合劫持者对付人质，结局还是取决于劫持者，万一他过河拆桥怎么办；同时反抗，集体将获得左右策略，但是这需要壮士断腕的勇气，部分人可能因此受伤。这里是实力与勇气的较量，而且实力暂居上风。 事例 童话故事里有一个给猫拴铃挡的故事，大意是这样：老鼠们意识到，假如可以在猫脖子上拴一个铃挡，那么，它们的小命就会大有保障。问题在于，谁会愿意冒赔掉小命的风险给猫拴上铃档呢？ 这个问题同样摆在老鼠和人类面前。占据支配地位的党派或独裁暴君怎样才能通过规模相对较小的军队长期控制数目很大的一个人群呢？整架飞机的众多乘客为什么只要出现一个持枪劫机者就会显得无计可施，束手就擒？ 在这两个例子里，只要大多数人同时采取行动，就很容易取得成功。不过，统一行动少不了沟通与合作，偏偏沟通与合作在这个时候变得非常困难，而压迫者由于深知群众的力量有多大，还会采取特殊的措施，阻挠他们进行沟通与合作。一旦人们不得不单独行动，希望聚沙成塔，集腋成裘，问题就出来了：“谁该第一个采取行动？”担当这个任务的领头人意味着要付出重大代价，甚至可能付出生命。他得到的回报则会是死后的光荣或受人感激。确实有人在想到责任或荣誉的时候会感到热血沸腾，挺身而出，但大多数人还是认为这么做的代价超出了得益。 分析 现在用这个困境阐述一个不同的观点，确切地说，就是惩罚经常压倒回报而处于上风。独裁者可以通过向大众提供物质乃至精神安慰保持局势稳定，不过，这个做法可能需要付出高昂代价。建立在人质困境之上的压迫和恐吓可能是一种代价小得多的替代选择。 实例1：在一个大型出租车队里，汽车经常是由调度员派给司机的。车队里既有好车，也有年久失修的老爷车。调度员可以利用他的调度权向每个司机收取一点贿赂。谁若是拒绝行贿，就一定会得到一部老爷车，而那些愿意合作的司机就会“抽到”上上好签。这么一来，调度员是发达了，但司机们作为一个群体，面对的还是他们就算不贿赂调度员也能得到的同样一些汽车。假如司机们联合起来，也许可以结束这种被迫行贿的日子，问题在于怎样才能组织起来采取行动。问题的关键不是调度员能从行贿者那里得到多少好处，而是他可以严厉惩罚那些不肯行贿的人。最终的结果是，哪怕大家都交钱，一些司机最后还是会分配到一辆老爷车。不过，假如老爷车是随机分配的，也就不会出现哪个司机比较容易得到老爷车的情况。相反，带头拒绝交钱的司机通常都会得到老爷车。 实例2：将租户从实行房租控制的公寓中赶出去是另外一个类似的例子。假如某人在纽约买了这么一幢房子，他有权赶走一个租户，这样自己就能住进去。不过，这个规定最后却变成了赶走全部租户的权利。一个新房东可以对住在1A房间的租户说：“我有权住在自己的房子里。因此，我打算把你赶走，搬进你的房间。不过，假如你肯合作，自愿离开，我会给你5000美元作为报答。”租户面临两个选择，一是拿着5000美元走人，二是什么也得不到，还是要走人，当然他选择前者。接下来，房东向1B1的租户说同样的话，直到所有租户都搬家走人。 实例3：汽车制造业工人工会在跟汽车制造商一个接一个进行谈判的时候也占有类似的优势。单是一场针对福特汽车公司的罢工就会使福特处于非常不利的地位，因为通用汽车公司和克莱斯勒公司继续对工会采取合作态度，因此，福特很有可能迅速采纳对工会有利的条件，达成和解。这么一场罢工在工会这边看来代价也是较小的，毕竟只有1/3的工会成员失去工作。赢得福特一役之后，工会转而会跟通用谈判，接着是克莱斯勒，引用前面各次战役的胜利作为先例，进一步壮大自己的声威。日本工会则另有一套做法，因为日本工会是由公司组织的，在公司里占有很大的利润份额。假如丰田的工会罢工，其成员的薪水就会随着丰田的利润下跌而下跌，他们以前的努力什么也得不到。 问题产生的机制称为“手风琴效应”，每一个折叠都会推动或拉动邻近一个折叠。每一个体都做了相同的选择，但都是错误的选择。这一现象虽然一再发生，其实又是可以克服的。[1]
三元悖论三元悖论，也称三难选择，它是由美国经济学家保罗·克鲁格曼就开放经济下的政策选择问题所提出的，其含义是：本国货币政策的独立性，汇率的稳定性，资本的完全流动性不能同时实现，最多只能同时满足两个目标，而放弃另外一个目标。 概念 三元悖论，也称三难选择，它是由美国经济学家保罗·克鲁格曼就开放经济下的政策选择问题所提出的，其含义是：本国货币政策的独立性，汇率的稳定性，资本的完全流动性不能同时实现，最多只能同时满足两个目标，而放弃另外一个目标。根据蒙代尔的三元悖论，一国的经济目标有三种：：①各国货币政策的独立性；②汇率的稳定性；③资本的完全流动性。 这三者，一国只能三选其二，而不可能三者兼得。例如，在1944年至1973年的“布雷顿森林体系”中，各国“货币政策的独立性”和“汇率的稳定性”得到实现，但“资本流动”受到严格限制。而1973年以后，“货币政策独立性”和“资本自由流动”得以实现，但“汇率稳定”不复存在。“永恒的三角形”的妙处，在于它提供了一个一目了然地划分国际经济体系各形态的方法。 提出 米德三元悖论理论最早可以溯源至英国经济学家米德（1953），他分析了开放经济条件下内部均衡目标和外部均衡目标发生冲突，即“米德冲突”。其中，在保证包括货币政策在内的支出增减政策有效的情况下，固定汇率制度和资本自由流动是不能共存的，这与后来提出的“三元悖论”理论之间有着理论传承关系。 米德 蒙代尔(1963)提出了著名的M-F模型，为后来“三元悖论”理论的提出奠定了重要基础。亚洲金融危机后，克鲁格曼(1998)在《亚洲发生了什么》一文中阐述了资本流动情况下固定汇率制度是危机爆发的主要原因这一观点，并首次明确提出了“三元悖论”的原则。后来，克鲁格曼又在其著作《萧条经济学的回归》一书中对这一原则进行了论述，使得该原则被越来越多的人所认同。[2] 形成及发展 蒙代尔三角 第二次世界大战后首先对固定汇率制提出异议的是米尔顿·弗里德曼(mihonfriedman)。他在1950年发表的《浮动汇率论》一文中指出，固定汇率制会传递通货膨胀，引发金融危机，只有实行浮动汇率制才有助于国际收支平衡的调节。接着，英国经济学家詹姆斯·米德(jamesmeade）在1951年写成的《国际经济政策理论》第一卷《国际收支》一书中也提出，固定汇率制度与资本自由流动是矛盾的。他认为，实行固定汇率制就必须实施资本管制，控制资本尤其是短期资本的自由流动。该理论被称为米德“二元冲突”或“米德难题”。[1]罗伯特·蒙代尔（Robert A。 Mundell）在研究了20世纪50年代国际经济情况以后，提出了支持固定汇率制度的观点。20世纪60年代，蒙代尔和J。马库斯·弗莱明（J。Marcus Flemins）提出的蒙代尔—弗莱明模型（Mundell-Fleming Model）对开放经济下的ISLM模型进行了分析，堪称固定汇率制下使用货币政策的经典分析。该模型指出，在没有资本流动的情况下，货币政策在固定汇率下在影响与改变一国的收入方面是有效的，在浮动汇率下则更为有效；在资本有限流动情况下，整个调整结构与政策效应与没有资本流动时基本一样；而在资本完全可流动情况下，货币政策在固定汇率时在影响与改变一国的收入方面是完全无能为力的，但在浮动汇率下，则是有效的。由此得出了着名的“蒙代尔三角”理论，即货币政策独立性、资本自由流动与汇率稳定这三个政策目标不可能同时达到。1999年，美国经济学家保罗·克鲁格曼（Paul Krugman）根据上述原理画出了一个三角形，他称其为“永恒的三角形”（The Eternal Triangle），从而清晰地展示了“蒙代尔三角”的内在原理。 内容 根据三元悖论，在资本流动，货币政策的有效性和汇率制度三者之间只能进行以下三种选择(1)保持本国货币政策的独立性和资本的完全流动性，必须牺牲汇率的稳定性，实行浮动汇率制。这是由于在资本完全流动条件下，频繁出入的国内外资金带来了国际收支状况的不稳定，如果本国的货币当局部进行干预，亦即保持货币政策的独立性，那么本币汇率必然会随着资金供求的变化而频繁的波动。利用汇率调节将汇率调整到真实反映经济现实的水平，可以改善进出口收支，影响国际资本流动。虽然汇率调节本身具有缺陷，但实行汇率浮动确实较好的解决了“三难选择”。但对于发生金融危机的国家来说，特别是发展中国家，信心危机的存在会大大削弱汇率调节的作用，甚至起到恶化危机的作用。当汇率调节不能奏效时，为了稳定局势，政府的最后选择是实行资本管制。 (2)保持本国货币政策的独立性和汇率稳定，必须牺牲资本的完全流动性，实行资本管制。在金融危机的严重冲击下，在汇率贬值无效的情况下，唯一的选择是实行资本管制，实际上是政府以牺牲资本的完全流动性来维护汇率的稳定性和货币政策的独立性。大多数经济不发达的国家，就是实行的这种政策组合。这一方面是由于这些国家需要相对稳定的汇率制度来维护对外经济的稳定，另一方面是由于他们的监管能力较弱，无法对自由流动的资本进行有效的管理。 (3)维持资本的完全流动性和汇率的稳定性，必须放弃本国货币政策的独立性。资本完全流动时，在固定汇率制度下，本国货币政策的任何变动都将被所引致的资本流动的变化而抵消其效果，本国货币丧失自主性。在这种情况下，本国或者参加货币联盟，或者更为严格地实行货币局制度，基本上很难根据本国经济情况来实施独立的货币政策对经济进行调整，最多是在发生投机冲击时，短期内被动地调整本国利率以维护固定汇率。可见，为实现资本的完全流动与汇率的稳定，本国经济将会付出放弃货币政策的巨大代价。 主要缺点 “三元悖论”原则的理论内涵经历了“米德二元冲突—M-F模型—三元悖论”这样一个发展历程。现在，“三元悖论”原则已经成为国际经济学中的一个著名论断。但是，该理论是高度抽象的，只考虑了极端的情况，即完全的货币政策独立、完全的固定汇率和完全的资本自由流动，并没有论及中间情况。正如弗兰克尔指出的，“并没有令人信服的证据说明，为什么不可以在货币政策独立性和汇率稳定两个目标的抉择中各放弃一半，从而实现一半的汇率稳定和一半的货币政策独立性。”这不能不说是“三元悖论”理论在具体目标选择问题分析方面的局限。 还有一点值得指出的是，根据“三元悖论”原则，资本自由流动、固定汇率制和货币政策非独立性三者的组合是一个可行的选择，但是这一组合在现实中有效的前提是在假设一国外汇储备无上限的条件下才能成立。实际上，现实中一国的外汇储备不可能无上限，一国的外汇储备总量再巨大，与规模庞大的国际游资相比也是力量薄弱的，一旦中央银行耗尽外汇储备仍无力扭转国际投资者的贬值预期，则其在外汇市场上将无法继续托市，固定汇率制也将彻底崩溃。因此，一国即使放弃货币政策的独立性，在巨大的国际游资压力下，往往也很难保证固定汇率制度能够得以继续。 [2]
概述 圣彼得堡悖论圣彼得堡悖论是决策论中的一个悖论。圣彼得堡悖论是数学家丹尼尔·伯努利（Daniel Bernoulli）的表兄尼古拉·伯努利(Daniel Bernoulli)在1738提出的一个概率期望值悖论，它来自于一种掷币游戏，即圣彼得堡游戏(表1)。设定掷出正面或者反面为成功，游戏者如果第一次投掷成功，得奖金2元，游戏结束；第一次若不成功，继续投掷，第二次成功得奖金4元，游戏结束；这样，游戏者如果投掷不成功就反复继续投掷，直到成功，游戏结束。如果第n次投掷成功，得奖金2n元，游戏结束。按照概率期望值的计算方法，将每一个可能结果的得奖值乘以该结果发生的概率即可得到该结果奖值的期望值。 基本介绍 游戏的期望值即为所有可能结果的期望值之和。随着n的增大，以后的结果虽然概率很小，但是其奖值越来越大，每一个结果的期望值均为l，所有可能结果的得奖期望值之和，即游戏的期望值，将为“无穷大”。按照概率的理论，多次试验的结果将会接近于其数学期望。但是实际的投掷结果和计算都表明，多次投掷的结果，其平均值最多也就是几十元。正如Hacking(1980)所说：“没有人愿意花25元去参加一次这样的游戏。”这就出现了计算的期望值与实际情况的“矛盾”，问题在哪里? 实际在游戏过程中，游戏的收费应该是多少? 决策理论的期望值准则在这里还成立吗?这是不是给“期望值准则”提出了严峻的挑战? 正确认识和解决这一矛盾对于人们认识随机现象、发展决策理论和指导实际决策无疑具有重大意义。、 圣彼得堡悖论 圣彼得堡问题对于决策工作者的启示在于，许多悖论问题可以归为数学问题，但它同时又是一个思维科学和哲学问题。悖论问题的实质是人类自身思维的矛盾性。从广义上讲，悖论不仅包括人们思维成果之间的矛盾，也包括思维成果与现实世界的明显的矛盾性。对于各个学科各个层次的悖论的研究，历来是科学理论发展的动力。圣彼得堡悖论所反映的人类自身思维的矛盾性，首先具有一定的哲学研究的意义；其次它反映了决策理论和实际之间的根本差别。人们总是不自觉地把模型与实际问题进行比较，但决策理论模型与实际问题并不是一个东西；圣彼得堡问题的理论模型是一个概率模型，它不仅是一种理论模型，而且本身就是一种统计的 “近似的”模型。在实际问题涉及到无穷大的时候，连这种近似也变得不可能了。 论文解释 丹尼尔·伯努利对这个悖论的解答在1738年的论文里，提出了效用的概念以挑战以金额期望值为决策标准，论文主要包括两条原理： 1、边际效用递减原理：一个人对于财富的占有多多益善，即效用函数一阶导数大于零；随着财富的增加，满足程度的增加速度不断下降，效用函数二阶导数小于零。 2、最大效用原理：在风险和不确定条件下，个人的决策行为准则是为了获得最大期望效用值而非最大期望金额值。 消解历史 圣彼得堡悖论的提出已有200多年了，所提出的消解方法大致可以归纳为以下几种观点： (一)边际效用递减论 Daniel Bernoulli在提出这个问题的时候就给出一种解决办法。他认为游戏的期望值计算不应该是金钱，而应该是金钱的期望效用，即利用众所周知的“期望效用递减律”，将金钱的效用测度函数用货币值的对数来表示:效用=log(货币值)，如表 2所示。所有结果的效用期望值之和将为一个有限值log(4)≈ 0.60206，如果这里的效用函数符合实际，则理性决策应以4元为界。这一解释其实并不能令人满意。姑且假定“效用递减律”是对的，金钱的效用可以用货币值的对数来表示。但是如果把奖金额变动一下，将奖金额提高为l0的2n次方(n=3时，奖金为108)，则其效用的期望值仍为无穷大，新的悖论又出现了 当然，我们并不清楚效用值与货币值之间究竟有什么样的关系，不过只要我们按照效用的2n倍增加奖金，悖论就总是存在。 圣彼得堡悖论 (二)风险厌恶论 圣彼得堡悖论对于奖金额大小没有限制，比如连续投掷40次才成功的话，奖金为1.1万亿元。但是这一奖金出现的概率极小，1.1万亿次才可能出现一次。实际上，游戏有一半的机会，其奖金为 2元，四分之三的机会得奖4元和2元。奖金越少，机会越大，奖金越大，机会越小。如果以前面 Hacking所说。花25元的费用冒险参与游戏将是非常愚蠢的，虽有得大奖的机会，但是风险太大。因此，考虑采用风险厌恶因素的方法可以消解矛盾。Pual Weirich就提出在期望值计算中加人一种风险厌恶因子，并得出了游戏费用的有限期望值，认为这种方法实际上解决了该悖论。 但是这种方法也并不十分完美。首先，并非所有人都是风险厌恶的，相反有很多人喜欢冒险。如每期必买的彩票，以及Casino(卡西诺)纸牌游戏，其价格都高于得奖的期望值。你也可以说这些喜欢冒险买彩票和赌博的人是非理性的，可他们自有乐趣，喜欢这样的风险刺激。总之，风险厌恶的观点很难解释清楚实际游戏平均值非常有限的问题。退一步说，即便承认风险厌恶的观点，矛盾仍然不能消除。我们仍然可以调整奖金额，最后，考虑风险厌恶情况的期望值仍然是无穷大而与实际情况不符。 (三)效用上限论 对前两种观点的反驳，我们采用了增加奖金额的方法来补偿效用的递减和风险厌恶，两者均是假定效用可以无限增加。也有一种观点认为奖金的效用可能有一个上限，这样，期望效用之和就有了一个极限值。Menger认为效用上限是惟一能消解该悖论的方法。设效用值等于货币值，上限为100 单位，则游戏的期望效用为7.56l25，如表3所示。也许这里的效用上限太小了，不过我们可以任意选定一个更大的值比如225 。有多人如Russell Har—din (1982)，W illiam G uNtaNon (1994)，Richard Jeffrey(1983)等都赞成这样的观点。不过这种效用上限的观点似乎不太令人信服。效用上限与效用递减不同，或许你认为有225 的钱够自己花的了，可是钱并不能给我们带来所有的效用，有些东西不是钱所能买来的。效用上限意味着再也没有价值可以添加了。但是一个人有了钱，还希望他的朋友、亲戚也像他一样富有；同一个城市里的人和他一样富有...。而效用上限论认为到了这一上限他们就不用再做任何交易了，看起来这并不能成立。对有些人来讲，似乎期望和需求并不是无限增加的，对于现有的有限需求他们已经满足了。他们觉得这里的游戏期望效用值确实是有限的。不过是不是确实有这样的人还是一个不确定的问题，或者是个经验性的问题。但认为“越多越好”的人确实是存在的。对于决策准则这样的理性选择的理论，不能基于可疑的和经验性的判断而加以限制，因而期望有限论不足以消解这里的矛盾。 圣彼得堡悖论 (四)结果有限论 Gustason认为，要避免矛盾，必须对期望值概念进行限制，其一是限制其结果的数目；其二是把其结果值的大小限制在一定的范围内。这是典型的结果有限论，这一观点是从实际出发的。因为实际上，游戏的投掷次数总是有限的数。比如对游戏设定某一个投掷的上限数L，在投掷到这个数的时候，如果仍然没有成功，也结束游戏，不管你还能再投多少，就按照L付钱。因为你即便不设定L，实际上也总有投到头的时候，人的寿命总是有限的，任何原因都可以使得游戏中止。现在设定了上限，期望值自然也就可以计算了。 问题是，这已经不是原来的那种游戏了!同时也并没有证明原来的游戏期望值不是无限大。原来的游戏到底存在吗? Jeffrey说：“任何提供这一游戏的人都是一个骗子，谁也没有无限大的银行!” 是说实际上没有这种游戏吗? 恐怕这也不见的。如果我邀请你玩这种游戏，你说我实际上不是在这样做吗? 或者说我实际上邀请你玩的不是这种游戏而是另外的什么游戏? 很多游戏场提供许多概率极小、奖金额极大几乎不可能的游戏，他们仍然在经营、在赚钱，照样吃饭睡觉，一点儿也不担心哪一天会欠下一屁股债，崩盘倒闭。 Jeffrey在这样说的时候，实际上是承认了圣彼得堡游戏的期望值是无穷大了。认为游戏厅不提供这样的游戏，正是因为他们认为其期望值是无穷大，迟早他们会因此而破产倒闭。这正是用了常规的决策理论，而反过来又说这种游戏实际上不存在，应该排除在期望值概念之外。因此，用限制期望值概念的方法并不能消解悖论。 不能限制期望值概念的原因还有很多。比如，我们不能用限制期望值概念的方法仅把圣彼得堡游戏排除在外，而应该是通用的。在人寿保险中，有一个险种根据保险人的年龄，每长一岁给付一定的赔付金额。采用人类寿命的经验曲线给出每个年龄的生存机会。大于140岁的生存率已经没有经验可以借鉴，但可以采用一定的函数将生存年龄扩展至无穷大，当然其生存率趋向于零。注意到这里的给付金额也是无限的，但是其在期望值计算方面并没有出现什么问题。 问题的本质 所谓悖论， 《辞海》中的定义是：“一命题B，如果承认B，可推得非B，反之，如果承认非B，又可推得 圣彼得堡悖论B，称命题B 为一悖论。”可见，作为一种推理的矛盾现象，悖论是人们自己制造出来的。现在已经有人证明，这种意义上的悖论是不存在的。一个命题是一个具有真假的判断语句，如果一个命题B 和非B 能够相互推出，则B要么是非真非假的单义句，要么是非真非假的多义句。所以，悖论作为人类思维系统的一种矛盾形式，它的消解必须从人们思维系统自身的矛盾性和不完善性着手，需要人类战胜和超越自己。历史上一次一次的悖论的消解，提出了更完备的公理系统，完善了人类的思维和科学系统，使得科学得到进一步的发展。圣彼得堡悖论也是一样。 (一)对圣彼得堡悖论各种消解观点的评述 综合上述悖论的消解观点，效用递减论符合了 “边际效用递减律”，能够在一定程度上解决实际问题，但是却绕开了问题的基本面。圣彼得堡游戏的期望值到底是多少并没有真正得到解决；风险厌恶论，犯了同样的错误，只不过是用风险因子替换了效用函数，实际上只是一种风险效用；效用上限论和结果上限论试图回避问题的无限性，篡改了原问题，自然也不可能解决问题。这些观点都是从实际出发的，但都没有触及人们的思维系统，不能冲破自己思想的牢笼，即便解决了这一悖论，又会有新的悖论出现。 (二)最后的消解 从上述圣彼得堡悖论的消解方法来看，其效果都不是十分理想，都没有真正解决问题。但是正是这些努力，是我们认识到仅从实际出发是不能解决问题的，而最合理的解释就是— — 保留期望值的定义，调整我们的思维。当我们这样做的时候，圣彼得堡悖论就不再是一个悖论了!理论上期望值的计算没有什么错误，我们需要承认它的期望值是无穷大；而实际上它的均值又不可能是无穷大，因为它是样本均值，样本均值随着样本容量的增加，以概率收敛于其期望值。这都是正常的，它们本身就是应该有差距的!至于差距应该有多大，在小于无穷大的时候，样本均值随着实验次数的增多，越来越接近总体均值(或理论均值)，圣彼得堡游戏不正是这样的吗? 而在总体均值是无穷大的时候，我们如何让样本均值如何接近无穷大呢? 非得是我们认为的很大很大吗?再大也不是无穷大，和现在也没有区别，我们平时的“大小”概念已经不适应了。涉及无穷大概念比较的时候，就需要用相应的比较方法。圣彼得堡游戏的结果集合是一个无穷集合，而实际实验的样本是一个有穷集合，它们是不能用现有的办法比较的。 利用电脑进行模拟试验的结果说明，实际试验的平均值— — 样本均值是随着实验次数的增加而变化的。在大量实验以后，其实验均值X可以近似表示为X≈logn/log2，可见当实验次数趋向无穷大的时候，样本均值也趋向无穷大。比如100万即106次实验的平均值约等于6/0.301=19.9，即 20元左右；要样本均值达到1 000元，实验次数就要达到10332，这时候有可能出现的最高投掷次数约为1000次左右，相应的最高赔付金额为 ，已经达到了天文数字了。如果随着实验次数趋向无穷大，趋向于无穷大的速度是慢多了。 与现实的启示 虽然圣彼得堡游戏问题只是一个具体问题，但是类似的实际决策问题是存在的。它们起码是可观察的，其观察值确实也是存在的。而且它确实也给决策的期望值准则提出了挑战，所提出的问题需要我们给予解答。通过上述问题的消解，我们至少可以给出下列有关问题的答案和启示。 首先，理论上应该承认圣彼得堡游戏的“数学期望”是无穷大的。但理论与实际是有差别的，在涉及无穷大决策问题的时候，必须注意这种差别。 其次，实际试验中随着游戏试验次数的增加，其均值将会越来越大，并与实验次数呈对数关系，即样本均值=log 圣彼得堡悖论2(实验次数)=log(实验次数)/log2。 再次，实际问题的解决还是要根据具体问题进行具体分析。前面的圣彼得堡悖论消解方法都是很实用的方法。也--I以设计其他方法，比如可以运用“实际推断原理”，根据实验次数n设定一个相应的“小概率”，对于圣彼得堡问题来讲，是一个很实际的方法；或者建立一个近似模型，比如确定一个最大可能成功的投掷次数n，将投掷n 1次以后的概率设为1 / 2k，仍然符合概率分布的条件(所有结果的概率之和等于1)等等。 最后，圣彼得堡问题对于决策工作者的启示在于，许多悖论问题可以归为数学问题，但它同时又是一个思维科学和哲学问题。悖论问题的实质是人类自身思维的矛盾性。从广义上讲，悖论不仅包括人们思维成果之间的矛盾，也包括思维成果与现实世界的明显的矛盾性。对于各个学科各个层次的悖论的研究，历来是科学理论发展的动力。圣彼得堡悖论所反映的人类自身思维的矛盾性，首先具有一定的哲学研究的意义；其次它反映了决策理论和实际之间的根本差别。人们总是不自觉地把模型与实际问题进行比较，但决策理论模型与实际问题并不是一个东西；圣彼得堡问题的理论模型是一个概率模型，它不仅是一种理论模型，而且本身就是一种统计的 “近似的”模型。在实际问题涉及到无穷大的时候，连这种近似也变得不可能了。 决策科学是一门应用学科，它的研究需要自然科学和社会科学的各种基础理论和方法，包括数学方法。这些方法都具有很强的理论性和高度抽象性。但是，决策科学更是一门应用性、实践性很强的学科，要求决策理论与决策实践紧密结合。因此，我们在决策理论的研究和解决实际问题的时候，应高度重视理论和实践的关系。理论模型的建立，既要源于实践，又不能囿于实践，发挥主观创造力，才能有所突破，有所建立。
概述20世纪50年代早期，Lloyd Shapley提出了随机博弈的概念。Neyman和Sorin所著的书籍是最完备的有关随机博弈的参考材料。Filar和Vrieze所著的书更为基础，在书中给出了严密的关于马尔可夫决策过程和双人随机博弈的标准处理方法。他们创造了Competitive MDPs这个术语来概括单人和双人随机博弈这个概念。 规则 随机博弈是指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下： 1、每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子。 2、如果谁取到最后一枚石子就胜。 数学描述 随机博弈的组成部分有：有限参与者集I；状态空间M（可以是有限集，也可以是可测空间(M,{mathcalA})）；对于每一参与者iinI，存在行动集S^i,（可以是有限集，也可以是可测空间(S^i,{mathcalS}^i)）；P是MtimesS到M的转移概率，其中S=times_{iinI}S^i是行动组合，P(Amidm,s)是下一状态处于A中的概率，而A给定了当前状态m和当前行动组合s；从MtimesS到R^I,的收益函数g，其中g的第i个坐标g^i,是参与者i的收益，而g^i,是状态m和行动组合s的函数。 博弈以某个初始状态m1开始。在阶段t中，参与者最先观测到mt，同时选择行动s^i_tinS^i，然后观测到行动组合s_t=(s^i_t)_i，然后以概率P(cdotmidm_t,s_t)自然选择mt+1。一次随机博弈m_1,s_1,ldots,m_t,s_t,ldots定义了一个收益流g_1,g_2,ldots，其中g_t=g(m_t,s_t),。 目录 1理论 理论 在博弈论中，随机博弈是一种包含一个或多个参与者进行的具有状态概率转移的动态博弈过程。随机博弈由多个博弈阶段组成。在每一个阶段的开始，博弈处在某个特定状态下。参与者选择自身的策略并获得相应的由当前状态和策略决定的报酬。然后博弈按照概率的分布和参与者策略随机转移到下一个阶段。在新的状态阶段，重复上一次的策略选择过程，然后博弈继续进行。参与者在随机博弈中获得的全部报酬一般用各个阶段报酬的贴现值来计算，或者用各个阶段报酬平均值的下限来计算。 如果随机博弈中参与者的数量有限并且每个博弈阶段可能的状态数量有限，那么一个具有有限博弈阶段的随机博弈一般都存在一个纳什均衡。同样的，对于一个具有无穷阶段的随机博弈，如果使用各个阶段报酬的贴现值来计算整个博弈阶段的报酬，那么这个随机博弈也是具有纳什均衡的。Vieille已经证明具有有限阶段和有限状态的两人随机博弈当中，如果博弈过程的报酬使用各个阶段报酬平均值的下限来计算的话，是具有逼近纳什均衡的。然而，包含2个以上的参与者的随机博弈是否存在纳什均衡，仍然是个未决的问题。 随机博弈在经济学和演化生物学中都有应用。事实上，随机博弈是重复博弈的一般化过程（重复博弈是指在每个博弈阶段都处于相同的状态）。 重要结论 贴现因子为λ（0<lambdaleq1）的贴现博弈Γλ中，参与者i的收益是lambdasum_{t=1}^{infty}(1-lambda)^{t-1}g^i_t。n阶段博弈中，参与者i的收益是bar{g}^i_n:=frac1nsum_{t=1}^ng^i_t。 若存在有限多个状态和行动的二人零和博弈Γn（各自是Γλ）的值为vn(m1)（各自是vλ(m1)），则vn(m1)在n趋于无穷时收敛到一个极限，且vλ(m1)在λ趋于0时收敛到相同的极限。这一结论已被杜鲁门·彪利（TrumanBewley）和艾朗·克尔伯格（ElonKohlberg）于1976年证明。 非贴现博弈Gamma_infty中，参与者i的收益是各阶段收益平均值的极限。在定义二人零和博弈Gamma_{infty}的值与非零和博弈Gamma_{infty}的均衡收益之前需要注意一些事情：若对于每一varepsilon>0都有正整数N、参与者1的策略sigma_{varepsilon}和参与者2的策略tau_{varepsilon}，二人零和随机博弈Gamma_infty的一致值（uniformvalue）v_{infty}存在，这样对于每一σ、τ和每一ngeqN，博弈中由sigma_{varepsilon}和τ定义的概率的bar{g}^i_n期望至少为v_{infty}-varepsilon，由σ和tau_{varepsilon}定义的概率的bar{g}^i_n期望至多为v_{infty}+varepsilon。让·弗朗索瓦·梅顿斯（JeanFrancoisMertens）和亚伯拉罕·奈曼（AbrahamNeyman）于1981年证明二人零和随机博弈具有一致值。 若参与者数量有限且行动集和状态集有限，则有限阶段随机博弈总有纳什均衡，对于总收益是贴现和的无限多阶段随机博弈也是如此。尼古拉斯·维勒（NicolasVieille）已经证明当总收益是各阶段收益平均值的下极限时，所有具有有限状态和行动空间的二人随机博弈都有近似纳什均衡。不过，当参与者多于2名时，随机博弈是否存在这类均衡仍是一个极具挑战性的开放性问题。 应用 随机博弈在经济学、演化生物学和计算机网络中都有应用。事实上，随机博弈是重复博弈的一般化过程（重复博弈是指在每个博弈阶段都处于相同的状态）。 亚伯拉罕·奈曼（AbrahamNeyman）和SylvainSorin所著的书籍是最完备的有关随机博弈的参考材料。JerzyA.Filar和KoosVrieze所著的书更为基础[1]，在书中给出了严密的关于[[马尔可夫决策过程]（MDP）和双人随机博弈的标准处理方法。他们创造了CompetitiveMDPs这个术语来概括单人和双人随机博弈这个概念。[1]
解释 理解生日悖论的关键在于领会相同生日的搭配可以是相当多的。如23个人可以产生C(23,2)= 23 × 22/2 = 253 种不同的搭配，而这每一种搭配都有成功相等的可能。从这样的角度看，在253种搭配中产生一对成功的配对也并不是那样的不可思议。 换一个角度，如果你进入了一个有着22个人的房间，房间里的人中会和你有相同生日的概率便不是五十五十了，而是变得非常低。原因是这时候只能产生22种不同的搭配。生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少。 计算 不计特殊的年月，如闰二月。先计算房间里所有人的生日都不相同的概率，那么 第一个人的生日是 365选365 第二个人的生日是 365选364 第三个人的生日是 365选363 : : : 第n个人的生日是 365选365-(n-1) 所以所有人生日都不相同的概率是： (365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365) 那么，n个人中有至少两个人生日相同的概率就是： 1-(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365) 所以当n=23的时候，概率为0.507 当n=100的时候，概率为0.9999996 测试 生日悖论可以用计算机代码经验性模拟： days := 365; numPeople := 1; prob := 0.0; while prob < 0.5 begin numPeople := numPeople + 1; prob := 1 - ((1-prob) * (days-(numPeople-1)) / days); print "Number of people: " + numPeople; print "Prob. of same birthday: " + prob; 延伸 此问题另外一个范化就是求得要在随机选取多少人中才能找到2个人生日相同，相差1天，2天等的概率大于50％ 。这是个更难的问题需要用到容斥原理。结果(假设生日依然按照平均分布)正像在标准生日问题中那样令人吃惊： 2人生日相差k天 #需要的人数0 23 1 14 2 11 3 9 4 8 5 7 7 6 只需要随机抽取6个人，找到两个人生日相差一周以内的概率就会超过50%。 应用 生日悖论普遍的应用于检测哈希函数:N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解cryptographic hash function的生日攻击中。生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用，来估计湖里鱼的数量。[1]
三门问题——亦称为蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论（Monty Hall problem） 目录 1什么是三门问题 2问题与解答 3参考资料 什么是三门问题 三门问题（Monty Hall problem），是一个源自博弈论的数学游戏问题，大致出自美国的电视游戏节目Let's Make a Deal。问题的名字来自该节目的主持人蒙提·霍尔（Monty Hall）。 这个游戏的玩法是：参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门就可以赢得该汽车，而另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门，但未去开启它的时候，节目主持人会开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。问题是：换另一扇门会否增加参赛者赢得汽车的机会率？如果严格按照上述的条件的话，答案是会—换门的话，赢得汽车的机会率是 2/3。 这条问题亦被叫做蒙提霍尔悖论：虽然该问题的答案在逻辑上并不自相矛盾，但十分违反直觉。这问题曾引起一阵热烈的讨论。 问题与解答 问题 以下是蒙提霍尔问题的一个著名的叙述，来自 Craig F. Whitaker 于1990年寄给《展示杂志》（Parade Magazine）玛丽莲·沃斯·莎凡特（Marilyn vos Savant）专栏的信件： 假设你正在参加一个游戏节目，你被要求在三扇门中选择一扇：其中一扇后面有一辆车；其余两扇后面则是山羊。你选择了一道门，假设是一号门，然后知道门后面有什么的主持人，开启了另一扇后面有山羊的门，假设是三号门。他然后问你：“你想选择二号门吗？”转换你的选择对你来说是一种优势吗？ 以上叙述是对 Steve Selvin 于1975年2月寄给 American Statistician 杂志的叙述的改编版本。如上文所述，蒙提霍尔问题是游戏节目环节的一个引申；蒙提·霍尔在节目中的确会开启一扇错误的门，以增加刺激感，但不会容许玩者更改他们的选择。如蒙提·霍尔寄给 Selvin 的信中所写： 如果你上过我的节目的话，你会觉得游戏很快—选定以后就没有交换的机会。 —(letsmakeadeal.com) Selvin 在随后寄给 American Statistician 的信件中(1975年8月) 首次使用了“蒙提霍尔问题”这个名称。 一个实质上完全相同的问题于1959年以“三囚犯问题”（three prisoners problem）的形式出现在马丁·加德纳的《数学游戏》专栏中。葛登能版本的选择过程叙述得十分明确，避免了《展示杂志》版本里隐含的前提条件。 这条问题的首次出现，可能是在1889年约瑟夫·贝特朗所著的 Calcul des probabilités 一书中。 在这本书中，这条问题被称为“贝特朗箱子悖论”（Bertrand's Box Paradox）。 Mueser 和 Granberg 透过在主持人的行为身上加上明确的限制条件，提出了对这个问题的一种不含糊的陈述： 参赛者在三扇门中挑选一扇。他并不知道内里有什么。 主持人知道每扇门后面有什么。 主持人必须开启剩下的其中一扇门，并且必须提供换门的机会。 主持人永远都会挑一扇有山羊的门。 如果参赛者挑了一扇有山羊的门，主持人必须挑另一扇有山羊的门。 如果参赛者挑了一扇有汽车的门，主持人随机在另外两扇门中挑一扇有山羊的门。 参赛者会被问是否保持他的原来选择，还是转而选择剩下的那一道门。 解答 转换选择可以增加参赛者的机会吗？ 问题的答案是可以：当参赛者转向另一扇门而不是继续维持原先的选择时，赢得汽车的机会将会加倍。 有三种可能的情况，全部都有相等的可能性(1/3)： 参赛者挑山羊一号，主持人挑山羊二号。转换将赢得汽车。 参赛者挑山羊二号，主持人挑山羊一号。转换将赢得汽车。 参赛者挑汽车，主持人挑两头山羊的任何一头。转换将失败。 在头两种情况，参赛者可以透过转换选择而赢得汽车。第三种情况是唯一一种参赛者透过保持原来选择而赢的情况。因为三种情况中有两种是透过转换选择而赢的，所以透过转换选择而赢的概率是2/3。 如果没有最初选择，或者如果主持人随便打开一扇门，又或者如果主持人只会在参赛者作出某些选择时才会问是否转换选择的话，问题都将会变得不一样。例如，如果主持人先从两只山羊中剔除其中一只，然后才叫参赛者作出选择的话，选中的机会将会是 1/2。不过若主持人不知道哪扇门有羊，在参赛者选择后仍开出羊，此时透过转换选择而赢的概率仍为2/3。 另一种解答是假设你永远都会转换选择，这时赢的唯一可能性就是选一扇没有车的门，因为主持人其后必定会开启另外一扇有山羊的门，消除了转换选择后选到另外一只羊的可能性。因为门的总数是三扇，有山羊的门的总数是两扇，所以转换选择而赢得汽车的概率是2/3，与初次选择时选中有山羊的门的概率一样。 参考资料 1Bapeswara Rao, V. V. and Rao, M. Bhaskara (1992). "A three-door game show and some of its variants". The Mathematical Scientist 17, no. 2, pp. 89–94 2Bohl, Alan H.; Liberatore, Matthew J.; and Nydick, Robert L. (1995). "A Tale of Two Goats ... and a Car, or The importance of Assumptions in Problem Solutions". Journal of Recreational Mathematics 1995, pp. 1–9. 3Gardner, Martin (1959). "Mathematical Games" column, Scientific American, October 1959, pp. 180–182. 4Mueser, Peter R. and Granberg, Donald (1999), "The Monty Hall Dilemma Revisited: Understanding the Interaction of Problem Definition and Decision Making" (University of Missouri Working Paper 99-06). http://econwpa.wustl.edu:80/eps/exp/papers/9906/9906001.html (retrieved July 5, 2005). 5Nahin, Paul J. Duelling idiots and other probability puzzlers. Princeton University Press, Princeton,pp. 192-193. 6Selvin, Steve (1975a). "A problem in probability" (letter to the editor). American Statistician 29(1):67 (February 1975). 7Selvin, Steve (1975b). "On the Monty Hall problem" (letter to the editor). American Statistician 29(3):134 (August 1975). 8Tierney, John (1991). "Behind Monty Hall's Doors: Puzzle, Debate and Answer?", The New York Times July 21, 1991, Sunday, Section 1; Part 1; Page 1; Column 5 9vos Savant, Marilyn (1990). "Ask Marilyn" column, Parade Magazine p. 12 (Feb. 17, 1990). cited in Bohl et al., 1995 10Tijms, Henk (2004), Understanding Probability, Chance Rules in Everyday Life , Cambridge University Press, New York, pp. 213-215.
概述 几个世纪前，罗马教廷出了一本书，书中用当时最流行的数学推论，导出“上帝是万能的”。一位智者针锋相对地问：“上帝能创造出一块他搬不动的石头吗？”如果教廷回答说能的，那上帝不能搬动他创造的那块石头，所以上帝不是万能的。如果教廷回答说不能，那么上帝不能创造出一块他搬不动的石头，所以上帝也不是无所不能的。由此那位智者导出“上帝不是万能的”。 这就是历史上赫赫有名的“上帝悖论”。 详述 文艺复兴时，人文主义者曾说过一句很经典的话，用来攻击天主教。就是；“让上帝造一块自己也搬不动的石头。”这话听初听起来暴牛，恨不能给他鼓掌放花。因为天主教宣称上帝全知全能，所以如果上帝能造出这块石头，则他连块石头都搬不动还称什么全知全能。而如果上帝造不出来这种石头，那他连块石头都造不出来还称什么全知全能。所以上帝必定不是全知全能的。很遗憾我不知道天主教徒是怎么回应的，不然会很有趣 . 实例 香港中文大学哲学系讲师李天命于1987年与加拿大学园传道会巡回演讲员韩那的一次辩论中曾提及此具争议的悖论。他后来在明报月刊撰文解释，此悖论并非空废命题。 李天命举建筑工人作为例子--一个建筑工人可以因为体力缘故，有能力做出自己举不出来的石头。李天命另外提出以甲君做出乙君举不出的石头，然而甲君跟乙君最后被发现是同一人的方法来思考此问题。反方部分的神学家及哲学家认为全能上帝悖论是自相矛盾的空废命题。有人认为造出自己举不起来的石头这要求本身已抵触全能上帝的前提，等同上帝做出装满水的空杯、圆的方形等要求，因而命题可以作废。亦有人认为这命题跟本不自己矛盾--先是上帝做出一块石头，然后自己限制自己的能力使之举不起来,或相反:按定义，上帝创造了一切，所以上帝创造了万有引力。上帝既然能创造万有引力，当然他也能使万有引力消失。所以上帝能够搬动任何石头。 评价 非正非反方全能上帝悖论与理发师悖论，同是罗素悖论（数学版）的形象故事版。但这个故事版很糟糕，因为它用科学领域的逻辑去检验或嘲讽宗教领域的理念。在罗素悖论提出后，科学家们临时约定在科学领域不使用万有集合或自包含集合，这样，万能的上帝是不能出现在二维逻辑推理中的，亦即所有概念都必须是相对的而不能是绝对的，即仅有特定时空条件下的相对正确。而宗教依然维持其原有的逻辑方式来表述人生或宇宙的终极（绝对）真理。如此，就目前而言，它们是相安无事的：一个研究相对的概念的关系，一个研究绝对的概念的关系。因此，上帝悖论仅是过去的一个嘲讽，而不是当前的一个事实。 这个问题已有八百多年的历史了。在提出这个问题的时候，提问者已经假定了万有引力的存在，因为在这个问题里有一个“搬”字。什么是“搬”？我给“搬”的定义是：在逆着万有引力的方向上移动一个物体。按定义，上帝创造了一切，所以上帝创造了万有引力。上帝既然能创造万有引力，当然他也能使万有引力消失。所以上帝能够“搬动”任何石头。这个问题可以转换为：如果上帝用左手（万有引力）和右手（搬石头那只手）掰手腕，哪只手会赢？两只手都属于上帝，这不是一场竞争，没有输赢之说。所以这个问题是个愚蠢的问题。 如果上帝是全能的，那上帝就是一切，一切都是上帝。上帝之外没有任何东西，连空间都没有，因为上帝创造了时间和空间。其实，“上帝之外”是一个自相矛盾的概念。有上帝，就没有“之外”；有“之外”，就没有上帝。“上帝之外”没有万有引力，上帝不生活在引力场中。对于全能的上帝来说，不存在“搬”这个概念。万有引力存在于上帝之内。对于全能的上帝来说，也不存在“站”这个概念，因为“上帝之外”没有立足之地。依此类推，对于全能的上帝来说，不存在“呼吸”、“吃喝”、“排泄”、“穿衣”、“走路”、“坐”、“躺”这些概念。上帝没有身体。因为有身体就有身体之外的空间，有身体就有皮肤。皮肤是身体的边界。上帝是没有边界的。上帝没有五官，没有脸，没有形状。一个蚂蚁看见你在说话，你的嘴唇和舌头在动。它问你：“你是如何搬动你的嘴唇和舌头的?”你回答：“这是个愚蠢的问题。”一个人看见月亮在动，他问上帝：“你是如何搬动月亮的？”上帝说：“这是个愚蠢的问题。” [1]
目录 1定义 2生日攻击的方法解释 3相关条目 定义 生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。这种攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够长。生日攻击这个术语来自于所谓的生日问题，在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于1/2？这个问题的答案为23。 概述 数学上，如果一些函数，当提供一个任意的输入时，返回k类似相等的值中的一个，然后通过重复地计算不同输入的行为，我们期望获得相同的输出大概1.2sqrt(k)。对上述的生日悖论，用365替代了k。生日攻击通常用于寻找哈希函数的冲突。为了防止这种攻击，针对一个签名方案的哈希函数的输出的长度能够被广泛选择因此生日攻击变得计算上不可行的。 [1] 生日攻击的方法解释 生日攻击 下面详细描述生日攻击的方法。 设h：X->Y是一个Hash函数，X和Y都是有限的，并且|X|>=2|Y|，记|X|=m，|Y|=n。显然至少有n个碰撞，问题是如何去找到这些碰撞。一个很自然的方法是随机选择k个不同的元素x1,x2,x3,.....,xk ∈X,计算yI=h(xi)，1<=i<=k，然后确定是否有一个碰撞发生。这个过程类似于把k个球随机地扔到n个箱子里边，然后检查看是否某一箱子里边至少有两个球。k个球对应于k个随机数x1,x2,x3,.....,xk，n个箱子对应于Y中的n个可能的元素。我们将计算用这种方法找到一个碰撞的概率的下界，该下界只依赖于k和n，而不依赖于m。 因为我们关心的是碰撞概率的下界，所以可以假定对所有y∈Y，有|h-1(y)|≈m/n。这个假定是合理的，这是因为如果原像集h-1(y)( y∈Y)不是近似相等的，那么找到一个碰撞的概率将增大。 因为原像集h-1(y)( y∈Y)的个数都近似相等，并且xI(1<=i<=k)是随机选择的，所以可将yI=h(xi)，1<=i<=k视作Y中的随机元素（yi(1<=i<=k)未必不同）。但计算k个随机元素y1,y2, .....yk∈Y是不同的概率是一件容易的事情。依次考虑y1,y2, .....yk。y1可任意地选择；y2 ≠y1的概率为1-1/n；y3 ≠y1 ,y2的概率为1-2/n；.....；yk ≠y1,y2, .....,yk-1的概率为1-(k-1)/n。 因此，没有碰撞的概率是（1-1/n）(1-2/n）.....(1-(k-1)/n）。如果x是一个比较小的实数，那么1-x≈e-x，这个估计可由下式推出：e-x=1-x+x2/2!-x3/3!+ .....。现在估计没有碰撞的概率（1-1/n）(1-2/n）.....(1-(k-1)/n）约为1-e-k(k-1)/2n。我们设ε是至少有一个碰撞的概率，则ε≈1-e-k(k-1)/2n，从而有k2-k≈nln(1/(1-ε)2)。去掉-k这一项，我们有k2≈nln(1/(1-ε)2)，即k≈sqrt(2nln(1/(1-ε)2))。 如果我们取ε=0.5，那么k≈1.17 sqrt(n)。这表明，仅sqrt(n)个X的随机的元素就能以50%的概率产生一个碰撞。注意ε的不同选择将导致一个不同的常数因子，但k与sqrt(n)仍成正比例。 如果X是一个教室中的所有学生的集合，Y是一个非闰年的365天的集合，h(x)表示学生x的生日，这时n=365，ε=0.5，由k≈1.17 sqrt(n)可知，k≈22.3。因此，此生日问题的答案为23。 生日攻击隐含着消息摘要的长度的一个下界。一个40比特长的消息摘要是很不安全的，因为仅仅用220（大约一百万）次随机Hash可至少以1/2的概率找到一个碰撞。为了抵抗生日攻击，通常建议消息摘要的长度至少应取为128比特，此时生日攻击需要约264次Hash。安全的Hash标准的输出长度选为160比特是出于这种考虑。 中间相遇攻击是生日攻击的一种变形，它不比较Hash值，而是比较链中的中间变量。这种攻击主要适用于攻击具有分组链结构的Hash方案。中间相遇攻击的基本原理为：将消息分成两部分，对伪造消息的第一部分从初试值开始逐步向中间阶段产生r1个变量；对伪造消息的第二部分从Hash结果开始逐步退回中间阶段产生r2个变量。在中间阶段有一个匹配的概率与生日攻击成功的概率一样。 在修正分组攻击中，为了修正Hash结果并获得期望的值，伪造消息和一个分组级联。这种攻击通常应用于最后一个组，因此也称为修正最后分组攻击。差分分析是攻击分组密码的一种方法。这种攻击也可用来攻击某些Hash算法。 针对Hash算法的一些弱点可对Hash算法进行攻击，可利用Hash算法的代数结构及其所使用的分组密码的弱点来攻击一些Hash方案。例如针对DES的一些弱点（即互补性、弱密钥、密钥碰撞等）来攻击基于DES的Hash方案。 生日悖论 使k个人中至少有两个人生日相同的概率大于0.5的最小k值是多少?不考虑2月29号假定每个生日出现的概率一样 则定义:P(n,k)=Pr[k个元素中至少有一个元素重复出现，其中每个元素出现的概率均为1/n] 所以，只是找出使得P(365,k)>=0.5的最小的k，用Q（365，k）表示没有出现的概率，若k>365,则所有值都不等是不可能的。所以假定k<=365。设k个元素均不重复的数为N，那么，第一个元素有365种取值，第二种元素有364种取值，等等，因此，不同的方式数为：N=365*364*--（365-k+1）=365！/（365-k）！ 如果允许重复那么每一个元素有365种取法，共365^k种取法，所以不重复的概率为无重复数除以总数：Q（365，k）=365！/（365-k）！365^k则P(365,k)=1-365！/（365-k）！ 对于那些没考虑过该问题的人来说，该概率大的出奇。许多人以为要使至少有一个重复的概率大于0.5，那么大约应有100人，事实上，因为P(365,23)=0.5037,所以人数为23，k=100时至少有一个重复的概率为0.9999997，结果显得出乎意料的原因也许如下：如果你考虑某个组里有其他人和这个人有相同生日的概率很小 但是这里我们考虑的是任意两个人生日相同的概率在23个人中有23*(23-1)/2=253种不同的双人组合，因此生日的概率比较大。 相关条目 生日悖论
登录
工商服务
危机公关
金融律师
app开发
财税服务
金融牌照
网站建设
知识产权
企业征信
审计评估