附录 A 数学背景速查（原书附录 A–D）

原书第 VIII 部分的四个附录汇编了算法分析用到的数学工具：附录 A 求和，附录 B 集合、关系、函数、图与树，附录 C 计数与概率，附录 D 矩阵。前两部分是本册算法分析的直接工具，这里讲得完整一些；附录 C、D 与第 02 册（概率论）、第 01 册（线性代数）大量重叠，这里只列出公式、记号和本书特有的结论（如二项分布尾界），系统讲解请回查对应分册。每部分配一个量化小例子。

学习目标

读完本附录，你应当能够：

1. 熟记算术级数、几何级数、\(\sum kx^k\)、调和数等基本求和公式，并会用归纳、逐项放大、拆分、积分近似四种方法给和式定界，避开两个常见陷阱。
2. 掌握等价关系与划分的对应、偏序中"极大元"与"最大元"的区别、函数的单射/满射/双射，以及图与树的基本术语和自由树的六条等价刻画。
3. 快速查到排列组合、二项式系数的界、条件概率与 Bayes 公式、期望线性性、几何分布与二项分布的矩，以及二项分布尾部的几种界，并知道哪些界在什么情况下是松的。
4. 查到矩阵的基本运算、秩、行列式、正定性的定义和性质，理解"列满秩 ⇒ \(A^TA\) 正定"对样本协方差矩阵的含义。

读前导读

这份附录是工具箱，不是新内容。 本册分析算法时反复用到四类数学：求和（算循环总耗时）、集合与图（描述数据结构）、概率（分析随机算法）、矩阵（数值算法）。你在 CFA 里已经用过其中不少：年金现值就是有限几何级数，EWMA 波动率就是无穷几何级数，组合方差就是 \(w^T\Sigma w\)。这里把它们换成算法书的记号集中列出，遇到正文引用（如"由式 (A.8)"）时回来查即可，不必从头通读。

需要先想起来的数学

• 级数与收敛：无穷级数的值是部分和的极限。\(\sum_{k\ge0}x^k=1/(1-x)\) 只在 \(|x|<1\) 时成立，例如 \(x=0.5\) 时和为 2；这和永续年金 \(C/r\) 是同一个公式。详见 第 00 册第 04 章 级数与收敛。
• 逐项求导：对幂级数两边求导仍成立（在收敛区间内），式 (A.8) 就是这样得到的。这与"久期是价格对收益率的导数"是同一类操作。详见 第 00 册第 02 章 导数与泰勒展开。
• 定积分作为面积：\(\int_1^n\frac{dx}{x}=\ln n\)。A.1.2 的积分近似法就是拿矩形面积和曲线下面积比较。详见 第 00 册第 03 章 积分。
• 大 \(O\)、\(\Theta\)、\(\Omega\) 记号：\(f=O(g)\) 指存在常数 \(c\)，\(n\) 足够大时 \(f(n)\le c\,g(n)\)；\(\Omega\) 是下界，\(\Theta\) 是上下界同时成立。\(3n^2+5n=\Theta(n^2)\)。定义见 本册第 03 章，概率中的用法见 第 00 册第 07 章 概率中的分析工具。
• 矩阵、秩与正定：A.5 节默认你会矩阵乘法、知道秩和正定的含义。详见 第 00 册第 06 章 线性代数速成。
• 读证明与符号：本附录有大量"⇒""⇔"、归纳法和反证法（如定理 B.1、B.2、D.6），符号 \(\wedge\) 表示"且"。详见 第 00 册第 08 章 读懂数学证明与符号。

怎么读：A.1（求和）建议完整读一遍，它是第 2–4 章复杂度分析的直接工具。A.2、A.3 第一次读只看定义和定理 B.2，遇到图算法章节时再回来。A.4、A.5 当作公式表，需要时查；其中 A.4.3–A.4.4 的尾界比较和 A.5.3 的协方差奇异性对量化工作最有用，值得读完。

A.1 求和（原书附录 A）

循环的运行时间是各次迭代时间之和，所以求和是算法分析最常用的工具。例如插入排序第 \(j\) 次迭代最坏耗时正比于 \(j\)，总时间 \(\sum_{j=2}^nj=\Theta(n^2)\)。

A.1.1 基本性质与公式

• 有限和的值与相加顺序无关；\(n=0\) 时空和定义为 0。无穷级数 \(\sum_{k=1}^\infty a_k\) 定义为部分和的极限，极限存在称收敛，否则发散。收敛级数不一定能任意重排；绝对收敛（\(\sum|a_k|\) 收敛）的级数可以重排。
• 线性性：\(\sum(ca_k+b_k)=c\sum a_k+\sum b_k\)。用于渐近记号：\(\sum_{k=1}^n\Theta(f(k))=\Theta\!\left(\sum_{k=1}^nf(k)\right)\)（左边的 \(\Theta\) 作用于 \(k\)，右边作用于 \(n\)）。
• 乘积：\(\prod_{k=1}^na_k\)，空积为 1；取对数化为求和，\(\lg\prod a_k=\sum\lg a_k\)。

(A.8) 由对 (A.6) 两边求导再乘 \(x\) 得到；习题 A.1-3 再求一次导得 \(\sum k^2x^k=x(1+x)/(1-x)^3\)。望远镜和的经典例子：\(\frac1{k(k+1)}=\frac1k-\frac1{k+1}\)，所以 \(\sum_{k=1}^{n-1}\frac1{k(k+1)}=1-\frac1n\)；乘积版本见习题 A.1-8：\(\prod_{k=2}^n(1-1/k^2)=\frac{n+1}{2n}\)。

推导拆解：(A.8) 的三步。第一步，写下 (A.6)：\(\sum_{k\ge0}x^k=(1-x)^{-1}\)。第二步，两边对 \(x\) 求导：左边逐项求导得 \(\sum_{k\ge1}kx^{k-1}\)（\(k=0\) 项是常数 1，导数为 0）；右边用链式法则，\((1-x)^{-1}\) 的导数是 \((-1)(1-x)^{-2}\cdot(-1)=(1-x)^{-2}\)。第三步，两边乘 \(x\)，把 \(x^{k-1}\) 变回 \(x^k\)，得 \(\sum kx^k=x/(1-x)^2\)。逐项求导在 \(|x|<1\) 内合法，理由见 第 00 册第 04 章 级数与收敛 的幂级数部分。

金融直觉：把 \(x\) 看成贴现因子 \(1/(1+y)\)，\(\sum_{k\ge0}x^k\) 是从第 0 期起每期付 1 的永续年金（期初付款）现值，\(\sum kx^k\) 是各期时间按现值加权之和。两者相除就是这笔永续年金的麦考利久期 \(x/(1-x)=1/y\)（期末付款的普通永续年金则是 \((1+y)/y\)）。A.1.3 的"平均滞后"是同一个计算。

A.1.2 给和式定界的四种方法

1. 数学归纳法。可以证精确值，也可以证上界而不必知道精确值。例：证 \(\sum_{k=0}^n3^k\le c\,3^n\)。归纳步 \(\sum_{k=0}^{n+1}3^k\le c3^n+3^{n+1}=\left(\frac13+\frac1c\right)c3^{n+1}\le c3^{n+1}\)，只要 \(c\ge3/2\)。

陷阱一："证明" \(\sum_{k=1}^nk=O(n)\)：\(\sum_{k=1}^{n+1}k=O(n)+(n+1)=O(n+1)\)。这是错的——大 \(O\) 里隐藏的常数随 \(n\) 增长，并没有证明同一个常数对所有 \(n\) 成立。用归纳证渐近界时，必须写出显式常数。

2. 逐项放大。最简单的是用最大项界住每一项：\(\sum_{k=1}^na_k\le n\cdot a_{\max}\)。更强的是几何比值界：若存在常数 \(0<r<1\) 使对所有 \(k\) 有 \(a_{k+1}/a_k\le r\)，则

陷阱二：只证明"相邻项比值小于 1"不够。调和级数的比值 \(k/(k+1)<1\)，但 \(\sum1/k\) 发散——比值可以任意接近 1，不存在常数 \(r<1\)。

3. 拆分求和。求 \(\sum_{k=1}^nk\) 的下界，用最小项只得 \(n\)；拆成两半，后一半每项至少 \(n/2\)，得 \((n/2)^2=\Omega(n^2)\)。另两个技巧：丢掉前常数项（项与 \(n\) 无关时 \(\sum_{k=0}^n a_k=\Theta(1)+\sum_{k=k_0}^na_k\)，如 \(\sum k^2/2^k\) 在 \(k\ge3\) 后比值 \(\le8/9\)，所以是 \(O(1)\)）；按 2 的幂分段（把 \(1..n\) 分成 \(\lfloor\lg n\rfloor+1\) 段，每段贡献至多 1，得 \(H_n\le\lg n+1\)）。

4. 积分近似。\(f\) 单调递增时

白话解释：把 \(f(k)\) 画成第 \(k\) 个宽 1、高 \(f(k)\) 的柱子。\(f\) 递增时，柱子 \([k,k+1]\) 的高度 \(f(k)\) 是这一段上的最小值，所以柱子面积 \(\le\int_k^{k+1}f\)，加起来得右边的上界；把柱子挪到 \([k-1,k]\)，\(f(k)\) 变成这段上的最大值，得左边的下界。递减时最小、最大互换，不等号方向就反了。\(f(x)=1/x\) 是递减函数，所以调和数用的是 (A.12)。积分 \(\int dx/x=\ln x\) 的来历见 第 00 册第 03 章 积分。

思考题 A-1 的结论常用于复杂度分析：\(\sum_{k=1}^nk^r\lg^sk=\Theta(n^{r+1}\lg^sn)\)（\(r,s\ge0\) 为常数）。

A.1.3 量化小例：EWMA 的权重、滞后与半衰期

衰减因子为 \(\lambda\) 的指数加权移动平均（EWMA）给第 \(k\) 期前的观测权重 \((1-\lambda)\lambda^k\)。由 (A.6)，权重和为 1；由 (A.8)，平均滞后（权重加权的平均"年龄"）为

import numpy as np

for lam in (0.94, 0.97, 0.99):
    k = np.arange(100_000)
    w = (1 - lam) * lam ** k                       # EWMA 权重，和为 1（式 A.6）
    mean_lag = np.sum(k * w)                       # = λ/(1-λ)（式 A.8）
    half_life = np.log(0.5) / np.log(lam)          # λ^h = 1/2
    print(f"λ={lam}: 权重和 {w.sum():.6f}，平均滞后 {mean_lag:6.2f}（公式 {lam/(1-lam):6.2f}），半衰期 {half_life:5.1f} 期")

for n in (10, 1000, 10**6):                        # 调和数的积分界（式 A.13、A.14）
    H = np.sum(1.0 / np.arange(1, n + 1))
    print(f"n={n:>7}: ln(n+1)={np.log(n+1):.4f} <= H_n={H:.4f} <= ln n + 1={np.log(n)+1:.4f}")

输出：

λ=0.94: 权重和 1.000000，平均滞后  15.67（公式  15.67），半衰期  11.2 期
λ=0.97: 权重和 1.000000，平均滞后  32.33（公式  32.33），半衰期  22.8 期
λ=0.99: 权重和 1.000000，平均滞后  99.00（公式  99.00），半衰期  69.0 期
n=     10: ln(n+1)=2.3979 <= H_n=2.9290 <= ln n + 1=3.3026
n=   1000: ln(n+1)=6.9088 <= H_n=7.4855 <= ln n + 1=7.9078
n=1000000: ln(n+1)=13.8155 <= H_n=14.3927 <= ln n + 1=14.8155

RiskMetrics 日度 \(\lambda=0.94\) 的平均滞后约 16 天、半衰期约 11 天：它对新信息反应快，代价是估计噪声大。平均滞后大于半衰期，是因为指数权重有长尾。调和数还出现在第 35 章集合覆盖的近似比 \(H(\max|S|)\) 中。

A.2 集合、关系与函数（原书附录 B.1–B.3）

A.2.1 集合

• 集合中元素互不相同且无序，\(\{1,2,3,1\}=\{3,2,1\}\)；允许重复的叫多重集。本书 \(\mathbb N=\{0,1,2,\dots\}\) 从 0 开始。\(A\subset B\) 表示真子集。
• 运算律：交换、结合、幂等、吸收律 \(A\cap(A\cup B)=A\)；分配律 \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\) 及对偶；De Morgan 律 \(\overline{B\cap C}=\bar B\cup\bar C\)，\(\overline{B\cup C}=\bar B\cap\bar C\)。
• 划分（partition）：两两不相交、并为全集的非空子集族。
• 基数：\(|A\cup B|=|A|+|B|-|A\cap B|\)（B.3）；一般地有容斥原理（习题 B.1-3）
  \[|A_1\cup\cdots\cup A_n|=\sum|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n-1}|A_1\cap\cdots\cap A_n|.\]
• 幂集 \(2^S\) 有 \(2^{|S|}\) 个元素；笛卡儿积 \(|A\times B|=|A|\cdot|B|\)。可与 \(\mathbb N\) 一一对应的无限集称可数无限，\(\mathbb Z\) 可数，\(\mathbb R\) 不可数。

A.2.2 关系

\(A\) 上的二元关系 \(R\subseteq A\times A\)。三个性质：自反（\(aRa\)）、对称（\(aRb\Rightarrow bRa\)）、传递（\(aRb\wedge bRc\Rightarrow aRc\)）。

• 等价关系 = 自反 + 对称 + 传递。等价类 \([a]=\{b:aRb\}\)。定理 B.1：等价关系的等价类构成划分；反之每个划分确定一个等价关系。（证明要点：若 \([a]\)、\([b]\) 有公共元 \(c\)，由对称、传递得 \(aRb\)，进而 \([a]=[b]\)。）模 \(n\) 同余就是一个等价关系，把整数划分为 \(n\) 个剩余类（习题 B.2-2）。

白话解释："等价关系 ⇔ 划分"说的是：只要一个"同类"判断满足自己和自己同类、同类关系可以互换、同类的同类还是同类，它就一定能把全体干净地切成互不重叠的若干组；反过来，任何分组方式也定义了一个"在同一组"的关系。\(aRb\) 读作"\(a\) 与 \(b\) 有关系 \(R\)"。证明为什么用对称和传递：\(c\in[a]\) 且 \(c\in[b]\) 即 \(aRc\)、\(bRc\)，对称得 \(cRb\)，传递得 \(aRb\)。这类"⇒/⇔"证明的读法见 第 00 册第 08 章 读懂数学证明与符号。

• 偏序 = 自反 + 反对称（\(aRb\wedge bRa\Rightarrow a=b\)）+ 传递。偏序集可能没有唯一的最大元，却有多个极大元（没有别的元素比它"大"）。原书的比喻：一堆大小不一的盒子，可能有好几个装不进任何别的盒子的极大盒，但没有能装下所有盒子的最大盒。
• 全序 = 偏序 + 全关系（任意两元素可比）。只要求传递和全关系的叫全预序（本册第 31 章第三部分，即原书第 33 章，扫描线算法的线段次序就是全预序）。
• 陷阱（习题 B.2-5）："对称 + 传递 ⇒ 自反"是错的：若 \(a\) 与任何元素都没有关系，就推不出 \(aRa\)（空关系是反例）。

量化含义：行业分类、风格分组是对股票的划分，"行业中性化"就是在每个等价类内去均值。多目标比较（收益更高且回撤更小）只构成偏序，帕累托前沿就是极大元集合（第 31 章极大层算法），不存在唯一"最好"的策略。

A.2.3 函数

函数 \(f:A\to B\) 是一种关系，每个 \(a\) 恰对应一个 \(b\)。

• 单射（一对一）：\(a\ne a'\Rightarrow f(a)\ne f(a')\)，如 \(f(n)=2n\)；
• 满射（到上）：值域等于陪域，如 \(f(n)=\lfloor n/2\rfloor\) 是 \(\mathbb N\to\mathbb N\) 的满射；
• 双射：既单又满，有逆函数；集合到自身的双射叫置换。例：\(f(n)=(-1)^n\lceil n/2\rceil\) 是 \(\mathbb N\to\mathbb Z\) 的双射（\(0,-1,1,-2,2,\dots\)）。
• 有限序列是定义域为 \(\{0,\dots,n-1\}\) 的函数，无限序列定义域为 \(\mathbb N\)。

A.3 图与树（原书附录 B.4–B.5）

A.3.1 图的术语

• 有向图 \(G=(V,E)\)，允许自环；无向图的边是无序对，不允许自环。
• 度：无向图中关联的边数；有向图分入度与出度。握手引理（习题 B.4-1）：\(\sum_v\deg(v)=2|E|\)。
• 路径、简单路径（顶点互异）、回路、简单回路；无简单回路的图称无环。
• 连通分量是"可达"关系的等价类；有向图的强连通分量是"相互可达"关系的等价类。
• 同构、子图、诱导子图（取顶点子集及其间的全部边）。
• 特殊图：完全图、二部图、森林、（自由）树、DAG（有向无环图）、多重图、超图。边的收缩把两个端点合并成一个顶点。
• 思考题 B-1：二部图 ⇔ 可 2-着色 ⇔ 无奇数长回路；最大度为 \(d\) 的图可用 \(d+1\) 色贪心着色。思考题 B-2：任意 6 人中必有 3 人互相认识或 3 人互不认识（Ramsey 数 \(R(3,3)=6\)）。

A.3.2 树

自由树是连通、无环的无向图；无环但可能不连通的是森林。

定理 B.2（自由树的六条等价刻画） 对无向图 \(G=(V,E)\)，以下等价：

1. \(G\) 是自由树；
2. 任两顶点间有唯一简单路径；
3. \(G\) 连通，但删去任一条边就不连通；
4. \(G\) 连通，且 \(|E|=|V|-1\)；
5. \(G\) 无环，且 \(|E|=|V|-1\)；
6. \(G\) 无环，但加任一条边就产生回路。

证明是一条蕴含链 (1)⇒(2)⇒…⇒(6)⇒(1)。例如 (1)⇒(2)：若有两条不同的简单路径，从第一个分叉点到下一个汇合点的两段拼起来就是回路；(4)⇒(5)：若有回路，从回路出发逐个加入相邻顶点，每次加一个顶点至少加一条边，最终 \(|E|\ge|V|\)，矛盾。

有根树：指定一个顶点为根。术语：祖先、后代（每个结点是自身的祖先和后代）、父结点、孩子、兄弟、叶（外部结点）、内部结点；结点的度是孩子数（父结点不计）；深度是根到结点的路径长；高度是结点到叶的最长路径长，树高等于最大深度。有序树的孩子有先后次序。

二叉树递归定义：空树，或由根、左子树、右子树组成。二叉树不只是"每个结点至多两个孩子的有序树"：只有一个孩子时，它是左孩子还是右孩子有区别。\(k\) 叉树是孩子位置至多为 \(k\) 的位置树。完全 \(k\) 叉树：所有叶深度相同、内部结点度均为 \(k\)；高为 \(h\) 时叶数 \(k^h\)，内部结点数

A.3.3 量化小例：相关性网络的最小生成树

Mantegna 方法把相关系数变成距离 \(d_{ij}=\sqrt{2(1-\rho_{ij})}\)，对完全图求最小生成树（MST）。MST 是一棵自由树，有 \(|V|-1\) 条边（定理 B.2 第 4 条）；删去最长的 \(c-1\) 条边，树断成 \(c\) 个连通分量——它们是"在剩余边上可达"这一等价关系的等价类，也就是一个聚类结果。MST 的算法（Kruskal、Prim）及其与单链接聚类、层次风险平价的关系见第 21、23 章，这里只演示自由树性质。

import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree, connected_components

rng = np.random.default_rng(9)
n_ind, per = 3, 10                                 # 3 个行业，每个行业 10 只股票
N, T = n_ind * per, 500
mkt = rng.standard_normal(T)
ind = rng.standard_normal((n_ind, T))
R = np.array([0.5 * mkt + 0.8 * ind[i // per] + rng.standard_normal(T) for i in range(N)])
rho = np.corrcoef(R)
D = np.sqrt(2 * (1 - rho))                         # 相关系数 → 距离
np.fill_diagonal(D, 0)
mst = minimum_spanning_tree(D).toarray()
edges = np.argwhere(mst > 0)
print(f"顶点 {N}，MST 边数 {len(edges)}（自由树：|E| = |V| - 1）")
n_comp, _ = connected_components(mst, directed=False)
print("MST 连通分量数:", n_comp)
cut = mst.copy()                                   # 删去最长的 n_ind-1 条边
for i, j in edges[np.argsort(mst[edges[:, 0], edges[:, 1]])[::-1][:n_ind - 1]]:
    cut[i, j] = 0
n_comp, labels = connected_components(cut, directed=False)
print("删去最长 2 条边后的分量数:", n_comp)
print("每个分量对应的真实行业:", [sorted({int(i) // per for i in np.flatnonzero(labels == c)}) for c in range(n_comp)])

输出：

顶点 30，MST 边数 29（自由树：|E| = |V| - 1）
MST 连通分量数: 1
删去最长 2 条边后的分量数: 3
每个分量对应的真实行业: [[0], [1], [2]]

删去两条最长边后得到的三个分量恰好是三个模拟行业。这就是单链接层次聚类；HRP（层次风险平价）的第一步也是类似的树形聚类。真实数据中行业内相关性没这么整齐，MST 常呈现以几只龙头股为中心的星形结构。

A.4 计数与概率（原书附录 C）——速查

本部分与第 02 册高度重叠：计数见第 02 册第 1 章，概率公理与条件概率、Bayes 公式见第 2、3 章，随机变量、期望、方差和常见离散分布见第 04a、04b 章，期望的性质见第 07a 章，Markov 不等式等极限定理工具见第 8 章。下面只列出公式，以及原书本附录中 C.5 节的二项分布尾界（第 02 册未按这种方式展开）。

A.4.1 计数

A.4.2 概率与随机变量

• 公理：\(\Pr\{A\}\ge0\)，\(\Pr\{S\}=1\)，互斥事件可加。推论 \(\Pr\{A\cup B\}=\Pr\{A\}+\Pr\{B\}-\Pr\{A\cap B\}\)；Boole 不等式（union bound）\(\Pr\{\bigcup A_i\}\le\sum\Pr\{A_i\}\)（C.19）。
• 条件概率 \(\Pr\{A\mid B\}=\Pr\{A\cap B\}/\Pr\{B\}\)；Bayes 公式
  \[\Pr\{A\mid B\}=\frac{\Pr\{A\}\Pr\{B\mid A\}}{\Pr\{A\}\Pr\{B\mid A\}+\Pr\{\bar A\}\Pr\{B\mid\bar A\}}.\tag{C.18}\]
  原书例：一枚公平硬币、一枚总出正面的硬币，随机选一枚抛两次都是正面，选中偏硬币的后验概率为 \(\frac{(1/2)\cdot1}{(1/2)\cdot1+(1/2)\cdot(1/4)}=\frac45\)。第 31 章 Miller–Rabin 的贝叶斯分析、因子挖掘的假阳性分析都是这个公式。
• 两两独立 ≠ 相互独立：两枚硬币，\(A_1\)=第一枚正面，\(A_2\)=第二枚正面，\(A_3\)=两枚不同。三者两两独立，但 \(\Pr\{A_1\cap A_2\cap A_3\}=0\ne1/8\)。
• 期望线性性 \(E[X+Y]=E[X]+E[Y]\)，不需要独立；独立时 \(E[XY]=E[X]E[Y]\)。取值于 \(\mathbb N\) 的变量 \(E[X]=\sum_{i\ge1}\Pr\{X\ge i\}\)（C.25）。
• 方差 \(\mathrm{Var}[X]=E[X^2]-E^2[X]\)；\(\mathrm{Var}[aX]=a^2\mathrm{Var}[X]\)；两两独立即可使方差可加（C.29）。
• Jensen 不等式：凸函数 \(f\) 有 \(E[f(X)]\ge f(E[X])\)（C.26）。Markov 不等式：\(X\ge0\) 时 \(\Pr\{X\ge t\}\le E[X]/t\)（C.30）。
• 几何分布（首次成功所需次数）：\(\Pr\{X=k\}=q^{k-1}p\)，\(E=1/p\)，\(\mathrm{Var}=q/p^2\)。例：掷两颗骰子直到和为 7 或 11，\(p=8/36\)，平均 4.5 次。
• 二项分布：\(b(k;n,p)=\binom nkp^kq^{n-k}\)，\(E=np\)（用期望线性性一行得出），\(\mathrm{Var}=npq\)；单峰，众数在 \(np-q<k<(n+1)p\) 内（式 C.41 的相邻项比值）。

量化提示：组合收益的期望是各资产期望的加权和，不需要任何独立性；但方差可加需要不相关——这正是组合风险里协方差项不能省的原因。Jensen 不等式解释了几何平均收益不超过算术平均收益（对数是凹函数），以及凸收益（期权）的"凸性价值"。

A.4.3 二项分布的尾部（原书 C.5 节）

设 \(X\) 为 \(n\) 次独立伯努利试验的成功次数，\(\mu=E[X]\)。

定理 C.8 的证明是标准的 Chernoff 方法：对 \(\alpha>0\) 用 Markov 不等式得 \(\Pr\{X-\mu\ge r\}\le E[e^{\alpha(X-\mu)}]e^{-\alpha r}\)；由独立性把矩母函数拆成乘积；用 \(1+x\le e^x\) 得 \(E[e^{\alpha(X-\mu)}]\le\exp(\mu e^\alpha)\)；最后取 \(\alpha=\ln(r/\mu)\) 使界最小。

推导拆解：第一步，\(X-\mu\ge r\) 与 \(e^{\alpha(X-\mu)}\ge e^{\alpha r}\) 是同一事件（\(\alpha>0\) 时指数函数严格递增），对非负变量 \(e^{\alpha(X-\mu)}\) 用 Markov 不等式即得。第二步，\(X=\sum X_i\) 且各 \(X_i\) 独立，所以 \(E[e^{\alpha\sum(X_i-p_i)}]=\prod E[e^{\alpha(X_i-p_i)}]\)——独立变量乘积的期望等于期望的乘积。第三步，每个因子 \(p_ie^{\alpha q_i}+q_ie^{-\alpha p_i}\le p_ie^\alpha+1\le\exp(p_ie^\alpha)\)（先把两个指数分别放大到 \(e^\alpha\) 和 1，再用 \(1+x\le e^x\)），连乘得 \(\exp(\mu e^\alpha)\)。第四步，整个界是 \(\exp(\mu e^\alpha-\alpha r)\)，对 \(\alpha\) 求导令其为 0：\(\mu e^\alpha=r\)，即 \(\alpha=\ln(r/\mu)\)（要求 \(r>\mu\) 才有 \(\alpha>0\)）。代回得 \(\exp(r-r\ln(r/\mu))=(\mu e/r)^r\)。第三步的放大比较粗，这正是 A.4.4 里这个界在中等偏离下没有信息的原因。

白话解释：Chernoff 方法的核心是"先指数化再用 Markov"。Markov 只用到一阶矩，界很松；指数化后等于同时利用了所有阶矩，尾界从多项式衰减变成指数衰减。相关的不等式汇总见 第 00 册第 07 章 概率中的分析工具。

A.4.4 量化小例：胜率显著性与尾界的松紧

策略做了 200 笔交易，盈利 \(k\) 笔。若真实胜率只有 50%，出现这么多盈利笔数的概率是多少？比较精确二项尾概率与上表中的各种界，并加上标准的 Hoeffding 界 \(e^{-2r^2/n}\)。

from math import comb, e, exp
from scipy.stats import binom

n, p = 200, 0.5
mu = n * p
fmt = lambda b: f"{b:9.2e}" if b < 1 else "   >=1   "      # 界 >= 1 时没有信息
print("  k   精确尾概率   C.2: C(n,k)p^k   C.8: (μe/r)^r   C.5-6: e^{-r²/2n}   Hoeffding: e^{-2r²/n}")
for k in (110, 120, 130, 150, 180):
    r = k - mu
    exact = binom.sf(k - 1, n, p)                    # P(X >= k)
    print(f"{k:3d}   {exact:9.2e}      {fmt(comb(n, k) * p ** k)}       {fmt((mu * e / r) ** r)}"
          f"        {fmt(exp(-r ** 2 / (2 * n)))}          {fmt(exp(-2 * r ** 2 / n))}")

输出：

  k   精确尾概率   C.2: C(n,k)p^k   C.8: (μe/r)^r   C.5-6: e^{-r²/2n}   Hoeffding: e^{-2r²/n}
110    8.95e-02         >=1             >=1            7.79e-01           3.68e-01
120    2.84e-03         >=1             >=1            3.68e-01           1.83e-02
130    1.33e-05         >=1             >=1            1.05e-01           1.23e-04
150    4.20e-13         >=1             >=1            1.93e-03           1.39e-11
180    1.13e-33       1.05e-27          >=1            1.13e-07           1.60e-28

结论：

• 55% 的胜率（110/200）在 50% 的原假设下有约 9% 的概率出现，不显著；60%（120/200）的单侧 \(p\) 值约 0.003。
• 原书定理 C.2 和 C.8 的界在这个区间完全没有信息：C.8 只有 \(r>e\mu\) 时才小于 1，它是为 \(\mu\) 很小的问题（如"球与箱"中某个箱子的球数、散列表的最长链）设计的。C.5-6 的 Hoeffding 型界比标准 Hoeffding 界弱（指数上差 4 倍）。所有界都比精确值松几个数量级。
• 做显著性检验时直接用精确二项分布或正态近似；集中不等式的价值在于不需要知道分布、可用于证明（例如随机算法的成功概率），以及给出与样本量的定量关系：Hoeffding 界告诉你，要以 \(1-\delta\) 的把握把胜率估计误差控制在 \(\epsilon\) 内，需要 \(n\ge\frac{\ln(2/\delta)}{2\epsilon^2}\) 笔交易（双侧）。还要记住这些界都假设各笔交易独立，而真实交易收益常有序列相关和状态依赖。

A.5 矩阵（原书附录 D）——速查

本部分是第 01 册第 00 章（矩阵基础复习）的子集，正定矩阵的系统理论见第 01 册第 07a–07d 章。这里列出原书的记号与结论。

A.5.1 定义与运算

• \(A=(a_{ij})\) 为 \(m\times n\) 矩阵，转置 \(A^T\)；向量默认是列向量；\(e_i\) 为单位向量。
• 特殊方阵：对角 \(\mathrm{diag}(\cdot)\)、单位 \(I_n\)、三对角、上/下三角（对角线全为 1 称单位三角）、置换矩阵（每行每列恰一个 1，\(PA\) 置换行、\(AP\) 置换列，\(P^{-1}=P^T\)）、对称（\(A=A^T\)）。
• 乘法 \(c_{ij}=\sum_ka_{ik}b_{kj}\)（D.2），朴素算法 \(\Theta(n^3)\)；满足结合律、分配律，\(n>1\) 时不满足交换律，例 \(\begin{pmatrix}0&1\\0&0\end{pmatrix}\begin{pmatrix}0&0\\1&0\end{pmatrix}=\begin{pmatrix}1&0\\0&0\end{pmatrix}\)，交换次序得 \(\begin{pmatrix}0&0\\0&1\end{pmatrix}\)。
• 内积 \(x^Ty\)，外积 \(xy^T\)，欧氏范数 \(\|x\|=\sqrt{x^Tx}\)。\((AB)^T=B^TA^T\)，所以 \(A^TA\) 总是对称的（习题 D.1-2）。

A.5.2 逆、秩、行列式、正定

• 逆：\(AA^{-1}=A^{-1}A=I\)，存在则唯一；\((BA)^{-1}=A^{-1}B^{-1}\)，\((A^{-1})^T=(A^T)^{-1}\)。无逆的称奇异。
• 线性相关：存在不全为 0 的系数使线性组合为零向量。例：\((1,2,3)\)、\((2,6,4)\)、\((4,11,9)\) 满足 \(2x_1+3x_2-2x_3=0\)。
• 秩：最大线性无关列（行）组的大小，行秩 = 列秩。等价定义：使 \(A=BC\)（\(B\) 为 \(m\times r\)、\(C\) 为 \(r\times n\)）成立的最小 \(r\)——这正是低秩因子模型的结构。\(\mathrm{rank}(AB)\le\min(\mathrm{rank}A,\mathrm{rank}B)\)（习题 D.2-8）。
• 等价条件（定理 D.1、D.2、D.5、推论 D.3）：方阵 \(A\) 满秩 ⇔ 非奇异 ⇔ 没有零向量（\(Ax=0\) 只有零解）⇔ \(\det A\ne0\)。
• 行列式按第一行展开递归定义；性质（定理 D.4）：某行全零则为 0，一行乘 \(\lambda\) 则乘 \(\lambda\)，一行加到另一行不变，转置不变，交换两行变号，\(\det(AB)=\det A\det B\)。三角矩阵的行列式是对角元之积。
• 正定：对所有非零 \(x\) 有 \(x^TAx>0\)。定理 D.6：\(A\) 列满秩 ⇒ \(A^TA\) 正定。证明：\(x^TA^TAx=\|Ax\|^2\ge0\)，等于 0 时 \(Ax=0\)，由列满秩 \(x=0\)。

金融直觉：把 \(A\) 看成去均值的收益矩阵（每行一期、每列一只股票），\(x\) 看成组合权重，那么 \(Ax\) 是组合每期的收益序列，\(x^TA^TAx=\|Ax\|^2\) 正比于组合的样本方差。正定就是"任何非零组合的样本方差都大于 0"。列满秩失败意味着存在一个非零组合 \(x\)，在样本期内每一期收益都恰好为 0——样本认为它"零风险"，最小方差优化就会往这个方向加杠杆。A.5.3 就是这个现象。正定与特征值的关系见 第 00 册第 06 章 线性代数速成。

• 思考题 D-1：范德蒙德矩阵的行列式 \(\prod_{j<k}(x_k-x_j)\)，是第 30 章插值唯一性（定理 30.1）的依据。思考题 D-2 讨论 GF(2) 上矩阵定义的置换（线性置换），用计数论证说明线性置换远少于全部 \((2^n)!\) 个置换。

数值计算中几乎从不直接用行列式或显式求逆：判断奇异性看条件数或奇异值，解方程用 LU、Cholesky 或 QR 分解（第 01 册、第 04 册）。

A.5.3 量化小例：样本协方差矩阵何时奇异

\(T\) 期观测、\(N\) 只股票，去均值后的收益矩阵 \(R_c\) 为 \(T\times N\)，样本协方差 \(S=R_c^TR_c/(T-1)\)。去均值使 \(R_c\) 的各行之和为零，所以 \(\mathrm{rank}(R_c)\le T-1\)，从而 \(\mathrm{rank}(S)\le\min(N,T-1)\)。由定理 D.6，只有 \(R_c\) 列满秩（需要 \(T-1\ge N\)）时 \(S\) 才正定。

import numpy as np

rng = np.random.default_rng(0)
N = 100
for T in (60, 100, 101, 250):
    R = rng.standard_normal((T, N)) * 0.02
    S = np.cov(R, rowvar=False)                      # = Rc^T Rc / (T-1)
    eig = np.linalg.eigvalsh(S)
    cond = "∞（奇异）" if eig.min() < 1e-12 * eig.max() else f"{eig.max() / eig.min():.1e}"
    print(f"T={T:3d}: rank = {np.linalg.matrix_rank(S):3d}, 最小特征值 {eig.min():+.1e}, 条件数 {cond}")

T = 60                                               # T < N：收缩到对角目标后正定
R = rng.standard_normal((T, N)) * 0.02
S = np.cov(R, rowvar=False)
alpha = 0.3
S_shrink = (1 - alpha) * S + alpha * np.diag(np.diag(S))
print("收缩后 rank =", np.linalg.matrix_rank(S_shrink), "，最小特征值 %.2e" % np.linalg.eigvalsh(S_shrink).min())
w = np.linalg.solve(S_shrink, np.ones(N)); w /= w.sum()
print("最小方差组合权重和 %.3f，最大权重 %.3f" % (w.sum(), w.max()))

输出：

T= 60: rank =  59, 最小特征值 -5.6e-19, 条件数 ∞（奇异）
T=100: rank =  99, 最小特征值 -7.0e-20, 条件数 ∞（奇异）
T=101: rank = 100, 最小特征值 +4.0e-09, 条件数 3.8e+05
T=250: rank = 100, 最小特征值 +5.2e-05, 条件数 2.0e+01
收缩后 rank = 100 ，最小特征值 7.33e-05
最小方差组合权重和 1.000，最大权重 0.027

\(T=60\) 或 \(100\) 时秩恰为 \(T-1\)，矩阵奇异，最小方差组合 \(w\propto S^{-1}\mathbf 1\) 无法计算；\(T=101\) 时刚好满秩，但条件数高达 \(10^5\) 量级，求逆会把估计噪声放大成极端权重；\(T=250\) 时条件数降到 20。收缩估计（把 \(S\) 向对角矩阵拉近）、因子模型（\(B\Sigma_fB^T+D\)，低秩加对角）都是为了解决这个问题。收缩强度的选择（Ledoit–Wolf 等）与因子模型见第 06 册第 9 章。

本附录小结

求和部分要熟记几何级数及其导数形式、调和数的对数界，并掌握归纳、逐项放大、拆分、积分近似四种定界方法，注意"大 \(O\) 归纳"和"比值小于 1 但不被常数界住"两个陷阱。集合与关系部分的核心是等价关系与划分一一对应、偏序的极大元与最大元之别；图与树部分的核心是连通分量作为等价类、自由树的六条等价刻画（尤其 \(|E|=|V|-1\)）以及各类树的计数。计数与概率部分的期望线性性、两两独立即方差可加、Bayes 公式是全书概率分析的工具；二项分布的尾界在中等偏离下很松，检验时应用精确分布。矩阵部分的要点是满秩、非奇异、无零向量、行列式非零四者等价，以及列满秩时 \(A^TA\) 正定——样本数少于资产数时样本协方差必然奇异。

练习

基础

1. 证明 \(\sum_{k=1}^n(2k-1)=n^2\)，并用 (A.8) 求 \(\sum_{k\ge0}(k-1)/2^k\)。（原书 A.1-1、A.1-4。答案：后者为 0。）
2. 用望远镜乘积证明 \(\prod_{k=2}^n(1-1/k^2)=\frac{n+1}{2n}\)。（原书 A.1-8。）
3. 用拆分法证明 \(H_n=\Omega(\lg n)\)。（原书 A.2-3。）
4. 证明对称且传递的关系不一定自反，给出反例。（原书 B.2-5。）
5. 证明握手引理，并由此说明任何无向图中度为奇数的顶点有偶数个。（原书 B.4-1。）
6. 证明非空二叉树中度为 2 的结点数比叶数少 1。（原书 B.5-3。）
7. 某限价单在每个时间片以概率 \(p=0.05\) 成交（各时间片独立）。期望要等多少个时间片？等待超过 60 个时间片的概率是多少？（提示：几何分布，\(\Pr\{X>k\}=q^k\)。）

进阶

8. 用 Monty Hall 问题（原书 C.2-9）检验你对 Bayes 公式的理解：换门后中奖概率为什么是 2/3？
9. 构造 \(n\) 个两两独立、但任意 \(k>2\) 个都不相互独立的事件。（原书 C.2-7。）
10. 证明定理 C.8 证明中的最优 \(\alpha=\ln(r/\mu)\)，并完成习题 C.5-6：先证 \(p_ie^{\alpha q_i}+q_ie^{-\alpha p_i}\le e^{\alpha^2/2}\)，再推出 \(\Pr\{X-\mu\ge r\}\le e^{-r^2/2n}\)。
11. 用 Hoeffding 界估计：要以 95% 的把握把策略胜率的估计误差控制在 ±3 个百分点内，至少需要多少笔独立交易？与正态近似的结果比较。
12. 证明 \(\mathrm{rank}(AB)\le\min(\mathrm{rank}A,\mathrm{rank}B)\)，并据此说明：\(N\) 只股票、\(K\) 个因子的模型协方差 \(B\Sigma_fB^T\) 的秩至多为 \(K\)，加上对角特质方差矩阵 \(D\)（对角元为正）后才正定。（原书 D.2-8。）
13. 在 A.3.3 节的代码里把行业因子载荷从 0.8 降到 0.3，观察 MST 聚类还能否恢复行业结构；再把样本长度 \(T\) 从 500 降到 60，解释结果变化。

原书推荐习题：A.1-3，A.1-8，A.2-3，A.2-5，思考题 A-1；B.1-3，B.2-5，B.4-1，B.5-3，B.5-6，思考题 B-1(b)、B-2(b)；C.1-7，C.1-13，C.2-2，C.2-6，C.2-7，C.2-8，C.2-9，C.3-6，C.4-2，C.4-5，C.5-6，思考题 C-1；D.1-2，D.1-4，D.2-3，D.2-6，D.2-7，D.2-8，思考题 D-1。

原书对照