Explanation and proof of a well-know probabilistic lemma Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma:


  Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] \geq \epsilon$, then there exists $\Omega \subset X$ such that
  
  
  $\mathrm{Pr}[x \in \Omega] \geq \epsilon/2$
  whenever $a \in \Omega$, $\mathrm{Pr}[A(a, y)] \geq \epsilon /2$
  


I am not familiar with the notation used and I also can't find this result in my literature.

Questions:


Can $A$ be any set or it must be an event (measurable set)?
Does the notation $\mathrm{Pr}[A(x, y)]$ mean $\mathrm{P}\left(\{(x, y) \in A\}\right)$? Notation $A(x, y)$ could also imply that $A$ depends on $x$ and $y$, but I don't believe this is the case.
Does the notation $\mathrm{Pr}[x \in \Omega]$ mean $\mathrm{P}\left(\{(x, y) \in \Omega\times Y\}\right)$ or does it mean $\mathrm{P}\left(\{(x, y) \in (\Omega\times Y)\cap A\}\right)$
How can I prove this? Where can I find the proof?


In my definitions I assume that $A$ is an event and a subset of the sample space $X \times Y$ and that $P$ is a probability measure.

Thanks.
This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit).

First, I assume that when writing $\operatorname{Pr}[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both $x$ and $y$. Now, the claim is that there exists a subset of $x$ values of a "large enough size" so that for every $x$ in this set, the probability of the event is at least $\epsilon/2$ when taking a random $y$ only.

This can be proven as follows: Let $\Omega$ be the set of all values $a\in X$ for which $\operatorname{Pr}_y[A(a,y)=1]\geq \epsilon/2$. (Note that for any $a\in X\setminus \Omega$ it therefore holds that $\operatorname{Pr}_y[A(a,y)=1] &lt; \epsilon/2$.) 

Our aim is to prove that $\Omega$ is of size at least $\epsilon/2 \cdot |X|$, since this will show what we need.

\begin{eqnarray}
\epsilon \:\leq\:\operatorname{Pr}_{x,y}[A(x,y)=1] &amp; = &amp; \frac{1}{|X|} \cdot \sum_{a\in X} \operatorname{Pr}_y[A(a,y)=1]\\
&amp; = &amp; \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]\\
&amp; \leq &amp; \frac{1}{|X|} \cdot \sum_{a\in\Omega} 1 + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\\
&amp; &lt; &amp; \frac{|\Omega|}{|X|} + \frac{\epsilon}{2},
\end{eqnarray}
We therefore have that $\epsilon \cdot |X| &lt; |\Omega| + \epsilon/2 \cdot |X|$ and so $|\Omega| &gt; (\epsilon - \epsilon/2) \cdot |X| = \epsilon/2 \cdot |X|$, as required.

I hope that this is clear.