一個眾所周知的機率引理的解釋和證明
Pointcheval 和 Stern 在他們關於“簽名方案的安全證明”的論文中陳述了以下“眾所周知的”機率引理：
讓 $ A \subset X \times Y $ , 這樣 $ \mathrm{Pr}[A(x, y)] \geq \epsilon $ , 那麼存在 $ \Omega \subset X $ 這樣
- $ \mathrm{Pr}[x \in \Omega] \geq \epsilon/2 $
- 每當 $ a \in \Omega $ , $ \mathrm{Pr}[A(a, y)] \geq \epsilon /2 $
我不熟悉使用的符號，我也無法在我的文獻中找到這個結果。
問題：
- 能 $ A $ 是任何集合還是必須是事件（可測量集合）？
- 符號是否 $ \mathrm{Pr}[A(x, y)] $ 意思是 $ \mathrm{P}\left({(x, y) \in A}\right) $ ? 符號 $ A(x, y) $ 也可以暗示 $ A $ 取決於 $ x $ 和 $ y $ ，但我不相信是這樣的。
- 符號是否 $ \mathrm{Pr}[x \in \Omega] $ 意思是 $ \mathrm{P}\left({(x, y) \in \Omega\times Y}\right) $ 還是意味著 $ \mathrm{P}\left({(x, y) \in (\Omega\times Y)\cap A}\right) $
- 我怎樣才能證明這一點？我在哪裡可以找到證明？
在我的定義中，我假設 $ A $ 是一個事件，是樣本空間的一個子集 $ X \times Y $ 然後 $ P $ 是一種機率測度。
謝謝。
這是基於一個平均論點（它也用於 Goldreich-Levin 核心比特的證明）。
首先，我假設在寫作時 $ \operatorname{Pr}[A(x,y)=1] \geq \epsilon $ , 然後機率被接管兩者的隨機選擇 $ x $ 和 $ y $ . 現在，聲稱存在一個子集 $ x $ “足夠大”的值，因此對於每個 $ x $ 在這個集合中，事件的機率至少為 $ \epsilon/2 $ 隨機抽取的時候 $ y $ 只要。
這可以證明如下：讓 $ \Omega $ 是所有值的集合 $ a\in X $ 為此 $ \operatorname{Pr}_y[A(a,y)=1]\geq \epsilon/2 $ . （請注意，對於任何 $ a\in X\setminus \Omega $ 因此它認為 $ \operatorname{Pr}_y[A(a,y)=1] < \epsilon/2 $ .)
我們的目標是證明 $ \Omega $ 大小至少 $ \epsilon/2 \cdot |X| $ ，因為這將顯示我們需要什麼。
$$ \begin{eqnarray} \epsilon :\leq:\operatorname{Pr}{x,y}[A(x,y)=1] & = & \frac{1}{|X|} \cdot \sum{a\in X} \operatorname{Pr}y[A(a,y)=1]\ & = & \frac{1}{|X|} \cdot \sum{a\in\Omega} \operatorname{Pr}y[A(a,y)=1] + \frac{1}{|X|} \cdot \sum{a\notin\Omega} \operatorname{Pr}y[A(a,y)=1]\ & \leq & \frac{1}{|X|} \cdot \sum{a\in\Omega} 1 + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\ & < & \frac{|\Omega|}{|X|} + \frac{\epsilon}{2}, \end{eqnarray} $$ 因此，我們有 $ \epsilon \cdot |X| < |\Omega| + \epsilon/2 \cdot |X| $ 所以 $ |\Omega| > (\epsilon - \epsilon/2) \cdot |X| = \epsilon/2 \cdot |X| $ ， 按要求。 我希望這很清楚。