Estimate Size of Transitive Closure

PCP的那个坑先继续咕一段时间，今天给大家介绍一下最近学到的一个很有意思的问题。本文的idea来自Ilya Razenshteyn, 基于Cohen 94。

一个有向图。我们把能够从点到达的点的集合叫做点的传递闭包，记作。现在我们想知道这个图每个点的传递闭包的大小。对于这个问题的确定性演算法，最好的已知复杂度是 $mathcal O(min(|V||E|), |V|^{2.38}))$ 。

然而如果我们允许随机和近似的话，我们能够做到近乎线性：通过 $mathcal Oleft(frac{mlog^2 n}{epsilon^2} ight)$ 的时间复杂度，对于每个点,我们可以得到的近似使得。

演算法

首先我们对每一个点, 我们随机从指数分布给它赋值，使得 $X_vsim ext{Exp}(1)$ ，并且反转原图所有边的方向。然后，对于所有的, 我们从小到大的取出，从点开始进行BFS，对于被BFS到的点,我们标记,然后删除所有访问过的点。直到所有点都被访问过恰好一次。

我们可以证明,

我们每次都是在选出最小的然后标记在反向图里面能到达的所有点，所以的定义等价于 $Y_v=min_{uin R_v} X_u$ .

指数分布的最小值

定理1: 如果我们有个指数分布的随机变数 $X_1sim ext{Exp}(lambda_1), X_2sim ext{Exp}(lambda_2), ldots,X_nsim ext{Exp}(lambda_n)$ ,那么 $min{X_1,X_2,ldots, X_n} sim ext{Exp}(lambda_1+lambda_2+ldots+lambda_n)$ 。

证明：我们考虑指数分布的cdf的补集：我们知道如果，那么我们计算最小值的cdf的补集 $egin{align*} Pr(min{X_1,ldots, X_n} > t) &= Pr(X_1 > t, X_2 > t, ldots, X_n > t) \ &= prod_{i=1}^n exp(-lambda_i t) \ &=expleft(sum_{i=1}^n lambda_i t<br /> ight) end{align*}$

所以 $min{X_1,X_2,ldots, X_n} sim ext{Exp}(lambda_1+lambda_2+ldots+lambda_n)$ 。

这个告诉我们了 $mathbb E[Y_v] = mathbb E[min_{uin R_v} X_u] = mathbb E[ ext{Exp(|R_v|)}] = 1/|R_v|.$

我们知道了是对一个很好的估计(Estimator)，那么我们需要多少个的样本，才能很好的估计出呢？

Median Trick

事实上，我们只需要 $Oleft(frac{log 1/delta}{epsilon^2} ight)$ 个样本就有很高的概率()得到的估计。

证明：

首先假设我们我们有个的样本，标记为，然后我们取他们的平均值。很显然，此处。为了使用切比雪夫不等式，我们计算它的方差：

$egin{align*} ext{Var}(ar{Z}) &= ext{Var}left(sum_{i=1}^k frac{Z_i}{k} ight) \ &=frac{1}{k^2} ext{Var}(sum_{i=1}^k Z_i) \ &=frac{1}{k^2} cdot k cdot frac{1}{{|R_v|}^2} \ &=frac{1}{k{|R_v|}^2}\ &=frac{mu^2}{k} end{align*}$

同时，我们注意到，当的时候，如果得到了误差在的估计，那么的误差范围在内。

切比学夫不等式告诉我们，

$egin{align*} Pr[|{ar{Z} -mu}| leq 0.5epsilon mu] &geq 1-frac{mu^2}{0.25k epsilon^2 mu^2} \ &=1-frac{1}{0.25kepsilon^2} end{align*}$

我们让 $k= frac{4}{epsilon^2}$ , 我们有大于0.9的概率得到一个的估计。显然这个是不够高的 (考虑到我们后面需要使用union bound)，为了得到更高的概率，我们使用median trick来继续提高成功的概率。

假设我们把上面的过程独立地重复次，把这次的结果标做。我们观察到：如果有一半以上的结果满足条件，那么这些数的中位数也满足条件。

我们定义 $H_i := ??[{R_i in ((1-epsilon){|R_v|}, (1+epsilon){|R_v|})}].$

因为,所以 $mathbb E[sum_{i=1}^ell H_i] = ellcdot sum_{i=1}^ell mathbb E[H_i] geq 0.9l.$

然后我们使用Hoeffding不等式: $Prleft[sum_{i=1}^ell H_i leq frac{ell}{2} ight] leq Prleft[sum_{i=1}^ell H_i - mathbb Eleft[sum_{i=1}^ell H_i ight] > frac{ell}{4}<br /> ight]leq e^{-ell/8}.$

要让 $e^{-ell/8} leq delta$ , 我们只需要让。所以我们一共需要 $ell cdot k=mathcal Oleft(frac{log 1/delta}{epsilon^2} ight)$ 个样本。

总结

根据布尔不等式(Union bound), 我们每次都成功的概率大于, 要让这个概率大于的话，那么，所以我们把原图复制次，然后独立的运行最开始的演算法，我们就有很高的概率得到原图的估计。总的运行时间是: $mathcal Oleft(frac{1}{epsilon^2} cdot mlog^2 n ight).$