期望线性

先决条件： 随机变量 这篇文章是关于数学概念的，比如 预料 , 期望线性 .它涵盖了需要理解的主题之一 随机算法 .

让我们考虑下面的简单问题。

问题： 给定一个有6张脸的公平骰子，掷骰子n次，找到所有结果之和的期望值。 例如，如果n=2，则总共有36种可能的结果。

(1, 1), (1, 2), .... (1, 6)
(2, 1), (2, 2), .... (2, 6)
................
................
(6, 1), (6, 2), ..... (6, 6)

期望值 离散随机变量的R定义如下。假设R可以取R的值 _1. 概率为p ₁ ，r值 _2. 概率为p _2. ，以此类推，直至r值 _K 概率为p _k .那么这个随机变量R的期望值定义为：

E[R] = r1*p1 + r2*p2 + ... rk*pk

让我们计算上述示例的预期值。

Expected Value of sum = 2*1/36 + 3*1/36 + .... + 7*1/36 + 
of two dice throws      3*1/36 + 4*1/36 + .... + 8*1/36 + 
                        ........................
                        .........................
                        7*1/36 + 8*1/36 + .... + 12*1/36     
                  
                      = 7

当掷骰子较多时，上述解决问题的方法就会变得困难。 如果我们知道 期望线性 ，那么我们就可以快速解决上述问题，无论抛出多少次。

期望线性： 让R _1. 和R _2. 是某个概率空间上的两个离散随机变量

     E[R1 + R2] = E[R1] + E[R2] 

使用上述公式，我们可以快速解决骰子问题。

Expected Value of sum of 2 dice throws = 2*(Expected value of one dice throw)
                                       = 2*(1/6 + 2/6 + .... 6/6)
                                       = 2*7/2
                                       = 7 

Expected value of sum for n dice throws is = n * 7/2 = 3.5 * n 

关于期望值的一些有趣事实：

1. 独立事件和独立事件的预期线性均成立。另一方面，规则E[R] _1. R _2. ]=E[R _1. ]*E[R] _2. ]这只适用于独立活动。
2. 在某些概率空间上，对于任意数量的随机变量，期望的线性都成立。让R _1. R _2. ，R _3. ，…R _K 那么是k个随机变量吗 E[R] _1. +R ₂ +R _3. +…+R _K ]=E[R _1. ]+E[R] _2. ]+E[R] _3. ]+…+E[R] _K ]

另一个可以用期望线性轻松解决的例子： 帽子检查问题： 让n个人组成一个小组，每个人都有一顶帽子。帽子被重新分配，每个人都会得到一顶随机的帽子。预计有多少男性会拿回他们原来的帽子？

解决方案： 让R _我 作为一个随机变量，如果第i个人得到相同的帽子，则随机变量的值为1，否则为0。

So the expected number of men to get the right hat back is
  = E[R1] + E[R2]  +  .. + E[Rn] 
  = P(R1 = 1) + P(R2 = 1) + .... + P(Rn = 1) 
  [Here P(Ri = 1)  indicates probability that Ri is 1]
  = 1/n + 1/n + ... + 1/n 
  = 1

因此，平均每个人都能拿回正确的帽子。

练习：

1. 给定一枚公平的硬币，当硬币被抛n次时，预期的人头数是多少。
2. 球和箱子：假设我们有m个球，标记为i=1，…，m和n个箱子，标记为j=1，n、 每个球都会被独立地、均匀地随机扔进其中一个垃圾箱。 a） 每个箱子里预计有多少个球 b） 预计的空垃圾箱数量是多少。
3. 优惠券收集者：假设彩票中有n种类型的优惠券，每一批包含一张优惠券（概率为1=n）。在每种类型至少有一张优惠券之前，我们需要（预期）购买多少张。

有关优惠券收集器的解决方案，请参见下文。 成功前的预期试验次数

期望的线性在算法中很有用。例如，随机快速排序等随机算法的预期时间复杂度是使用预期线性来评估的（参见 这 供参考）。

参考资料： http://www.cse.iitd.ac.in/~mohanty/col106/Resources/linearity_expection。pdf

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-22-expectation-i/

本文由 舒巴姆·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论