Next: Stochastic Processes with Non-diminishing Up: -MDPs: Learning in Varying Previous: The Convergence of the

# Sampling from Near-identical Distributions

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 .

Naturally, will not be independent from .

Proof. Let us define the sets
 and

Furthermore, define the distributions11

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
 (14)

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.

Next: Stochastic Processes with Non-diminishing Up: -MDPs: Learning in Varying Previous: The Convergence of the