comp4270

what to know before start

O(), Ω(), Θ()

• 渐近复杂度：\(O(\cdot),\ \Omega(\cdot),\ \Theta(\cdot)\)

• 概率统计：\(\Pr[\cdot],\ \mathbb{E}[\cdot],\ \mathrm{Var}[\cdot],\ X\sim\pi\)

一、渐近复杂度符号（Asymptotic Notation）

![[asymptotic-notation-theta-o-omega.png]] \(O(1) < O(\log(n)) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!) < O(n^n)\)
需要注意的是：对数函数在没有底数时，默认底数为 \(2\)；如 \(lg,n = \log n = \log_2 n\)，因为计算机中很多程序是用二分法实现的。

设 f(n), g(n) 为非负函数，且 n 足够大时有意义。

1. \(O(g(n))\)：上界（Big-O）

定义：设 \(f(n)\) 和 \(g(n)\) 是定义域为自然数集 \(N\) 上的函数。若存在正数 \(c\) 和 \(n_0\)，使得对一切 \(n \ge n_0\) 都有 \(0 \le f(n) \le c g(n)\) 成立。

\[ 0\le f(n)\le c\,g(n). \]

则称 \(f(n)\) 的渐进的上界是 \(g(n)\)，记作 \(f(n) = O(g(n))\)。 通俗的说 \(n\) 满足一定条件范围内，函数 \(f(n)\) 的阶不高于函数 \(g(n)\)。

\[ f(n)=O(g(n)) \]

直观：\(f(n)\) 的增长速度“最多”与 \(g(n)\) 同阶（差一个常数倍）。

例子：

\[ 3n+2 = O(n),\qquad n\log n = O(n^2). \]

---

2. \(\Omega(g(n))\)：下界（Big-Omega）

定义：设 \(f(n)\) 和 \(g(n)\) 是定义域为自然数集 \(N\) 上的函数。若存在正数 \(c\) 和 \(n_0\)，使得对一切 \(n \ge n_0\) 都有 \(0 \le c g(n) \le f(n)\) 成立。

\[ 0\le c\,g(n)\le f(n). \]

则称 \(f(n)\) 的渐进的下界是 \(g(n)\)，记作 \(f(n) = \Omega(g(n))\)。通俗的说 \(n\) 满足一定条件范围内，函数 \(f(n)\) 的阶不低于函数 \(g(n)\)。

\[ f(n)=\Omega(g(n)) \]

直观：\(f(n)\) 的增长速度“至少”与 \(g(n)\) 同阶。

例子：

\[ 3n+2=\Omega(n),\qquad n^2=\Omega(n\log n). \]

---

3. \(\Theta(g(n))\)：紧确界（Big-Theta）

定义：\(\Theta(g(n)) = f(n)\)：存在正常量 \(c_1\)、\(c_2\) 和 \(n_0\)，使得对所有 \(n \ge n_0\)，

\[ 0\le c_1 g(n)\le f(n)\le c_2 g(n). \]

若存在正常量 \(c_1\)、\(c_2\)，使得对于足够大的 \(n\)，函数 \(f(n)\) 能夹入”\(c_1 g(n)\) 与 \(c_2 g(n)\) 之间，则 \(f(n)\) 属于集合 \(\Theta(g(n))\)，记作 \(f(n) \in \Theta(g(n))\)。作为代替，我们通常记

\[ f(n)=\Theta(g(n)) \]

直观：\(f(n)\) 与 \(g(n)\) 同一个量级（同时有上界和下界）。

例子：

\[ 3n+2=\Theta(n),\qquad 5n^2+7n=\Theta(n^2). \]

---

二、概率与统计符号

1. \(\Pr[\cdot]\)：概率（Probability）

定义：事件发生的概率，取值在 [0,1]。

\[ \Pr(A)\in[0,1]. \]

常见形式：

\[ \Pr(X=x),\quad \Pr(A\cap B),\quad \Pr(A\mid B). \]

---

2. \(\mathbb{E}[\cdot]\)：期望（Expectation）

定义：随机变量在概率权重下的平均值（长期平均）。

\[ \mathbb{E}[X]. \]

离散型随机变量（取值集合为 \(S\)）：

\[ \mathbb{E}[X]=\sum_{x\in S} x\,\Pr(X=x). \]

连续型随机变量（密度为 \(f_X\)）：

\[ \mathbb{E}[X]=\int_{-\infty}^{\infty} x\,f_X(x)\,dx. \]

更一般地，对函数 g：

\[ \mathbb{E}[g(X)] = \begin{cases} \sum_{x\in S} g(x)\Pr(X=x), & \text{离散}\\ \int_{-\infty}^{\infty} g(x)f_X(x)\,dx, & \text{连续} \end{cases} \]

---

3. \(\mathrm{Var}[\cdot]\)：方差（Variance）

定义：衡量随机变量围绕期望的波动程度。

\[ \mathrm{Var}(X)=\mathbb{E}\!\left[(X-\mathbb{E}[X])^2\right]. \]

常用等价式：

\[ \mathrm{Var}(X)=\mathbb{E}[X^2]-\big(\mathbb{E}[X]\big)^2. \]

性质（常用）：

\[ \mathrm{Var}(aX+b)=a^2\mathrm{Var}(X). \]

---

4. \(X\sim\pi\)：服从分布 \(\pi\)

定义：随机变量 \(X\) 的概率分布是 \(\pi\)。

\[ X\sim\pi. \]

例子：

\[ X\sim\mathcal{N}(0,1),\qquad X\sim\mathrm{Bernoulli}(p),\qquad X\sim\mathrm{Poisson}(\lambda). \]

含义分别为：标准正态分布、参数为 \(p\) 的伯努利分布、参数为\(\lambda\) 的泊松分布。

---

三、快速对照表

符号	名称	核心含义
O(g(n))	上界	增长速度至多是 g(n) 的常数倍
(g(n))	下界	增长速度至少是 g(n) 的常数倍
(g(n))	紧确界	增长速度与 g(n) 同阶
	概率	事件发生的可能性
[]	期望	随机变量平均水平
[]	方差	随机变量波动程度
X	分布记号	X 服从分布

---

四、简短示例（连起来看）

若算法运行时间 \(T(n)=3n+2\)，则：

\[ T(n)=O(n),\quad T(n)=\Omega(n),\quad T(n)=\Theta(n). \]

若随机变量 \(X\sim\mathrm{Bernoulli}(p)\)，则：

\[ \Pr(X=1)=p,\quad \Pr(X=0)=1-p, \]

\[ \mathbb{E}[X]=p,\quad \mathrm{Var}(X)=p(1-p). \] # Tutorial ## Problem 1 ![[problem-1-cards-same-suit.png]] 第一题可以用“指示变量 + 期望线性性”完整做出来。

题目：4n 张牌，4 种花色各 n 张。随机洗牌后，相邻同花色对数的期望是多少？

设随机变量

\[ X=\text{相邻同花色对的总数}. \]

牌位有 \(1,2,\dots,4n，\)所以相邻对一共有 \(4n-1\)个：\((1,2),(2,3),\dots,(4n-1,4n)\)。

对每个 \(i=1,\dots,4n-1\)，定义

\[ I_i= \begin{cases} 1, & \text{第 }i\text{ 张和第 }i+1\text{ 张同花色}\\ 0, & \text{否则} \end{cases} \]

那么

\[ X=\sum_{i=1}^{4n-1} I_i. \]

由期望线性性：

\[ \mathbb E[X]=\sum_{i=1}^{4n-1}\mathbb E[I_i] =\sum_{i=1}^{4n-1}\Pr(I_i=1). \]

现在算\(\Pr(I_i=1)\)（任意 i 都一样）：

• 先看第 \(i\) 张，不管它是什么花色；

• 剩下 \(4n-1\)张里，和它同花色的还剩 \(n-1\) 张。

所以

\[ \Pr(I_i=1)=\frac{n-1}{4n-1}. \]

代回去：

\[ \mathbb E[X]=(4n-1)\cdot \frac{n-1}{4n-1}=n-1. \]

结论：

\[ \boxed{\mathbb E[X]=n-1}. \]

补充两个容易错的点：

1. 不是 4n 个相邻对，而是 4n-1 个。

2. 不需要假设这些相邻事件独立；期望线性性永远成立。

Problem 2

![[problem-2-consecutive-runs-of-3-ones.png]] 第二题本质是在数：长度为 2024 的随机比特串里，有多少个位置 i 满足 (第 i 位, 第 i+1 位, 第 i+2 位) = 111。 注意这里允许重叠，因为题目给了 1111 有 2 个（位置 1-3 和 2-4）。

设比特串是 \(B_1,\dots,B_{2024}\)，每位独立且 \(\Pr(B_j=1)=1/2\)。

1. 定义指示变量

\[ I_i=\mathbf 1[(B_i,B_{i+1},B_{i+2})=(1,1,1)],\quad i=1,\dots,2022. \]

为什么是 2022？因为长度为 3 的窗口起点只能到 2024-3+1=2022。

2. 总个数写成和

\[ X=\sum_{i=1}^{2022} I_i. \]

3. 求每一项期望

\[ \mathbb E[I_i]=\Pr(I_i=1)=\Pr(B_i=1,B_{i+1}=1,B_{i+2}=1)=(1/2)^3=1/8. \]

4. 用期望线性性

\[ \mathbb E[X]=\sum_{i=1}^{2022}\mathbb E[I_i]=2022\cdot\frac18=\frac{2022}{8}=\frac{1011}{4}=252.75. \]

结论：

\[ \boxed{\mathbb E[X]=252.75} \]

补充：期望可以不是整数；它表示“重复很多次实验后的平均个数”。 （这里不需要窗口之间独立，线性性直接成立。）

Problem 3

![[problem-3-fixed-point-permutation.png]]

题目：在 \(\{1,2,\dots,n\}\) 的均匀随机排列 \(\pi\) 中，定义不动点为满足 \(\pi(i)=i\)的位置 \(i\)。设 \(X\) 为不动点个数。求 \(E[X]\) 和 \(\mathrm{Var}(X)\)。

1. 定义指示变量

\[ X_i=\mathbf{1}\{\pi(i)=i\},\quad i=1,\dots,n \]

则

\[ X=\sum_{i=1}^n X_i. \]

2. 先求期望 \(E[X]\) 对任意 \(i\)，因为排列均匀随机，\(\pi(i)\) 在 \(1,\dots,n\) 上等可能：

\[ P(\pi(i)=i)=\frac1n. \]

所以

\[ E[X_i]=P(X_i=1)=\frac1n. \]

由期望线性性：

\[ E[X]=\sum_{i=1}^n E[X_i]=\sum_{i=1}^n \frac1n=1. \]

3. 求方差 \(\mathrm{Var}(X)\)

\[ \mathrm{Var}(X)=E[X^2]-E[X]^2. \]

已知 \(E[X]=1\)，只需算 \(E[X^2]\)。

4. 展开 \(X^2\)

\[ X^2=\left(\sum_{i=1}^n X_i\right)^2 =\sum_{i=1}^n X_i^2+\sum_{i\ne j}X_iX_j. \]

取期望：

\[ E[X^2]=\sum_{i=1}^n E[X_i^2]+\sum_{i\ne j}E[X_iX_j]. \] 关键在于“交叉项怎么计数”。

有两种等价写法：

2. 按无序对写： \[ \left(\sum_{i=1}^n X_i\right)^2 = \sum_{i=1}^n X_i^2 + 2\sum_{1\le i<j\le n}X_iX_j \] 这里有系数 \(2\)。

3. 按有序对写： \[ \left(\sum_{i=1}^n X_i\right)^2 = \sum_{i=1}^n X_i^2 + \sum_{i\ne j}X_iX_j \] 这里没有显式的 \(2\)，因为 \((i,j)\) 和 \((j,i)\) 都在 \(\sum_{i\ne j}\) 里，等价于前面的 \(2\sum_{i<j}\)。

所以不是 \(2E[X_i^2]\)。
“2”乘的是交叉项，不是平方项。平方项每个只出现一次。

4. 计算第一项 \(X_i\in\{0,1\}\)，所以 \(X_i^2=X_i\)。因此

\[ \sum_{i=1}^n E[X_i^2]=\sum_{i=1}^n E[X_i]=1. \]

6. 计算第二项

\[ E[X_iX_j]=P(\pi(i)=i,\ \pi(j)=j),\quad i\ne j. \]

用条件概率：

\[ P(\pi(i)=i,\pi(j)=j)=P(\pi(i)=i)\,P(\pi(j)=j\mid \pi(i)=i) =\frac1n\cdot\frac1{n-1} =\frac1{n(n-1)}. \]

而 \(i\ne j\) 的有序对个数是 \(n(n-1)\)，所以

\[ \sum_{i\ne j}E[X_iX_j] =n(n-1)\cdot\frac1{n(n-1)}=1. \]

7. 合并

\[ E[X^2]=1+1=2. \]

\[ \mathrm{Var}(X)=E[X^2]-E[X]^2=2-1^2=1. \]

结论：

\[ \boxed{E[X]=1,\quad \mathrm{Var}(X)=1.} \]

---

知识点总结

1. 指示变量法：计数问题写成 \(X=\sum X_i\)。

2. 期望线性性：\(E[\sum X_i]=\sum E[X_i]\)，不要求独立。

3. 随机排列对称性：\(P(\pi(i)=i)=1/n\)。

4. 平方展开：\((\sum X_i)^2=\sum X_i^2+\sum_{i\ne j}X_iX_j\)。

5. 指示变量性质：\(X_i\in\{0,1\}\Rightarrow X_i^2=X_i\)。

6. 交集概率计算：\(P(A\cap B)=P(A)P(B\mid A)\)，不是默认直接相乘。

7. 有序对计数：\((i,j),i\ne j 共 n(n-1)\) 个。

8. 方差公式：\(\mathrm{Var}(X)=E[X^2]-E[X]^2\)。

Problem 4

![[problem-4-infinite-expectation.png]] 1. 给出一个定义在 \([0,\infty)\) 上的随机变量 \(X\)，使得 \(\mathbb E[X]=\infty\)。

2. 给出一个定义在 \(\mathbb N\) 上的随机变量 \(X\)，使得 \(\mathbb E[X]=\infty\)。

口诀 \[ \sum \frac1{n^p},\ \int_1^\infty \frac1{x^p}dx \]

都是 \(p>1\) 收敛，\(p\le1\) 发散。

看“收敛/发散”就看极限是不是有限数。

1. 积分的收敛/发散（广义积分）
   \[ \int_0^\infty g(x)\,dx:=\lim_{R\to\infty}\int_0^R g(x)\,dx \]

• 极限是有限数：收敛
  
• 极限是 \(\infty\) 或不存在：发散

2. 级数的收敛/发散
   \[ \sum_{n=1}^\infty a_n:=\lim_{N\to\infty}\sum_{n=1}^N a_n \]

• 极限有限：收敛
  
• 否则发散

常用秒判（你现在最有用）：

1. \(p\)-型积分
   \[ \int_1^\infty \frac1{x^p}dx \]

• \(p>1\) 收敛
  
• \(p\le 1\) 发散

2. \(p\)-型级数
   \[ \sum_{n=1}^\infty \frac1{n^p} \]

• \(p>1\) 收敛
  
• \(p\le1\) 发散（如调和级数 \(\sum 1/n\) 发散）

3. 比较法
   如果 \(g(x)\) 在无穷远处“长得像” \(1/x^p\)，就按上面判。
   你那题里： \[ \frac{x}{(1+x)^2}\sim \frac1x \] 所以积分发散，\(E[X]=\infty\)。

---

什么是离散型/连续型随机变量：

1. 离散型（Discrete）
   

• 取值是可数的（如 \(1,2,3,\dots\)）
  
• 用概率质量函数 \(P(X=k)\)
  
• 期望： \[ E[X]=\sum_k k\,P(X=k) \]

2. 连续型（Continuous）
   

• 取值在区间上（不可数）
  
• 用密度函数 \(f(x)\)，满足 \(\int f(x)dx=1\)
  
• \(P(X=a)=0\)（单点概率为0）
  
• 期望： \[ E[X]=\int x f(x)\,dx \]

一句话：
- 离散型用“求和”
- 连续型用“积分”。

3步模板（构造 \(E[X]=\infty\)）

1. 先选“慢衰减尾巴” 连续型常用：\(f(x)\sim 1/x^2\)（在 \([1,\infty)\)） 离散型常用：\(p_n\sim 1/n^2\)

2. 调成合法分布（总概率=1） 连续：乘常数 C 让 \(\int f=1\) 离散：乘常数 C 让 \(\sum p_n=1\)

3. 检查期望 连续：\(\int x f(x)\,dx\) 是否发散（通常变成 \(\int 1/x\)） 离散：\(\sum n p_n\) 是否发散（通常变成 \(\sum 1/n\)）

4. 连续（\([0,\infty)\)）

\[ f(x)=\frac1{(1+x)^2},\quad x\ge0 \]

\[ \int_0^\infty f(x)\,dx=1,\qquad E[X]=\int_0^\infty \frac{x}{(1+x)^2}dx=\infty \]

5. 离散（\(\mathbb N\)）

\[ P(X=n)=\frac1{n(n+1)},\quad n\ge1 \]

\[ \sum_{n=1}^\infty P(X=n)=1,\qquad E[X]=\sum_{n=1}^\infty \frac1{n+1}=\infty \]

Problem 5

![[problem-3-fixed-point-permutation.png]]

题目翻译

证明课上的结论：如果随机变量 \(X\) 的方差有限，那么 \[ \mathrm{Var}(X)=\mathbb E[X^2]-\big(\mathbb E[X]\big)^2. \]

解题过程

设 \[ \mu=\mathbb E[X]. \] 由方差定义： \[ \mathrm{Var}(X)=\mathbb E\!\left[(X-\mu)^2\right]. \]

展开平方： \[ (X-\mu)^2=X^2-2\mu X+\mu^2. \]

两边取期望（用期望线性性）： \[ \mathrm{Var}(X)=\mathbb E[X^2]-2\mu\,\mathbb E[X]+\mu^2. \]

因为 \(\mu=\mathbb E[X]\)，所以 \[ \mathrm{Var}(X)=\mathbb E[X^2]-2\mu^2+\mu^2 =\mathbb E[X^2]-\mu^2 =\mathbb E[X^2]-\big(\mathbb E[X]\big)^2. \]

证毕。

知识点

1. 方差定义：\(\mathrm{Var}(X)=\mathbb E[(X-\mathbb E[X])^2]\)
   
2. 代数展开：\((a-b)^2=a^2-2ab+b^2\)
   
3. 期望线性性：\(\mathbb E[A+B]=\mathbb E[A]+\mathbb E[B]\)，\(\mathbb E[cX]=c\,\mathbb E[X]\)
   
4. “方差有限”保证相关期望量是良定义的，推导合法。

Problem 6

![[problem-4-infinite-expectation.png]]

题目翻译

证明课上的结论：如果随机变量 \(X\) 取值于 \(\mathbb N=\{0,1,2,\dots\}\)，且 \(\mathbb E[X]<\infty\)，那么 \[ \mathbb E[X]=\sum_{n=1}^{\infty}\Pr[X\ge n]. \]

解题过程

对每个样本点 \(\omega\)，因为 \(X(\omega)\) 是非负整数，有恒等式 \[ X(\omega)=\sum_{n=1}^{\infty}\mathbf 1_{\{X(\omega)\ge n\}}. \] （若 \(X(\omega)=k\)，右边前 \(k\) 项是 1，后面全是 0，总和就是 \(k\)。）

两边取期望： \[ \mathbb E[X]=\mathbb E\!\left[\sum_{n=1}^{\infty}\mathbf 1_{\{X\ge n\}}\right]. \]

由于求和项非负，可用单调收敛定理（等价地 Tonelli）交换期望与无穷求和： \[ \mathbb E[X] =\sum_{n=1}^{\infty}\mathbb E[\mathbf 1_{\{X\ge n\}}] =\sum_{n=1}^{\infty}\Pr(X\ge n). \]

即得所证。

知识点

1. 非负整数随机变量可写成指示变量和：\(X=\sum_{n\ge1}\mathbf 1_{\{X\ge n\}}\)。
   
2. 指示变量期望：\(\mathbb E[\mathbf 1_A]=\Pr(A)\)。
   
3. 单调收敛定理 / Tonelli：非负项时可交换 \(\mathbb E\) 与无穷和。
   
4. 尾和公式（tail-sum formula）：\(\mathbb E[X]=\sum_{n\ge1}\Pr(X\ge n)\)。
   
5. 条件 \(\mathbb E[X]<\infty\) 保证右侧级数是有限值。

Problem 7

![[problem-7-biased-coin-fair-toss.png]] 中文翻译

题目 7：假设你有一枚有偏硬币，正面概率为 \(p=\Pr[\text{Heads}]\in(0,1)\)，但 p 的值未知。你的目标是：只能使用这枚有偏硬币，生成一次均匀随机的掷硬币结果（即公平硬币结果）。

1. 描述一种实现该目标的策略。

2. 给出一个关于未知参数 p 的界：为了生成一次公平结果，期望需要掷这枚有偏硬币多少次。

---

解题思路（标准做法：Von Neumann 方法）

1. 连掷两次硬币。

2. 若结果是 HT，输出 H；若结果是 TH，输出 T。

3. 若结果是 HH 或 TT，丢弃这一轮，重新做第 1 步。

为什么公平：

\[ \Pr(HT)=p(1-p),\quad \Pr(TH)=(1-p)p \]

两者相等，所以在“接受事件” {HT,TH} 下，

\[ \Pr(\text{输出 }H)=\Pr(\text{输出 }T)=\tfrac12. \]

期望掷币次数：

• 一轮成功概率

\[ q=\Pr(HT\text{ 或 }TH)=2p(1-p). \]

• 需要的轮数 \(N\sim \text{Geom}(q)\)，

\[ \mathbb E[N]=\frac1q. \]

• 每轮 2 次掷币，所以

\[ \mathbb E[T]=2\mathbb E[N]=\frac{2}{2p(1-p)}=\frac{1}{p(1-p)}. \]

这个值对该策略是精确值（不只是上界）。 并且不存在与 \(p\) 无关的统一常数上界（当 \(p\to0\) 或 \(p\to1\) 时会变大）。

---

解这题需要知道的知识点

1. 独立伯努利试验（每次掷币独立）。

2. 条件概率与对称性（\(\Pr(HT)=\Pr(TH)\)）。

3. 拒绝采样思想（HH/TT 丢弃重来）。

4. 几何分布的期望（\(\mathbb E[N]=1/q\)）。

5. 期望线性放缩（\(总次数 = 每轮次数 \times 轮数期望\)）。