Sampling from Near-identical Distributions

In this section we prove a technical lemma that is needed for the proof of Lemma 3.4.

and | |||

Furthermore, define the distributions

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:

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

and | |||

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 .

and | |||

In both cases we get , which was to be proven.