Estimate Size of Transitive Closure
PCP的那個坑先繼續咕一段時間，今天給大家介紹一下最近學到的一個很有意思的問題。 本文的idea來自Ilya Razenshteyn, 基於Cohen 94。
一個有向圖。我們把能夠從點到達的點的集合叫做點的傳遞閉包，記作。現在我們想知道這個圖每個點的傳遞閉包的大小。對於這個問題的確定性演算法，最好的已知複雜度是。
然而如果我們允許隨機和近似的話，我們能夠做到近乎線性：通過的時間複雜度，對於每個點,我們可以得到的近似使得。
演算法
首先我們對每一個點, 我們隨機從指數分佈給它賦值， 使得， 並且反轉原圖所有邊的方向。然後，對於所有的, 我們從小到大的取出，從點開始進行BFS，對於被BFS到的點,我們標記,然後刪除所有訪問過的點。直到所有點都被訪問過恰好一次。
我們可以證明,
我們每次都是在選出最小的然後標記在反向圖裡面能到達的所有點，所以的定義等價於.
指數分佈的最小值
定理1: 如果我們有個指數分佈的隨機變數,那麼。
證明： 我們考慮指數分佈的cdf的補集：我們知道如果，那麼我們計算最小值的cdf的補集
所以。
這個告訴我們了
我們知道了是對一個很好的估計(Estimator)，那麼我們需要多少個的樣本，才能很好的估計出呢？
Median Trick
事實上，我們只需要個樣本就有很高的概率()得到的估計。
證明：
首先假設我們我們有個的樣本，標記為，然後我們取他們的平均值。很顯然，此處。 為了使用切比雪夫不等式，我們計算它的方差：
同時，我們注意到，當的時候，如果得到了誤差在的估計，那麼的誤差範圍在內。
切比學夫不等式告訴我們，
我們讓, 我們有大於0.9的概率得到一個的估計。顯然這個是不夠高的 (考慮到我們後面需要使用union bound)，為了得到更高的概率，我們使用median trick來繼續提高成功的概率。
假設我們把上面的過程獨立地重複次，把這次的結果標做。我們觀察到：如果有一半以上的結果滿足條件，那麼這些數的中位數也滿足條件。
我們定義
因為,所以
然後我們使用Hoeffding不等式:
要讓, 我們只需要讓。所以我們一共需要個樣本。
總結
根據布爾不等式(Union bound), 我們每次都成功的概率大於, 要讓這個概率大於的話，那麼，所以我們把原圖複製次，然後獨立的運行最開始的演算法，我們就有很高的概率得到原圖的估計。 總的運行時間是:
推薦閱讀：