導出“從有錯誤的奇偶校驗中學習”的機率估計
在 Regev 的論文“On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”中，他在論文的介紹中考慮了“從錯誤中學習奇偶校驗”。我們在哪裡有一個未知數 $ s \in \mathbb{Z}_2^n $ 我們的目標是找到這個 $ s $ ，給定一個有錯誤的方程列表，例如 $ \langle s,a_i \rangle \approx b_i (\text{ mod } 2) $ 等。 $ a_i $ 的選擇獨立於上的均勻分佈 $ \mathbb{Z}_2^n $ , $ \langle s, a_i\rangle = \sum_j s_j (a_i)_j $ 是內積模 2 $ s $ 和 $ a $ , 每個方程都是正確的機率 $ 1-\epsilon $ . 如果沒有錯誤，我們將能夠使用高斯消元法求解方程組，這是可以理解的。
Regev 更進一步，考慮了高斯消除過程，並假設我們只對恢復 $ s $ . 他說使用高斯消元法，我們可以找到一個集合 $ S $ 的 $ O(n) $ 等式使得 $ \sum_S a_i $ 是 $ (1,0,…,0) $ . 對相應值求和 $ b_i $ 給我們一個猜測 $ s $ .
我不明白的部分，這是我的問題：他說用標準計算可以證明這個猜測是正確的 $ \frac{1}{2} + 2^{-\Theta(n)} $ . 究竟是如何得出這個估計的，這個標準計算是什麼？我不太明白，所以我想在這裡問這個問題。
我希望我的問題是可以理解的。感謝您提供有用的評論/答案。
對於給定的線性方程 $ \langle s,a_i\rangle $ 有相關的聲稱答案 $ b_i $ . 我們稱這個值是正確的，如果 $ \langle s,a_i\rangle=b_i $ 如果不正確 $ \langle s,a_i\rangle=b_i\oplus 1 $ . 請注意，我們可以通過 mod 2 加法從兩個或多個方程形成一個新方程，例如 $ \langle s,a_i\oplus a_j\rangle $ 並關聯到這個聲稱的答案 $ b_i\oplus b_j $ . 如果兩者中的任何一個，我們的主張都是正確的 $ b_i $ 是正確的或兩者都不正確。一般來說，當組合方程時，如果組合的偶數個，新方程聲稱的答案將是正確的 $ b_i $ 不正確。
假設 $ S $ 由組成 $ k $ 方程，我們求和 $ k $ 的值 $ b_i $ 模 2，如果偶數個代表不正確的值，則 $ b_i $ 等於正確值的總和。根據二項式定理，恰好 $ c $ 的 $ b_i $ 值不正確是 $ \binom{k}c(1-\epsilon)^{k-c}\epsilon^{c} $ . 因此，正確猜測的總機率為 $$ \sum_{d=0}^{[k/2]}\binom{k}{2d}(1-\epsilon)^{k-2d}\epsilon^{2d} $$ 比較二項式展開中的項 $ ((1-\epsilon)+\epsilon)^k $ 和 $ ((1-\epsilon)-\epsilon)^k $ 我們看到上面的表達式是 $$ \frac12\left(\left((1-\epsilon)+\epsilon\right)^k+\left((1-\epsilon)-\epsilon\right)^k\right)=\frac12\left(1+(1-2\epsilon)^k\right). $$ 現在大 $ k $ 並固定 $ \epsilon $ 我們有 $ (1-2\epsilon)^k\approx \exp(-2k\epsilon)=2^{-O(n)} $ 按要求。