2018-10-06

期望的线性

$E(x+y)=E(x)+E(y)$

当事件独立时,$E(x\cdot y)=E(x)\cdot E(y)$

方差

随机变量的方差$$V(x)=E((x-E(x))^2)=E(x^2)-E^2(x)$$

也就是说，方差的期望等于平方的期望家去期望的平方。

小练习

• 随机一个$[1,n]$的数，期望$n\ln n$能随机出所有的数。

证明：对于第$i+1$个数，$P(随机到)=\cfrac{n-i}{n}$，则$E(随机到)=\cfrac{n}{n-i}$

• 给定一个有向无环图，求从$S$到$T$随机游走的期望步数。

方法：$f_u$