Friday, September 18, 2009

Extended Chernoff-Hoeffding bounds

Sriram V. Pemmaraju 在 APPROX-RANDOM 2001 發表了一篇paper
title 是 Equitable coloring extends Chernoff-Hoeffding bounds.
一般來說,使用 Chernoff bounds 會有一個重大的限制,就是 random variables 必須是 mutually indepedent 才行。而 Pemmaraju's 這篇文章裡,證明了當這些隨機變數代表的事件存在著相依性的時候,我們仍然可得到形如 Chernoff-Hoeffding bounds 的 sharp bounds (i.e., exponentially small tail probability)。


這些事件可以用 dependency graph 來表示,也就是說,每個點代表一個事件,而對於事件 i 而言,如果 (i,j) 沒有邊,那麼事件 i 對於這些事件 j 而言是 mutually independent,亦即 Pr[Event i | for all j, \bigcap_j Event j] = Pr [Event i] 如果有唸過 Lov\'{a}sz Local Lemma (LLL) 的話,你就知道這裡所說的 dependency graph 與 LLL 那邊的一樣。當 dependency graph 的 degree 有上限 d 的時候,Pemmaraju 算出了類似 Chernoff bounds 的一些 bounds。甚至當 dependency graph 為 trees 或 outerplanar 的時候,一樣也可以推導出 sharp bounds。證明的原理是利用 equitable coloring 的性質 (任兩個 color classes 的 size 大小相差至多為 1),以及同一個 color class 裡頭的 vertices 必為 independent set,因此可以局部套用傳統的 Chernoff bounds。

當初會找到這篇文章,是因為手頭的問題需要一個夠 sharp 的 bound,然後不管三七二十一就拿 binomial distribution 和 Chernoff bounds 來搞,經過 Peter 糾正以後,我才驚覺自己沒有考慮到事件的獨立與否。於是 Peter 建議可以找一些即使事件不是 mutually independent 也能用的 probability bounds,沒想到 Google 大神一下子就幫我找到答案了。另外也順道糾正了自己對 dependency graph 的錯誤認知,原來兩點有一條邊並不一定是他們對應的兩事件相依啊,而且對應一組事件的 dependency graphs 並不唯一,當時聽 Ton Kloks 上課解說的時候我可能恍神了吧。

我想這篇文章應該是很有意思,沒想到圖論的研究還可以用來 improve 在機率論上面的結果,蠻令我意外的,跟 Szemer\'{e}di's Regularity Lemma 有異曲同工之妙。

No comments: