0%

概率和期望(旧文补档)

简单介绍概率和期望。

基本定义

概率反映随机事件出现的可能性大小,是事件发生的可能性的度量。

样本空间$\Omega$是某个随机实验的所有基本结果的集合。

  • 比如,$\{\texttt{叉义叉爆零}\}$是一个样本空间,因为一考试(随机试验)x义x就只能爆零。

  • $\{\texttt{ZK拿rank1},\texttt{ZK拿rank2},\texttt{ZK拿rank3}\}$是一个样本空间。

  • x义x抛两枚硬币,$\{\texttt{正正},\texttt{正反},\texttt{反正},\texttt{反反}\}$是一个样本空间。

样本空间的一个子集称为事件,所有事件的集合称为事件集合$F$。

概率测度$P$,即常说的概率,是一个从$F$到实数的函数,或者说,一个事件对应了一个它的概率。一个合理的概率测度需要满足概率公理:

  • $\forall A\in F,P(A)\ge 0$。任何一个事件的概率非负。(非负性)

  • $P(\Omega)=1$。(规范性)

  • $\forall A,B\in F$,如果$A\cap B=\phi$,那么有$P(A)+P(B)=P(A\cup B)$。(可加性)

因此我们知道,在一个合理的概率测度下x义x的爆零是必然的

条件概率

条件概率

记$P(A|B)$为,$B$发生的情况下$A$发生的概率。同时把$P(A\cap B)$简记为$P(AB)$或$P(A,B)$。

条件概率公式:

事实上,我们把$B$看作了一个新的样本空间,条件概率公式也是两个样本空间上的概率测度的关系。

全概率公式

设$\forall i,j,\ B_i\cap B_j=\phi$,且$\bigcup B_i=\Omega$,则称$\{B_i\}$是样本空间的一个划分

如果$\{B_i\}$是样本空间的一个划分,那么有

容易证明。

贝叶斯公式

联系了两个概率空间 $A$ 和 $B$ 的重要公式。如果把 $P(A),P(B)$ 展开写为 $P(A|\Omega),P(B|\Omega)$ 再看看的话可能会获得一些更深的理解。

缝合怪(???)

就是把贝叶斯公式和全概率公式结合一下

例题

似乎OI中用得不多?就不讲例题了。

随机变量,期望,方差

如果没有特殊说明,以下默认随机变量为离散的。

离散的是说,如果一个随机变量的取值只有有限或可数个。可数的意思比较难解释,大意就是“可以列举出来”。比如所有偶数可以按第一个偶数,第二个偶数……这样列举出来,所有有理数也可以列举出来。但是$[0,1]$间的实数则不可以列举出来。不展开讲严谨定义了。

随机变量

随机变量本身没有随机性,也不是变量,它其实是一个定义在$\Omega$上的函数:一个基本结果对应一个值。出现哪一个基本结果才是随机的,同一个基本结果对应的函数值是固定的。

然而大多数应用情况下我们反而不主要分析,甚至不明确指出样本空间……

有时我们说,随机变量$X=x$的概率$P(X=x)$,其实是说$P(\{e|e\in \Omega,X(e)=x\})$。再换句话说,$X=x$是一个新的事件,我们按这些事件把样本空间重新作了划分。接下来我们将完全把$X=x$当事件看待。

顺便再提一句,$\sum P(X=x)=1$。即$P(\Omega)=1$。

我们说两个随机变量$X_1,X_2$是独立的,是说,

期望

一个随机变量$X$的期望$\text{E}X$是

期望具有线性性。对于两个不一定独立的随机变量$X,Y$,有

对于两个独立的$X,Y$,还有

还容易得到

也就是所谓整数概率公式

例题

例一

抛一枚质地均匀的硬币。求期望正面朝上的次数。

解答

有两个基本结果:正面朝上或反面朝上,概率均为$\frac 1 2$。然后$X(\texttt{正面朝上})=1$,$X(\texttt{反面朝上})=0$,于是显然$\text{E}X=\frac 1 2$。

例二

抛$N$枚质地均匀的硬币。求期望正面朝上的次数。

解答

根据期望的线性性,显然有$\text{E}X=\frac N 2$。

条件期望

我们前面提到了有关如果已经有某事件发生的约束,随机变量会如何行为的内容。实际上,就是缩小随机变量的定义域。

如果$A$已经发生,那么随机变量$(X|A)$是一个从$A$到实数域的函数。

类似条件概率公式,我们有条件期望公式:

全期望公式则看起来比较奇怪和不可思议:

先来解读一下。$X|(Y=y)$是一个随机变量,它的期望就是$\text{E}(X|(Y=y))$;$\text{E}(X|Y)$也显然是一个从所有基本结果$Y=y$构成的样本空间到实数的函数(即一个随机变量),它的期望就是$\text{E}(\text{E}(X|Y))$,我们将要证明,它与$\text{E}X$相等。

感性理解估计是理解不了了,我们爆拆吧。

大意就是,$Y=y$是样本空间的一个划分,于是我们换一下求和号再用一下全概率公式就得出来了。

话说,其实我觉得(其中$B_i$是$\Omega$的一个划分)

才更应该叫“全概率公式”?证法同。

例题

例三

P2473 [SCOI2008]奖励关

解答

首先发现宝物数很少,考虑状压。一个宝物吃还是不吃,取决于吃/不吃之后能有多好,所以需要倒推。

显然本题中,一个基本结果就是一串扔出的宝物序列$e$。我们设$F_{i,s}$是只考虑第$i$次到第$N$次扔出的宝物时的价值的期望(只考虑是说,$X_i$是所有这些宝物的价值和),即

后面那个事件太长,记为$A_{i,s}$。

我们知道

即“全期望公式”。

现在我们考虑选择$B$。我们定义,$B_j$是$A_{i,s}$中,第$i$个宝物确定为$j$的宝物排列构成的集合,容易发现$P(B_j|A_{i,s})=\frac 1 N$。

事实上,可以发现$A_{i+1,s’}$中的元素在开头加一个$j$就得到了$B_j$中的元素。于是有$E(X_i|B_j)=F_{i+1,s’}+W_j$。

容易发现,$s’$并不好处理,但是反过来根据$i+1,s’,j$去确定$i,s$是容易的($s=s’\cup\{j\}$),那么枚举$i,s,j$DP即可。

花了这么长一段证了一个极其直观的DP

方差

提一句吧。

连续情形下的随机变量

对于随机变量$X$,如果存在一个非负可积的函数$f(x)$使得

则称$X$是一个连续型随机变量,$P(X\le x)$是它的分布函数,也是上文的概率测度,$p(x)$是$X$的密度函数

显然有

然而,$X=x$并非不可能事件($\phi$),也就是常说的:

  • 概率为0不一定不可能($\phi$);

  • 概率为1不一定必然(整个$\Omega$)。

分布函数和密度函数当然要满足下面的性质:

  • $p(x)\ge 0$。(非负性)

  • $\int_{-\infty}^\infty p(t)\text{d}t=1$。(规范性)

  • 因为$p(t)$可积,所以可加性自然满足。

然后我们重新定义期望。我们的策略是,用离散型随机变量的期望“逼近”它。我们把图像切成宽度均为$\Delta x$的一小条一小条,$[x,x+\Delta x)$的概率近似看成$p(x)\Delta x$,此时随机变量的值近似看成$x$。其实就是积分:

你也可以理解为和离散情况更像的一种形式

同样有线性性,独立情况下的可乘性和如下的连续版的整数概率公式:

例题

例四

从$[l,r]\ (l,r>0)$中随机取一个实数,取$N$次,求这取出的$N$个实数的最大值的期望。

解答

设$X_n$是取了$n$次后的最大值。同时,设$X_0=l$。

显然:

又显然有

所以

运用连续情况下的整数概率公式,得到答案为

例五

P3343 [ZJOI2015]地震后的幻想乡

解答

_rqy 的题解写得太清晰了以至于我完全没有可以补充的地方……所以直接看罢。

例六

#372. 【UR #17】滑稽树前做游戏

解答

这里