《应用随机过程》PPT课件.ppt

应用随机过程 主讲教师段禅伦2011年秋季学期 计算机学院研究生专业基础课程 应用数学基础 AppliedStochasticprocesses 第2章关于条件概率与条件期望 有关概率模型 ProbabilityModels 的练习 引言条件概率与条件期望是概率论最有用的概念 因为 在实践中 我们常常对于计算在部分信息已知时的概率和期望感兴趣 而这样的概率和期望就是条件概率和条件期望 其次 在计算需要的概率和期望时 在某些随机变量上取条件是极其有用的方法 离散情形我们知道 对于任意两个事件E和F 当P F 0且给定F时 E的条件概率被定义为P E F P EF P F 因此 如果X和Y都是离散随机变量 那么对于所有使P Y y 0的y值 在Y y给定的条件下 X的条件概率分布列函数定义为pX Y x y P X x Y y 而对于所有使P Y y 0的y值 在Y y给定的条件下 X的条件概率分布函数定义为FX Y x y P X x Y y pX Y a y 在Y y给定的条件下 X的条件期望定义为E X Y y xP X x Y y xpX Y x y 若X与Y独立 那么条件概率分布列函数 条件概率分布函数和条件期望都与无条件时一样 因为 当X与Y独立时 pX Y x y P X x Y y P X x 例1假设X和Y的联合概率分布列函数p x y 给定为p 1 1 0 5 p 1 2 0 1 p 2 1 0 1 p 2 2 0 3 计算在Y 1给定条件下X的条件概率分布列函数 解 由pY 1 p x 1 p 1 1 p 2 1 0 6 及pX Y 1 1 P X 1 Y 1 类似地pX Y 2 1 例2假定X1和X2分别是具有参数 n1 p 与 n2 p 的独立的二项随机变量 计算在X1 X2 m给定的条件下X1的条件概 率分布列函数 解 记q 1 p 由条件概率定义与独立性 有P X1 k X1 X2 m 其中 运用了X1 X2 m是具有参数 n1 n2 p 的二项随机变量 例2 53 的已有结果 进而知 在给定的X1 X2 m的条件下 X1的条件概率分布列函数是 P X1 k X1 X2 m 此式描述的分布 称超几何分布 首见于例2 34 其模型可解释为 从装有n1只蓝色球和n2只红色球的袋中 随机选取m只球 求蓝色球个数的分布 例3假定X和Y分别是具有参数 1与 2的独立泊松随机变量 计算在给定X Y n的条件下X的条件期望 解 我们计算在X Y n给定的条件下X的条件概率分布列函数时 注意到例2 36的结果和X与Y的独立性 有 P X k X Y n 上式说明 在给定两个独立的泊松随机变量X与Y的和X Y n的条件下 X的条件分布是参数为n和 1 1 2 的二项分布 由例2 53知 X Y n的条件下X的条件期望为E X X Y n n 注 条件期望具有普通期望的一切性质 例如E Xi Y y E Xi Y y 例4一个试验 出现三个结果之一 结果i出现的概率为pi i 1 2 3 p1 p2 p3 1 假设独立地重复此试验n次 并以Xi i 1 2 3 记其中结果i出现的次数 求在给定X2 m时X1的条件期望 解 对于k n m P X1 k X2 m 显然 若X1 k且X2 m 则X3 n k m 且P X1 k X2 m X3 n k m 它是结果1有k次 结果2有m次 结果3有n k m次的n次试验的所有这种序列事件发生的概率 于是P X1 k X2 m 式中运用了X2是具有参数n和p2的二项分布的事实 进而 有P X1 k X2 m 记p3 1 p1 p2 则上式可等价地写为P X1 k X2 m 即在给定X2 m时X1的条件分布是参数为n m和p1 1 p2 的二项分布 因而还有E X1 X2 m n m 为了易于理解 对例4中所求的条件概率 我们也可以运 用下述方式计算 考虑不出现结果2的n m次试验 在每个这样的试验中 结果1出现的概率是P 结果1 非结果2 P 非结果2 由此就可得到在给定X2 m时 结果1出现的次数是以参数n m和二项地分布的 例5有n个部件 对于i 1 2 n 部件i在雨天运转的概率为pi 在非雨天运转的概率为qi 明天将下雨的概 P 结果1 非结果2 率为 计算给定明天下雨时 运转的部件数的条件期望 解 令Xi 若明天下雨 定义Y为1 而在相反的情形 定义Y为0 则所求的条件期望为E Xi Y 1 E Xi Y 1 pi 连续情形如果X和Y有联合概率密度函数f x y 那么对于所有fY y 0的y值 给定Y y时X的条件概率密度函数定义为fX Y x y 1 部件i明天运转 0 其他情形 X的条件概率密度函数如此定义的理由 对定义式左边乘以dx 右边乘以 dxdy dy 看出fX Y x y dx P x X x dx y Y y dy 换句话说 对于小的值dx和dy fX Y x y dx近似地为给定Y在y和y dy之间时 X在x和x dx之间的条件概率 我们知道 对于所有fY y 0的y值 给定Y y时X的条件期望定义是E X Y y xfX Y x y dx 例6 习题6 假定X和Y有联合概率密度函数6xy 2 x y 0 x 1 0 y 1 0 其它 对于0 y 1 计算给定Y y时X的条件期望 解 我们首先计算条件密度fX Y x y 0 x 1 因此 有 f x y E X Y y 例7假定X和Y的联合密度为4y x y e x y 0 x 0 y x 0 其它 计算给定Y y的E X Y y 解 给定Y y时X的条件密度为fX Y x y x y x y w x y f x y x y e x y 最后的等号 运用了均值为1的指数随机变量的期望值也为1的事实 而且 对均值为1的指数随机变量W 我们有E X Y y x x y e x y dx w y we wdw E W2 yE W 2 y 1 例8设X和Y的联合密度为ye xy 0 x 0 y 2 0 其它 求E ex 2 Y 1 的值 f x y 解 给定Y 1时X的条件密度为fX Y x 1 e x 由命题2 2的 2 随机变量函数的数学期望 有E eX 2 Y 1 ex 2fX Y x 1 dx ex 2e xdx 2 通过取条件计算期望让我们以E X Y 记随机变量Y的这样的函数 它在Y y处取得值是E X Y y 注意 E X Y 本身是一个随机变量 我们已经讨论了条件期望的一个极为重要的性质 对于所有的随机变量X和Y E X E E X Y 如果Y是离散随机变量 那么上述重要性质可写为E X E X Y y P Y y 如果Y是密度为fY y 的连续随机变量 那么上述重要性质可写为E X E X Y y fY y dy 下面是对X和Y都是离散随机变量的情形 关于条件期望重要性质的证明 E X Y y P Y y xP X x Y y P Y y xP Y y xP X x Y y P X x Y y P X x E X 对条件期望重要性质的解释 条件期望重要性质说明 对于计算E X 我们可以取Y y给定时X的条件期望的加权平均 每一项E X Y y 用取条件的那个事件的概率加权 以下的例子显示其用途 例9小李准备读一章概率书或一章高数书 如果在他读的一章概率书中的印刷错误数是均值为2的泊松分布 而在他读的一章高数书中的印刷错误数是均值为5的泊松分布 那么在假定小李选取哪一本数是等可能的时 小 李读到的印刷错误数的期望是多少 解 以X记印刷错误数 令1 如果小李选取高数书 2 如果小李选取概率书 则E X E X Y 1 P Y 1 E X Y 2 P Y 2 例10 随机变量的随机数量和的期望 假定工厂设备每周出现事故次数的期望为4 又在每次事故中受伤工人数是具有相同均值2的独立随机变量 再假定在每次事故中受伤工人数与每周发生的事故数目相互独立 求每周受伤人数的期望 解 以N记事故次数 以Xi记在第i次事故中的受伤人数 i Y 1 2 那么伤者总数可以表示为X 现在E E E N 但是E N n E N n E nE X 由此 导出E N NE X 因此E E NE X E N E X 所以 一周中受伤人数的期望为E N E X 4 2 8 随机变量等于N个独立同分布的随机变量的和 称之为复合随机变量 其期望值是 E E N E X 例11 几何分布的均值 连续抛掷一枚出现正面的概率为p的硬币 直至出现正面为止 求需要抛掷次数的期望 解 以N记需要抛掷的次数 令1 如果第一次抛掷的结果是正面 0 如果第一次抛掷的结果是反面 按照离散随机变量期望重要性质 有E N E N Y 1 P Y 1 E N Y 0 P Y 0 pE N Y 1 1 p E N Y 0 Y 由于Y 1的定义是第一次抛掷结果是正面 故需要抛掷的次数的期望是1 因而E N Y 1 1 Y 0 第一次抛掷结果是反面 但是假定相继的抛掷是独立的 可见在第一次出现反面后直到正面首次出现时的附加抛掷次数的期望是E N 因而E N Y 0 1 E N 于是 有E N p 1 1 p 1 E N 解之得E N 1 p 其实 N是有概率分布列函数p n p 1 p n 1的几何随机变量 它的期望正如例2 22 通过E N np n 很容易算得 而无须求助于条件期望 不过 通过下一个例子 就会看出 取条件 求期望是一个多么有用的技巧 例12某矿工身陷在有三个出口的矿井之中 经第一个出口的通道行进2小时后 他将到达安全地带 经第二个出口的通道行进3小时后 他将回到矿井原地 经第三个出口的通道行进5小时后 他又将回到矿井原地 假定这位矿工每次都等可能地选择任意一个出口 求他直到到达安全地带所需时间的期望值 解 以X记矿工到达安全地带所需的时间 以Y记他最初选取的出口 则E X E X Y 1 P Y 1 E X Y 2 P Y 2 E X Y 3 P Y 3 E X Y 1 E X Y 2 E X Y 3 但E X Y 1 2 E X Y 2 3 E X E X Y 3 5 E X 所以E X 2 3 E X 5 E X 解之得E X 10 例13 匹配轮数问题 假设在例2 17中 取到自己帽子的人离开 而其余的人 没有匹配到的那些人 将他们取到的帽子放回房间中央 混杂后重新取 假定这个过程连续进行到每个人都取到了自己的帽子为止 a 假定Rn是开始时有n个人出席的轮数 求E Rn b 设Sn是开始时n n 2 个人参选的总次数 求E Sn c 求这n n 2 个人误取的期望数 解 a 由例2 17知 不论留在那里的人有多少 平均每轮有一次匹配 这就使人想到E Rn n这个结果是正确的 下面给出一个归纳性的证明 显然 E R1 1 假定对k 1 2 n 1 有E Rk k 为了计算E Rn 我们先对第一轮中的匹配数Xn取条件 它给出E Rn E Rn Xn i P Xn i 现在 给定了最初一轮的全部匹配数i 需要的轮数将等于1加上余下的n i个人匹配他们的帽子需要的匹配轮数 所以E Rn 1 E Rn i P Xn i 1 E Rn P Xn 0 E Rn i P Xn i 1 E Rn P Xn 0 n i P Xn i 1 E Rn P Xn 0 n 1 P Xn 0 E Xn E Rn P Xn 0 n 1 P Xn 0 其中 最后一个式子使用了例2 17建立的结果 E Xn 1 对以上等式 就E Rn 解方程 便得E Rn n b 对于n 2 取条件于第一轮中的匹配数Xn 有E Sn E Sn Xn i P Xn i n E Sn i P Xn i n E Sn i P Xn i 式中 E S0 0 为了求解以上关于E Sn 的方程 将其改写为E Sn n E 我们想 如果在每轮中恰有一次匹配 那么共有n 2 1 n n 1 2次选取 现在我们在 中来试探形式为E Sn an bn2的解 为了该解在n 2时满足 需要an bn2 n E a n Xn b n Xn 2 或者 等价地an bn2 n a n E Xn b n2 2nE Xn E 利用例2 17和第2章的习题4 所得到的E Xn 1 Var Xn 1的结果及E Var Xn E2 Xn 知 只要有an bn2 n an a bn2 2nb 2b即可 经试解知 此式当a 1 b 1 2时成立 也就是E Sn n n2 2满足E Sn 的递推方程 这个结论对不对呢 下面 我们通过对n 2 做归纳完成E Sn n n2 2的形式证明 n 2 此时 必须是第一轮没有人取到自己的帽子 n 2时 若第一轮有一人取到了帽子 就都取到了帽子 因而不会有第二轮的选取了 选取数为2 第二轮结束选取 选取数也是2 满足E S2 2 22 2 现在将递推关系写成E Sn n E Sn P Xn 0 E Sn i P Xn i 由于n 2 所以应取E S1 E S0 0 而归纳假设E Sk k k2 2 k 2 3 n 1 其实 还有P Xn n 1 0 故 E Sn n E Sn P Xn 0 n i n i 2 2 P Xn i n E Sn P Xn 0 n n2 2 1 P Xn 0 n 1 E Xn E 2将E Xn 1 E 2代入 便得E Sn n n2 2 c 记第j个人取帽子的次数为Cj j 1 2 n 则Cj Sn 取期望 并用每个Cj具有同样的均值的事实 进而有结果E Cj E Sn n 1 n 2 因此 第j个人取错帽子的期望为E Cj 1 n 2 例14如果连续地做每次成功的概率为p的独立试验直至有k次相继成功 那么所需试验的次数的均值是多少 解 以Nk记为了得到k次相继的成功必须试验的次数 并以Mk记它的均值 通过对k 1次相继成功所必须试验的次数Nk 1取条件 我们就得到Mk的一个递推方程 即Mk E Nk E E Nk Nk 1 而E Nk Nk 1 Nk 1 1 p 1 p 1 E Nk 所以E Nk Nk 1 Nk 1 1 1 p E Nk 这是因为若取Nk 1次试验得到k 1次相继的成功 则下一次或者是成功 我们就接着得到k次成功 或者是失败 我们就必须重新开始 对此式两边取期望 得 Mk Mk 1 1 1 p Mk 或者Mk 由于首次成功的次数N1是参数为p的几何随机变量 所以M1 1 p并且 做递推 则有M2 M3 进而 更一般地 有Mk 例15 快速排序算法 假设有n个不同的值x1 x2 xn的一个集合 我们要将它们排列为增加的次序 即将它们排序 sort 我们知道 完成递增排序的一个有效算法是快速排序算法 这是一个递推的方法 当n 2时 该算法比较两个值 将它们置于合适的次序 当n 2时 它开始在n个值中随机地选取一个譬如xi 然后将其它的n 1个值与xi比较 注意哪些小于xi 哪些大于xi 以Si记小于xi的元素的集合 记大于xi的元素的集合 然后对集合Si和分别排序 最后的次序由集合Si的元素的次序 xi和集合的元素的次序排序组成 例如 假定元素集合是 10 5 8 2 1 4 7 我们以1 7 的概率先选取其中一个 设为4 然后将其它6个值的每一个与4作比较 得到 2 1 4 10 5 8 7 将集合 2 1 排序得1 2 4 10 5 8 7 在 10 5 8 7 中随机选取一个 譬如是7 将其它三个值与7作比较 得1 2 4 5 7 10 8 最后 将 10 8 排序并结束 得1 2 4 5 7 8 10 对该算法有效性的一个量度是做比较的次数的期望 现以Mn记n个不同值的一个集合的快速排序算法的比较 次数的期望 为了得到Mn的一个递推式 我们取条件于初始的取值 有Mn E 比较数 取到的是第j小的值 若初始的取值是第j小的值 则值比j小的集合的容量是j 1 值比j大的集合的容量是n j 由于对于选定初始取值后算法接着要作n 1次比较 因此Mn n 1 Mj 1 Mn j n 1 Mk M0 0 即nMn n n 1 2Mk 此式对n 1个不同值的集合一样成立 所以也有 n 1 Mn 1 n 1 n 2Mk 后式减前式 得 n 1 Mn 1 nMn 2n 2Mn亦即 n 1 Mn 1 n 2 Mn 2n从而 得对该式进行迭代 有 2 递推项M1 0 所以Mn 1 2 n 2 2 n 2 n 1 利用恒等式对较大的n 得近似式Mn 1 2 n 2 2 n 2 dx dx 2 n 2 2ln n 2 ln n 1 ln2 2ln3 2 n 2 ln n 2 ln ln2 2ln3 2 n 2 ln n 2 下面介绍一个运用条件期望恒等式 重要性质 计算条件期望的例子 例16在例2 17的有n n 1 个人的匹配问题中 求给定第一个人没有匹配时的匹配数的条件期望 解 以X记匹配数 如果第一个人有一个匹配 令X1等于1 否则令X1等于0 E X E X X1 0 P X1 0 E X X1 1 P X1 1 E X X1 0 E X X1 1 但是 由例2 17知 E X 1 此外 给定第一个人有一个匹配时 匹配数的期望等于1加上当n 1个人在他们自己 的n 1个帽子中选取的匹配数的期望 也就是说E X X1 1 2所以 有E X X1 0 通过取条件计算方差条件方差也可以用来计算随机变量的方差 特别地 当我们运用Var X E X2 E X 2计算方差时 可以通过取条件得到E X 和E X2 例17 几何随机变量的方差 连续地做每次成功的概率为p的独立试验 N是首次成功时的试验次数 求Var N 解 如果首次试验成功则记Y 1 否则记Y 0 方差计算公式Var N E N2 E N 2 为计算E N2 对Y取条件并有E N2 E E N2 Y 而E N2 Y 1 1 E N2 Y 0 E 1 N 2 因为 如果首次试验的结果是成功 那么显然N 1 从而N2 1 如果首次试验的结果是失败 那么得到第一次成功所需的试验总次数等于1 首次试验是失败 加上进行额外试验所需的试验次数 由于此量与N同分布 故有上面第二式 因此 我们有 E N2 E N2 Y 1 P Y 1 E N2 Y 0 P Y 0 p E 1 N 2 1 p 1 1 p E 2N N2 由于 见例11 E N 1 p 所以E N2 1 1 p E N2 即E N2 是此 故有Var N E N2 E N 2 另一个用取条件得到随机变量的方差的途径是运用条件方差公式 在给定Y y时X的条件方差定义为Var X Y y E X E X Y y 2 Y y 也就是 条件方差正好与通常的方差由相同的方式定义 不同之处是所有的概率都是在条件Y y下确定的 将条件方差定义式展开 且逐项地取期望 可推得Var X Y y E X2 Y y E X Y y 2以Var X Y 记Y如此的函数 它在Y y的值是Var X Y y 我们有如下结果 命题1 条件方差公式 Var X E Var X Y Var E X Y 证明 E Var X Y E E X2 Y E X Y 2 E E X2 Y E E X Y 2 E X2 E E X Y 2 而Var E X Y E E X Y 2 E E X Y 2 E E X Y 2 E X 2所以E Var X Y Var E X Y E X2 E X 2 例18 复合随机变量的方差 设X1 X2 Xn是独立同分布于X的随机变量 其分布函数为F 具有均值 和方差 2 且假设它们与取非负整数值的随机变量N独立 在例10中 计算了S 的期望值 有E S E N E X 并称随机变量为复合随机变量 本例是求S的方差 解 之前 通过对N取条件计算了E S2 这里代之以的是 利用条件方差公式 Var S N n Var Xi N n Var Xi N n Var Xi n 2 以同样的推理 得E S N n n 所以Var S N N 2 E S N N 由条件方差公式 便有Var S E N 2 Var N 2E N 2Var N 若N是泊松随机变量 则S 称为复合泊松随机变量 因为泊松随机变量的方差等于它的期望 所以对于一个E N 的复合随机变量 我们有Var S 2 2 E X2 式中 X具有分布函数F 通过取条件计算概率我们不仅可以通过对合适的随机变量取条件得到期望 而且也可以用此方法计算概率 以E记一个任意事件 定义示性随机变量X为1 若E发生 0 若E不发生 X 由X的定义可推得E X P E E X Y y P E Y y 再由通过取条件计算期望的关于离散与连续随机变量的两个公式 得P E Y y P Y y 若Y离散 P E Y y fY y dy 若Y连续 例19假定X和Y是独立的随机变量 分别具有概率密度函数fX和fY 计算P X Y 解 对Y取条件 得P X Y P X Y Y y fY y dy P E 对任意随机变量Y P X y fY y dy FX y fY y dy式中FX y fX x dx 例20保险公司假定参保人每年发生的事故数是均值依赖于参保人的泊松随机变量 且设一个随机选取的参保人的泊松均值具有密度函数g e 0的伽玛分布 问一个随机选取的参保人明年恰有n次事故的概率是多少 解 以X记一个随机选取的参保人明年发生的事故数 以Y 记该参保人发生事故数的泊松均值 那么对Y取条件 得P X n P X n Y g d e e d n 1e 2 d 注意到h 0是伽玛 n 2 n 随机变量的密度函数 它的积分为1 所以1 d n 1e 2 d 于是知P X n n 1 2n 2 例21假定每天参加瑜珈训练的人是均值为 的泊松随机变量 且参加的人是相互独立的 其中是女性的概率为p 是男性的概率为1 p 求在今天恰有n个女性 m个男性参加瑜珈训练的联合概率 解 将今天参加的女性人数记为N1 男性人数记为N2 以N N1 N2记参加的总人数 对N取条件 有P N1 n N2 m P N1 n N2 m N n m e 注意到n m个人中的每一个独立地以概率p为女性 我们推知 在给定n m人参加时 其中女性n个 男性m个 的条件概率 正是在n m次试验中恰有n次成功的二项概率 所以P N1 n N2 m pn 1 p me pn 1 p me pe 1 p e pe 1 p 因为以上联合概率分布列函数可以分解为两项的乘积 第一项只依赖于n 第二项只依赖于m 可见N1与N2是独立的 此外 由于P N1 n P N1 n N2 m e pe 1 p e p类似地 自然还有P N2 m e 1 p 这就是说 N1与N2是均值分别为 p和 1 p 的独立泊松随机变量 从该例 我们建立了一个重要的结论 当每一个泊松随机事件独立地以概率p被分入第一类 或者以概率1 p被分入第二类时 第一类与第二类中的事件数是独立的泊松随机变量 例22令X1 X2 Xn为独立的伯努里随机变量 Xi具有参数pi i 1 2 n 即P Xi 1 pi P Xi 0 qi 1 pi 现在要计算它们的和X1 X2 Xk的概率分布列函数 为此 我们以递推的方式来求X1 X2 Xk的概率分布列函数 首先取k 1 然后k 2 继续工作 直到k n 现在记 Pk j P X1 X2 Xk j 并且注意到Pk k pi Pk 0 qi 就0 j k 对Xk取条件得到递归式Pk j P X1 X2 Xk j Xk 1 pk P X1 X2 Xk j Xk 0 qk P X1 X2 Xk 1 j 1 pk P X1 X2 Xk 1 j qk pkPk 1 j 1 qkPk 1 j 从P1 1 p1 P1 0 q1开始 利用此式 就可递推地解出P2 j P3 j 直到Pn j 例23 最佳奖问题 假设可以从一系列先后宣布的n个不同的奖项中选取一个 在一个奖项宣布后我们必须是立刻决定是接受 还是拒绝转而考虑随后的奖项 我们只能根据该奖项与前面已经宣布的奖项的比较决定是否接受它 例如 当第五个奖项宣布时 我们知道它与前面已经宣布的四个奖是如何比较的 假设拒绝了一个奖就失去了这次机会 我们的目标是使得到最佳奖的概率达到极大 假定奖项的所有n 个次序都是等可能的 我们该怎样做 解 让我们吃惊的是 这可以做得很好 为了明白此理 选 定一个k 0 k n 同时考虑前k个都拒绝并接受此后第一个的奖比前面k个更好的策略 将使用此策略选到最佳奖的概率记为Pk 最佳 为了计算该概率 对最佳奖项的位置X取条件 有Pk 最佳 Pk 最佳 X i P X i Pk 最佳 X i 如果最佳奖在前k个奖项之中 那么用所考虑的策略就选不到最佳奖 另一方面 如果最奖在位置i i k 那么当前k个的最佳奖也是前i 1个的最佳奖时 我们就可以选到最佳奖 因为在位置k 1 k 2 i 1中的奖项都没有被选取 于是 有 若i k Pk 最佳 X i 0 若i k Pk 最佳 X i P 前i 1个中的最佳在前k个之中 k i 1 从此式 得Pk 最佳 dx ln ln 考虑函数g x ln 有g x ln 而且 由g x 0ln 1x 因为Pk 最佳 g k 由于所考虑的策略中的最佳策略 就是放弃前面的n e个奖项 然后接受第一个比这些都好的一个奖 另外 鉴于g n e 1 e 所以这一策略选取到的最佳奖的概率近似地为1 e 0 36788 例24n个人在聚会上摘下他们的帽子 帽子混合在一起后 每人随机地取一个 如果一个人选取到他自己的帽子 就说发生了一次匹配 那么 没有匹配的概率是多少 恰巧有k个人匹配的概率是多少 解 令E为无匹配的事件 为了表达清楚对n的依赖性 记Pn P E 我们先对第一个人是否取到自己的帽子取条件 记相应的事件为M和MC 于是Pn P E P E M P M P E MC P MC 显然 P E M 0 进而有Pn P E MC P E MC 是n 1个人从不含他们自己的帽子的n 1个帽子的集合中各取一个时无匹配的概率 这有互不相容的两种情况 第一种情况是无匹配 但是被第一个人取走帽子的那个人并没有取到第一个人的帽子 第二种情况是无匹配 但是被第一个人取走帽子的那个人 取到了第一个人的帽子 这有1 n 1 的可能 当将第一个人的帽子就看成是这个人的帽子时 第一种情况的事件 其概率为Pn 1 第二种情况的事件 其概 率为Pn 2 n 1 也就是P E MC Pn 1 Pn 2 n 1 从而 有Pn Pn 1 Pn 2 亦即Pn Pn 1 Pn 1 Pn 2 因为Pn是n个人在他们自己的帽子中选取时无匹配的概率 故有P1 0 P2 1 2所以P3 P2 P2 P1 3 1 3 或P3 1 2 1 3 P4 P3 P3 P2 4 1 4 或P4 1 2 1 3 1 4 一般地 有Pn 为了得到恰有k个匹配的概率 我们考察任意固定的k个人 只有他们取到自己的帽子的概率是Pn k Pn k 式中的Pn k是其余的n k个人 在他们自己的帽子中选取时无匹配的条件概率 因为k个人的集合有种取法 所以所求的恰有k个匹配的概率是Pn k 对于大的n 它近似地等于e 1 k 例25 再论选票问题 我们知道原问题是这样的 在一次选举中 候选人A得到了n张选票 候选人B得到了m张选票 其中n m 假设所有不同的次序都是等可能的 证明在计算选票时A总是领先的概率为 n m n m 原证是 以Pn m记所求的概率 取条件于得到最后一张选票的人 有Pn m P A总领先 A得到最后一张选票 P A总领先 B得到最后一张选票 鉴于在给定A得到最后一张选票的条件下 A总领先的概率与A得到了n 1张选票 B得到了m张选票的情形一样 而且 在给定B得到最后一张选票的条件下 A总领先的概率与B得到了m 1张选票 A得到了n张选票的情形一样 故有Pn m Pn 1 m Pn m 1 进而 我们对n m运用归纳法证明了 Pn m n m n m 证明是这样的 当n m 1时 P1 0 1 上述递推式是正确的 设n m k时 递推式成立 则在n m k 1时 归纳直接对n进行 有Pn m 于是就完成了对结论的证明 选票问题有一些有趣的应用 现在给出其中的一例 考虑连续地抛掷一枚出现正面的概率总是p的硬币 让我们确定在抛掷开始后 首次出现正面总数与反面总数相等时抛掷次数的概率分布 首次在第2n次抛掷发生这个事件的概率 可以由先对前2n次试验中正面出现的总数取条件得到 即P 首次出现相等时的次数 2n P 首次出现相等时的次数 2n 在前2n次中有n次是正面 pn 1 p n 给定前2n次抛掷中有n次是正面时 由于出现n次是正面和n次是反面的所有不同次序都是等可能的 因而上面的条件概率 等价于在一次选举中每个候选人得到n张选票 在计数到最后一张选票 这约束了他们 时 其中一个候选人总是领先的概率 但是对无论是谁得到最后一张选票取条件 这正是选票问题中m n 1时的概率 所以P 首次出现相等时的次数 2n Pn n 1pn 1 p n pn 1 p n 假定现在要确定在2n i次抛掷后 首次出现正面总数比反面总数多i次的概率 为此 以下的两个事件必须发生 a 前2n i次抛掷的结果是n i次正面 n次反面 b n i次正面与n次反面的出现次序 是使直到最后的 抛掷为止 正面的次数绝不比反面次数多i次的情形 事件b 发生 当且仅当n i次正面与n次反面的出现次序是从最后一次抛掷出发反向观测时 正面总是领先的情形 例如 如果有4个正面 2个反面 n 2 i 2 那么结果 TH并不满足 因为这会在第6次抛掷前正面比反面多2次 因为前4次的结果是正面比反面多2次 在a 中指定的事件的概率正是抛掷2n i次硬币得到n i次正面和n次反面的二项概率 下面来确定在给定抛掷2n i次硬币 得到n i次正面和n次反面时b 中指定的事件的条件概率 由于在给定抛掷2n i次硬币 得到总数为n i次正面与n 次反面时 抛掷的所有可能的次序都是等可能的 所以在给定a 时 b 的条件概率正是n i次正面与n次反面的一个随机排序中 当从相反的次序计数时 正面总比反面多的概率 考虑到所有相反的排序都是等可能的 这就由选票问题推出此条件概率是i 2n i 这样 我们证明了P a pn i 1 p n P b a 于是P 在抛掷2n i次时 正面首次领先i次 pn i 1 p n 例26设U1 U2 是独立的 0 1 均匀随机变量 令N min n 2 Un Un 1 M min n 1 U1 U2 Un 1 就是说 N是第一个大于前一个的均匀随机变量的指标 而M是其和超过1的均匀随机变量的最少个数 令人惊奇的是 N与M有相同的概率分布 而且它们的共同均值是e 解 先求N的分布 由于U1 U2 的所有n 种排序都是等可能的 所以有P N n P U1 U2 Un 1 n 再证P M n 1 n 用数学归纳法 其实 由归纳法 可以证明更强的结论 即对0 x 1 P M x n xn n n 1 式中M x min n 1 U1 U2 Un x 是和超过x的均匀随机变量的最少个数 为了证明P M x n xn n 首先证明它对于n 1是正确的 事实上P M x 1 P U1 x x x1 1 假设对于所有的0 x 1 P M x n xn n 为了确定P M x n 1 取条件于U1 得P M x n 1 P M x n 1 U1 y dy P M x n 1 U1 y dy U1 x P M x y n dy dy 归纳假设 du 综之 我们证明了对0 x 1 n 1 有P M x n xn n 置x 1 显示N与M具有相同的概率分布 从而有E M E N nP N n n 2 N 1 P N n P N n 1 n e 例27设X1 X2 是有相同分布函数F和相同密度函数f F 的独立连续随机变量 并且假设它们逐个地依次被观测 设N min n 2 Xn是X1 X2 Xn中第二大者 且设M min n 2 Xn是X1 X2 Xn中第二小者 问哪一个随机变量更大 是观测值中第二大的首个随机变量XN 还是观测值中第二小的首个随机变量XM 解 为了计算XN的概率密度函数 自然地 通过取条件于N的取值 为此 我们从确定它的概率分布列函数入手 现在 如果对i 2 令Ai Xi X1 X2 Xi中第二大者 那么 对于n 2P N n P A2A3 An 1 由Xi独立同分布推出 事件Ai i 2是独立的 此外 由Xi等可能地是最大 或是第二个大 或是X1 X2 Xi中第i个大 就可推出P Ai i 1 i i 2 因而 我们有P N n 于是 取条件于N就推出XN的概率密度函数在给定N n时 XN的条件分布等于具有分布函数F的n个 随机变量的集合中的第二大者的分布 在下面的讨论中 要使用到第二章的例2 37的结论 例2 37是这样的一个问题 为方便 我们将它复述如下 例2 37设X1 X2 Xn为独立同分布的连续随机变量 具有概率分布F x 和密度函数F x f x 我们以X i 记这些随机变量中第i个最小的值 则称X 1 X 2 X n 为次序统计量 orderstatistics 为了得到X i 的分布 我们知道X i 小于或等于x当且仅当这n个随机变量X1 X2 Xn至少有i个小于或 或等于x 因而P X i x F x k 1 F x n k由求导运算 即得X i 的密度函数 x f x k F x k 1 1 F x n k f x n k F x k 1 F x n k 1 f x F x k 1 1 F x n k f x F x k 1 F x n k 1 f x F x k 1 1 F x n k f x F x j 1 1 F x n j f x F x i 1 1 F x n i 上面的密度十分直观 因为为了使X i 等于x n个值X1 X2 Xn中的i 1个必须小于x n i个必须大于x 而且有一个必须等于x 现在 对于指定的i 1个Xj的每个成员都小于x 指定的另外n i个Xj的每个成员都大于x 而余下的值等于x的概率密度是 F x i 1 1 F x n if x 而由n个随机变量分成这样三组的不同划分数为 于是有以上所计算出的概率密度函数 运用例2 37中关于次序随机变量的密度函数的结论 得 F x n 2f x 1 F x f x 1 F x F x i f x 这让人有些惊奇 XN与X1有着相同的分布F 而且 如果取Wi Xi i 1 那么WM是已经看到的第二大观测值的第一个Wi的值 从而 由上面就得到WM与W1有相同的分布 即 XM与 X1有相同的分布 所以XM也有分布F 换句话说 不论是停止在已经出现的那些观测值中的第二大的首个随机变量 还是停止在已经出现的那些观测值 中第二小的首个随机变量 它们都将是具有分布F的随机变量 这一结果十分惊人 这是一个称为Ignatov定理的一般结果的特殊情形 由它可以推出更多的惊喜 例如 对k 1 令Nk min n k Xn X1 X2 Xn中第k大者 此时 N2是我们在前面记为N的那个 而是在到此为止已经出现的那些观测值中的第k个大的首个随机变量 运用同样的方法可以证明 对于所有的k 有分布函数F 另外 还可以证明 对任意k 1 随机变量是独立的 以下讨论利用取条件可得到比直接计算更为有效的解 例28考虑n个独立的试验 其中每个试验的结果是分别具有概率p1 p2 pk的结果1 2 k之一 pi 1 进而假定n k 我们关心的是确定每个结果至少出现一次的概率 如果以Ai记在n次试验的任意一次中 结果i都没有发生的事件 那么要求的概率是1 P Ai 运用包含 排斥定理得 P Ai P Ai P AiAj P AiAjAk 1 k 1P A1 Ak 其中P Ai 1 pi n P AiAj 1 pi pj n i j P AiAjAk 1 pi pj pk n i j k 求解的困难在于计算上式 需要计算2k 1项 而每项是一个高至幂n的量 当k大时 我们所给出的如上解是计算上非有效的 以下 我们来看如何利用取条件得到一个有效解 开始注意 如果取条件于Nk 结果k出现的次数 那么当Nk 0时 结果的条件概率将等于 做n Nk次试验 所有结果1 2 k 1至少发生一次的概率 其中每次结果i发生的概率为pi p1 p2 pk 1 i 1 2 k 1 然后 对这些项使用相似的取条件的步骤 按照以上想法 对于m n r k 在做m次独立的试验时 将结果1 2 r中的每一个至少发生一次的事件记为Am r 其中每次试验的结果是1 2 r之一 分别以概率p1 Pr p2 Pr pr Pr出现 Pr pj 令P m r P Am r 注意P n k 就是所求的概率 为了得到P m r 的表达式 取条件于结果r发生的次数 并给出P m r P Am r r发生j次 P m j r 1 从P m 1 开始 我们利用上面的递推关系得到量P m 2 m 2 3 n k 2 然后得到量P m 3 m 3 4 n k 3 依次类 1 若m 1 0 若m 0 推 直到P m k 1 m k 1 k 2 n 1 此时 就可利用这一递推关系计算P n k 计算所需的计算量是k的多项式 k大时 要比2k小得多 前面我们已经指出这样的事实 除了所有的概率是取条件在事件Y y上以外 给定Y y的条件期望恰与普通的期望一样 因此 条件期望满足普通期望的所有性质 例如E X W w P W w 若W是离散的 E X W w fW Y w y dw 若W是连续的 它们所对应的关系是E X W w Y y P W w Y y 若W离散 E X W w Y y fW Y w y dw 若W连续的 E X E X Y y 如果E X Y W 定义为Y和W的函数 使得当Y y和W w时 它等于E X Y y W w 那么上面的关系可以写成E X Y E E X Y W Y 例29汽车保险公司将每个参保户分为i 1 2 k种类型 假定类型i的参保户在相继的年份中的事故服从均值为 i的独立泊松分布 i 1 2 k 一个新的参保户属于类型i的概率是pi pi 1 已知一个参保户在第一年中有n次事故 问在她的第二年平均有多少事故 在她的第二年有m次事故的条件概率是多少 解 以Ni记投保户在第i年的事故次数 i 1 2 取条件于她的风险类型T并得到E N2 N1 n E N2 N1 n E N2 T j N1 n P T j N1 n E N2 T j P T j N1 n jP T j N1 n 其中最后的等式源于P T j N1 n Bayes 给定她在第一年中有n次事故 在她的第二年有m次事故的条件概率也可以通过对她的风险类型取条件得到 P N2 m N1 n P N2 m T j N1 n P T j N1 n P T j N1 n 另一种计算P N2 m N1 n 的方法是 先写出 P N2 m N1 n 然后通过取条件于T以确定分子与分母 由此得到P N2 m N1 n 一些应用列表模型考虑n个元素e1 e2 en 他们是一个有序的列表 在每一个单位时间 对于其中的一个元素ei有需求的概率Pi独立于过去的情形 在这个元素被需求后 它就移至列表的第一个位置 例如 如果现在的位置是e1 e2 e3 e4 而若e3被需求 则下一个次序是e3 e1 e2 e4 我们关心的是在此过程经长时间运作后 确定被需求元素的位置的期望 在计算这个期望之前 我们来观测这个模型的两个可能的应用 第一个应用是 假如我们有一摞参考书 在每一个单位时间随机选取了一本书 然后放回到这摞书的最上面 第二个应用是 我们有一台计算机 其内存中存放着被需求的元素 元素被需求的概率可能并不知道 所以为了减少计算机查找各元素所花费的平均时间 如果计算机往下查找这个元素 则它与被需求元素的位置成正比 它将把这个元素放在列表的起点 为了计算被需求的元素的位置的期望 我们从对选取的元素取条件入手 于是有E 被需求的元素的位置 E 位置 选取到ei Pi E ei的位置 选取到ei Pi E ei的位置 Pi 其中最后的等式 用了ei的位置与ei被选上的事件是独立的条件 因为不管ei的位置它被选上的概率是Pi 鉴于ei的位置 1 Ij其中1 如果ej在ei前面 0 其它情形 所以E ei的位置 1 E Ij 1 P ej在ei前面 为了计算P ej在ei前面 注意 ej在ei前面 如果对它们两者的最近需求是ej 此时当给定需求是ej或ei的条件下 需求是ej的条件概率是 Ij P ej ei或ej Pj Pi Pj 故而P ej在ei前 Pj Pi Pj 因此我们有E 被需求的元素的位置 1 Pi随机图一个图 由称为顶点的一个元素集合V及称为弧 端点有序称有向弧 无序称无向弧 的V中元素对形成的一个集合A组成 关于图有许多常用概念 如图的图示 自结圈 从顶点i到顶点j i j 的一条路径 存在一系列顶点i i1 i2 ik j 使 i i1 i1 i2 ik j 都是弧 无向图 有向 图 连通图 在个相异顶点对的每对间都存在1条路径 我们考虑随机图 设V 1 2 n A i X i X i 是独立随机变量 i 1 2 n 式中的X i 满足P X i j 1 n j 1 2 n换句话说 我们从每个顶点i随机地在n个顶点中选取一个 包括可能是顶点i自己 并在顶点i与选取的顶点间连一弧 这种图通常称为随机图 我们关注的是确定这样得到的随机图是连通图的概率 先从某个顶点出发 例如顶点1 让我们沿着顶点序列1 X 1 X2 1 继续 其中Xn 1 X Xn 1 1 定义N为Xk 1 不再是一个新顶点的首个k值 即 N 第一个k 使Xk 1 1 X 1 Xk 1 1 其表示图如 其中从XN 1 1 出发的弧返回此前已经访问过的顶点 为了得到此图为连通图的概率 我们首先取条件于N 得P 图为连通图 P 图为连通图 N k P N k 现在 在N k给定时 k个顶点1 X 1 Xk 1 1 是彼此连通的 而且没有从这些顶点出发的其它的弧 换言之 如果我们将此k个顶点视为一个超顶点 那么其情形就类似于譬如 我们有一个超顶点与n k个普通顶点 而且有从这些普通顶点出发的其它的弧 每一条通向超顶点的概率为k n 1 X 1 X2 1 XN 1 1 这种情形的解可以通过在引理1中取r n k得到 引理1给定由顶点0 1 r和r条弧组成的随机图 i Yi i 1 2 r其中j概率为1 r k j 1 2 r 0概率为k r k 那么P 图为连通图 k r k 引理所述为 图有r 1个顶点 其中有r个普通顶点 一个超顶点 每个顶点发出一条弧 该弧以概率k r k 通向超顶点 而以概率1 r k 通向普通顶点 没有弧从超顶点发出 Yi 证明 对r做归纳 对于任意的k 当r 1时命题成立 假定命题对于比小于r的值都正确 考虑r的情形 对连接Yj 0的弧 j Yj 的个数取条件 并有P 连通 P 连通 Yj 0的弧有i个 现在给定有i个弧通向超顶点 其余r i个弧不通向超顶点 此情形类似于譬如我们有r i个普通顶点和一个超顶点 从每个普通顶点有一个弧以概率i