Monday, June 16, 2008

Error probability of majority vote

假設我們有一個針對性質 P 的 tester,其成功機率至少為 2/3,那麼重複執行這個 tester 三次,以所謂的 "majority vote" 來當 output 的答案,那麼這樣子 testing 成功的機率至少有多少?

Paper* 上寫明為 20/27,但是我從 Chernoff bound 繞了一大圈,始終得不到這個答案。後來我才發現,是我殺雞了牛刀的關係。

從 tester 三次的 outputs 來看,taking majority vote 的失敗情形,只可能為 0 次 "yes" 與 1 次 "yes" 兩種。因此,



這樣子就說得過去了。能 "exactly" 分析當然比較好,Chernoff bound、 Chebyshev inequality 或 Markov inequality 只能說是「沒有辦法中的好辦法」。不過,花點時間練習使用 Chernoff bound 當然也是一件好事。久久沒做演練,數學技巧都有些生鏽了。


* 正在拜讀的 paper:
N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy: Efficient testing of large graphs. Combinatorica 20 (2000) 451-476.


1 comment:

Joseph, Chuang-Chieh Lin said...

這一篇 paper 因為很多 notations,加上很多繁複或類似的定理,看到後面會有點令人頭昏。

現在先跳到 monotone graph property 的結果去看。