C/C++教程

算法导论 附录C C.4-8

本文主要是介绍算法导论 附录C C.4-8，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考虑n次伯努利试验，其中i = 1，2，...，n，第i次试验成功的概率为p_{i}，令X为表示总成功次数的随机变量。令对所有i = 1，2，...，n有p\geq p_{i}。证明：对于1\le k \le n，

Pr\left \{ X< k\right \} \ge \sum_{i=0}^{k-1}b(i;n,p)

证明：

这里我们进行一个更强的证明：

考虑仅增大其中一次试验的成功概率，不妨记为p_{c}\rightarrow p_{c} + \sigma，其中0 \le \sigma < 1-p_{c}，并记总成功次数随机变量为X^{'}，有 Pr\left \{ X< k\right \} \ge Pr\left \{ X^{'}< k\right \}

构造辅助函数

 \prod_{i = 1}^{n}[p_{i}x + (1 - p_{i})] = a_{0} + a_{1}x + a_{2}x^{2} + ... + a_{n}x^{n}

易知

 Pr\left \{ X< k\right \} = \sum_{i = 0}^{k-1}a_{i}

列出系数第一项

a_{0} = \prod_{i = 1}^{n}(1 - p_{i})

考虑相邻两项系数间的关系 a_{n}与 a_{n+1}，每项系数均可写成 b_{i}\cdot p_{c} + d_{i} \cdot (1 - p_{c})形式，即：

a_{n} = b_{n} \cdot p_{c} + d_{n} \cdot (1 - p_{c})

a_{n+1} = b_{n+1} \cdot p_{c} + d_{n+1} \cdot (1 - p_{c})

其中p_{c}是之前我们选择增大的那次试验成功概率

注意a_{n+1}与a_{n}间的生成关系，在a_{n+1}中p_{c}被选中的情况分为两种：

1、在a_{n}时已被选中，由b_{n}中未选中的某次变为选中得到（与2中重复）

2、在a_{n}时未被选中，由d_{n}对应的(1 - p_{c})变为p_{c}得到（无重复）

因此有

b_{n+1} = d_{n}

回到a_{0}：

a_{0} = [\prod_{i = 1\wedge i\neq c}^{n}(1 - p_{i})](1 - p_{c}) + 0 \cdot p_{c}

可推出

Pr\left \{ X< k\right \} = \sum_{i = 0}^{k-1}a_{i} = t_{1}p_{c} + t_{2}(1 - p_{c})

其中t_{1} \le t_{2}

因此

Pr\left \{ X^{'}< k\right \} - Pr\left \{ X< k\right \} = t_{1}\sigma - t_{2}\sigma \le 0

即

Pr\left \{ X< k\right \} \ge Pr\left \{ X^{'}< k\right \}

原命题也得证

 

这篇关于算法导论 附录C C.4-8的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航