1. 随机试验

定义：

不能预先确知结果
试验之前可以预测所有可能结果或范围
可以在相同条件下重复实验

样本空间：随机试验所有可能结果组成的集合 .

分类：离散样本空间、无穷样本空间

样本空间的任意一个子集称之为事件 .

事件发生：在一次试验中，事件的一个样本点发生

必然事件：样本空间
不可能事件：空集

事件 (A,B) 的关系与运算：

包含：和集合里的一样
相等：和集合里的一样
互斥：(Acap B=varnothing)
补：和集合里的补集一样，记作 (overline A)
和：和集合里的并集一样，记作 (A+B)
差：和集合里的差集一样，记作 (A-B)
积：和集合里的交集一样，记作 (AB)

运算律：

交换律：(A+B=B+A)，(AB=BA) .
结合律：((A+B)+C=A+(B+C))，((AB)C=A(BC))
分配律：((A+B)C=AC+BC)，((AB)+C=(A+C)(B+C)) .
对偶律：(overline{A+B}=overline Acdotoverline B)，(overline{AB}=overline A+overline B) .

2. 概率

1. 平凡

定义：为样本空间 (S) 的每一个事件定义一个实数，这个实数称为概率 . 事件 (A) 的概率记作 (P(A)) .

有：

(0le P(A)le 1) .
(P(S)=1) .
若 (AB=varnothing)，则 (P(A+B)=P(A)+P(B)) .

性质：

(P(varnothing)=0) .
若 (A_1A_2cdots A_n=varnothing)，则 (P(sum_{i=1}^n A_i)=sum_{i=1}^n P(A_i)) .
若 (Asubset B)，则 (P(B-A)=P(B)-P(A)) .
一般的，(P(B-A)=P(B)-P(AB)) .
(P(A+B)=P(A)+P(B)-P(AB)) .

2. 条件概率

定义已知事件 (B) 发生时事件 (A) 发生的概率为 (P(A|B)=dfrac{P(AB)}{P(B)})

移项即得乘法法则：(P(AB)=P(A|B)P(B)) .

性质（其实和普通的差不多）：

(P(varnothing | A)=0)
若 (A_1A_2cdots A_n=varnothing)，则 (P(sum_{i=1}^n A_i | B)=sum_{i=1}^n P(A_i | B)) .
(P(overline B | A)=1-P(B|A))
(P(A+B | C)=P(A | C)+P(B | C)-P(AB | C)) .

贝叶斯公式：

若 (B_1,B_2,cdots,B_n) 是样本空间的一个划分，则有

[P(B_i|A)=dfrac{P(A|B_i)P(B_i)}{sumlimits_{i=0}^n P(A|B_j)P(B_j)} ]

Proof：

[egin{aligned}dfrac{P(A|B_i)P(B_i)}{sumlimits_{i=0}^n P(A|B_j)P(B_j)}&=dfrac{P(AB_i)}{sumlimits_{i=0}^n P(AB_j)}\&=dfrac{P(AB_i)}{P(A)Pleft(sumlimits_{i=0}^n B_j ight)}\&=dfrac{P(AB_i)}{P(A)}=P(B_i|A)end{aligned} ]

[ ag*{□} ]

如果两个事件满足 (P(AB)=P(A)P(B))（即 (P(B|A)=P(B))），那么称他们独立 .

3. 期望

期望就是平均事件发生的情况，定义：

[E(f(X))=sum P(X=x)f(X) ]

例如，投掷一个骰子期望投到 (3.5) .

期望有如下性质：

[重要] (E(c_1X_1+c_2X_2+cdots+c_nX_n)=c_1E(X_1)+c_2E(x_2)+cdots+c_nE(x_n))（线性性）
如果 (X_1,X_2) 独立，则 (E(X_1X_2)=E(X_1)E(X_2))

习题

1

(n imes m) 的矩形

每次随机刷掉一个矩形

问 (k) 次之后期望刷掉了多少个格子

(n,mle 1000,kle 100)

期望染的格子数 = 每个格子染的状态的期望之和 = 每个格子被染色的期望 .

2

检验矩阵乘法式 (AB=C) 是否成立

(A,B,C) 均为 (n imes n) 矩阵，(nle 1000) .

随机弄几个 (n imes 1) 矩阵 (D)，然后检验是否有

[A(BD)=CD ]

3

给定平面上 (n) 个点

找到一个最小的圆覆盖住他们

暴力是 (O(n^3)) 的，随机打乱点的顺序后是期望 (O(n)) 的 [表情]（分析每个 if 的进入条件）

钟神的伪代码：

point p[2333];

circle o;
random_shuffle(p+1,p+n+1);
for (int i=1;i<=n;i++)
	if (p[i] not in o)//3/i
	{
		o = circle(p[i],0);//p[i]为圆心 0为半径 
		for (int j=1;j<i;j++)
			if (p[j] not in o)
			{
				o = circle(p[i],p[j]);//p[i] p[j]距离为直径 
				for (int k=1;k<j;k++)
					if (p[k] not in o)
						o=circle(p[i],p[j],p[k]);
			}
	}

4

(n) 次操作，第 (i) 次操作成功的概率为 (p_i) .

成功记为 (1) 否则记为 (0) .

连续 (x) 个 (1) 会贡献 (x^3) 的分数，求期望分数