目前人在第三章, 但理解應該只有到第二章...
這是一篇寫得相當清楚的文章,
動機充足, 技術細節也寫得簡潔, 難怪別人也常引用它!
第一章提到 Expander 這種擁有某種 "特殊性質" 的圖被造出來的三個用途,
目前先嘗試的講其中一種, 也就是減少 random bits 的使用量.
考慮底下這樣的問題:
若有一個問題 Q, 假設我們有一個演算法能在 poly. time 決定給定的 input 是不是在 Q 中,
若在的話我們有 1/16 的機率會答錯成不在, 而若不在的話一定不會答錯.
(注: 這樣的問題的集合稱作 RP, randomized poly. time, 1/16 是亂定的, 小於 1/2 就可以)
請問若原先的演算法需要 k 個 random bits,
那若我們想將錯誤的機率 1/16 降到某個夠小的 e (例如 1/2^100),
需要多少個 random bits?
最直接的想法, 就是將原先的演算法跑個 L 次,
這樣錯誤率就會降至 (1/16)^L = 1/2^4L.
在題目中我們令 e = 1/2^100, 因此 L = 25.
這時, 我們需要 k*L = 25k 個 random bits.
Expander graph 厲害的地方,
就在於同樣重複執行了數次的演算法,
它仍然只需要 k 個 random bits!!
(當然, 這裡用了一些骯髒的手段, 例如只有對於 input 長度夠大時才行)
我們先定義 (n,m,d)-expander 為一張 bipartite graph G = (L,R,E),
|L| = n, |R| = m, 分別為圖的兩個點集,
而任意點 v in L 都有 d 個鄰居在 R 中,
滿足底下的延展性質(expansion properties):
(1) N(S) >= 5/8 * d * |S| 對於所有 L 的子集 S 滿足 |S| <= n/10d;
(2) N(S) >= |S| 對於所有 L 的子集 S 滿足 n/10d < |S| <= n/2.
換句話說, expander graph 所擁有的特殊性質其實就是:
對於每個點的子集, 它們的鄰居都很多!
當然第一個問題就是, 真的會有這麼好的圖嗎?
下面的引理保證了這件事.
Lemma. 對於夠大的 (n,m,d), (n,m,d)-expander 存在.
因此, 我們可以利用這樣的圖來讓演算法的錯誤機率降低,
同時又不使用額外的 random bits.
令原先的演算法為 M(x,r), x 是 input, 而 r 是 random bits.
因此我們有 M(x,r) = 0 若 x 不在 Q 中,
而有 1/16 的機率 M(x,r) = 0 且 x 在 Q 中.
固定一個 x 在 Q 中,
我們把這種壞掉不好的 r 的集合取名叫 B = {r in {0,1}^k | M(x,r) = 0}.
這時我們有的資訊很少, 若我們令 n = 2^k,
先固定一個 (n,n,d)-expander (L,R,E),
(n 其實也就是所有長度為 k 的 random bits 的數量, 同時也是 L 跟 R 的大小)
我們知道 B 是 L 跟 R 的一個子集, 而且 B 很小, 只有 <= n/16.
我們可以想像演算法選了某一個 r, 就像是從 L 中挑一個點一樣.
利用 expander 的延展性, 我們現在要從 R 的子集當中選出 d 個點,
讓演算法執行 M(x,r_1), ..., M(x,r_d),
如果其中有任何一次它成功的回答 M(x,r_i) = 1,
我們就知道其實 x 是在 Q 中的. (因為如果不在, 演算法一定答 0)
不然就還是回答 x 不在 Q 中.
這時答錯的機率有多少呢?
唯有當我們選到的 r_1, ... r_d 通通都掉在 B 裡!
怎麼選呢? 我們就從剛剛用 k 個 random bits 選出的 L 中的一點,
取它在 R 中的 d 個鄰居!!(這就是省 random bits 的所在! 因為鄰居是固定的!)
我們來算算這 d 個鄰居都在 B 中的機率:
令 S 是 L 的子集合, 包含了所有點 v 使得 N(v) 都在 B 中;
只要算出 S 的大小, 就是答錯的機率了.
假設 |S| > n/10d, 會得到以下的矛盾:
|B| >= |N(S)| > 5/8 * d * |S| > 5/8 * d * n/10d = n/16,
這樣跟 B 的大小矛盾!
所以, 我們有 |S| <= n/10d, 換句話說,
錯誤率只有 1/10d!!!
回想剛剛的例子中 e = 1/2^100,
如果我們選 d = 2^100/10,
一切就搞定了...
甚至更可怕的, 對於任意的 e,
我們只要選一個鄰居夠多(d 夠大) 的 (n,n,d)-expander 就好了!
無怪乎 expander 是這樣強大的工具...
什麼? 你說減少 random bits 有什麼用?
哼哼... 請期待下集 (對不起我累了... 下次再打!)
