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).$