随机变量&期望

随机变量

定义: 随机变量X是定义在样本空间Ω上的一个实值函数X:Ω→R

需要注意的是，随机变量在这里是一个函数 ,而不是一个"变量 ",在没有特殊说明的情况下，这里的随机变量都是指离散的情况。

定义: 两个随机变量是独立的，当且仅当

Pr[(X=x)∧(Y=y)]=Pr[X=x]⋅Pr[Y=y]

这和事件独立的定义很相似。

期望

定义: 离散随机变量的期望E[X]定义如下:

E[X]=∑x∈XxPr[X=x]

定理(期望的线性可加性): 对于任意的随机变量X1,X2,⋯,Xn,和实数a1,a2,⋯,an,均有

E[n∑i=1aiXi]=n∑i=1ai⋅E[Xi]

上述定理可以理解成"和的期望=期望的和 "

证明:

要证明上述的定理，我们首先需要证明两个等式:

• E[X+Y]=E[X]+E[Y]
• E[cX]=cE[X]

上述两个等式的证明非常简单:

第一个等式:

第二个等式:

有了上述两个等式之后，我们可以用归纳法来证明这个定理:

n=2时:

假设n=k−1时，E[k−1∑i=1aixi]=k−1∑i=1aiE[xi]成立，则当n=k时:

◻

---

期望的线性可加性这个定理非常有用，因为它没有任何的附加的条件，不管是否独立，这个定理总是成立的。

定义: 对于随机变量X和Y来说，条件期望定义为:

E[X|Y=y]=∑x∈XxPr[X=x|Y=y]

定义: 对于随机变量X和Y来说，总期望定义为:

E[X]=∑y∈YE[X|Y=y]⋅Pr[Y=y]

Union Bound

Union Bound是指一个不等式，这个不等式在概率论中经常被用到，它的描述如下:对于任何的有限或可数事件集合，至少一个事件发生的概率不大于所有独立事件的概率和。

对于事件集合A1,A2,⋯,我们有:

三种常见的分布

伯努利分布(Bernoulli Distribution)

伯努利分布描述了单个抛硬币的情况，以p的概率出现正面(1)，而以1−p的概率出现反面(0)。

如果X服从与伯努利分布，则:

可以看到，对于伯努利分布来说，E[X]=p

几何分布(Geometric Distribution)

重复投掷一个硬币直到第一次出现正面,其中的每一次的投掷都是服从伯努利分布的.

令X表示一共投掷了多少次的随机变量，则我们称X服从于参数为p的几何分布:

对于几何分布来说，我们可以直接利用插值法来计算几何分布的期望，但是，其实还有一种更加巧妙的方法来计算其期望。

令Yk表示一个布尔值，当前k次投掷都没有出现正面时，Yk=1，否则Yk=0.很显然，我们有E[Yk]=(1−p)k,且X=∞∑k=0Yk.

则利用期望的线性可加性:

二项分布(Binomial Distribution)

如果我们将硬币投掷n次，每一次投掷都是服从伯努利分布的，用X表示在这n投掷中出现正面的次数，则Pr[X=k]=(nk)(1−p)n−kpk

通常来说，我们用B(n,p)来表示一个二项分布。

我们可以利用期望的线性可加性来计算二项分布的期望:

令Xi表示事件"第i次投掷为正面"，也即当第i次投掷为正面时，Xi=1，否则Xi=0.

显然有X=n∑i=1Xi，且E[Xi]=p,所以:

问题举例

优惠券搜集问题(Coupon Collector)

优惠券问题是我小时候常常被坑的一种把戏，某个卖干脆面的商家在每一包的干脆面中都会放置一张小卡片，每一张小卡片都代表一个历史或武侠小说(三国、水浒等)中的人物，如果你能够集齐所有的人物卡片，那么商家会赠送一个大奖给你。这对于小学生来说，是非常具有诱惑力的¹。

现在我们可以用数学的方式来看一下这种营销模式，我们首先假设商家的这些卡片人物都是均匀分布的²,那么我们将整个问题建模成一个小球投掷的问题: 假设我们有n个空箱子(卡片人物)，每次都任意地向其中一个箱子投掷一个小球(买一包干脆面)，每次投掷都是独立的，且是均匀分布的。那么，现在的问题是平均需要投掷多少次小球，才能使所有的箱子都是非空的。

令X表示最终投掷小球的数目，这样我们的目标就变成了计算E[X].

令Xi表示有i−1个箱子非空时，需要投掷多少个小球才能变成有i个箱子非空。根据这样的建模，我们有X=n∑i=1Xi.

其次，很显然，Xi是一个几何分布,且对于每一次的投掷来说，投入到一个空箱子的概率是pi=1−i−1n,因此我们有

所以E[Xi]=1pi=nn−i+1

利用期望的可加性，我们有:

上式中的H(n)表示第n个调和数。

又因为H(n)=lnn+O(1)，所以为了能够集齐所有的卡片，我们平均需要购买nlnn+O(n)袋干脆面。

负载问题(Occupancy Problem)

我们可以继续来看一下小球投掷的模型，在优惠券搜集的问题中，我们考虑的关注点在于有多少个箱子是非空的，而在这里，我们考虑的是，每个箱子最多会被投掷多少个小球。

这种模型的一种典型应用就是大型网站的流量分配，对于大型门户网站来说，它的服务器集群都是上百台服务器，如何分配流量请求使得这些服务器不会出现负载过重的现象是非常重要的。要分析类似的负载问题时，我们就可以利用小球投掷来建模。

假设现在有m个小球需要投掷到n个箱子中，我们首先来看一下平均情况下每一个箱子的负载情况:

令Xi表示第i个箱子被投掷的小球数，很显然我们有n∑i=1Xi=m，利用期望的可加性,我们有:

又因为我们每一次的投掷都是均匀分布的，且是独立的，因此可以得到E[Xi]=mn

可以看到，在均匀分布且每次投掷都是独立的情况下，每一个箱子的负载E[Xi]=mn.

---

在实际情况下，除了平均情况以外，我们通常比较关注的是最坏情况，也就是一个箱子在最差情况下它的负载是多少。我们现在就来分析一下这样的最坏情况:

令M表示某一个箱子在最坏情况被投掷的小球数目，而我们的任务就是要计算Pr[max1≤i≤nXi≥M],首先利用Union Bound,我们有:

上式中中间的不等号是因为Union Bound,最后一个等号是因为X_i是均匀分布且独立的。

现在我们的问题就变成了估算Pr[X1≥M],表示第一个箱子至少被投入M个小球的概率。很显然，我们有:

对于右侧的不等式，我们可以继续计算:

利用Stirling逼近,我们有M!≈√2πM(Me)M,因此:

将这个结果代回???中:

当M=3lnnlnlnn时³,我们有:

因此，我们可以得出结论:

总结

随机算法的很多问题在于怎么建模，比如之前的计算几何分布和二项分布的期望的时候，将随机变量设置成一个{0,1}的布尔值，这就在很大程度上简化了计算难度，很容易就能计算其期望。

另外常见的不等式(Union Bound)，分布都要比较熟悉，这样才能在遇到具体问题时灵活应用。

Share on: Twitter ❄ Facebook ❄ Email

---

---