概率论

为了延续学位而重温的概率论，原本只是随意每周花几小时，但昨日偶然刷到日本大逃杀电影里的概率论，突然感觉莫非概率论也别有风味。
其实做事情不以结果为导向的确如此。

概率空间的定义

概率计算的几种类型

首先记住计算概率的最基础也是最终极方法就是计算概率相等的总outcome数量和事件所包含的outcome数量，也就是通过排列组合进行求解。

概率的性质

Pr(A \cap B) \ge Pr(A)+Pr(B)-1

建立在同一概率空间上的事件之间的两种关系：
– Disjoint 不相交:是指同一个概率空间的两个事件不能同时发生。从集合论的角度看，意识是两个事件的集合是空集，也即是定义为：A \cap B = \empty
数学特征：Pr[A\cup B]=Pr[A]+Pr[B]
– Independent 独立：是指一个事件发生与否影响另一个事件发生的概率，也即是定义为Pr[A\cap B]=Pr[A] \cdot Pr[B] 或者：Pr[A|B] = Pr[A]

• 二者之间的关系：不相交的事情通常是不独立的，因为一个发生了另一个就一定不会发生
  证明：如果既独立又相交，则：Pr[A\cap B]=Pr[A] \cdot Pr[B]=0，那么只有其中事件的概率为0才成立

如何从逻辑上分辨?
– 随机试验可以是投掷硬币一次，可以是投掷硬币多次，也可以是同时投掷两枚硬币一次
– 同一个随机试验中，两个事件可以是独立的：例如投掷一个公平骰子两次，A是第一次投出偶数，B是第二次投出奇数，A和B是互相独立的；但是当B和第一次投出的相关时，比如第一次投出奇数，或者两次都投出3的倍数，那么A和B就不独立。但是A和B在两种情况下都是有交集的。
– 没有交集的两个事件是，A是投出两个奇数，B是投出两个偶数。

独立性的特征
* 对称性
* 是否独立可以用定义的Pr[A\cap B]=Pr[A] \cdot Pr[B] 来证明的，也就是若等式不成立就是不独立
* 容斥原理：Pr[A\cup B]=Pr[A] + Pr[B] – Pr[A\cap B] = Pr[A] + Pr[B] – Pr[A] \cdot Pr[B]

两两独立和互相独立的区别

1）伯努利实验

伯努利实验是独立同分布的，也就是事件的结果只有两个，一个概率p另一个概率1-p.

1. 小球和盒子类型：k个小球扔到n个盒子里
   则每个小球被扔到任意一个盒子里的概率为\frac{1}{n}
   一个盒子始终为空的可能性是(\frac{n-1}{n})^k

2) 条件概率

Pr[A|B]=\frac{Pr[A \cap B]}{Pr[B]}
1. 贝叶斯定理

Pr[D|P] = Pr[P|D] \cdot Pr[D]/Pr[P]
全概率公式：Pr[P] = Pr[P|D] \cdot Pr[D] + Pr[P|\overline{D}] \cdot Pr[\overline{D}]
病|阳 = 阳|病 * 病 / (病了阳病+不病还阳不病）病|阳 = 阳|病 * 病 / (病了阳病+不病还阳不病）

链式法则: 要知道一组事情同时发生的概率，分为两种情况。一种是当事件之间互相独立的时候，可以直接点乘所有事件的概率；当事件之间并不互相独立的时候，就等于前一件事发生的概率与前一件事发生后下一件事发生概率的乘积。一般来说第二种情况下，事件之间是互相包含的关系而且有发生的先后次序差别
已知一个人患病的概率和如果患病检测为阳性的概率，那么一个人患病且检测为阳性的概率就是患病概 ✖ 患病且检测为阳性的概率。

3）期望

引入”indicators”指示随机变量以简化复杂期望值的计算
伯努利试验的期望值是np;同样适用于k个小球投掷给n个盒子，每个盒子里小球数量的期望值，是\frac{k}{n}

趣题

1. A是一个有n个字母的集合，随意取两个排列，他们互文的概率是？
总排列(permutations)的数量是n!, 接下来有两种思路：
1）对于任何一个排列来说，有且只有另一个和它互文，所以选中这个互文的概率是(\frac{1}{n!-1})
2）总不含序配对(inordered pairs)的数量是n!(n!-1)/2，对于每一个排列，都有另一个和它互文，所以一共有n!/2对

类似题：
– 抽牌对：每人分别从一副牌中抽一张，A比B大的概率是？
Ordered pairs共有$5252$对，而其中数字相等的对数有134*4对，因此相等的概率为1/13,所以A比B大的概率是6/13

2. 一个8位数二进制111开头或者结尾的概率
概率空间是\Omega,是所有长度为8的二进制序列的集合，序列总数|\Omega|=2^8=256, 每个序列等可能出现。
事件A:前三位为1，事件B:后三位为1，所以：
Pr(A \cup B)=Pr(A)+Pr(B)-Pr(A \cap B)=\frac{2^5+2^5-2^2}{2^8}

3. 大理石交换游戏 – 条件概率的链式公式
前一个人成功的前提下后一个人成功的概率总是相通的

4. 帽子和陌生人 – 指示变量经典模型
* 期望：n个帽子，每个帽子物归原主的概率是1/n,所以平均而言只有1顶帽子回到它原来的主人手上。的确这里E_k= 客人k得到他的帽子和其他事件并不独立，但是不影响期望的线性是成立的。
* 概率：一共有n!种帽子和人的排列方式，这其中只有1种是正确的，所以事情达成的概率是1/n!

类似题：直到…为止
投掷硬币直到得到硬币正面为止。
E[X_i]=(1/2)^{(i-1)} \cdot (1/2)
所以E[X]=\sum_{i \in n}^{10}{(1/2)^n}

类似题：Draw balls
一共N个球，其中r个红色球，余下都是黄色球，抽取b个，则抽中黄球数量的均值是？
抽中黄球的概率是(N-r)/N,所以均值是b(N-r)/N

5. 圆桌问题 – 指示变量变体
n个人一起掷骰子，得到三个连续数字的概率是：
X_k是第k人是中间人，则k必须是整数[2…5],因此概率为2/3; 而k-1个人必须为i-1因此概率为1/6, 或者反之为i+1;
因此Pr(X_k) = 2/3 \cdot 1/6 \cdot 1/6 \cdot 2 = 1/27
因此E[X]=n\cdot (1/27)=n/27

一些小妙招：
* 要使两个数之和c+d能被3整除，它们的余数之和必须是3的倍数
符合条件的余数对只有三种情况：(0,0),(1,2),(2,1)