线性期望介绍和使用指南

先决条件：随机变量

这篇文章是关于数学概念的，比如期望，期望的线性性。它涵盖了需要理解的主题之一

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

问题:给定一个有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取r1的概率为p1，取r2的概率为p2，以此类推，直到取rk的概率为pk，则该随机变量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

当掷骰子更多时, 上述解决问题的方法将变得困难。

如果我们知道期望的线性，那么我们可以快速地解决上述问题的任何次数。

线性期望： 让R1和R2是某个概率空间上的两个离散随机变量, 然后

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 [R1[R2] = E [R1] * E [R2]仅对独立事件有效。
2. 期望的线性对于某个概率空间上的任意数量的随机变量均成立。让R1, R2, R3, ... Rk是k个随机变量, 则
   E [R1+ R2+ R3+…+ Rk] = E [R1] + E [R2] + E [R3] +…+ E [Rk]

可以通过期望的线性轻松解决的另一个示例：

帽子保管问题：

假设有一群n个男人, 每个男人都有一个帽子。重新分配了帽子, 每个人都随机得到了帽子。带回原来帽子的男性预期人数是多少？

解：让R一世是一个随机变量, 如果我的男人拿回同一顶帽子, 则随机变量的值为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个人会拿回正确的帽子。

练习：

1. 给定一个公平的硬币, 当硬币被抛掷n次时, 预期的正面数是多少。
2. 球和垃圾桶：假设我们有m个球, 标记为i = 1, …, m和n个垃圾桶, 标记为j = 1, .., n。每个球都独立且均匀地随机扔进一个垃圾箱。
   a)每个料箱中的预期球数是多少
   b)空箱的预期数量是多少。
3. 优惠券收集者：假设彩票中有n种类型的优惠券, 并且每批包含一张优惠券(概率为1 = n)。直到我们每种类型的至少有一张优惠券, 才需要购买多少手(预期)。

有关Coupon Collector的解决方案, 请参见以下内容。

直到成功的预期试验次数

期望的线性在算法中很有用。例如, 使用线性期望来评估随机算法(如随机快速排序)的预期时间复杂度(请参见这个以供参考)。

参考文献：

http://www.cse.iitd.ac.in/~mohanty/col106/Resources/linearity_expectation.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/

本文作者：Shubham Gupta。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。