In this section we prove a technical lemma that is needed for the
proof of Lemma 3.4.
be two different distributions over the finite set
sampled from distribution
can be selected so
that its distribution is
Let us define the sets
Furthermore, define the distributions11
The denominator in the definition of
is positive, because for
is non-negative, therefore
is zero only if
. In this
by the same reasoning, which means
It is easy to check that is indeed a distribution over
(with support set ).
Let and be independent random variables from distributions
and , respectively. Now define as follows:
We claim that the such defined is suitable. Indeed, by Equation
By applying Bayes' Theorem on each term, we get
We calculate each term of Equation 14 separately, both for
and . First assume that . Then
Before the last equation we used the definition of
, and in
the last equation we have used the equality
, which is true because
Now let us consider the case .
In both cases we get
, which was to be proven.