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

2021/6/17 20:57:07

编程Tag： 概率选中 ... 成功系数导论试验附录 C.4

本文主要是介绍算法导论附录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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

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

相关编程文章

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