离散概率()-其他
离散概率()
离散概率的公理与推论
概率空间
概率空间由三个要素组成：样本空间\(\Omega\)，可容许事件\(\mathcal{F}\)，概率函数\(\Pr\)。样本空间是所有可能结果的集合，其中的每个元素称为一个“基本事件”；\(\mathcal{F}\)是\(\Omega\)的子集，它是由基本事件构成的集合；\(\Pr\)是\(\mathcal{F} \to \R\)的函数，对应一个可容许事件发生的概率。比如“掷一次骰子”就构成了一个概率空间\((\Omega,\mathcal{F},\Pr)\)，其中\(\Omega\)中有6个样本\(\{1,2,3,4,5,6\}\)。一个可容许事件是\(\Omega\)的子集，比如“掷出偶数”对应的\(\mathcal{F}=\{2,4,6\}\)，对应的\(\Pr(\mathcal{F})=1/2\)。
事件是集合，因此我们用集合的符号来表示来表示事件：\(E_1 \cup E_2\)表示\(E_1\)与\(E_2\)至少一个发生，\(E_1 \cap E_2\)表示\(E_1\)和\(E_2\)同时发生。\(\overline{E}\)表示\(\Omega \setminus E\)，表示\(E\)不发生。
事件是集合，因此我们用集合的符号来表示来表示事件：\(E_1 \cup E_2\)表示\(E_1\)与\(E_2\)至少一个发生，\(E_1 \cap E_2\)表示\(E_1\)和\(E_2\)同时发生。\(\overline{E}\)表示\(\Omega \setminus E\)，表示\(E\)不发生。
我们规定概率函数的取值必须在\([0,1]\)之间，并且满足\(\Pr(\Omega)=1\)。由于我们讨论离散概率，我们有公理：对于两两不相交的有限或可数无穷序列\(E_1,E_2,\cdots\)，必须满足\(\Pr\left(\bigcup\limits_{i \geq 1}E_i\right)=\sum\limits_{i \geq 1}\Pr(E_i)\)——即任何一个可容许事件的概率都可以由组成它的基本事件的概率之和唯一确定。
容斥原理
概率事件是集合，而概率函数是以集合为自变量的函数，因此概率函数也应当满足容斥原理。我们从公理出发就可以给出证明：\(\Pr(E_1 \cup E_2)=\Pr(E_1)+\Pr(E_2)-\Pr(E_1 \cap E_2)\)……？？？……
Union Bound
从二元情形的容斥原理\(\Pr(E_1 \cup E_2)=\Pr(E_1)+\Pr(E_2)-\Pr(E_1 \cap E_2)\)中可以看出，如果我们丢掉\(-\Pr(E_1 \cap E_2)\)这一项，就会得到\(\Pr(E_1 \cup E_2)\leq\Pr(E_1)+\Pr(E_2)\)，推广到\(n\)元都\(\Pr\left(\bigcup\limits_{i \geq 1}E_i\right)\leq \sum\limits_{i \geq 1}\Pr(E_i)\)，这个结论称为“Union Bound”。
独立事件
定义两个事件是独立的当且仅当\(\Pr(E \cap F)=\Pr(E) \cdot \Pr(F)\)。对于更多的事件也这样定义独立——这些事件同时发生的概率等于它们单独发生的概率之积。
条件概率
定义\(\Pr(E|F)=\dfrac{\Pr(E \cap F)}{\Pr(F)}\)，称为\(F\)发生的条件下\(E\)发生的概率。这是符合我们的直观的，当我们讨论“\(F\)发生的条件下”时，我们把讨论区域限制在了\(F\)内，因此需要做“归一化”，所以我们除掉\(F\)发生的概率。并且两个互相独立的事件其中一个在另一个的条件下发生的概率还应当是它本身，代入\(\Pr(E \cap F)=\Pr(E) \cdot \Pr(F)\)恰好得到\(\Pr(E|F)=\Pr(E)\)。
我们可以把条件概率的等式变形为\(\Pr(E\cap F) = \Pr(E|F) \cdot \Pr(F)\)。那么根据条件概率的定义，我们能够得到一个求解概率的链式法则：\(\Pr(E_1 \cap \cdots \cap E_n)\)\(=\Pr(E_n|E_1 \cap \cdots \cap E_{n-1}) \cdot \Pr(E_1 \cap \cdots \cap E_{n-1})\)\(=\cdots\)\(=\Pr(E_1)\cdot \Pr(E_2 | E_1)\cdot \Pr(E_3|E_1 \cap E_2) \cdots \Pr(E_n|E_1 \cap \cdots \cap E_{n-1})\)。
全概率定理
设样本空间\(\Omega\)可以划分为互不相交的事件\(E_1, \cdots ,E_n\)。那么
\(\forall B, \Pr(B)=\sum\limits_{i=1}^{n}\Pr(B \cap E_i)=\sum\limits_{i=1}^{n}\Pr(B|E_i)\cdot \Pr(E_i)\)。
其中最后一步用到了条件概率的定义。
贝叶斯定理
设样本空间\(\Omega\)可以划分为互不相交的事件\(E_1, \cdots ,E_n\)。那么根据条件概率的定义和全概率定理：
\(\Pr(E_j|B)=\dfrac{\Pr(E_j \cap B)}{\Pr(B)}=\dfrac{\Pr(E_j \cap B)}{\sum\limits_{i=1}^{n}\Pr(B|E_i)\cdot \Pr(E_i)}\)
随机变量
随机变量是从样本空间到实数的映射。比如“投两个骰子”总共产生了36个可能的事件，而“点数之和”这一随机变量却只能有2到12这11个取值。形式化地，我们用\(X=a\)来表示随机变量\(X\)的取值为\(a\)这一事件，它其实表示的是集合\(\{s\in \Omega|X(s)=a\}\)。
根据基本事件的定义，\(\Pr(X=a)=\sum\limits_{X(s)=a,s\in\Omega}\Pr(s)\)。
同理我们可以定义随机变量的独立性：\(X\)与\(Y\)独立当且仅当对于任何的\(a,b\)始终成立\(\Pr((X=a)\cap (Y=b))=\Pr(X=a)\cdot\Pr(Y=b)\)。
期望是随机变量的一个基本特征：随机变量的期望定义为其概率的加权平均值。\(E[X]=\sum\limits_{i}i\Pr(X=i)\)。
期望的线性性
一个最重要的定理称为“期望的线性性”：对于有限个随机变量\(X_1,\cdots,X_n\)始终满足\(E\left[\sum\limits_{i=1}^{n}X_i\right]=\sum\limits_{i=1}^{n}E[X_i]\)。证明就是根据定义：\(E[X+Y]=\sum\limits_{i}\sum\limits_{j}(i+j)\Pr((X=i)\cap(Y=j))\)，提出固定的变量得到\(\sum\limits_{i}i\sum\limits_{j}\Pr((X=i)\cap(Y=j))+\sum\limits_{j}j\sum\limits_{i}\Pr((X=i)\cap(Y=j))\)，而后面的那个和式恰好就是全概率公式，因此直接可以化简得到\(\sum\limits_{i}i\Pr(X=i)+\sum\limits_{j}j\Pr(Y=j)\)，这就是\(E[X]+E[Y]\)。这就证明了期望的线性性。重要的是，期望的线性性没有对随机变量提出任何的要求，即使两个随机变量不是“独立”的，它们的期望也始终符合“线性性”这一特征。这对我们计算期望提供极大的方便。当然，为了完善“线性性”这一概念，我们还应当证明\(E[cX]=cE[X]\)：这是容易的，\(E[cX]=\sum\limits_{i}ci\Pr(X=i)=cE[X]\)。
Jensen不等式
对于非线性的函数，期望就不再满足这样的性质了：在\(\{1,99\}\)里选一个数，这构成随机变量\(X\)。由这个随机变量的大小为边长的正方形面积也对应着一个“随机变量”，方便起见我们记这个变量为\(X^2\)。根据定义，我们计算出\(E[X^2]=\sum\limits_{i=1}^{99}i^2 \Pr(X=i)=\dfrac{\sum\limits_{i=1}^{99}i^2}{99}=\dfrac{9950}{3}\)。而\((E[X])^2=\left(\sum\limits_{i=1}^{99}\dfrac{i}{99}\right)^2=2500\)，因此\(E[X^2] \neq (E[X])^2\)。
我们可以更精确地描述这二者的关系：我们构造一个\(E[(X-E[X])^2]\)，由于它只对非负的随机变量求期望，因此它的值一定非负。而把它展开\(E[(X-E[X])^2]=E[X^2+(E[X])^2-2XE[X]]\)，根据期望的线性性，它等于\(E[X^2]+E[(E[X])^2]-E[2XE[X]]\)。\(E[X]\)本身也是一个随机变量，只不过它是一个常数，因此它的期望就是这个常数，也可以作为常数被提出外面。于是得到\(E[X^2]+(E[X])^2-E[X]E[2X] \geq 0\)。化简得结论：\(E[X^2] \geq (E[X])^2\)。
这个结论只是函数\(X^2\)作为一个特例存在。对于任何下凸函数\(f\)这个不等式都是成立的，这就是概率形式的Jensen不等式：\(E[f(X)] \geq f(E[X])\)。证明：凸函数满足\(f(x)\geq f(\mu)+f'(\mu)(x-\mu)\)，那么取\(\mu=E[X]\)，并在不等式两边同时取期望（等式两边都是随机变量）就得到\(E[f(X)] \geq f(E[X])+f'(E[X])(E[X]-E[E[X]])=f(E[X])\)。
二项分布
如果事件表示某件事的成功与否，成功概率为\(p\)，变量\(X=1\)，否则失败，变量\(X=0\)，那么这个变量\(X\)就称为伯努利随机变量。独立重复\(n\)次，记成功的次数为\(Y\)，那么称\(Y\)为二项随机变量，满足二项分布：
\(\Pr(Y=i)=\dbinom{n}{i}p^i(1-p)^{n-i}\)
由此可以求出二项随机变量的期望：
\(\begin{aligned}E[Y]&=\sum\limits_{i=0}^{n}i\dbinom{n}{i}p^i(1-p)^{n-i}\\&=\sum\limits_{i=1}^{n}\dfrac{n!}{(i-1)!(n-i)!} \cdot p^i(1-p)^{n-i}\\&=np\sum\limits_{i=1}^{n}\dfrac{(n-1)!}{(i-1)!(n-i)!}p^{i-1}(1-p)^{}n-i\\&=np(p+1-p)^{n-1}\\&=np \end{aligned}\)
事实上还有更简单的证明方法，二项随机变量\(Y\)可以被拆解成\(n\)个基本事件的随机变量\(X_i\)，其中\(X_i\)表示第\(i\)次实验是否成功。于是就有关系\(Y=\sum\limits_{i=1}^{n}X_i\)。两边同时取期望，\(E[Y]=E\left[\sum\limits_{i=1}^{n}X_i\right]\)，根据期望的线性性，\(=\sum\limits_{i=1}^{n}E[X_i]=\sum\limits_{i=1}^{n}p=np\)。
几何分布
二项分布可以理解为丢\(n\)次硬币统计正面朝上的次数，那么几何分布就可以相应地理解为不停丢直到第一次出现正面的次数。因此\(\Pr(X=n)=(1-p)^{n-1}p\)。
如何算几何分布的期望？从直觉上看，丢一个\(1/10\)概率出正面的硬币大约需要10次，因此我们可以期望\(E[X]=\dfrac{1}{p}\)。它的计算就是暴力求解等差乘等比数列的和。
条件期望
基于事件我们定义了条件期望，那么依赖于这样的事件的期望就被称为条件期望。所以自然地定义\(E[Y|Z=z]=\sum\limits_{y}y\Pr(Y=y|Z=z)\)。
离散概率的公理与推论
概率空间
概率空间由三个要素组成：样本空间\(\Omega\)，可容许事件\(\mathcal{F}\)，概率函数\(\Pr\)。样本空间是所有可能结果的集合，其中的每个元素称为一个“基本事件”；\(\mathcal{F}\)是\(\Omega\)的子集，它是由基本事件构成的集合；\(\Pr\)是\(\mathcal{F} \to \R\)的函数，对应一个可容许事件发生的概率。比如“掷一次骰子”就构成了一个概率空间\((\Omega,\mathcal{F},\Pr)\)，其中\(\Omega\)中有6个样本\(\{1,2,3,4,5,6\}\)。一个可容许事件是\(\Omega\)的子集，比如“掷出偶数”对应的\(\mathcal{F}=\{2,4,6\}\)，对应的\(\Pr(\mathcal{F})=1/2\)。
事件是集合，因此我们用集合的符号来表示来表示事件：\(E_1 \cup E_2\)表示\(E_1\)与\(E_2\)至少一个发生，\(E_1 \cap E_2\)表示\(E_1\)和\(E_2\)同时发生。\(\overline{E}\)表示\(\Omega \setminus E\)，表示\(E\)不发生。
事件是集合，因此我们用集合的符号来表示来表示事件：\(E_1 \cup E_2\)表示\(E_1\)与\(E_2\)至少一个发生，\(E_1 \cap E_2\)表示\(E_1\)和\(E_2\)同时发生。\(\overline{E}\)表示\(\Omega \setminus E\)，表示\(E\)不发生。
我们规定概率函数的取值必须在\([0,1]\)之间，并且满足\(\Pr(\Omega)=1\)。由于我们讨论离散概率，我们有公理：对于两两不相交的有限或可数无穷序列\(E_1,E_2,\cdots\)，必须满足\(\Pr\left(\bigcup\limits_{i \geq 1}E_i\right)=\sum\limits_{i \geq 1}\Pr(E_i)\)——即任何一个可容许事件的概率都可以由组成它的基本事件的概率之和唯一确定。
容斥原理
概率事件是集合，而概率函数是以集合为自变量的函数，因此概率函数也应当满足容斥原理。我们从公理出发就可以给出证明：\(\Pr(E_1 \cup E_2)=\Pr(E_1)+\Pr(E_2)-\Pr(E_1 \cap E_2)\)……？？？……
Union Bound
从二元情形的容斥原理\(\Pr(E_1 \cup E_2)=\Pr(E_1)+\Pr(E_2)-\Pr(E_1 \cap E_2)\)中可以看出，如果我们丢掉\(-\Pr(E_1 \cap E_2)\)这一项，就会得到\(\Pr(E_1 \cup E_2)\leq\Pr(E_1)+\Pr(E_2)\)，推广到\(n\)元都\(\Pr\left(\bigcup\limits_{i \geq 1}E_i\right)\leq \sum\limits_{i \geq 1}\Pr(E_i)\)，这个结论称为“Union Bound”。
独立事件
定义两个事件是独立的当且仅当\(\Pr(E \cap F)=\Pr(E) \cdot \Pr(F)\)。对于更多的事件也这样定义独立——这些事件同时发生的概率等于它们单独发生的概率之积。
条件概率
定义\(\Pr(E|F)=\dfrac{\Pr(E \cap F)}{\Pr(F)}\)，称为\(F\)发生的条件下\(E\)发生的概率。这是符合我们的直观的，当我们讨论“\(F\)发生的条件下”时，我们把讨论区域限制在了\(F\)内，因此需要做“归一化”，所以我们除掉\(F\)发生的概率。并且两个互相独立的事件其中一个在另一个的条件下发生的概率还应当是它本身，代入\(\Pr(E \cap F)=\Pr(E) \cdot \Pr(F)\)恰好得到\(\Pr(E|F)=\Pr(E)\)。
我们可以把条件概率的等式变形为\(\Pr(E\cap F) = \Pr(E|F) \cdot \Pr(F)\)。那么根据条件概率的定义，我们能够得到一个求解概率的链式法则：\(\Pr(E_1 \cap \cdots \cap E_n)\)\(=\Pr(E_n|E_1 \cap \cdots \cap E_{n-1}) \cdot \Pr(E_1 \cap \cdots \cap E_{n-1})\)\(=\cdots\)\(=\Pr(E_1)\cdot \Pr(E_2 | E_1)\cdot \Pr(E_3|E_1 \cap E_2) \cdots \Pr(E_n|E_1 \cap \cdots \cap E_{n-1})\)。
全概率定理
设样本空间\(\Omega\)可以划分为互不相交的事件\(E_1, \cdots ,E_n\)。那么
\(\forall B, \Pr(B)=\sum\limits_{i=1}^{n}\Pr(B \cap E_i)=\sum\limits_{i=1}^{n}\Pr(B|E_i)\cdot \Pr(E_i)\)。
其中最后一步用到了条件概率的定义。
贝叶斯定理
设样本空间\(\Omega\)可以划分为互不相交的事件\(E_1, \cdots ,E_n\)。那么根据条件概率的定义和全概率定理：
\(\Pr(E_j|B)=\dfrac{\Pr(E_j \cap B)}{\Pr(B)}=\dfrac{\Pr(E_j \cap B)}{\sum\limits_{i=1}^{n}\Pr(B|E_i)\cdot \Pr(E_i)}\)
随机变量
随机变量是从样本空间到实数的映射。比如“投两个骰子”总共产生了36个可能的事件，而“点数之和”这一随机变量却只能有2到12这11个取值。形式化地，我们用\(X=a\)来表示随机变量\(X\)的取值为\(a\)这一事件，它其实表示的是集合\(\{s\in \Omega|X(s)=a\}\)。
根据基本事件的定义，\(\Pr(X=a)=\sum\limits_{X(s)=a,s\in\Omega}\Pr(s)\)。
同理我们可以定义随机变量的独立性：\(X\)与\(Y\)独立当且仅当对于任何的\(a,b\)始终成立\(\Pr((X=a)\cap (Y=b))=\Pr(X=a)\cdot\Pr(Y=b)\)。
期望是随机变量的一个基本特征：随机变量的期望定义为其概率的加权平均值。\(E[X]=\sum\limits_{i}i\Pr(X=i)\)。
期望的线性性
一个最重要的定理称为“期望的线性性”：对于有限个随机变量\(X_1,\cdots,X_n\)始终满足\(E\left[\sum\limits_{i=1}^{n}X_i\right]=\sum\limits_{i=1}^{n}E[X_i]\)。证明就是根据定义：\(E[X+Y]=\sum\limits_{i}\sum\limits_{j}(i+j)\Pr((X=i)\cap(Y=j))\)，提出固定的变量得到\(\sum\limits_{i}i\sum\limits_{j}\Pr((X=i)\cap(Y=j))+\sum\limits_{j}j\sum\limits_{i}\Pr((X=i)\cap(Y=j))\)，而后面的那个和式恰好就是全概率公式，因此直接可以化简得到\(\sum\limits_{i}i\Pr(X=i)+\sum\limits_{j}j\Pr(Y=j)\)，这就是\(E[X]+E[Y]\)。这就证明了期望的线性性。重要的是，期望的线性性没有对随机变量提出任何的要求，即使两个随机变量不是“独立”的，它们的期望也始终符合“线性性”这一特征。这对我们计算期望提供极大的方便。当然，为了完善“线性性”这一概念，我们还应当证明\(E[cX]=cE[X]\)：这是容易的，\(E[cX]=\sum\limits_{i}ci\Pr(X=i)=cE[X]\)。
Jensen不等式
对于非线性的函数，期望就不再满足这样的性质了：在\(\{1,99\}\)里选一个数，这构成随机变量\(X\)。由这个随机变量的大小为边长的正方形面积也对应着一个“随机变量”，方便起见我们记这个变量为\(X^2\)。根据定义，我们计算出\(E[X^2]=\sum\limits_{i=1}^{99}i^2 \Pr(X=i)=\dfrac{\sum\limits_{i=1}^{99}i^2}{99}=\dfrac{9950}{3}\)。而\((E[X])^2=\left(\sum\limits_{i=1}^{99}\dfrac{i}{99}\right)^2=2500\)，因此\(E[X^2] \neq (E[X])^2\)。
我们可以更精确地描述这二者的关系：我们构造一个\(E[(X-E[X])^2]\)，由于它只对非负的随机变量求期望，因此它的值一定非负。而把它展开\(E[(X-E[X])^2]=E[X^2+(E[X])^2-2XE[X]]\)，根据期望的线性性，它等于\(E[X^2]+E[(E[X])^2]-E[2XE[X]]\)。\(E[X]\)本身也是一个随机变量，只不过它是一个常数，因此它的期望就是这个常数，也可以作为常数被提出外面。于是得到\(E[X^2]+(E[X])^2-E[X]E[2X] \geq 0\)。化简得结论：\(E[X^2] \geq (E[X])^2\)。
这个结论只是函数\(X^2\)作为一个特例存在。对于任何下凸函数\(f\)这个不等式都是成立的，这就是概率形式的Jensen不等式：\(E[f(X)] \geq f(E[X])\)。证明：凸函数满足\(f(x)\geq f(\mu)+f'(\mu)(x-\mu)\)，那么取\(\mu=E[X]\)，并在不等式两边同时取期望（等式两边都是随机变量）就得到\(E[f(X)] \geq f(E[X])+f'(E[X])(E[X]-E[E[X]])=f(E[X])\)。
二项分布
如果事件表示某件事的成功与否，成功概率为\(p\)，变量\(X=1\)，否则失败，变量\(X=0\)，那么这个变量\(X\)就称为伯努利随机变量。独立重复\(n\)次，记成功的次数为\(Y\)，那么称\(Y\)为二项随机变量，满足二项分布：
\(\Pr(Y=i)=\dbinom{n}{i}p^i(1-p)^{n-i}\)
由此可以求出二项随机变量的期望：
\(\begin{aligned}E[Y]&=\sum\limits_{i=0}^{n}i\dbinom{n}{i}p^i(1-p)^{n-i}\\&=\sum\limits_{i=1}^{n}\dfrac{n!}{(i-1)!(n-i)!} \cdot p^i(1-p)^{n-i}\\&=np\sum\limits_{i=1}^{n}\dfrac{(n-1)!}{(i-1)!(n-i)!}p^{i-1}(1-p)^{}n-i\\&=np(p+1-p)^{n-1}\\&=np \end{aligned}\)
事实上还有更简单的证明方法，二项随机变量\(Y\)可以被拆解成\(n\)个基本事件的随机变量\(X_i\)，其中\(X_i\)表示第\(i\)次实验是否成功。于是就有关系\(Y=\sum\limits_{i=1}^{n}X_i\)。两边同时取期望，\(E[Y]=E\left[\sum\limits_{i=1}^{n}X_i\right]\)，根据期望的线性性，\(=\sum\limits_{i=1}^{n}E[X_i]=\sum\limits_{i=1}^{n}p=np\)。
几何分布
二项分布可以理解为丢\(n\)次硬币统计正面朝上的次数，那么几何分布就可以相应地理解为不停丢直到第一次出现正面的次数。因此\(\Pr(X=n)=(1-p)^{n-1}p\)。
如何算几何分布的期望？从直觉上看，丢一个\(1/10\)概率出正面的硬币大约需要10次，因此我们可以期望\(E[X]=\dfrac{1}{p}\)。它的计算就是暴力求解等差乘等比数列的和。
条件期望
基于事件我们定义了条件期望，那么依赖于这样的事件的期望就被称为条件期望。所以自然地定义\(E[Y|Z=z]=\sum\limits_{y}y\Pr(Y=y|Z=z)\)。