From 8d3344c96d3c3900a80fb857444a97c1f98e7318 Mon Sep 17 00:00:00 2001
From: Tianyi Qiu <gordanqiu@outlook.com>
Date: Thu, 19 Nov 2020 09:02:23 +0800
Subject: [PATCH] feat rand-technique.md

---
 docs/misc/rand-technique.md | 34 +++++++++++++++++++++++++++-------
 1 file changed, 27 insertions(+), 7 deletions(-)

diff --git a/docs/misc/rand-technique.md b/docs/misc/rand-technique.md
index 7aaa243c..7121c6c8 100644
--- a/docs/misc/rand-technique.md
+++ b/docs/misc/rand-technique.md
@@ -4,7 +4,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 前置知识：[随机函数](../misc/random.md)和[概率初步](../math/expectation.md)
 
-本文将对 OI/ICPC 中的随机化相关技巧做一个简单的分类，并对每个分类予以介绍。本文也将介绍一些在 OI/ICPC 中很少使用，但与 OI/ICPC 在风格等方面较为贴近的方法，这些内容前将用 `*` 标注。
+本文将对 OI/ICPC 中的随机化相关技巧做一个简单的分类，并对每个分类予以介绍。本文也将介绍一些在 OI/ICPC 中很少使用，但与 OI/ICPC 在风格等方面较为贴近的方法，这些内容前将用 `(*)` 标注。
 
 这一分类并不代表广泛共识，也并不能囊括所有可能性，因此仅供参考。
 
@@ -56,7 +56,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
     $n\cdot m\leq 2\cdot10^5;q\leq 10^6;\epsilon=0.5,\delta=0.2$
 
 ??? "解法"
-    引理：令 $X_{1\cdots k}$ 为独立的随机变量，且取值在 $[0,1]$ 中均匀分布，则 $\mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1}$ 。
+    引理：令 $X_{1\cdots k}$ 为互相独立的随机变量，且取值在 $[0,1]$ 中均匀分布，则 $\mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1}$ 。
 
     - 证明：考虑一个单位圆，其上分布着 **相对位置** 均匀随机的 $k+1$ 个点，分别在位置 $0,X_1,X_2,\cdots,X_k$ 处。那么 $\min\limits_i X_i$ 就等于 $k+1$ 段空隙中特定的一段的长度。而因为这些空隙之间是“对称”的，所以其中任何一段特定空隙的期望长度都是 $\dfrac 1{k+1}$ 。
 
@@ -71,7 +71,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
     然而，这个算法并不能令人满意。它的输出值的期望是 $\mathrm{E}\Big[\dfrac 1{\min\limits_i X_i}-1\Big]$ ，但事实上这个值并不等于 $\dfrac 1{\mathrm{E}\big[\min\limits_i X_i\big]}-1=k$ ，而（可以证明）等于 $\infty$ 。
 
-    也就是说，我们不能直接把 $\min\limits_i X_i$ 的单次取值放在分母上，而要先算得这个式子的期望，再把期望值放在分母上。
+    也就是说，我们不能直接把 $\min\limits_i X_i$ 的单次取值放在分母上，而要先算得它的期望，再把期望值放在分母上。
 
     怎么算期望值呢？多次随机取平均！
 
@@ -159,8 +159,28 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
     void pop(int &now) { now = merge(nd[now].child[0], nd[now].child[1]); }
     ```
 
+随机堆对堆的形态没有任何硬性或软性的要求，合并操作的期望复杂度对任何两个堆（作为 `merge` 函数的参数）都成立。下证。
+
 ???+ note "期望复杂度的证明"
-    To be written
+    将证，对于任意的堆 $A$ ，从根节点开始每次随机选左或者右走下去（直到无路可走），路径长度（即路径上的结点数）的期望值 $h(A)\leq\log_2 (|A|+1)$。
+
+        - 注意到在前述过程中合并堆 $A,B$ 的期望复杂度是 $O(h(A)+h(B))$ 的，所以上述结论可以保证随机堆的期望复杂度。
+
+    证明采用数学归纳。边界情况是 $A$ 为空图，此时显然。下设 $A$ 非空。
+
+    假设 $A$ 的两个子树分别为 $L,R$ ，则：
+
+    $$
+    \begin{align}h(A)
+    &=1+\frac{h(L)+h(R)}2
+    &\leq1+\frac{\log_2(|L|+1)+\log_2(|R|+1)}2
+    &\leq\log_2{2\sqrt{(|L|+1)(|R|+1)}}
+    &\leq\log_2{\frac{2((|L|+1)+(|R|+1))}2}
+    &\leq\log_2{|A|+1}
+    $$
+
+    证毕。
+
 
 ## 与随机性有关的证明技巧
 
@@ -193,7 +213,7 @@ $$
 **自然常数的使用** ： $\Big(1-\dfrac 1n\Big)^n\leq \dfrac 1e,\forall n\geq1$
 
 -  左式关于 $n\geq 1$ 单调递增且在 $+\infty$ 处的极限是 $\dfrac 1e$ ，因此有这个结论。
--  这告诉我们，如果 $n$ 个独立的坏事件，每个的发生概率为 $1-\dfrac 1n$ ，则它们全部发生的概率至多为 $\dfrac 1e$ 。
+-  这告诉我们，如果 $n$ 个互相独立的坏事件，每个的发生概率为 $1-\dfrac 1n$ ，则它们全部发生的概率至多为 $\dfrac 1e$ 。
 
 **(\*) Hoeffding** 不等式：若 $X_{1\cdots n}$  为互相独立的实随机变量且 $X_i\in [a_i,b_i]$ ，记随机变量 $X:=\sum\limits_{i=1}^n X_i$ ，则
 
@@ -206,7 +226,7 @@ $$
 #### 例子
 
 ???+ note "例：抽奖问题"
-    一个箱子里有 $n$ 个球，其中恰有 $k$ 个球对应着大奖。你要进行若干次独立、等概率的随机抽取，每次抽完之后会把球放回箱子。请问抽多少次能保证以至少 $1-\epsilon$ 的概率，满足 **每一个** 奖球都被抽到至少一次？
+    一个箱子里有 $n$ 个球，其中恰有 $k$ 个球对应着大奖。你要进行若干次独立、等概率的随机抽取，每次抽完之后会把球放回箱子。请问抽多少次能保证以至少 $1-\epsilon$ 的概率，满足 **每一个** 奖球都被抽到至少一次？给出一个尽量紧的上界即可，不要求精确答案。
 
 与该问题类似的模型经常出现在随机算法的复杂度分析中。
 
@@ -216,7 +236,7 @@ $$
     现在有 $k>1$ 个奖球，那么根据 Union Bound ，我们只需保证每个奖球被漏掉的概率都不超过 $\dfrac \epsilon k$ 即可。于是答案是 $-n\log\dfrac \epsilon k$ 。
 
 ???+ note "例：(\*)随机选取一半元素"
-    给出一个算法，从 $n$ 个元素中等概率随机选取一个大小为 $\dfrac n2$ 的子集，保证 $n$ 是偶数。你能使用的唯一的随机源是一枚均匀硬币，同时请你尽可能减少抛硬币的次数。
+    给出一个算法，从 $n$ 个元素中等概率随机选取一个大小为 $\dfrac n2$ 的子集，保证 $n$ 是偶数。你能使用的唯一的随机源是一枚均匀硬币，同时请你尽量减少抛硬币的次数（不要求最少）。
 
 ??? note "解法"
     首先可以想到这样的算法：
-- 
2.11.0