MIT 6.042J & 18.062J：计算机科学中的数学

证明 Introduction and Proofs

广义上的证明 Proof：确定事实的方法

手段：

• 实验和观察
• 抽样找反例
• 法官-陪审团
• 上帝的话
• 老板
• 内心的信念

数学上的证明是通过一系列公理的逻辑推理来验证一个命题

定义：命题 Proposition 是要么为真要么为假的陈述

定义：谓词 Predicate 是一个真值依赖于变量值的命题

定义：如果 $p$ 为假或 $q$ 为真，则蕴含 implication $p \implies q$ 为真

所以猪会飞 $\implies$ 我是国王是正确的

定义：公理 axiom 是一个假定为真的命题

例如：如果 $a = b$ 且 $b = c$，则 $a = c$

欧几里得几何中的：给定一条直线 $l$ 和不在直线 $l$ 上的点 $p$，通过点 $p$ 与直线 $l$ 的平行线有且只有一条

但在球面几何中该公理是错误的

公理必须是：

• 一致的 consistent ：一个命题不能同时为真或为假
• 完整的 complete ：所有命题必须为真或为假

很可惜，根据哥德尔不完备定理，不存在一组一致且完整的公理，即永远无法证明出一些命题的真假

反证法 数学归纳法 Induction

反证法 Proof by contradiction ：为了证明 $p$ 为真，通过假设 $p$ 为假推导出错误或矛盾

例如：证明 $\sqrt2$ 是无理数

假设 $\sqrt2$ 是有理数，即 $\sqrt2 = \frac ab$，分数为最简形式

$$\begin{aligned} & \implies 2b^2 = a^2 \\ & \implies \text{a 为偶数} (2|a) \\ & \implies 4|a^2 \\ & \implies 4|2b^2 \\ & \implies 2|b^2 \\ & \implies \text{b 是偶数} \\ & \implies \frac ab \text{不是最简形式} \\ & \implies \text{矛盾} \\ & \implies \sqrt 2 \text{是无理数} \end{aligned}$$

归纳法公理 Induction axiom ：$P(n)$ 为谓词，如果 $P(0)$ 为真且 $∀n∈N$，$P(n)\implies P(n+1)$ 为真，那么 $∀n ∈ N, P(n)$为真

类似于推倒多米诺骨牌

例：求证 $∑_{i=1}^n i = \frac{n(n+1)}{2}$

证明：通过归纳法

$P(n)$ 是命题 $∑_{i=1}^n i = \frac{n(n+1)}{2}$

基本情况 Base case ：$P(0)$ 为真

归纳步骤 inductive step ：对 $n ≥ 0$，证明 $P(n) \implies P(n+1)$ 为真
假设 $P(n)$ 为真，即

$$∑_{i=1}^n i = \frac{n(n+1)}{2}$$

需要证明

$$∑_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2}$$

因为

$$\frac{n(n+1)}{2} + n + 1 = \frac{(n+1)(n+2)}{2}$$

故得证

一般来说归纳法需要预先知道结论

错误的归纳法证明：所有的马颜色相同

证明：通过归纳法
$P(n)$ 对于所有 $n$ 匹马的集合，马的颜色相同 基本情况：$P(1)$ 正确
归纳步骤：考虑任何马的集合 $H_1,H_2,…,H_{n+1}$，$H_1,H_2,…,H_{n}$ 颜色相同，$H_2,H_3,…,H_{n+1}$ 颜色相同，则 $H_1$ 的颜色 = $H_2,H_3,…,H_{n+1}$ 的颜色 = $H_{n+1}$ 的颜色

这个例子说明归纳法不总是有效的/不能相信数学

该归纳法的错误之处在于 $P(1)$ 无法推导出 $P(2)$，“$…$”迷惑了我们

对于 $2^n × 2^n$ 的区域，用 L 型的地砖铺，可以在中间留下一个空隙

该命题用归纳法证明起来不方便，尝试加强命题的结论：

对于 $2^n × 2^n$ 的区域，用 L 型的地砖铺，可以在任何位置留下一个空隙

此命题较容易证明，因为在结论增强的同时，归纳法使用的假设也增强了

不变式 强归纳法 Strong Induction

八数码问题：交换了相邻的两个滑块，无法恢复原位

不变式 invariant ：为了证明你的系统不能变为一个特定的特殊状态，能在每次移动中，保持初始状态不变，并且不会变成那个特殊状态，与归纳法紧密相关

引理 1：横向移动不改变物品的相对顺序 relative order

证明：观察某个字母从位置 $i$ 变成了 $i - 1$ 或 $i + 1$

引理 2：纵向移动改变了两对字母的相对顺序

证明：留给读者自证某个字母从位置 $i$ 变成了 $i - 3$ 或 $i + 3$

引理 3：在一次移动中，逆序对的数量只会增加 2、减少 2 或不变

证明：如图所示横向移动：没有改变；纵向移动：改变两对字母的相对顺序

推论 1：在一次移动中，逆序对数的奇偶性不会改变

证明：显然成立增加或减少 2 不会改变奇偶性

引理 4：每个从初始状态得到的状态，逆序对的数量都是奇数

证明：略通过归纳法
$P(n)$ 为任意 n 次移动后逆序对的数量都是奇数
基本情况：$P(0)$ 成立
归纳步骤：每次移动不改变逆序对数的奇偶性

强归纳法：$P(n)$ 为谓词，如果 $P(0)$ 为真且 $∀n ∈ N, P(0)∧P(1)∧…∧P(n) \implies P(n+1)$ 为真，那么 $∀n ∈ N, P(n)$ 为真

本质上和归纳法是一样的，只是显示表达了归纳法得出了结论

例：对 n 块积木游戏的任意策略都得到相同的分数 $S(n) = \frac{n(n-1)}{2}$

证明：通过强归纳法：

$$P(n) = \frac{n(n-1)}{2}$$

基本情况：$P(0)$ 成立
归纳步骤：$P(n+1) = k(n+1-k) + P(k) + P(n+1-k)$

状态机 最大公约数 欧几里得算法 Number Theory

定理：在两个水桶相互倒水的问题中，如果 $m|a$ 并且 $m|a$（即 $m$ 是 $a$，$b$ 的公约数），则 $m|$ 任何得到的结果

状态机：$(x,y)$
其中，$x$ 表示在 a 桶中的水量，$y$ 表示在 b 桶中的水量

状态转移：

• 倒空：
  • $(x,y)→(0,y)$
  • $(x,y)→(x,0)$
• 装满：
  • $(x,y)→(a,y)$
  • $(x,y)→(x,b)$
• 相互倒：
  • $(x,y)→(0,x+y),x+y≤b$
  • $(x,y)→(x-(b-y),b)=(x+y-b,b),x+y≥b$
  • $(x,y)→(x+y,0),x+y≤a$
  • $(x,y)→(a,y-(a-x))=(a,y-a+x),x+y≥a$

证明：通过归纳法
$P(n)$为如果$(x,y)$是在 $n$ 次转移后得到的状态，则 $m|x$ 并且 $m|y$
基本情况：$P(0)$ 成立
归纳步骤：转移得到的状态有 $0$、$a$、$b$、$x$、$y$、$x+y-a$、$x+y-b$，都能被 $m$ 整除（两个数的线性组合能被它们的公因数整除）

定义：$\gcd(a,b)$ 为 a 和 b 的最大公约数 greatest common divisor

定理：任何 $a$，$b$ 的线性组合都能得到

欧几里得算法（辗转相除法）：

存在唯一的 $q$（商）和 $r$（余数），使得 $b = qa + r, 0 ≤ r < a$

引理：$\gcd(a,b)=\gcd(\operatorname{rem}(b,a),a)$

相当于每次减去了一个线性组合，使得得到的数大于 0 且尽量最小，而每次得到的余数减小，故算法会终止

定理：$\gcd(a,b)$ 是 $a$ 和 $b$ 的最小正线性组合

同余式 欧拉定理 RSA 加密算法 Number Theory

密码学：

• 提前交换键 keys
• 加密 encryption ：$m^{\prime}=E_{keys}(m)$
• 解密 decryption ：$m=D_{keys}(m^{\prime})$

图灵密码 v1：

• 提前交换秘密质数 $k$
• 加密：$m^{\prime}=mk$
• 解密：$m=m^{\prime}/k$

基于因式分解两个大质数的乘积很困难

问题：捕捉到两个密文 $m_1^{\prime}$、$m_2^{\prime}$ 后，$\gcd(m_1^{\prime},m_2^{\prime})=k$

图灵密码 v2：

• 提前交换公共质数 $p$，秘密质数 $k$
• 加密：密码 $m ∈ {0,1,…,p-1}$，计算 $m^{\prime}=\operatorname{rem}(mk,p)$
• 解密：$m=\operatorname{rem}(m^{\prime}k^{-1},p)$

定义：如果 $n|(x-y)$，则 $x$ 和 $y$ 被 $n$ 取模同余 congruent，记作 $x ≡ y \pmod{n}$

定义：$x \mod n$ 的乘法逆元 multiplication inverse，记作 $x^{-1}∈\{0,1,…n-1\}$，使得 $x * x^{-1} ≡ 1 \pmod{n}$

已知明文攻击

定义：欧拉函数 $Φ(n)$ 表示在 $0$ 到 $n - 1$ 中，与 $n$ 互质的整数的数量

欧拉定理：如果 $n$ 和 $k$ 互质，则 $k^{Φ(n)} ≡ 1 \pmod{n}$

当且仅当 $n$ 和 $k$ 互质时，$k$ 有乘法逆元

引理：如果 $n$ 和 $k$ 互质，$ak ≡ kb \pmod{n}$，则$a ≡ b \pmod{n}$

证明：如果 $n$ 和 $k$ 互质，$k_1, k_2, …, k_r$ 是 $\{1,2,…,n-1\}$ 中的与 $n$ 互质的数（$r=Φ(n)$），那么 ${\operatorname{rem}(kk_1, n),…,\operatorname{rem}(kk_r, n)} = \{k_1,…, k_r\}$

分为两步：

1. 证明前者有 $r$ 个余数
2. 证明前者是后者的子集

故：

$$\begin{aligned} k_1k_2…k_r & = \{ \operatorname{rem}(kk_1,n),…,\operatorname{rem}(kk_r,n) \} \\ & ≡ k_1kk_2k…k_rk \pmod{n} \\ & ≡ k_1k_2…k_rk^r \pmod{n} \\ \end{aligned}$$

费马小定理：如果 $p$ 是质数，且 $k∈{1,2,…,p-1}$，则 $k^{p-1} ≡ 1 \pmod{n}$

本质是欧拉定理在质数时的特殊情况

应用：$kk_{p-2}=k^{p-1} ≡ 1 \pmod{p}$，即可得 $k^{-1} ≡ k^{p-2} \pmod{p}$

RSA：

• 预先生成公钥和私钥
• 生成两个质数 $p$ 和 $q$
• $n=pq$
• 选择一个整数 $e$，使得 $\gcd(e,(p-1)(q-1)) = 1$，公钥就是 $e$ 和 $n$
• 计算 $d$，使得 $de ≡ 1 \pmod{(p-1)(q-1)}$
• 加密：$m^{\prime}=\operatorname{rem}(m^e,n)$
• 解密：$m = \operatorname{rem}(m^{\prime}d,n)$

图着色问题 NP 完备性 Graph Theory and Coloring

定义：图是 $(V,E)$ 的集合，其中 $V$ 是非空物品的集合，叫做结点 nodes 或顶点 vertex，$E$ 是 $V$ 选择两个结点的集合，叫做边 Edges

定义：如果两个顶点 $x_i, x_j$ 有边相连，则称 $x_i, x_j$ 邻接 adjacent

定义：如果 $e = \{x_ix_j\}$ 有边相连，则称 e 与 $x_ix_j$ 关联 incident

定义：与某个顶点关联的边的数量叫作该顶点的度数 degree

定义：如果一个图没有自环或多重边，则该图是简单的 simple

图着色问题：给定图和 k 种颜色，给每个顶点分配颜色使得相邻的顶点颜色不一样

定义：k 的最小值为图色数 $Χ(G)$

三色及以上的问题是NP 完全问题

定理：如果图中每个顶点的度数都不超过 d，则基本算法使用最多 $d + 1$ 种颜色

证明：归纳法，但是对图的顶点数 n，而不是 d，归纳

定义：如果一个图的顶点 V 可以被分成 $V_C, V_R$，且每一条边都连接 $V_C$ 和 $V_R$ 中的点二分图 bipartite

匹配 二分图 稳定婚姻算法 Matching Problems

定义：给定一个图 G，匹配 matching 是 G 的一个子图，其中每个顶点度数为 1

定义：给定一个匹配，如果 x 和 y 相比他们的伴侣更喜欢彼此，则称x 和 y 的配偶被戴了绿帽子x 和 y 是一对流氓夫妻 rough couple

定义：如果一个匹配中没有流氓夫妇，则称该匹配为稳定匹配 stable

定理： 当同性可以在一起的时候，不存在稳定匹配 （果然同性不是真爱）

证明：反证法

更让人惊讶的是， 在异性才能结婚的世界中，总能找到稳定匹配

算法：男生向未划掉的自己最喜欢的女生表白，女生留下其中最喜欢的，拒绝其余的 （你是个好人），被拒绝的男生划掉该女生，如此循环操作

需要证明：

• TMA 会终止（速度快）
• 没有人受伤每个人都会找到另一半
• 没有人被戴绿帽没有流氓夫妇
• TMA 对男生和女生是公平的吗

定理 1：TMA 在不超过 $N^2 + 1$ 天终止

证明：每天都划掉至少一个女孩

不变式：如果一个女生拒绝了一个男生 B，她有比 B 更好的求婚者

证明：对天数归纳

定理 2：每个人都结婚了

证明：反证法，若某个男生没有结婚，则他被所有女生拒绝了

定理 3：TMA 生成了稳定匹配

证明：任何不是一对的 Bob 和 Gail

• 情况 1：Gail 拒绝 Bob $\implies$ 她有更喜欢的人
• 情况 2：Gail 没有拒绝 Bob $\implies$ Bob 没有向 Gail 表白 $\implies$ Bob 被更喜欢的人接受了

定义：一个人可能域是指若他能得到稳定匹配的伴侣的集合

定义：一个人的最优伴侣是他/她的可能域中最喜欢的

定理 4：TMA 让每个男生和他的最优伴侣结婚

定理 5：TMA 让每个女生和他的最坏伴侣结婚

最小权重生成树 Graph Theory: Minimum Spanning Trees

定义：通路 walk 是被边依次相连的顶点序列（点、边可以相同）

定义：路径 path 是顶点不相同的通路（点、边均不相同）

引理：如果存在通路，则存在路径

证明：良序定理：存在最短的通路 + 反证法

定义：如果两点之间有路径，则称两点连通 connected

定义：如果图中任意两点都连通，则该图连通

定义：回路 closed walk 是起点和终点相同的通路

定义：环 cycle 是只有起点和终点相同的回路，即是起点和终点相同的路径

定义：连通且无环的图被称为树 tree

定义：叶结点是树中度为 1 的结点

引理：树的任何连通子图也是一棵树

证明：反证法：若该子图有环，则原图有环，不是树

引理：n 个结点的树有 n-1 条边

证明：归纳法，删除叶结点

定义：连通图生成树 spanning tree 是和原图有相同结点的树

引理：每个连通图都有生成树

证明：反证法

定义：加权图的最小权重生成树

算法：一步一步生成子图，每一步都保持子图无环，添加最小权重的边

引理：S 为算法中已经选择的 m 条边的集合，则 s 为 MST 边的集合的子集

证明：归纳法，添加边生成环，去掉边，注意某条边和此环内另一条边相等的情景（交换生成树）

通信网络 Communication Networks

交换机 Switch，终端 terminal

延迟 latency 是一个包从输入到输出所需时间

直径 diameter 等于最远的输入和输出之间的最小路径的长度

置换 permutation 是将 $n = \{0,1,…,N-1\}$ 映射到另一个集合的函数，没有冲突

堵塞 congestion 等于通过某个交换机的路径数量的最大值

蝴蝶网络：每个交换机都是根据其行和列唯一命名的，用 $(b_1,…,b_{\log N},l)$ 表示，其下一个结点是 $(b_1,…,!b_{l+1},b_{\log N},l+1)$ 和 $(b_1,…,b_{l+1},b_{\log N},l+1)$

Benes：将两个蝴蝶网络背靠背地连接起来

定理：堵塞为 1

证明：归纳法，对 a 归纳，$N=2^a$

约束法：若一个结点有两个输入，则将这两个输入相连；若一个结点有两个输出，则将这两个输出相连。该约束图可以用两种颜色染色

转化为两个小一层的子网

N*N 的网络	直径	交换机大小	交换机数量	堵塞
二叉树	$2(1+\log N)$	$3*3$	$2N-1$	$N$
2 维数组	$2N$	$2*2$	$N^2$	$2$
蝴蝶网络	$2+\log N$	$2*2$	$N(1+\log N)$	$sqrt{N}$ 或 $\sqrt{N/2}$
Benes	$1+2\log N$	$2*2$	$2N\log N$	$1$

欧拉图 竞赛图 Graph Theory

定义：一个欧拉闭迹 Euler tour 是遍历每一条边一次的通路

定理：一个连通图有欧拉闭迹，当且仅当每个顶点度数为偶数

定理：$P_{ij}^{(k)}$ 为从 $v_k$ 到 $v_j$ 长度为 $k$ 的通路的数量，那么邻接矩阵 $A^k = {P_{ij}^{(k)}}$

证明：通过归纳法，对 k 归纳

定义：如果一个有向图每一对结点之间都有有向通路，则该图是强连通的 strongly connected

定义：如果一个有向图没有有向环，则其为有向无环图 DAG

竞赛图 tournament graph：每对结点之间都有有向边相连

定义：有向哈密顿路径 directed Hamilton path 是有向的通路，每个顶点都要访问一次

定理：所有竞赛图都有有向哈密顿路径

证明：归纳法，对结点 n 归纳，考虑将多余的顶点插入到原路径中

菜鸡互啄：如果一只鸡 $u$ 打败了 $v$，或存在一只或多只鸡 $w$，$u$ 打败了 $w$，$w$ 打败了 $v$，则称 $u$ 打败了 $v$

如果一只鸡打败了其它所有的鸡，则称此鸡为公鸡中的战斗机

定理：出度最大的鸡一定是鸡王之一

证明：反证法，两种情况同时不满足，则出度不是最大

关系 偏序 拓扑排序 Relations, Partial Orders, and Scheduling

定义：集合 A 到集合 B 的关系 relation 是 A 和 B 的笛卡尔积的子集，即$R⊂A×B$

写法：$(a,b) ∈ R$，或 $a \operatorname{R} b$ ，或 $a∼\operatorname{R}b$

A 的关系是一个子集 $R ⊂ A × A$

对于一个有向图 $G = (V, E)$，$V = A$，$E = R$

对 A 的关系 R 性质：

• 自反性 reflexive：对所有 $x ∈ A$，$x \operatorname{R} x$
• 对称性 symmetric：对所有 $x, y ∈ A$，$x\operatorname{R} y \implies y \operatorname{R} x$
• 反对称性 antisymmetric：如果 $x \operatorname{R} y ∧ y \operatorname{R} x \implies x = y$
• 传递性 transitivity：如果 $x \operatorname{R} y ∧ y \operatorname{R} z \implies x \operatorname{R} z$

例如：

关系	自反	对称	反对称	传递
$x ≡ y \pmod{n}$	$✓$	$✓$	$×$	$✓$
$x \vert y$	$✓$	$×$	$✓$	$✓$
$x ≤ y$	$✓$	$×$	$✓$	$✓$

定义：等价关系 equivalence relation 是自反的，对称的，可传递的

定义：A 的分割 partition 是不同的、非空的 A 的子集，其并集为 A

定理：一个集合 A 的等价关系的等价类表示 A 的分化

定义：如果一个关系是自反的，反对称的，可传递的，则该关系是 （弱）偏序 (weak)patrial order 的，关系符号为$≤$，因为“小于等于”就是一种典型的偏序关系

定义：$(A,≤)$ 被称为偏序集 partially order set，有向图就是一个偏序集

定义：一个偏序集 $(A,≤)$ 的哈斯图 Hasse diagram 是一个有向图，其保留了所有顶点并删除所有自环和通过传递性得到的边

定理：偏序集除了自环外没有有向环

定义：如果既不 $a ≤ b$ 也不 $b ≤ a$，则 $a$ 和 $b$ 是不可比较 incomparable 的

定义：如果 $a ≤ b$ 或 $b ≤ a$，则 $a$ 和 $b$ 是可比较 comparable 的

定义：全序 total order 是每对元素都可以比较的偏序

定义：如果全序和偏序一致，则成为拓扑排序 topological sort

定理：每个偏序集都有拓扑排序

引理：每个有限偏序集都有最小元素

求和 渐进 Sums and Asymptotics

定义：n 年 m 美元年金 n-year $m-payment annuity 是每年付 m 美元，持续 n 年

假设：固定利率 p

$$V = \sum_{i=0}^{n-1}\frac{m}{(1+p)^i} = m \frac{1-x^n}{1-x}$$

扰动法 Perturbation method：其实就是错位相减法

推论：如果 $|x|<1$，则

$$\sum_{i=0}^{∞}x^i = \frac{1}{1-x}$$

该级数称为几何级数

$∑_{i=0}^{∞}ix^i$ 除了错位相减法以外，还可以使用求导的方法

定理：如果 $|x|<1$，则

$$\sum_{i=0}^{∞}ix^i = \frac{x}{(1-x)^2}$$

对于递增函数 $f(x)$，

$$f(1) + ∫_1^nf(x)\mathrm{d}x ≤ \sum_{i=1}^{n} f(i) ≤ f(n) + ∫_1^nf(x)\mathrm{d}x$$

类似的，递减函数为

$$f(n) + ∫_1^nf(x)\mathrm{d}x ≤ \sum_{i=1}^{n} f(i) ≤ f(1) + ∫_1^nf(x)\mathrm{d}x$$

定义：$g(x) ∼ h(x)$ 意思是 $\lim_{x→∞} \frac{g(x)}{h(x)} = 1$

定义：第 n 个调和数 harmonic number 表示为

$$H_n = \sum_{i=1}^n \frac {1}{i}$$

$$H_n = \ln n + δ + \frac{1}{2n} + \frac{1}{12n^2} + \frac{ϵ(n)}{120n^4}$$

其中 $0 < ϵ(n) < 1$，欧拉常数 $δ = 0.577215664…$，不知道是无理数还是有理数

斯特林公式 Stirling's Formula：

$$n! = (\frac{n}{e})^n \sqrt{2πn} e^{ϵ(n)}$$

其中 $\frac{1}{12n+1} ≤ ϵ(n) ≤ \frac{1}{12n}$

渐进符号 asymptotic notation：

• $f(x) ∼ g(x) : \lim_{x→∞} \frac{f(x)}{g(x)} = 1$
• $f(x) = O(g(x)) : \lim_{x→∞} \big| \frac{f(x)}{g(x)} \big| < ∞$
• $f(x) = Ω(g(x)) : \lim_{x→∞} \big| \frac{f(x)}{g(x)} \big| > 0$
• $f(x) = Θ(g(x)) : \lim_{x→∞} \big| \frac{f(x)}{g(x)} \big| > 0$ 或 $< ∞$
• $f(x) = o(g(x)) : \lim_{x→∞} \big| \frac{f(x)}{g(x)} \big| = 0$
• $f(x) = ω(g(x)) : \lim_{x→∞} \big| \frac{f(x)}{g(x)} \big| = ∞$

在归纳法中不能使用渐进符号，因为渐进符号用于衡量函数，而归纳法中的谓词表示的是某个数字的特殊情况

分治 递归 Divide and Conquer Recurrences

汉诺塔问题：$T_n = 1 + 2 T_{n-1}$

证明方法：

• 归纳法
• 迭代法

归并排序：$T(n) = 2 T(n/2) + n - 1$

$$T(n) = 2 T(n-1) + 1 \implies T(n) ∼ 2^n$$

$$T(n) = 2 T(n/2) + n - 1 \implies T(n) ∼ n \log n$$

$$S(n) = S(⌊\frac n2 ⌋) + S(⌈ \frac n2 ⌉) + 1 \implies S(n) ∼ n$$

定义：分治递归 divide and conquer recurrence 的形式为

$$T(x) = a_1T(b_1x+ϵ_1(x)) + a_2T(b_2x+ϵ_2(x)) + … + a_nT(b_nx+ϵ_n(x)) + g(x)$$

其中 $a_i > 0, 0 < b_i < 1, |ϵ_i(x)|≤O (\frac{x}{\log^2x}), g(x)$ 为多项式

Akra&Bazzi‘96 定理：$p$ 满足

$$\sum_{i=1}^k a_i b_i^p = 1$$

那么

$$T(x) = Θ(x^p + x^p\int_1^x\frac{g(u)}{u^{p+1}}\mathrm{d}u)$$

定理：特殊的，如果 $g(x) = θ(x^t)$ 且 $\sum_{i=1}^t a_i b_i^p < 1$，那么 $T(x) = Θ(g(x))$

线性递归 Linear Recurrences

定义：线性递归 linear recurrence 的形式为

$$f(n) = a_1 f(n-1) + a_2 f(n-2) + … + a_d f(n-d)$$

对于斐波那契数列 $f(n) = f(n-1) + f(n-2)$

尝试 $f(n) = α^n$，$α$ 是常数

解一元二次方程，得到 $α_1 = \frac{1 + \sqrt{5}}{2}, α_2 = \frac{1 - \sqrt{5}}{2}$

如果 $f(n) = α_1^n$ 和 $f(n) = α_2^n$ 是线性递归的解，则线性组合 $f(n) = c_1 α_1^n + c_2 α_2^n$ 也是一个解

初值约束解得 $c_1, c_2$

解为

$$f(n) = \frac{1}{\sqrt 5}\Big(\frac{1 + \sqrt{5}}{2}\Big)^n - \frac{1}{\sqrt 5}\Big(\frac{1 - \sqrt{5}}{2}\Big)^n$$

对于更一般的线性递归问题，所使用的方法相似，都类似于微分方程（因为这就是微分方程的离散形式）

矩阵的解释可参照线性代数

重根时的情况也类似：若对于 $α$ 有 $r$ 个重根，则根为 $α^n, n α^n, n^2 α^n … n^{r-1} α^n$

非齐次的情况：

1. 视为齐次方程，求齐次解
2. 求非齐次的特解 不断
3. 通解 = 特解 + 非齐次解

求特解时，例如：若 $g(n) = 2^n + n$，猜测 $f(n) = a 2^n + bn + c$，若不正确，继续猜测 $f(n) = (an + d)2^n + bn + c$

计数法则 Counting Rules

定义：集合 set 是无序且唯一的元素的 collection，用 $\{a,b,c\}$ 表示

定义：基数 cardinality 是集合拥有的元素数，用 $|X|$ 表示

定义：序列 sequence 是有序的 collection（元素可以不唯一），用 $(a,b,c)$ 表示

定义：排列 permutation 是每个元素恰好出现一次的序列

$n$ 个元素的排列数为 $n!$

定义：函数 function$f:x→y$，表示集合 x 到 y 的关系，每个 x 中的元素关系到 y 中的一个元素，x 为定义域 domain，y 为值域 range

定义：如果 y 中的每个元素都至少被映射到一次，则称函数 $f:x→y$ 是满射 surjective 的

定义：如果 y 中的每个元素都最多被映射到一次，则称函数 $f:x→y$ 是单射 injective 的

定义：如果 y 中的每个元素都恰好被映射到一次，则称函数 $f:x→y$ 是双射 bijective 的

映射法则：如果 $f:x→y$ 是

• 满射，则 $|x|≥|y|$
• 单射，则 $|x|≤|y|$
• 双射，则 $|x|=|y|$

广义鸽巢原理 generalized pigeon hole principle：如果 $|x| > k|y|$，那么对于 $f:x→y$，在 $x$ 中一定存在 $k + 1$ 个不同元素映射到 $y$ 中相同元素

证明：反证法

例：选取 10 个随机的两位数，其某一子集的和必然与另一子集相等

证明：

• 该集合子集的大小为 $2^{10}$
• 可能的和最多为 990<1024

定义：“k to 1”函数把 $x$ 中的每 $k$ 个元素映射到 $y$ 中的每个元素

除法法则：如果 f 是“k to 1”函数，则 $|x|=k|y|$

广义乘法法则：s 为长度为 k 的序列的集合，如果第一项有 $n_1$ 种选择，然后第二项有 $n_2$ 种选择……，则共有 $n_1n_2…n_k$ 种选择

定义：$A_1 × A_2 × … × A_n = \{ (a_1, a_2, …, a_n): a_1 ∈ A_1, a_2 ∈ A_2, … , a_n ∈ A_n \}$

乘法法则：$|A_1 × A_2 × …× A_n| = |A_1||A_2|…|A_n|$

和法则：如果 $A_1, A_2, …, A_n$ 是独立的，那么 $|A_1 ∪ A_2 ∪ … ∪ A_n| = |A_1| + |A_2| + … + |A_n|$

容斥原理：

$$|A_1 ∪ A_2 ∪ … ∪ A_n| = \sum_{k = 1}^n(-1)^{k + 1}\sum_{S ⊂ \{1…n\} ∧ |S| = k}|∪ A_i|, i ∈ S$$

bookkeeper rule：不同字母 $l_1, l_2, …, l_k$，分别有 $n_1, n_2, …, n_k$ 份，则总共有 $\frac{(n_1+n_2+…+n_k)!}{n_1! n_2! … n_k!}$，也被称为二项式系数

概率介绍 Probability Introduction

世界上三种谎言，分别是谎言、该死的谎言和统计数字(There are three kinds of lies: lies, damnedlies, and statistics)。
——马克·吐温

定义：一个实验的样本空间 sample space 是所有可能的结果的集合

定义：一个结果或样本点包括所有关于实验的信息，包括所有随机选择的值

定义：概率空间 probability space 由样本空间和概率函数组成，记作 $\operatorname{Pr}$

定义：事件 event 是结果的一个子集 “三门问题”：使用树形法，不要依赖于直觉秘密在于当你一开始选择了正确的门时，交换后失败；一开始选择的是错误的时，交换后成功，而一开始选择错误的概率大于选择正确的概率

骰子问题：当扔一次时，A 打败 B，B 打败 C，C 打败 A，概率都是 $\frac 59$，因为概率不可传递

但当扔 k 次时，可以得到任何打败的组合

可以把任何竞赛图关系到抛某个次数的某个骰子上

条件概率 Conditional Probability

条件概率 conditional probability：$\operatorname{Pr}(A|B)$

定义：如果 $\operatorname{Pr}(B)≠0$，$\operatorname{Pr}(A|B)=\frac{\operatorname{Pr}(A\cap B)}{\operatorname{Pr}(B)}$

乘法法则：$\operatorname{Pr}( ∩ B) = \operatorname{Pr}(B)\operatorname{Pr}(A|B)$

医学测试：如果你只按照人群中的比例猜测一个人得病的概率，则比通过有可能失误的测试概率高多了

容斥原理也对条件概率有效

两个航空公司，其中航空公司 A 的每个地点的准点率都比 B 的准点率低，但总体来说准点率更高，原因是它在两者准点率都高的地点有更多的航班

独立性 生日悖论 Independence

定义：如果 $\operatorname{Pr}(A|B) = \operatorname{Pr}(A)$ 或 $\operatorname{Pr}(B)=0$，则称 A 对 B 是独立的 independent

另一种等价定义：乘法法则：$\operatorname{Pr}(A∩B) = \operatorname{Pr}(B)\operatorname{Pr}(B)$

独立的对称性：如果 A 独立于 B，则 B 也独立于 A，故常称 A 与 B 独立

定义：如果事件集合中的所有子集相互独立，则称事件 $A_1, A_2, …, A_n$ 相互独立 mutually independent

等价定义（乘法法则形式）：$\operatorname{Pr}(∩A_j)=\prod_{j∈J}\operatorname{Pr}(A_j)$

定义：如果任意两对 $A_i, A_j$ 相互独立，则称事件 $A_1, A_2, …, A_n$ 两两独立 pairwise independent

生日问题：N 个生日，M 个人，2 个或多个人有相同的生日的概率

$$\operatorname{Pr}(\text{生日不同})=\frac{N!}{(N-M)!N^M}$$

使用斯特林公式得到闭式：

$$\operatorname{Pr}(\text{生日不同}) ∼ e^{(N-M+\frac 12)\ln(\frac{N}{N+M})-M}$$

当 $N = 365, m = 23$ 时，概率为 0.49，接近于 $\frac 12$

如果 $M = o(N^{\frac 23})$，则当 $m=1.177 \sqrt{N}$ 时，有 50% 的概率匹配到相同的生日

随机变量 Random Variables

定义：随机变量 random variable 是函数 $R:S$(样本空间)$→R$(真实空间)

定义：指示器 indicator 或 Bernouli 或 characteristic 是值域为 $\{0,1\}$ 的随机变量

定义：

$$\operatorname{Pr}(R=x) = \sum^{\operatorname{Pr}(w)=x}\operatorname{Pr}(w)$$

随机变量的独立性定义依旧相同，不再赘述

定义：给定随机变量 R，其概率分布函数 probability distribution function 是 $f(x)=\operatorname{Pr}(R=x)$

定义：随机变量 R 的累积分布函数 cumulative distribution function 是 $f(x)=\operatorname{Pr}(R≤x)$

猜数字游戏：出题人预先写好两个数字，挑战者内心均匀想好一个数字，根据亮出的一个数字和内心想好的某个数字的大小关系决定是否要更换所选数字

当挑战者预期的数字是均匀分布时，获胜的概率为 $\frac 12 + \frac{1}{2n}$，此策略为最优策略

而出题者给出的策略是选择相邻的两个数字，此策略也为最优策略

无偏差二项分布 unbiased binomial distribution：$f_n(k)=C_n^k2^{-n}$，是一般情况 $p=\frac 12$ 时的特殊情况

一般二项分布 general binomial distribution：$f_n(k)=C_n^kp^k(1-p)^{n-k}$

$$f_{n,p}(αn)≤\frac{2^{[α\log {\frac pα} + (1-α)\log{\frac{1+p}{1-α}}]n}}{\sqrt{2πα(1-α)n}}$$

当$α=p$时取最大值为：

$$f_{n,p}≤\frac{1}{2πp(1-p)n}$$

概率分布的图像最高点为 $Θ(\frac{1}{\sqrt π})$，指数级缩小，驼峰宽度为 $Θ(\sqrt{n})$

期望 Expectation

定义：随机变量 R 在样本空间 S 上的期望 expected value

$$\operatorname{Ex}(R) = \sum^{w ∈ S}R(w)\operatorname{Pr}(w)$$

定义：R 的中位数 median 是 $x ∈ range(R)$ 且满足 $\operatorname{Pr}(R<x)≤\frac 12$ 且 $\operatorname{Pr}(R>x)<\frac 12$

三个人玩猜硬币游戏，其中两个人始终猜测相反的结果，则第三个人最终一定会亏钱，每轮的期望为 $-\frac 12$

所以避免大多数人的选择，虽然失败的概率较大，但成功后获得的收益更大，最终的期望更大

定理：

$$\operatorname{Ex}(R) = \sum^{x∈range(R)}x\operatorname{Pr}(R=x)$$

定理：如果 R 在自然数上，则

$$\operatorname{Ex}(R) = \sum_{i=0}^{∞}\operatorname{Pr}(R>i) = \sum_{i=1}^{∞}\operatorname{Pr}(R≥i)$$

若信号延迟 D 满足 $\operatorname{Pr}(D≥i)=\frac 1i$，则 $\operatorname{Ex}(D)=∞$，但如果仅计算前面有限个数的期望，则为有限值

线性期望：定理：对任何随机变量 $R_1, R_2$ 来说，$\operatorname{Ex}(R_1+R_2)=\operatorname{Ex}(R_1) + \operatorname{Ex}(R_2)$，也可以推广到 $n$ 个数，这些 $R$ 不需要相互独立

每个人随机拿回一顶帽子，则刚好拿回自己帽子的概率

$$\operatorname{Ex}(R) = \operatorname{Ex}(R_1) + … + \operatorname{Ex}(R_n) = \operatorname{Pr}(R_1=1)+ … + \operatorname{Pr}(R_n=1) = \frac 1n + … + \frac 1n = 1$$

相似的，吃饭时随机选择桌子，每个人拿到自己喜欢的菜的期望是 1

定理：概率空间 $S$ 中的事件 $A_1, A_2, …, A_n ⊂ S$，则这些事件发生的个数的期望是 $\sum_{i=1}^{n}\operatorname{Pr}(A_i)$

定理：$\operatorname{Pr}(T≥1)≤\operatorname{Ex}(T)$，也可写成$\operatorname{Pr}(T≥1)≤\sum_{i=1}^{n}\operatorname{Pr}(A_i)$

墨菲定律：如果有互相独立的事件 $A_1,A_2,…,A_n$，则 $\operatorname{Pr}(T=0)≤E^{-\operatorname{Ex}(T)}$

证明：使用了 $1 - x ≤ e^x$

推论：如果有 10 或更多独立的事件可能发生，则则没有事件发生的概率 $≤ e^{-10} ≤ \frac{1}{22000}$

在宏观上的墨菲定律是因为存在着大量可能发生的事件，则其中几乎必然有事件会发生，而我们很难考虑到所有可能发生的情况，所以会对很多几乎不可能发生的情况的发生而感到不可思议

一堆纸牌中有大量的 1，这延长了结束的时间，增加了冲突的概率，故结束时往往会有大量人同步

定理（期望的乘法法则）：对任何独立的随机变量 $R_1, R_2$，$\operatorname{Ex}(R_1R_2)=\operatorname{Ex}(R_1)\operatorname{Ex}(R_2)$，同样可以推广到 n 个随机变量

推论（线性）：$\operatorname{Ex}(aR+b)=a\operatorname{Ex}( R )+b$

一些误区：

• $\operatorname{Ex} (\frac 1R)≠\frac{1}{\operatorname{Ex}( R )}$
• $\operatorname{Ex}(\frac{R}{T})>1$无法得出$\operatorname{Ex}( R )>\operatorname{Ex}(T)$

事实上有时你可以同时得出 $\operatorname{Ex}(\frac{R}{T})>1$ 和 $\operatorname{Ex}(\frac{T}{R})>1$，所以你想要得出哪个结论，就使用相应的方法分析

定义：随机变量 R 的方差 Variance 是$\operatorname{Var}( R )=\operatorname{Ex}((R-\operatorname{Ex}( R ))^2)$

之所以使用平方来定义是因为：如果直接使用偏差的平均值，则始终为 0；若使用绝对值，则无法得出一些优秀的定理；若使用四次方则过于麻烦，事实上确实有使用四次方定义的量

定义：标准差 standard deviation $σ( R ) = \sqrt{\operatorname{Var}( R )}$，也称为偏差的均方根 root-mean-square

大偏差 Large Deviations

马尔科夫定理 Markov's theorem：如果 R 是个非负随机变量，则 $\operatorname{Pr}(R≥x)≤\frac{\operatorname{Ex}(R)}{x}$

要求非负是因为证明中使用到了 $\operatorname{Ex}(R|R<x)\operatorname{Pr}(R<x)≥0$

推论：$R>0$，$\operatorname{Pr}(R≥c\operatorname{Ex}(R))≤\frac{1}{c}$

推论：对 $u ∈ S$，如果 $R ≤ u$，则 $∀x < u,\operatorname{Pr}(R≤x)≤\frac{u-\operatorname{Ex}(R)}{u-x}$

本质上是保证了 $u - r > 0$ 的马尔科夫定理

切比雪夫定理 Chebyshev's theorem （方差版本的马尔科夫定理）：$∀x > 0, \operatorname{Pr}(|R - \operatorname{Ex}(R)| ≥ x) ≤ \frac{\operatorname{Var}(R)}{x^2}$

同样的，也有一个推论：$\operatorname{Pr}(|R-\operatorname{Ex}(R)| ≥ cσ(R)) ≤ \frac{1}{c^2}$

注意，这些定理得出的边界都和实际分布无关，事实上是最坏分布下得出的边界

切诺夫界 Chernoff bound：$T_1, …, T_n$ 是任何独立的随机变量且 $0 ≤ T_i ≤ 1$（若不是，则标准化），令 $T=\sum_{i=1}^n T_i$，则对于所有 $c>1$，$\operatorname{Pr}(T≥c\operatorname{Ex}(T))≤e^{-z\operatorname{Ex}(T)}$，其中$z=c\ln c + 1 - c > 0$

三者的共同点：$\operatorname{Pr}(A>B)=\operatorname{Pr}(f(A)>f(B))≤\frac{\operatorname{Ex}(f(A))}{f(B)}$，在切比雪夫中使用了平方，在切诺夫中使用了 e 指数

分配网络负载的方法：随机分配，超过 2 倍的概率为 $\frac{1}{16000}$

随机游走 Random Walks

赌徒破产问题：一开始有 n 元，赢得 1 元的概率为 p，输掉 1 元的概率为 1-p，重复玩，直到输光钱或赢到 m 元

若获胜概率为 $\frac{9}{19}$，由 1000 元赢到 1100 的概率 $≤ \frac{1}{37648}$

定义：

• $W^*$：在到达 0 之前到达 $T = n + m$ 的事件
• D：开始时的钱
• $x_n=\operatorname{Pr}(W^*|D=n)$

$$x_n = \begin{cases} 0, n = 0 \\ 1, n = T \\ px_{n+1}+(1-p)x_{n-1}, 0<n<T \end{cases}$$

解得特征根 $r_1 = 1, r_2 = \frac{1-p}{p}$

若 $p < \frac 12$，代入初值并近似 $≤ (\frac{p}{1 - p})^m$，故几乎不可能成功，且答案中与 n 无关马斯克来都被榨干

若 $p = \frac 12$，赢得 m 元的概率为 $\frac{n}{n + m}$所以在“公平”的游戏中，有钱人比没钱人更“公平”

在 x 步后，偏移 drifted 的幅度为 $(1-2p)x$，摆动 swing 为 $Θ(\sqrt{x})$，偏移比摆动增长更快

有一些样本点会导致永远无法结束，但这些点之和为 0

借用老师画的图：

定义：

• S：输光之前的步数
• $E_n=\operatorname{Ex} (S|D=n)$

$$E_n = \begin{cases} 0, n = 0 \\ 0, n = T \\ pE_{n+1}+(1-p)E_{n-1} + 1, 0<n<T \end{cases}$$

同样可得出结论：

$$E_n = \frac{n}{1-2p} - \frac{T}{1-2p} \frac{(\frac{1-p}{p})^n - 1}{(\frac{1-p}{p})^T - 1}$$

忙活了半天，得出的结论和直观理解的 $\frac{n}{1-2p}$ 差不了多少

若 $p=\frac 12$，$E_n = mn$

趁早退出定理：如果 $p=\frac 12$，不断地玩，最终一定会破产

证明：反证法（摆动幅度越来越大）