Problem 1.1
设 $ \mathcal{F} $ 是一个有限的 $ \sigma $-代数。定义其中“最小"的元素为其包含于 $ \mathcal{F} $ 中的子集仅为自身和空集，形式化地描述，若 $ A\in \mathcal{F} $ 为“最小”的元素，那么如果 $ B\in \mathcal{F} $ 并且 $ B\subseteq A $，那么一定有 $ B\in \{ \emptyset,A \} $。
可以证明这样的元素存在并且有限：如果不存在，那么我们每次任取一个 $ \mathcal{F} $ 中的元素，都能找到属于它的一个更小的元素，但 $ \mathcal{F} $ 是有限集，所以这样的过程不可能一直重复下去，因此“最小”元素必然存在并且有限。
我们设所有这些不同的“最小”元素为 $ S=\{ A_{1},A_{2},\dots,A_{n} \} $。我们先证明这构成了全空间的一个分划：
首先这些元素肯定两两不相交，否则不满足“最小”的定义。假设 $ A_{i}\cap A_{j}= C\neq\emptyset $，根据“最小”，非空的 $ C $ 是 $ A_{i} $ 的子集，一定有 $ C=A_{i} $，同样也有 $ C=A_{j} $，这就推出了 $ A_{i}=A_{j} $，从而矛盾。
其次证明这些元素的并集为全空间。设全空间为 $ X $，并且 $ A=\bigcup_{i=1}^{n}A_{i} $，令 $ A^{c}=X\setminus A $。如果 $ A^{c} $ 不是空集，我们肯定能找出一个“最小元素” $ A'\subseteq A^{c} $，这与我们取出了所有“最小”元素的前题矛盾。因此 $ X=A $，所有“最小”元素的并集为全空间。结合两两不相交的性质，我们就证明了这构成了全空间的一个分划。
下面证明 $ \mathcal{F} $ 的大小为 $ 2^{n} $。我们考虑 $ S $ 的所有子集的集合 $ 2^{S} $。根据 $ \sigma $-代数的性质，由于 $ S $ 的任意一个子集都是若干个 $ \mathcal{F} $ 中元素的并，因此必然也是 $ \mathcal{F} $ 中的元素，于是 $ \mathcal{F} $ 中至少有 $ 2^{\left| S \right|}=2^{n} $ 个元素。如果除此之外 $ \mathcal{F} $ 中还有别的元素，根据上面的证明，这违反了 $ S $ 为全空间的分划的条件，因此 $ \mathcal{F} $ 的大小为 $ 2^{n} $。
综上我们证明了有限 $ \sigma $-代数 $ \mathcal{F} $ 的大小为 $ 2^{n} $，并且能找到一个恰有 $ n $ 个元素的全空间的分划。
Problem 1.2
(1)
设每个人的生日为 $ b_{k} $，那么样本空间 $ \Omega=\{ (b_{1},b_{2},\dots,b_{n})| b_{k}\in[m]\text{ for }k\in[n]\} $。对于事件 $ A_{i,j} $ 表示 $ i $ 和 $ j $ 在同一天，我们有 $$ A_{i,j} = \{ (b_{1},b_{2},\dots,b_{n})\in\Omega : b_{i} = b_{j} \} $$ 因此 $ \left| A_{i,j} \right|=m\cdot m^{n-2} $，可以得到 $ \mathbb{P}(A_{i,j})= \frac{\left| A_{i,j} \right|}{\left| \Omega \right|}=\frac{1}{m} $。
要证明两两独立性，我们需要证明对于任意两个不同事件 $ A_{i,j},A_{k,l} $（其中 $ i< j,k< l $ 并且 $ \{ i,j \}\neq \{ k,l \} $），需要有 $$ \mathbb{P}(A_{i,j}\cap A_{k,l})=\mathbb{P}(A_{i,j})\cdot \mathbb{P}(A_{k,l}) = \dfrac{1}{m^{2}} $$ 下面我们计算 $ \left| A_{i,j}\cap A_{k,l} \right| $。分类讨论。
如果 $ \{ i,j \}\cap \{ k,l \}\neq \emptyset $，也就是两个事件共享某一个学生，此时确定三个人的生日相同，有 $$ |A_{i,j}\cap A_{k,l}| = m\cdot m^{n-3} = m^{n-2} $$ 如果 $ \{ i,j \}\cap \{ k,l \}=\emptyset $，此时 $$ \left| A_{i,j}\cap A_{k,l} \right| = m^{2}\cdot m^{n-4}=m^{n-2} $$ 因此无论那种情况，都有 $$ \mathbb{P}(A_{i,j}\cap A_{k,l})=\dfrac{\left| A_{i,j}\cap A_{k,l} \right| }{\left| \Omega \right| }= \dfrac{1}{m^{2}} $$ 因此 $$ \mathbb{P}(A_{i,j}\cap A_{k,l})=\mathbb{P}(A_{i,j})\cdot \mathbb{P}(A_{k,l}) $$
于是证明了 $ A_{i,j} $ 两两独立。
(2)
我们直接考虑 $ A_{1,2}, A_{2,3}, A_{1,3} $ 三个事件。事件 $ A_{1,2}\cap A_{2,3}\cap A_{1,3} $ 说明 $ 1,2,3 $ 三个人的生日在同一天，因此 $$ \mathbb{P}(A_{1,2}\cap A_{2,3}\cap A_{1,3}) = \dfrac{m\cdot m^{n-3}}{m^{n}} = \dfrac{1}{m^{2}} $$ 然而 $$ \mathbb{P}(A_{1,2})\cdot \mathbb{P}(A_{2,3})\cdot \mathbb{P}(A_{1,3}) = \left( \dfrac{1}{m} \right)^{3} = \dfrac{1}{m^{3}} \neq \mathbb{P}(A_{1,2}\cap A_{2,3}\cap A_{1,3}) $$ 这就说明了它们并不相互独立。
(3)
首先不妨令 $ n\leq m $，否则必然有两个人生日相同，肯定不是满足条件的 $ n $ 的最小值。我们直接考虑班上任意两个人的生日都不相同，设为事件 $ B $，我们需要 $ \mathbb{P}(B)\leq \frac{1}{2} $。下面计算 $ B $ 中含有的样本数量 $$ \left| B \right| = m^{\underline{n}} $$ 因此 $$ \mathbb{P}(B) = \dfrac{m^{\underline{n}}}{m^{n}} = \dfrac{30^{\underline{n}}}{30^{n}} $$ 使用计算机依次计算 $ n=3,4,\dots $ 我们可以发现 $$ \mathbb{P}(B)|_{n=6} \approx 0.59,\quad \mathbb{P}(B)|_{n=7} \approx 0.47 < \dfrac{1}{2} $$ 这就得到了 $ n_{\min}=7 $。
Problem 1.3
(1) $$ \begin{align*} \\ F \searrow E \implies & \mathbb{P}(E|F) = \dfrac{\mathbb{P}(EF)}{\mathbb{P}(F)} \leq \mathbb{P}(E) \\ \implies & \mathbb{P}(EF) \leq \mathbb{P}(E)\cdot \mathbb{P}(F) \\ \implies & \mathbb{P}(F|E) = \dfrac{\mathbb{P}(EF)}{\mathbb{P}(E)} \leq \mathbb{P}(F) \\ \implies & E \searrow F \end{align*} $$ (2)
不正确，直接令 $ F,G $ 为发生概率不为 $ 1 $ 的同一个事件，显然这不会违背条件，但是有 $$ \mathbb{P}(G|F) = 1 \not\le \mathbb{P}(G) $$
(3)
不正确。考虑集合 $ \Omega=\{ 1,2,3,4 \} $，每个样本点的概率均为 $ \frac{1}{4} $，我们令 $ E=\{ 1,2 \},F=\{ 1,3 \},G=\{ 1,4 \} $，这时 $$ \mathbb{P}(E|F) = \dfrac{1}{2} \leq \mathbb{P}(E) = \dfrac{1}{2}, \mathbb{P}(E|G) = \dfrac{1}{2}\leq \mathbb{P}(E) = \dfrac{1}{2} $$ 但是 $$ \mathbb{P}(E|(F\cap G)) = 1 \not\leq \mathbb{P}(E) $$
Problem 2
(1)
Case 1：如果 $ j\leq K $，那么必然不会被录用，此时 $ \mathbb{P}(A|B_{j})=0 $。
Case 2：如果 $ j=K+1 $，那么必然被录用，此时 $ \mathbb{P}(A|B_{j})=1 $。
Case 3：如果 $ j>K+1 $，这是如果想要被录用，必须要有前 $ j-1 $ 个面试者中表现最好的人出现在前 $ K $ 轮面试，否则就会先于第 $ j $ 个人被录用。由于出现在每个位置的概率都相等，因此此时 $ \mathbb{P}(A|B_{j})=\frac{K}{j-1} $。
综上， $$ \mathbb{P}(A|B_{j}) = \begin{cases} 0 & ,j\leq K \\ \dfrac{K}{j-1} & ,j >K \end{cases} $$ (2)
由于 $ P(B_{j})=\dfrac{1}{n}\,\text{for }j\in[n] $，因此根据全概率公式，有 $$ \mathbb{P}(A) = \sum_{j=1}^{n} \mathbb{P}(A|B_{j})\cdot \mathbb{P}(B_{j}) = \dfrac{1}{n}\sum_{j=K+1}^{n} \dfrac{K}{j-1} = \dfrac{K}{n}\sum_{j=K}^{n-1} \dfrac{1}{j} $$
(3)
根据提示，在 $ n,K $ 足够大时 $$ \mathbb{P}(A)\approx \dfrac{K}{n}\cdot \ln \dfrac{n}{K} \xlongequal{p= \frac{K}{n}}-p\ln p = \varphi(p) $$ 对 $ \varphi(p) $ 求极值，容易得到在 $ p= \frac{1}{e} $ 时 $ \varphi(p)_{\max}= \frac{1}{e} $。
因此我们取 $ K\approx \dfrac{n}{e} $，可以得到 $$ \mathbb{P}(A)\approx \dfrac{1}{e} \approx 0.368 $$
Problem 3
(1)
由于 $ A_{i,\sigma_{i}}\in \{ 0,1 \} $，因此 $ \prod_{i=1}^{n}A_{i,\sigma(i)}=[\forall i\in[n],A_{i,\sigma(i)}=1]=[\sigma \in T_{n}] $。因此 $ \sum_{\sigma \in S}\prod_{i=1}^{n}A_{i,\sigma(i)} $ 表示 $ T_{n} $ 中的置换的数量。
如果一个映射 $ f\in T_{n} $ 是完美匹配，必然有 $ f $ 是 $ [n] $ 的一个置换，否则无法让 $ V_{1},V_{2} $ 中的点两两匹配（反证法易证）；并且如果 $ f\in T_{n} $ 是 $ [n] $ 的一个置换，带入定义，同样容易证明这是一个完美匹配。因此 $ f $ 是一个完美匹配和 $ f $ 是一个置换为充要条件。因此 $ M $ 成立当且仅当 $ f $ 为一个置换，于是 $ \left| M \right|=\sum_{\sigma \in S}\prod_{i=1}^{n}A_{i,\sigma(i)} $。这就有 $$ \mathbb{P}(M) = \dfrac{\left| M \right| }{\left| T_{n} \right|} = \dfrac{\sum_{\sigma \in S}\prod_{i=1}^{n}A_{i,\sigma(i)}}{\left| T_{n} \right| } $$ (2)
首先根据上一问的分析，事件 $ E_{\emptyset}=M $（映射的值域刚好是 $ [n] $ 等价于这是一个置换）。因此事件 $ E_{\emptyset} $ 的补集 $ E_{\emptyset}^{c} $ 表示 $ f $ 不是满射，值域为 $ \{ 1 \} $ 或 $ \{ 2 \} $，两种可能分别表示元素 $ 2 $ 或元素 $ 2 $ 不在值域中，对应事件 $ E_{2} $ 和 $ E_{1} $，于是 $ E_{\emptyset}^{c}=E_{1}\cup E_{2} $。
根据容斥原理 $$ \mathbb{P}(E_{1}\cup E_{2}) = \mathbb{P}(E_{1}) + \mathbb{P}(E_{2}) - \mathbb{P}(E_{1}E_{2}) $$ 于是 $$ \mathbb{P}(E_{\emptyset}) = 1-\mathbb{P}(E_{1}\cup E_{2}) = 1-\mathbb{P}(E_{1})-\mathbb{P}(E_{2}) + \mathbb{P}(E_{1}E_{2}) $$ 下面我们带入 $ E^{+}_{*} $：
- $ E_{\emptyset}^{+}=T_{n}\implies\mathbb{P}(E_{\emptyset}^{+})=1 $。
- $ E_{\{ 1 \}}^{+} = \bigcap_{j\in \{ 1 \}}E_{j}=E_{1}\implies \mathbb{P}(E_{\{ 1 \}}^{+})=\mathbb{P}(E_{1}) $。
- $ E_{\{ 2 \}}^{+} = \bigcap_{j\in \{ 2 \}}E_{j}=E_{1}\implies \mathbb{P}(E_{\{ 2 \}}^{+})=\mathbb{P}(E_{2}) $。
- $ E_{\{ 1,2 \}}^{+} = \bigcap_{j\in \{ 1,2 \}}E_{j}=E_{1}E_{2}\implies \mathbb{P}(E_{\{ 1 \}}^{+})=\mathbb{P}(E_{1}E_{2}) $。 得到 $$ \mathbb{P}(E_{\emptyset}) = \mathbb{P}(E_{\emptyset}^{+}) - \mathbb{P}(E_{\{ 1 \}}^{+}) - \mathbb{P}(E_{\{ 2 \}}^{+})+\mathbb{P}(E_{\{ 1,2 \}}^{+}) $$ (3)
同理 $ (2) $，我们有 $ E_{\emptyset}^{c}=\bigcup_{i=1}^{n}E_{i} $，根据容斥原理 $$ \mathbb{P}\left( \bigcup_{i=1}^{n}E_{i} \right) = \sum_{r=1}^{n} (-1)^{r-1}\sum_{J\subseteq[n],|J|=r}\mathbb{P}\left( \bigcap_{j\in J}E_{j} \right) $$
$ E_{j} $ 表示映射的值域是 $ [n]\setminus\{ j \} $ 的子集。$ \forall J\subseteq[n] $，我们有 $ [n]\setminus J=\bigcap_{j\in J}([n]\setminus \{ j \}) $，于是 $$ E_{J}^{+} = \bigcap_{j\in J}E_{j} \implies \mathbb{P}(E_{J}^{+}) = \mathbb{P}\left( \bigcap_{j\in J}E_{j} \right) $$ 因此 $$ \sum_{r=1}^{n} (-1)^{r-1}\sum_{J\subseteq[n],|J|=r}\mathbb{P}\left( \bigcap_{j\in J}E_{j} \right) = \sum_{r=1}^{n} (-1)^{r-1}\sum_{J\subseteq[n],|J|=r}\mathbb{P}\left( E_{J}^{+} \right) $$ 带入得到 $$ \begin{align*} \mathbb{P}(M)=\mathbb{P}(E_{\emptyset}) & = 1-\mathbb{P}(E_{\emptyset}^{+}) \\ & = 1 - \sum_{r=1}^{n} (-1)^{r-1}\sum_{J\subseteq[n],|J|=r}\mathbb{P}\left( E_{J}^{+} \right) \\ & = \mathbb{P}(E_{\emptyset}^{+})- \sum_{r=1}^{n} (-1)^{r-1}\sum_{J\subseteq[n],|J|=r}\mathbb{P}\left( E_{J}^{+} \right) \\ & = \sum_{r=0}^{n} (-1)^{r}\sum_{J\subseteq[n],|J|=r}\mathbb{P}\left( E_{J}^{+} \right) \\ & = \sum_{J\subseteq[n]}(-1)^{\left| J \right| }\mathbb{P}(E_{J}^{+}) \end{align*} $$ (4)
要证明 $ \mathbb{P}(E_{J}^{+})=\left( \prod_{i=1}^{n}\left( \sum_{j\in [n]\setminus J} A_{i,j}\right) \right) / \left| T_{n} \right| $，我们只需要证明 $ \left| E_{J}^{+} \right|=\prod_{i=1}^{n}\left( \sum_{j\in [n]\setminus J} A_{i,j}\right) $。
我们需要找出所有在 $ T_{n} $ 中并且值域为 $ [n]\setminus J $ 的映射的数量。对于每个 $ i $，可能的 $ f(i) $ 的数量为 $ \sum_{j\in [n]\setminus J}A_{i,j} $（映射到 $ [n]\setminus J $ 并且图中存在对应的边）。根据乘法原理，由于每个 $ i $ 相互独立，因此总的映射数量为 $$ \left| E_{J}^{+} \right|=\prod_{i=1}^{n}\left( \sum_{j\in [n]\setminus J} A_{i,j}\right) $$ 于是 $$ \mathbb{P}(E_{J}^{+}) = \dfrac{\left| E_{J}^{+} \right| }{\left| T_{n} \right| } = \dfrac{\prod_{i=1}^{n}\left( \sum_{j\in [n]\setminus J} A_{i,j}\right)}{\left| T_{n} \right| } $$ 直接带入 $ (3) $ 中得到的容斥原理公式，即可得到 $$ \begin{align*} \mathbb{P}(M) & = \sum_{J\subseteq[n]}(-1)^{\left| J \right| }\mathbb{P}(E_{J}^{+}) \\ & = \sum_{J\subseteq[n]}(-1)^{\left| J \right| }\dfrac{\prod_{i=1}^{n}\left( \sum_{j\in [n]\setminus J} A_{i,j}\right)}{\left| T_{n} \right| } \\ & = \dfrac{\sum_{J\subseteq[n]}(-1)^{\left| J \right| }\prod_{i=1}^{n}\left( \sum_{j\in [n]\setminus J} A_{i,j}\right)}{\left| T_{n} \right| } \end{align*} $$
Problem 4
(1)
我们定义 $ A_{k} $ 为执行完 $ k $ 次缩边操作以后，最小割 $ C $ 中任意一条边都还没有被删掉的概率，那么 $ p(G,t)=\mathbb{P}(A_{n-t}) $。
为了分析 $ A_{k} $，我们定义事件 $ B_{k} $ 为第 $ k $ 次缩边选择的不是 $ C $ 中的点，于是 $ A_{k}=\bigcap_{i=1}^{k}B_{i} $。因此根据链式法则，得到 $$ p(G,t)=\mathbb{P}(A_{n-t}) = \prod_{i=1}^{n-t}\mathbb{P}\left( B_{i}\bigg|\bigcap_{j=1}^{i-1}B_{i} \right) $$ 我们关心这个概率的下界，需要说明在前 $ i-1 $ 轮都没有选到 $ C $ 中的边的情况下，第 $ i $ 轮时图中剩下的边足够多。设最小割的大小为 $ k $，注意到此时图中每个点的度数都不小于 $ k $，否则直接取这些边就能得到一个更小的割。因此我们可以知道在第 $ i-1 $ 轮结束，剩下 $ n-i+1 $ 个节点时，图中至少有 $ \frac{k}{2}(n-i+1) $ 条边，这就可以得到 $$ \mathbb{P}\left( B_{i}\bigg|\bigcap_{j=1}^{i-1}B_{j} \right) \geq 1 - \dfrac{k}{\frac{k}{2}\cdot(n-i+1)} = \dfrac{n-i-1}{n-i+1} $$ 带入即可得到 $$ \begin{align*} p(G,t) & \geq \prod_{i=1}^{n-t} \frac{n-i-1}{n-i+1} = \dfrac{t(t-1)}{n(n-1)} \\ & = \dfrac{\left\lceil \frac{n}{\sqrt{ 2 }} \right\rceil \left\lceil 1 + \frac{n}{\sqrt{ 2 }} \right\rceil }{n(n-1)} \\ & \geq \dfrac{\left\lceil n + \sqrt{ 2 } \right\rceil }{2(n-1)} > \dfrac{1}{2} \end{align*} $$ (2)
我们定义事件 $ A_{1},A_{2} $ 分别表示把图缩到 $ G_{1},G_{2} $ 后没有删掉 $ C $ 中的边，事件 $ B_{1},B_{2} $ 分别表示 KS 算法以 $ G_{1},G_{2} $ 为输入，正确输出了最小割。
根据第一问，$ \mathbb{P}(A_{i})=p(G,t)> \frac{1}{2} $。根据题目条件，$ \mathbb{P}(B_{i})=p(t)> \frac{c}{\log t} $。由于事件 $ A_{i},B_{i} $ 独立（两个算法互不干扰），因此我们对于一个图先执行 contract 算法再执行 KS 算法能正确输出最小割的概率为
$$
\mathbb{P}(A_{i}\cap B_{i})=\mathbb{P}(A_{i})\cdot\mathbb{P}(B_{i}) > \dfrac{1}{2}\cdot \dfrac{c}{\log t} \xlongequal{c' = c / 2} \dfrac{c'}{\log t}
$$
由于我们最后选择的是较小的边集，因此 $ \text{KS}(G_{1}),\text{KS}(G_{2}) $ 中只要有一个正确输出了最小割，我们就可以成功找到最小割，因此正确输出最小割的概率为
$$
\begin{align*}
p_{\text{success}} & = 1- (1-\mathbb{P}(A_{1}\cap B_{1}))(1-\mathbb{P}(A_{2}\cap B_{2})) \\
& > 1-\left( 1-\dfrac{c'}{\log t} \right)^{2} \\
& = \dfrac{2c'}{\log t} - \dfrac{(c')^{2}}{(\log t)^{2}}
\end{align*}
$$
（经询问 ai 关于 $ \Omega $ 定义后作出）根据 $ \Omega $ 记号的定义，$ f(n)=\Omega(g(n)) $ 说明存在正常数 $ k $ 和 $ n_{0} $ 使得当 $ n\geq n_{0} $ 时，$ f(n)\geq k\cdot g(n) $。
对于 $ p_{\text{succsee}} $，我们有（在 $ n>3 $ 时显然有 $ t< n $） $$ p_{\text{success}} > \dfrac{1}{\log t}\left( 2c' - \dfrac{(c')^{2}}{\log t} \right) > \dfrac{1}{\log n}\left( 2c' - \dfrac{(c')^{2}}{\log t} \right) $$
当 $ n $ 足够大时，我们显然可以使得 $ \log t>c' $，此时 $ 2c'-(c')^{2}/(\log t)>c' $，于是 $$ p_{\text{success}} > \dfrac{1}{\log n}\cdot c' $$ 根据定义，这就证明了 $ p_{\text{success}}=\Omega\left( \frac{1}{\log n} \right) $。
(3)
根据 $ (2) $ 的提示，我们考虑递归调用 contract 算法。下面给出递归算法 $ f $ 的描述：
- 输入：无向图 $ G $，规模为 $ n $。
- 若 $ n\leq n_{0} $（$ n_{0} $ 为一个比较小的边界值），直接暴力求出最小割。
- 否则令 $ t=\lceil 1+n / \sqrt{ 2 } \rceil $，独立分别执行两次
contract算法：- $ G_{1}\leftarrow\text{contract}(G,t) $；
- $ G_{2}\leftarrow\text{contract}(G,t) $。
- 分别对 $ G_{1},G_{2} $ 执行递归，返回 $ \min\{ f(G_{1}),f(G_{2}) \} $。
我们设 $ p(n) $ 为单次执行算法 $ f $ 在规模为 $ n $ 的图 $ G $ 上能达到的正确率，那么我们有 $$ p(n) > 1-\left( 1-\dfrac{1}{2}p(t) \right)^{2} = p(t) - \dfrac{1}{4}p^{2}(t),\quad t = \left\lceil 1+\dfrac{n}{\sqrt{ 2 }} \right\rceil $$ 由于我们只用考虑 $ n $ 较大的情形，因此可以近似地认为 $ t=\frac{n}{\sqrt{ 2 }} $，于是 $$ p(n) > p\left( \dfrac{n}{\sqrt{ 2 }} \right) - \dfrac{1}{4}p^{2}\left( \dfrac{n}{\sqrt{ 2 }} \right) $$ 为了分析这个递推式，我们设递归层数为 $ r=\left\lfloor \log_{\sqrt{ 2 }} \frac{n}{n_{0}} \right\rfloor=\Theta(\log n) $，如果当前递归层数为 $ r-k $，令概率为 $ q_{k} $，于是 $$ q_{k+1} > q_{k} - \dfrac{1}{4}q_{k}^{2} $$ 对这个式子进一步化简 $$ \begin{align*} \dfrac{1}{q_{k+1}} & < \dfrac{1}{q_{k}\left( 1-\frac{1}{4}q_{k} \right)} \\ & = \dfrac{1}{q_{k}}\cdot \dfrac{1}{1-\frac{1}{4}q_{k}} \\ & < \dfrac{1}{q_{k}} \left( 1 + \dfrac{1}{4}q_{k} \right) \\ & = \dfrac{1}{q_{k}} + \dfrac{1}{4} \end{align*} $$ 因此 $$ \dfrac{1}{q_{k}} < \dfrac{1}{q_{0}} + \dfrac{k}{4} = 1 + \dfrac{k}{4} \implies q_{k} > \dfrac{1}{1 + k / 4} = \Omega\left( \dfrac{1}{k} \right) $$ （实际上我们并不是从 $ q_{0} $ 开始迭代，不过这并不影响我们计算下界，为了计算方便，直接从 $ q_{0} $ 开始计算，并且认为 $ q_{0}=1 $）
回到 $ p(n) $，我们这就推出了 $$ p(n) > \dfrac{4}{r+4} \implies p(n) = \Omega\left( \dfrac{1}{\log n} \right) $$ 所以重复算法 $ O(\log n) $ 次可以以比较高的概率得到正确答案。下面我们证明这个概率大于 $ \dfrac{2}{3} $。
设重复算法 $ \lceil \log_{2} n \rceil $ 次，能得到最小割的概率为 $ p_{\text{success}} $，那么 $$ p_{\text{success}} = 1 - (1 - p(n))^{\lceil \log_{2} n \rceil } > 1 - e^{ -p(n) \cdot \lceil \log_{2} n \rceil } $$
由于递归层数 $ r=\left\lfloor 2\log_{2} \dfrac{n}{n_{0}} \right\rfloor $，对于足够大的 $ n $，我们可以忽略小常数 $ n_{0} $，因此 $ r\approx 2\log_{2}n $。于是 $$ p(n) > \dfrac{4}{r+4} \approx \dfrac{2}{\log_{2}n + 2} $$ 带入得到 $$ p_{\text{success}} > 1 - e^{ - \frac{2\log_{2} n}{\log_{2}n + 2} } $$
我们要证明 $ p_{\text{success}}>\frac{2}{3} $，只需要证明 $ \exp\left( - \frac{2\log_{2}n}{\log_{2}n + 2} \right) < \frac{1}{3} $，即 $$ \dfrac{2\log_{2}n}{\log_{2}n + 2} > \ln 3 \approx 1.1 $$ 对于比较大的 $ n $，这是显然成立的。因此我们重复 $ \lceil \log_{2}n \rceil $ 次这个算法能得到正确答案的概率大于 $ \dfrac{2}{3} $。
接着求出这个算法的复杂度。设 $ T(n) $ 表示规模为 $ n $ 的图需要的运算次数，那么我们可以得到递推式 $$ T(n) = 2T\left( \dfrac{n}{\sqrt{ 2 }} \right) + O(m) $$ 如果 $ m=\Theta(n^{2}) $，是稠密图，那么根据主定理，$ T(n)=\Theta(n^{2}\log n) $。
如果为稀疏图，递归项的是主导，复杂度为 $ T(n)=\Theta(n^{2}) $。
综上，算法复杂度为 $ O(n^{2}\log ^{2}n)=\tilde{O}(n^{2}) $。优于原来的算法。