In this section we prove a technical lemma that is needed for the
proof of Lemma 3.4.
Lemma B.1
Let
and
be two different distributions over the finite set
such that
, and
is
sampled from distribution
. Then
can be selected so
that its distribution is
, but
.
Proof.
Let us define the sets
Furthermore, define the distributions
11
The denominator in the definition of
is positive, because for
all
,
is non-negative, therefore
is zero only if
over
. In this
case
over
by the same reasoning, which means
, but
and
are different.
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:
|
(13) |
We claim that the such defined is suitable. Indeed, by Equation
13
Furthermore,
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.