离散概率part3

Outline

Expectation

期望的两种计算方法

期望的定义：所有的随机变量可能的取值乘以对应的概率，然后再求和。

但是我们要知道E(X)是一个加权的平均数。E(X)不再是一个随机变量了

定义一个偏差(deviation)为随机变量减去期望

基于定义求

比如说我抛硬币100次，我们要看正面朝上的次数为多少，向上的概率为p

那么如果按照普通的算法，那么就要对每一个出现情况的概率进行求和，也就是对$2^{100}$个样本求和，那么我们如果对随机变量X求和，（X对应硬币朝上的个数）那么只要对0-100求和就行了。

只要知道分布，就知道期望了

基于随机变量来求

例题

例一

我们不仅仅可以算X的期望，也可以计算$X^2$ ,$X^3$的期望，直接用它的函数值带入即可

例二

贝努力分布和几何分布的期望

贝努力分布

The expected number of successes when n mutually independent Bernoulli trials are performed, where p is the probability of success on each trial, is np.

几何分布

The expected number of successes when a r.v. X follows a Geometric distribution is 1 p , where p is the probability of success on each trial.

也就是说第一次成功之前，已经做了多少次

Linearity of expectations

期望的线性性质

1.和的期望等于期望的和

2.具有线性运算的性质$E(aX_i+b) = aE(X_i)+b$

1. 线性可加性 ,比如

证明：

贝努力实验的期望

根据期望的线性性，我们很容易就能算出n次贝努力实验的期望了

例子：

例一：

A new employee checks the hats of n people at a restaurant, forgetting to put claim check numbers on the hats. When customers return for their hats, the checker gives them back hats chosen at random from the remaining hats. What is the expected number of hats that are returned correctly?

就是说这个服务员是新来的，没有给顾客发取帽码，所以只能随便拿(帽子都一样)，问这个期望拿对的概率是多少

如果我们按照定义来算，那么就要算出来没有人能拿对的概率，一个人拿对的概率，。。。全部拿对的概率，也就是说先找分布，再计算期望。但这显然太麻烦了

所以 这样考虑：0个人拿对，那么n个人错排；1个人拿对，n-1个人错排。所以我们用期望的性质来做。我们来看第i个人是否拿对，拿对的概率 1/n,拿错的概率 n-1/n。求和即可

例二：

计算一个数列中逆排列的数字对，逆排列就是说a<b 但是a在b的后面，如图中所举例

那么对于一个数字对来说 $I_{i,j}$来说，他要么是逆序列，要么不是。所以说他的期望是 1/2

然后我们只要计算有几个这样的数字对即可，C(2,n) = n(n-1)/2 相乘得答案

独立随机变量的期望

当X，Y相互独立的时候，期望的乘积就等于乘积的期望

$E(XY) = E(X)E(Y)$

Average-case computational complexity

通过期望来计算平均的算法复杂度，也就是一般情况下大概是什么复杂度

那么他的期望就是输入一个数字的 概率，乘以其对应的比较次数

Finding the average-case computational complexity of an algorithm is usually much more diffcult than nding its worst-case computational complexity, and often involves the use of sophisticated methods.

线性搜索算法

Question: What is the average-case computational complexity of the linear search algorithm if the probability that x is in the list is p and it is equally likely that x is any of the n elements in the list?

Solution: 也就是说，x和$a_i$ 去比较，那么需要比较 i 是否小于等于n 和 比较 x是否等于 $a_i$也就是说要比较两次，那么如果最终找到了，然后还要跳出循环，判断i是不是小于等于n，所以一共比较2i+1次

那么如果没找到，那么就是比较2n+2次

The probability that x equals ai ,
the i-th element in the list, is p/n, and the probability that x is not in the list is q = 1 - p.

令p指的是这个x落在这n个数中的概率。因为每个数可能是均匀分布在这个序列里面的，所以如果有5个数字，那么概率就是p/5,如果有n个数字，那么就是p/n.

那么我们就可以进行计算了

插入排序算法

Question：What is the average number of comparisons used by the insertion sort to sort n distinct elements?

Solution:We first suppose that X is the r.v. equal to # comparisons used by the insertion sort to sort a list a1, a2, … ; an of n distinct elements.
Then E(X) is the average number of comparisons used.

记作$a_k$为前j个元素中最大的元素,$1\leq k \leq j$

所以关键是看k落在第几个位置。如果k在第一个，那么每一个后来的都比 $a_k$ 小

如果是落在最后一个，那么每个都要比较一下

方差

定义

方差可以对定义求和，也可以对随机变量来求

定理

也可以这样来计算：X偏离均值的平方的期望

各种分布的方差

例一：贝努力实验的方差

Question: A coin is flipped one time. Let $\Omega$ be the sample space of the possible outcomes, and let X be r.v. that assigns to an outcome # heads in this outcome. What is the variance of X if it is a biased coin with P({H}) = p?

例二： 二项分布的方差

Question: Let r.v. X be the number of successes of n mutually independent Bernoulli trials, where p is the probability of success on each trial. What is the variance of X?

例三：几何分布的方差

Question: Let r.v. X be the rst occurrence of success requires n mutually independent Bernoulli trials, where p is the probability of success on each trial. What is the variance of X?

方差的非线性性

这说明什么道理呢？

说明对一列数进行平移，那么不会影响我的方差，如果对一列数进行拉伸a倍，那么方差就会扩大a的平方倍。

如果对一列数进行压缩，那么方差就会压缩的更厉害。

Bienayme‘s formula

当随机变量两两之间相互独立的时候，那么这时候方差的和就等于和的方差

例子

因为$X_i$ 是独立的而且是同分布的随机变量（独立且分布函数相同），这意味着所有的$X_i$的期望是一样的，$X_i$ 的方差也是一样的（比如抛筛子两次，第一次X1和第二次X2）

这个例子告诉我们什么呢？

原来$X_i$的方差是 $\sigma^2$ 那么 现在我们把 所有的$X_i $加起来后取平均数的话 方差会随着数量的增加而逐渐趋向于0

$\lim\limits_{n->\infty}V(\overline{X_n}) = 0$

也就是说，随着随机变量数量的增加，当n越来越大的时候，最后随机变量会变成一个常数。均值的方差会变得很小很小。

举个例子，我们 利用标记重补法来估算池塘中的鱼，那么一次的话可能说明不了问题，那么我们可以做很多次，然后取一平均值，这时候根据上面的公式，方差（波动）不会很大

Tail probability尾概率

比如果我抛出100次硬币，那么50是它的期望

那么我们如果想要计算$P_n(X>90)$和$P_n(X<10)$ 这两个概率，就是一种尾概率

如果我们硬算，会变得很麻烦，很难计算 $\sum{k=91}^{100}C{100}^k \frac{1}{2}^{100} $

所以我们给他一个上界，估计估计，但是我又让这个上界越接近越好。那么怎么计算一下呢？

像上面这张图片，我们可以把这个看作抛了n次的模型，我们看到最后的概率接近0.5。这是因为Xi = {0,1},那么

当n越大的时候，方差越小，方差越小，波动就越小。

回到上面的问题 $Pn(X>90) = P_n(\sum{1}^nX_i>=90)$

Markovs inequality

Theorem

也就是说刚才的尾概率可以通过这样的方法来进行计算

Proof

就比如说，我投n次币 ，我计算正面朝上的概率大于0.9

但这个上界有问题，放的太宽了。n=100,n=1000，n越来越大的时候，概率应该越来越稳定才对，所以偏离p=0.5的概率会越来越小，但是根据马尔可夫不等式，却发现上界始终不变。所以不科学，不太准确

Chebyshevs inequality

所以我们来看切比雪夫不等式。马尔科夫不等式用的是期望，切比雪夫不等式用的是方差。这个方差会随着n的增加而慢慢减小，但是期望是不会随着n的变化而变化的，所以这就导致了两者的区别，一个和n无关，一个和n有关

Theorem

Proof

马尔可夫不等式，是单尾的，只能计算> 某个值的上界，但是切比雪夫不等式是双尾的，

双尾的肯定要比单尾的概率要大，所以我们通过这个关系把单尾转化成双尾再进行计算。

通过下面两个例子计算出的结果，要比马尔可夫不等式更科学，当n趋向于无穷的时候，尾概率会趋向于0，符合上面方差趋向于0的判断。

比如说我要计算刚才抛硬币的例子

但是这样虽然符合观测结果，但也不能说切比雪夫不等式给出的上界，就是一个很好的上界，所以我们需要

Chernoff bound

Chernoff bound

Theorem

Proof

Theorem for upper tail

这是另外一个尾巴

关于这里分母为什么是4，我一直没搞明白

其实这里分母可以为大于2的任何数，3，4都可以。因为我们通过泰勒展开得到的分母为2，而

$\frac{-\mu\delta^2}{4}$ >$\frac{-\mu\delta^2}{2}$ ,所以事实上这个界比$e^{\frac{-\mu\delta^2}{2}}$ 要松

example

比如说我们想要计算 $P(|x-\mu|>\delta\mu)$

这里的$\delta$ 是怎么求出来的呢？凑出来的。因为知道$\mu=\frac{n}{2}$（期望） 然后 根据我们要求的尾概率，提取出$\mu$ 来看他的系数即可

像下面这个例子，对我们理解切诺夫界更有帮助

这相当于一个不均匀的硬币，有$\frac{\pi}{4}$ 的概率正面（红色圆域） ，剩下的概率为反面（绿色部分）

Y就相当于抛出n次后打包在一起的一个随机变量。

那么我如果要计算$Y>\frac{\pi}{2}$ 的概率（事实上这个等于0）那么我们就可以按照上面的方法计算。

$P(Y-\frac{\pi}{4}>\frac{\pi}{4})$ 的 意思，其实就是偏移方差量大于$\frac{\pi}{4}$ 的意思，概率肯定是随着n的增加而接近于0。

所以根据切比雪夫不等式我们可以得到了当n=100的时候，这个概率的上界是0.0025 但这还不是最准确的

当我们用切诺夫界来计算的时候，那么概率变成了e^(-75/4)^ 也就是小数点后10个0的概率，而事实上的概率比这个还要小。所以说切诺夫界比切比雪夫不等式更加的准确

所以说我们想要达到一个精度（偏移期望的概率达到足够小） 对于切比雪夫来说，需要做的次数要远高于切诺夫界所需要的次数，因为切诺夫界是按照指数缩小的