The relation between the closeness of random variables and their distributions by Péter Major Mathematical Institute of the Hungarian Academy of Sciences

Abstract: If two random variables are close to each other, then the same relation holds for their distributions. This statement cannot be reversed. Nevertheless, some non-trivial results can be proved in this in the opposite direction if the question is formulated in the right way. Given two probability measures on a general metric space let us try to construct two random variables with these distributions which are close to each other. In this problem the distribution of the random variables are prescribed, but we have the freedom to “couple them”, to define their joint distribution at our taste.

We show that the questions how close two probability measures are to each other and how close random variables can be constructed with such distributions are closely related. Such problems will be discussed here. In particular, we introduce the notion of the Prochorov metric, the quantile transform and discuss their most important properties. It is worth mentioning that these results are strongly related to a classical result in combinatorics, the König–Hall theorem.

Introduction

If two random variables are close to each other, then the same relation holds for their distributions. The converse statement does naturally not hold. For instance these two random variables can be independent. But an interesting and non-trivial answer can be given to the following question. Let two (close) probability measures μ and ν be given on the Borel σ-algebra of a metric space (X, ρ). Is it possible to construct a probability space (Ω, A, P) and two random variables ξ and η on it in such a way that the distribution of ξ is μ, the distribution of η is ν, and the random variables ξ and η are close to each other? Naturally, in a detailed discussion we must tell explicitly what we mean by closeness of probability measures and random variables.

In the study of this problem the following approach is natural: Put (Ω, A, P) = (X × X, A × A, P), where × denotes direct product, A is the σ-algebra induced by the metric ρ, or more precisely by the topology generated by it, and P is an appropriate probability measure on the space (X, A). Furthermore, let us define the random variables ξ(x_{1}, x_{2}) = x_{1} and η(x_{1}, x_{2}) = x_{2}, (x_{1}, x_{2}) ∈ X × X, on this space. After the introduction of these objects the problem of constructing random variables with prescribed distributions close to each other can be reformulated in the following way: Let us construct a probability measure P on the space (X × X, A × A) whose marginal distributions are the measures μ and ν, and which is essentially concentrated close to the diagonal {(x, x), x ∈ X}. In the investigation of this problem a classical combinatorial result, the König–Hall theorem (sometimes called the marriage problem), or more precisely a continuous version of this result is very useful. We formulate these results, and also write down their proofs in an Appendix.

Péter Major

König–Hall theorem, (marriage problem). Let us consider n boys and n girls such that some boys and girls know each other. (All acquaintances are mutual.) We want to put these boys and girls into pairs (make married couples) in such a way that all persons put into a pair know each other. This is possible if and only if an arbitrary group of the girls knows at least as many boys as the number of this group.

In a more formal way: Let us consider a bipartitated graph consisting of two sets Y = {y_{1}, …, y_{n}} and Z = {z_{1}, …, z_{n}} and a map Y × Z → {0, 1}. We can interpret the relation d(y, z) = 1, y ∈ Y, z ∈ Z so that the points y and z are connected, while d(y, z) = 0 means that they are not connected. For all sets A ⊂ Y let us define the set B(A) ⊂ Z which contains the points which are connected to one of the points of A, i.e. let

B(A) = {z: z ∈ Z, and there exists such an y ∈ A, for which d(y, z) = 1}.

There exists a factorization of this bipartitated graph, i.e. we can divide the points of the sets Y and Z into pairs (y_{j}, z_{π(j)}), y_{j} ∈ Y, z_{π(j)} ∈ Z, j = 1, 2, …, n, in such a way that d(y_{j}, z_{π(j)}) = 1 for all j = 1, 2, …, n, and π(j), j = 1, …, n, is an appropriate permutation of the set {1, …, n} if and only if |B(A)| ≥ |A| for all sets |A| ⊂ Y, where |C| denotes the cardinality of a set C.

The continuous version of the König–Hall theorem. Let r depots with stocks

u_{1}, u_{2}, …, u_{r} and s plants with claims v_{1} …, v_{s} be given such that ∑_{j=1}^{r} u_{j} = ∑_{k=1}^{s} v_{k}. Let

certain depots and plants be connected by a route. We can satisfy all claims of the plants by transporting the stocks of the depots on these routes if and only if the joint demand of an arbitrary group of plants is not greater than the joint stock of the depots which are connected by a route with one of these plants.

In a more formal way: Let us consider a bipartitated graph consisting of two sets Y = {y_{1}, …, y_{r}} and sets Z = {z_{1}, …, z_{s}} and a map d: Y × Z → {0, 1}. We connect two points y and z, y ∈ Y, z ∈ Z, if d(y, z) = 1, and we do not connect them if d(y, z) = 0. Furthermore, let two weight function u(y), u(y) ≥ 0, y ∈ Y and v(z), v(z) ≥ 0, z ∈ Z be given such that ∑_{y∈Y} u(y) = ∑_{z∈Z} v(z). For all sets A ⊂ Y let us define

the set B(A) ⊂ Z by the formula

B(A) = {z: z ∈ Z, and there exists such an y ∈ A, for which d(y, z) = 1}.

There exists a “transport function” w(y, z) ≥ 0 with the properties

i.) ∑_{z: d(y,z)=1} w(y, z) = u(y) for all y ∈ Y,

and ∑_{y: d(y,z)=1} w(y, z) = v(z) for all z ∈ Z.

ii.) The inequality w(y, z) > 0 holds only if d(y, z) = 1,

if and only if the relation ∑_{z∈B(A)} v(z) ≥ ∑_{y∈A} u(y) holds for all sets A ⊂ Y.

Coupling methods in Probability Theory

Problems

0.) Let us show that the conditions in the König–Hall theorem and in its continuous version are symmetric for the sets Y and Z, i.e. these conditions remain valid, if we replace in them (and in the definition of the set B(A)) the sets Y and Z.

1.) Let two probability measures μ and ν be given on the σ-algebra determined by the topology generated by the metric of a separable metric space (X, ρ). Let B^{α} = {x: ρ(x, B) < α} denote the open neighborhood of the set B ⊂ X of radius α. Let us assume that the measures μ and ν satisfy the condition μ(B) ≤ ν(B^{α}) + β for all closed sets B ⊂ X with some numbers α > 0 and β > 0. Then for all ε > 0 a probability space (Ω, A, P) can be constructed, together with two random variables ξ and η on this probability space with values in the space (X, ρ) whose distributions are μ and ν respectively, and which satisfy the relation

P (ρ(ξ, η) > α + ε) ≤ β + ε  (a)

Conversely, if two random variables ξ and η with distributions μ and ν respectively satisfy relation (a), then μ(B) ≤ ν(B^{α+ε}) + β + ε for all closed sets B. If X is not only a separable, but also a complete separable metric space, then under the above conditions relation (a) also holds with ε = 0. (In the proof of this statement we may apply the result by which a uniformly compact sequence of probability measures on a complete metric space has a subsequence which is convergent with respect to the weak convergence of probability measures.)

2.) Let a separable metric space (X, ρ) be given together with the Borel σ-algebra A induced by the natural topology of this space. Let M denote the space of probability measures on the space (X, A), and let us introduce the following function d(·, ·) on the pairs of probability measures on the space (X, ρ): If μ ∈ M and ν ∈ M, then

d(μ, ν) = inf{α: μ(B) ≤ ν(B^{α}) + α for all closed sets B ⊂ X},

where B^{α} has the same meaning as in the previous problem. Let us show that d(·, ·) is a metric on the space M which metrizes the weak convergence in this space, i.e. the relation μ_{n} ⇒ μ, as n → ∞, holds for a sequence of measures μ_{n} ∈ M, n = 1, 2, …, and μ ∈ M, where ⇒ denotes weak convergence, if and only if d(μ_{n}, μ) → 0. The space (M, d) is a separable metric space, and if (X, ρ) is a complete separable metric space, then the same property holds for (M, d).

Remark: The property whether a metric generating a topology is complete or noncomplete is not topologically invariant, i.e. it is possible that a complete and a non-complete metric generate the same topology on a space. There is a classical result by which the space of probability measures on a complete metric space can be endowed with a metric which induces weak convergence, and with which the space of probability measures is a complete metric space. By the above remark this result does not imply automatically that also the metric introduced in problem 2 has this property.

We shall also prove the following Statement A:

Statement A: Let us apply the notations of problem 2. If μ_{n} ∈ M, n = 1, 2, …, is a sequence of probability measures on a metric space (X, ρ), and this sequence of measures together with a probability measure μ ∈ M satisfy the relation μ_{n} ⇒ μ, then there exists a probability space (Ω, A, P) and a sequence of random variables ξ_{n}, n = 1, 2, …, together with a random variable ξ on this space in such a way that the distribution of ξ_{n} is μ_{n}, n = 1, 2, …, the distribution of ξ is μ, and ξ_{n} → ξ with probability one.

The proof of Statement A is based on the observation that in an appropriate construction it can be achieved that the sets depending on the index n where the distance between the random variables ξ_{n} and ξ is relatively large almost overlap each other. This can be achieved if the joint distribution of the random variables ξ_{n} is appropriately chosen. As a consequence, the almost sure convergence in Statement A is less useful than it may seem at first sight. The deep results of the probability theory containing ”with probability one … ” statements depend on the joint distribution of the random variables. On the other hand, Statement A allows the changement of the joint distribution of the random variables.

The proof of Statement A is simpler in complete separable spaces, and in this case the probability space where the convergent sequence of random variables is constructed can be chosen in a very special way. To prove Statement A in this special case it is useful first to solve the following problem.

3.) Let (X, ρ) be a complete metric space, μ a probability measure on the Borel σalgebra of this space. Let us consider the special probability space (Ω, A, P) for which Ω = [0, 1], A is the Borel σ-algebra on the interval [0, 1], and P is the Lebesgue measure on the Borel σ-algebra of the interval [0, 1]. On this probability space a random variable can be constructed with values on the space (X, ρ) whose distribution is μ.

4.) Let us prove Statement A in the case when (X, ρ) is a complete separable metric space. Show that in this case the probability space (Ω, A, P) where the convergent sequence of random variables is constructed can be chosen in the following special way: Ω = [0, 1], A is the Borel σ-algebra on the interval [0, 1], and P is the Lebesgue measure on the Borel σ-algebra of the interval [0, 1].

5.) Statement A also holds for convergent sequence of probability measures on an arbitrary separable (not necessarily complete) metric space. (In this space the sequence of convergent random variables has to be constructed on an appropriate (generally very large) probability space (Ω, A, P).)

6.) Let ξ_{n}, n = 1, 2, …, and ξ be (X, ρ) valued random variables, where (X, ρ) is a separable metric space. Let us assume that ξ_{n} ⇒ ξ, where ⇒ denotes stochastic convergence. The distributions μ_{n} of the random variables ξ_{n} and the distribution μ of the random variable ξ satisfy the relation μ_{n} ⇒ μ, where ⇒ denotes weak convergence of probability measures.

We have investigated the question that given two probability measures μ and ν on a metric space (X, ρ) how a pair of μ distributed ξ and ν distributed η random variables can be constructed which are close to each other. We have seen that informally saying this question leads to the to the following “transport problem”: How can a system of points with mass distribution μ be transported with relatively few movements to a system of points with mass distribution ν? If the metric space (X, ρ) where we are working is the real line with the usual metric, then because of the simple structure of this space the “transport problem” we have to handle becomes considerably simpler. In this case if some “natural evaluation of the transport cost” is considered (see the subsequent problem 9, where such a problem is formulated in an explicit form) it is useful to exclude the following possibility: There exist such pairs of numbers x_{1} < x_{2} and x_{3} < x_{4} for which the point x_{1} is transported to the point x_{4} and the x_{2} to the point x_{3}. In this case the transports x_{1} → x_{3} and x_{2} → x_{4} are more economic. The following construction, called the quantile transform, excludes the possibility of such non-economic transports.

To define the quantile transform we recall the following fact often used also in mathematical statistics. If ξ is a random variable with distribution F on the real line, then under some slight restrictions the random variable η = F (ξ) is a random variable with uniform distribution on the interval [0, 1]. Conversely, if η is a random variable with uniform distribution on the interval [0, 1], then ξ = F^{−1}(η), where F^{−1}(x) is the inverse of the distribution function F (x) is an F distributed random variable. In the next problem we formulate the above result in a more precise and slightly more general form.

7.) Let ξ be a random variable with distribution function F (x) = P (ξ < x) and η a random variable uniformly distributed in the interval [0, 1]. Let us define the generalized inverse of the (not necessarily strictly) monotone increasing function F (x) by the formula F^{−1}(x) = sup{u: F (u) < x}. Then ξ̄ = F^{−1}(η) is an F distributed random variable. Conversely, let ε be a random variable with uniform distribution in the interval [0, 1] which is independent of the random variable ξ. Then η̄ = F̃(ξ, ε) = F (ξ) + ε[F (ξ + 0) − F (ξ)], where F (x + 0) = lim_{h>0,h→0} F (x + h),

is uniformly distributed in the interval [0, 1]. 8.) Let F and G be two distribution functions. If ζ is a random variable with uniform

distribution on the interval [0, 1], then the random variables ξ̄ = F^{−1}(ζ) and η̄ = G^{−1}(ζ), where the inverse functions F^{−1} are G^{−1} are defined in the same way as in the previous problems, have distributions F and G. If ¯ ξ̄ is a random variable with distribution F, and ε is an on the interval [0, 1] uniformly distributed random variable independent of the random variable ¯ ξ̄, then the random variable ¯ η̄ = G^{−1}(F̃(¯ξ̄, ε)) has distribution G. The distributions of the random vectors (ξ̄, η̄) and (¯ξ̄, ¯ η̄) agree.

In the problems of probability theory we sometimes have to construct two random variables ξ and η who have prescribed distributions μ and ν. Actually in the problems of probability theory generally it is enough to give the joint distribution of the random vector (ξ, η). Two constructions which determine random vectors with the same distribution can be considered equivalent. Hence the construction of both random vectors (ξ̄, η̄) and (¯ξ̄, ¯ η̄) given in the previous problem are called the quantile transform in the literature. In the next problem we formulate an optimality property of the quantile transform.

9.) Let ξ and η be two random variables on the real line with distribution functions F (x) and G(x), which satisfy the conditions E|ξ| < ∞, E|η| < ∞. Beside this, let us consider a convex function Φ(x) on the real line. Then

EΦ(ξ − η) ≥ ∫_{0}^{1} Φ (F^{−1}(x) − G^{−1}(x)) dx > −∞,

where F^{−1}(x) and G^{−1}(x) are the inverse functions defined in problem 7. If the random vector is defined by means of the quantile transform, then the two sides of the above inequality are equal.

9a.) Let ξ and η be two random variables on the real line with distribution functions F (x) and G(x), which satisfy the conditions E|ξ| < ∞, E|η| < ∞. Then E|ξ −η| ≥ ∫_{−∞}^{∞} |F (x) − G(x)| dx, and the inequality can be replaced by identity if the pair (ξ, η) is constructed by means of quantile transform.

Finally we formulate some problems different of the previous ones which may be useful in some investigations. Their proofs apply some non-trivial facts from measure theory like the existence of conditional distribution, the Banach decomposition theorem or the Radon–Nikodym theorem which implies the latter result.

10.) Let three complete separable metric spaces (X_{i}, ρ_{i}), i = 1, 2, 3 be given, and let A_{i}, i = 1, 2, 3, denote the σ-algebra induced by the topology of these spaces. Let μ be a probability measure on the space (X_{1} × X_{2}, A_{1} × A_{2}) and ν a probability measure on the space (X_{2} × X_{3}, A_{2} × A_{3}). Let us assume that the projections of the measures μ and ν to the space X_{2} agree. Then there exists such a probability measure P on the space (X_{1} × X_{2} × X_{3}, A_{1} × A_{2} × A_{3}) whose projection to the space X_{1} × X_{2} is μ, and to the space X_{2} × X_{3} is ν.

Let us remark that if (X, ρ) is a complete separable space, then the direct product of infinitely many copies of this space X × X × ⋯ can also be considered as a complete metric space with an appropriate metric ρ̄. Indeed, we may assume that the metric in the space (X, ρ) is such that ρ(x, x̄) ≤ 1 for all points x ∈ X and x̄ ∈ X, by introducing for instance the new metric ρ′(x, x̄) = min(ρ(x, x̄), 1) if it is necessary. Then the metric

ρ̄((x_{1}, x_{2}, …), (x̄_{1}, x̄_{2}, …)) = ∑_{k=1}^{∞} \frac{1}{2^{k}} ρ(x_{k}, x̄_{k})

can be defined on the product space X × X × · · ·. The space (X × X × ⋯, ρ̄) is a separable complete metric space with this metric.

It follows from the results of problem 10 that if μ and ν are two probability measures on a complete separable metric space (X, ρ) and we want to construct two random variables ξ and η with distributions μ and ν respectively which are close to each other then we can apply the following approach. We introduce some auxiliary random variables ζ and ζ̄ with values in the space (X, ρ) in such a way that the members of the pairs (ξ, ζ) and (η, ζ̄) are close to each other, ξ is a μ, η is a ν distributed random variable, and the distributions of ζ and ζ̄ agree. Furthermore, by the remark made after problem 10 this approach can be applied also in the case if we want to approximate a series of random variables ξ_{1}, ξ_{2}, … with a prescribed distribution with another sequence of random variables η_{1}, η_{2}, … of possibly different distribution.

The statement of the previous paragraph can be slightly strengthened. Let us have a μ distributed random variable ξ on a sufficiently rich probability space (Ω, A, P) and a probability measure ν on a product space X ×X, where (X, ρ) is a complete separable metric space. Let us further assume that the projection of the probability measure ν to the first coordinate of the product space X × X is the distribution μ of the random variable ξ. Then a random variable η can be constructed on the probability space (Ω, A, P) for which the random vector (ξ, η) is ν distributed. This means that if we want to construct a coupled pair (ξ, η) with prescribed joint distribution on a sufficiently rich probability space, then we may demand that the random variable ξ (with the right distribution) be fixed at the start. An analogous statement also holds if we consider two sequences of random variables ξ_{1}, ξ_{2}, … and η_{1}, η_{2}, … instead of the random variables ξ and η.

We shall prove the above statement in the next problem 11. We remark that a probability space is “sufficiently rich” in the sense we need it if there exists an in the interval [0, 1] uniformly distributed random variable in this space which is independent of the random variable ξ or the random sequence ξ_{1}, ξ_{2}, … which we want to couple with an appropriate random variable or random sequence.

11.) let ν be a probability measure on a product space X ×X, where (X, ρ) is a complete separable metric space. Let μ be the projection of the measure ν to the first coordinate of the space X × X. Let ξ be a μ distributed random variable on a probability space (Ω, A, P), and let us assume that there exists a random variable χ on this probability space (Ω, A, P) with uniform distribution on the interval [0, 1] which is independent of ξ. Then such a random variable η can be constructed for which the distribution of the random pair (ξ, η) is ν.

12.) If ξ and η are two random variables taking their values on a measurable space (X, A), the distribution of ξ is μ and the distribution of η is ν, then P (ξ ≠ η) ≥ Var (μ, ν), where Var (μ, ν) = sup_{A∈A} |μ(A)−ν(A)|, is the variational distance between

the measures μ and ν. For arbitrary probability measures μ and ν there exist such μ and ν distributed random variables ξ and η, for which the two sides of the above inequality are equal.

Finally, we give a concise proof of two statements with the help of the above results. The first of them is the functional central limit theorem which is also called the invariance principle in the literature. The second statement enables us to deduce some useful consequences of the functional central limit theorem. Before its formulation let us recall the following form of the central limit theorem.

Central limit theorem. Let ξ_{k,j}, k = 1, 2, …, 1 ≤ j ≤ n_{k}, with some positive integers n_{k}, be a triangular array, i.e. assume that the random variables ξ_{k,j}, 1 ≤ j ≤ n_{k}, are independent for a fixed number k. Assume that Eξ_{k,j} = 0, Eξ_{k,j}^{2} = σ_{k,j}^{2} < ∞,

lim_{k→∞} ∑_{j=1}^{n_{k}} σ_{k,j}^{2} = 1. If beside this the triangular array ξ_{k,j}, k = 1, 2, …, 1 ≤ j ≤ n_{k},

satisfies the Lindeberg condition, i.e.

lim_{k→∞} Eξ_{k,j}^{2}I(|ξ_{k,j}| > ε) = 0 for all numbers ε > 0,

where I(A) denotes the indicator function of a set A, then the sums S_{k} = ∑_{j=1}^{n_{k}} ξ_{k,j},

k = 1, 2, …, converge in distribution to the standard normal distribution as k → ∞.

The functional central limit theorem, formulated below, says that under the conditions of the central limit theorem also the following sharper statement holds.

Functional central limit theorem. Let ξ_{k,j}, k = 1, 2, …, 1 ≤ j ≤ n_{k}, be a triangular

array such that Eξ_{k,j} = 0, Eξ_{k,j}^{2} = σ_{k,j}^{2} < ∞, lim_{k→∞} ∑_{j=1}^{n_{k}} σ_{k,j}^{2} = 1. Let us also assume that

the triangular array ξ_{k,j}, k = 1, 2, …, 1 ≤ j ≤ n_{k}, satisfies the Lindeberg condition. In-

troduce the partial sums S_{k,l} = ∑_{j=1}^{l} ξ_{k,j}, k = 1, 2, …, 1 ≤ l ≤ n_{k}, and define the random

broken line S_{k}(t), 0 ≤ t ≤ 1, k = 1, 2, …, in the following way. Put u_{k,l} = ∑_{j=1}^{l} σ_{k,j}^{2},

ū_{k,l} = \frac{u_{k,l}}{u_{k,n_{k}}}, let S_{k}(ū_{k,l}) = S_{k,l}, S_{k}(0) = 0, k = 1, 2, …, 1 ≤ l ≤ n_{k}, and let the func-

tion S_{k}(t) be linear in the intervals [0, ū_{k,1}] and [ū_{k,l−1}, ū_{k,l}], k = 1, 2, …, 2 ≤ l ≤ n_{k}. Then the random broken lines S_{k}(t), 0 ≤ t ≤ 1, can be considered as random variables taking values in the Banach space C([0, 1]) of continuous functions endowed with the supremum norm. The functional central limit theorem states that the distributions of the random variables S_{k}(t) (in the space C([0, 1])) converge in distribution to the socalled Wiener measure, i.e. to the distribution of a Wiener process W (t), 0 ≤ t ≤ 1, as k → ∞.

13.) Prove (with the help of the results in this work, the central limit theorem, inequalities for the maximum of sums of independent random variables and some basic facts about Wiener processes) the functional central limit theorem.

The coupling results of this work can be useful also in the proof of the following statement which may help for instance to understand why the functional central limit theorem is a useful result of probability theory.

14.) Let μ_{n}, n = 1, 2, …, be a sequence of probability measures on a separable (not necessarily complete) metric space (X, ρ) which converges weakly to a probability measure μ_{0} on this space. Let F be a measurable map from this separable metric space (X, ρ) to some other separable metric space (Y, ρ_{1}) such that the map F is continuous with probability one with respect to the limit measure μ_{0}. Let us consider the probability measures Fμ_{n}, defined as Fμ_{n}(B) = μ{x: F(x) ⊂ B} if B ⊂ Y is a Borel-measurable set, n = 0, 1, …, on the space (Y, ρ_{1}). Prove with the help of the result of Problem 5 that the probability measures Fμ_{n} converge weakly the probability measure Fμ_{0} as → ∞.

Remarks

The result of problem 1 was originally proved by V. Strassen. I learned about it and its close relation to the “transport problem” and the König–Hall theorem, an important method of combinatorics, from the works of R. M. Dudley. Let us remark that this result gives a non-trivial answer to the question how closely two random variables or two stochastic processes with prescribed distributions can be put to each other. Nevertheless this result does not give a real help in most coupling problems. The reason for this deficiency is that generally it is not simpler to check formula (a) for all closed sets than to construct a coupling in an explicit way.

The result of problem 2 was proven by Yu. V. Prochorov, and the metric introduced there is called the Prochorov metric in the literature. The result of problem 4 (and the result of problem 3 which serves as basis for its solution) belongs to A. V. Skorochod. The construction supplying the solution of problem 5 belongs to R. M. Dudley. The generalization of problem 4 given in problem 5 is non-trivial. One could try to deduce the result of problem 5 to problem 4 by embedding a separable metric space to a complete separable metric space. Such an embedding is always possible, but it may happen that the embedded space is a non-measurable subset of the larger space. Hence one cannot get a solution for problem 5 in such a simple way.

The quantile transform is a well-known method in probability theory, and it is frequently used in certain investigations. It is hard to relate its introduction to a definite person. It is worth mentioning that the proof of the optimality property of the quantile transform formulated in problem 9 is based on its reformulation for a “transport problem”. It is the simple structure of the real line which enables us to prove such an explicit result in this case.

The results of problems 10, 11 and 12 are more or less well-known for mathematicians working in this subject. However, I had the impression that the answer to the question how big freedom we have to construct random variables or random sequences with prescribed distribution is not sufficiently well understood. Hence I thought it may be useful to discuss some results which may help to study such questions.

The functional central limit theorem is a classical result of probability theory. Its usual proof is based on the investigation of the convergence of probability measures. The functional central limit theorem together with the result formulated in problem 14 explain why all “natural” functions of partial sums of independent random variables have a limit distribution which is independent of the distribution of the summands and can be expressed as the distribution of a functional of a Wiener process.

Solutions

0.) Let us define for all sets B ⊂ Z the set

A(B) = {y: y ∈ Y, d(y, z) = 1 for some z ∈ B}.

We have to show that if the conditions of the König–Hall theorems are satisfied, then |A(B)| ≥ |B|. This statement is equivalent to the relation |Y \ A(B)| ≤ |Z \ B|. It follows from the conditions of the problem that |B(Y \ A(B))| ≥ |Y \ A(B)|. Hence, it is enough to show that B(Y \ A(B)) ⊂ Z \ B. This relation holds, since if y ∈ B(Y \ A(B)), i.e. there exists an z ∉ A(B) such that d(y, z) = 1, then by the definition of the set A(B) y ∉ B, i.e. B(Y \ A(B)) ⊂ Z \ B. The analogous statement in the case of the continuous version of the König–Hall theorem can be proved similarly. In this case the statement we have to prove is equivalent to the inequality ∑_{y∈Y \A(B)} u(y) ≤ ∑_{z∈Z\B} v(z) because of the identity

∑_{y∈Y} u(y) = ∑_{z∈Z} v(z). This inequality follows from the relation B(Y \A(B)) ⊂ Z \B.

1.) Let us define the probability space (Ω, A, P) with the following choice: Ω = X ×X, A is the σ algebra generated by the topology of the space X × X, and P is an appropriate probability measure on the measure space (Ω, A) we still have to define. Put ξ(x_{1}, x_{2}) = x_{1} and η(x_{1}, x_{2}) = x_{2}. We solve the problem if we can construct a probability measure P on the space (Ω, A) which satisfies the following relations:

a.) P (A × X) = μ(A), P (X × A) = ν(A) for all measurable sets A ⊂ X. b.) P ({(x_{1}, x_{2}): ρ(x_{1}, x_{2}) > α + ε}) ≤ β + ε.

We shall construct such a probability measure P with the help of the continuous version of the König–Hall theorem. First we define a bipartitated graph with an appropriate weight function. To do this we introduce some notations. Let G(x, α) denote the ball with center x and radius α in the metric space (X, ρ). Let x_{1}, x_{2}, …, be an everywhere dense sequence on

the space X, and let us fix a number ε > 0. As ⋃_{n=1}^{∞} G (x, \frac{ε}{5}) = X, there exists such

a number N = N(ε) for which the set W_{N} = ⋃_{n=1}^{N(ε)} G (x, \frac{ε}{5}) satisfies the relations

μ(W_{N}) > 1 − \frac{ε}{2} and ν(W_{N}) > 1 − \frac{ε}{2}. Let us define the sets V_{k} = G (x_{k}, \frac{ε}{5}) \

⋃_{j=1}^{k−1} G (x_{j}, \frac{ε}{5}), k = 1, …, N and V_{N+1} = X \ W_{N}. Then V_{k}, k = 1, …, N + 1 is a

partition of the space X, d(V_{k}) ≤ \frac{ε}{5}, if 1 ≤ k ≤ N, where d(A) denotes the diameter of set A ⊂ X. Further, μ(V_{N+1}) < \frac{ε}{2} and ν(V_{N+1}) < \frac{ε}{2}. We shall call the point x_{k} the center of the set V_{k}, 1 ≤ k ≤ N. We define the following bipartitated graph (Y, Z, d(·, ·)): Y = {y_{1}, …, y_{N+1}} = {V_{1}, …, V_{N+1}}, Z = {z_{1}, …, z_{N+1}} = {V_{1}, …, V_{N+1}}, d(y_{j}, z_{k}) = 1, if ρ(x_{j}, x_{k}) ≤ α + \frac{ε}{2}, 1 ≤ j, k ≤ N, and also d(y_{N+1}, z_{k}) = 1 and d(y_{j}, z_{N+1}) = 1 for all indices 1 ≤ j, k ≤ N + 1. In all other cases we define d(y, z) = 0. (The relation d(y, z) = 1 means that the points y and z are connected.) We also introduce the following weight functions u(·) and v(·) on the sets Y and Z: u(y_{j}) = μ(V_{j}), v(z_{j}) = ν(V_{j}), j = 1, …, N, u(y_{N+1}) = μ(V_{n+1}) + β, v(z_{N+1}) = ν(V_{n+1}) + β. We claim that this bipartitated graph and weight function satisfy the conditions of the continuous version of the König–Hall theorem. The desired inequality obviously holds for such sets A ⊂ Y, for which y_{N+1} ∈ A. Indeed, in this case B(A) = Z, since y_{N+1} is connected to all points of the set

Z. If y_{N+1} ∉ A then put D_{1} = ⋃_{V_{j}∈A} V_{j} and D_{2} = ⋃_{V_{j}∈B(A)} V_{j}. In this case

∑_{y∈A} u(y) = μ(D_{1}), and ∑_{z∈B(A)} v(z) = ν(D_{2}) + β, since y_{N+1} ∉ A and z_{N+1} ∈ B(A).

Hence, it is enough to show that D̄_{1}^{α} ⊂ D_{2}, where D̄_{1} denotes the closure of the set D_{1}. But if x ∈ D̄_{1}, then there exists such a set y_{j} = V_{j} ∈ A whose center x_{j} satisfies the inequality ρ(x, x_{j}) ≤ \frac{ε}{5}, thus G(x, α) ⊂ G (x_{j}, α + \frac{ε}{5}). We claim that G(x, α) ⊂ G (x_{j}, α + \frac{ε}{5}) ⊂ D_{2}, with this point x, hence D̄_{1}^{α} ⊂ D_{2} as we claimed. Indeed, if this statement did not hold, then there would exist a point v ∈ G (x_{j}, α + \frac{ε}{5}), such that the element V_{k} of the partition \{V_{1}, …, V_{N+1}\} for which v ∈ V_{k} and its center x_{k} have the following properties: The points V_{k} and V_{j} are not connected in the bipartitated graph we have defined, hence 1 ≤ k ≤ N, and ρ(x_{j}, x_{k}) ≥ α + \frac{ε}{2}. But this is not possible, since d(V_{k}) ≤ \frac{ε}{5} and thus ρ(x_{j}, x_{k}) ≤ ρ(x_{j}, v) + \frac{ε}{5} ≤ α + \frac{2ε}{5}. We have shown the continuous version of the König–Hall theorem can be applied to this system. Let w̄(y, z), y ∈ Y, z ∈ Z be a “transport function” satisfying the continuous version of the König–Hall theorem in the above system, and let us define the following function w_{1}(y_{j}, z_{k}) with its help:

w_{1}(y_{j}, z_{k}) = w̄(y_{j}, z_{k}) if 1 ≤ j, k ≤ N,
and w_{1}(y_{j}, z_{k}) = 0, if j = N + 1 or k = N + 1.

This function w_{1}(y, z) satisfies the following properties:

i.) w_{1}(y_{j}, z_{k}) ≥ 0, and w_{1}(y_{j}, z_{k}) > 0 only if 1 ≤ j, k ≤ N and ρ(x_{j}, x_{k}) < α + \frac{ε}{2}

ii.) ∑_{z∈Z} w_{1}(y_{j}, z) ≤ u(y_{j}) = μ(V_{j}), ∑_{y∈Y} w_{1}(y, z_{k}) ≤ v(z_{k}) = ν(V_{k}).

iii.) ∑_{y∈Y,z∈Z} w_{1}(y, z) ≥ 1 − β − ε, because ∑_{y∈Y,z∈Z} w_{1}(y, z) ≥ ∑_{y∈Y,z∈Z} w(y, z) −

u(y_{N+1}) − v(z_{N+1}) ≥ 1 + β − 2(β + \frac{ε}{2}).

By the properties of the function w_{1}(y, z) there is a function w_{2}(y_{j}, z_{k}) ≥ 0, 1 ≤ j, k ≤ N + 1, such that the function w(y, z) = w_{1}(y, z) + w_{2}(y, z) satisfies the properties

∑_{z∈Z} w(y_{j}, z) = u(y_{j}) = μ(V_{j}), ∑_{y∈Y} w(y, z_{k}) = v(z_{k}) = ν(V_{k})

We shall define a probability measure P which satisfies properties a.) and b.) with the help of the function w(y, z). Put

P (C × D) = \frac{μ(C)}{μ(W_{j})} \frac{ν(C)}{ν(W_{k})}w(y_{j}, z_{k}) if C ⊂ W_{j}, D ⊂ W_{k}

with some indices 1 ≤ j, k ≤ N + 1. In the general case let us define

P (C × D) = ∑_{j=1}^{N+1} ∑_{k=1}^{N+1} P ((C ∩ V_{j}) × (D ∩ V_{k})) .

After this definition the measure P can be extended from the above rectangular sets to the whole σ algebra A in a unique way. We claim that this measure P satisfies both properties a.) and b.). Indeed, for all sets A ⊂ V_{j}, 1 ≤ j ≤ N + 1

P (A × X) = ∑_{k=1}^{N+1} P (A × V_{k}) = \frac{μ(A)}{μ(V_{j})} ∑_{k=1}^{N+1} w(y_{j}, z_{k}) = μ(A),

and this implies that P (X × A) = ν(A) for all measurable sets A ⊂ X. The second part of statement a.) can be proved similarly. On the other hand,

P ((x_{1}, x_{2}): ρ(x_{1}, x_{2}) ≤ α + ε) ≥ ∑_{(j,k) : ρ(x_{j},x_{k})≤α+ \frac{ε}{2}} P (V_{j} × V_{k})

= ∑_{(j,k) : ρ(x_{j},x_{k})≤α+ \frac{ε}{2}} w(V_{j} × V_{k})

≥ ∑_{y_{j}∈Y, z_{k}∈Z} w_{1}(V_{j} × V_{k}) ≥ 1 − β − ε

by the property iii.), and this statement is equivalent to condition b.) Conversely, if property (a) holds, then for arbitrary closed set B {ξ ⊂ B, η ∉ B^{α+ε}} ⊂ {(ξ, η): ρ(ξ, η) > α + ε}, hence P (ξ ∈ B, η ∉ B^{α+ε}) ≤ β + ε. As {ξ ∈ B} ⊂ {ξ ∈ B, η ∉ B^{α+ε}} ∪ {η ∈ B^{α+ε}}, this implies that μ(B) ≤ β + ε + ν(B^{α+ε}), and this is what we have to prove.

To prove the last statement of problem 1 let us make the following observation. If X is a complete metric space, and P_{n}, n = 1, 2, …, is a sequence of probability measures on the space X ×X whose marginal distributions are two measures μ and ν which do not depend on the index n, then this sequence of probability measures has a convergent subsequence if the weak convergence of probability measures are considered. To prove this statement let us observe that for all numbers ε > 0 there exists such a compact set K ⊂ X for which μ(K) ≥ 1− \frac{ε}{2}, and ν(K) ≥ 1− \frac{ε}{2}. Hence the compact set K ×K ⊂ X ×X and a sequence of probability measures P_{n} on the space X ×X whose marginal distributions are μ and ν satisfy the inequality P_{n}(K × K) ≥ 1 − ε for all indices n. By some classical results in probability theory this implies that the sequence of the probability measures P_{n} is tight, hence it has a weakly convergent subsequence. Let P_{n}, n = 1, 2, …, be a sequence of probability measures on the space X ×X with marginal distributions μ and ν which satisfy property (a) with numbers ε_{n} = \frac{1}{n}. Let P_{n_{k}}, k = 1, 2, …, be a convergent subsequence of this sequence, and let P denote its limit. The marginal distributions of the measure P are μ and ν. We claim that a random vector with distribution P satisfies property (a) also with the number ε = 0. Indeed, the sets of the form {(x_{1}, x_{2}): (x_{1}, x_{2}) ∈ X ×X, ρ(x_{1}, x_{2}) > α+ε} are open. Hence

β ≥ lim sup_{k→∞} P_{n_{k}} ({(x_{1}, x_{2}): ρ(x_{1}, x_{2}) > α + ε}) ≥ P ({(x_{1}, x_{2}): ρ(x_{1}, x_{2}) > α + ε})

for all numbers ε > 0. This implies that

P ({(x_{1}, x_{2}): ρ(x_{1}, x_{2}) > α}) = lim_{ε→0} P ({(x_{1}, x_{2}): ρ(x_{1}, x_{2}) > α + ε}) ≤ β.

Problem 1 is proved. 2.) Let us first show that the function d(·, ·) is a metric. i.) d(μ, μ) = 0. On the

other hand, we show that in the case d(μ, ν) = 0 μ = ν. Indeed, if d(μ, ν) = 0, then μ(F) ≤ ν(F) for all closed sets F ⊂ X, since F = ⋂_{ε→0} F^{ε}, and μ(F) ≤

lim inf_{ε→0}(ν(F^{ε}) + ε) = ν(F). We show that also the identity μ(F) = ν(F) holds

for closed sets F. Indeed, as μ(G) ≥ ν(G) for all open sets G, hence μ(F) = lim_{ε→0} μ(F^{ε}) ≥ lim_{ε→0} ν(F^{ε}) = ν(F). This implies that μ(A) = ν(A) for all closed or open sets A. On the other hand, a probability measure is uniquely determined by its values on the open sets, hence μ = ν. ii.) d(μ, ν) = d(ν, μ). Let d(μ, ν) < α with some number α > 0. We show that in this case d(ν, μ) ≤ α. Let F ⊂ X be an arbitrary closed set, and let us define the set F′ = X \ F^{α}. We claim that (F′)^{α} ⊂ X \F. Indeed, if y ∈ (F′)^{α} then d(y, X \F^{α}) < α, that is there exists such a point z ∈ X, for which d(z, F) ≥ α, and d(z, y) < α. This implies that y ∉ F, hence (F′)^{α} ⊂ X\F. With the help of this relation we get that 1−μ(F^{α}) = μ(F′) ≤ ν((F′)^{α})+α ≤ ν(X \F)+α = 1−ν(F)+α, i.e. ν(F) ≤ μ(F^{α})+α. Hence d(ν, μ) ≤ α. In such a way we have shown that d(ν, μ) ≤ d(μ, ν). Because of symmetry reasons d(μ, ν) = d(ν, μ). iii.) d(μ_{1}, μ_{3}) ≤ d(μ_{1}, μ_{2}) + d(μ_{2}, μ_{3}). If d(μ_{1}, μ_{2}) = α, d(μ_{2}, μ_{3}) = β, then μ_{1}(F) ≤ μ_{2}(F^{α+ε}) + α + ε, μ_{2}(F^{α+ε}) ≤ μ_{3}((F^{α+ε})^{β+ε}) + β + ε for all numbers ε > 0 and closed sets F. As (F^{α+ε})^{β+ε}) ⊂ F^{α+β+2ε} this implies that μ_{1}(F) ≤ μ_{3}(F^{α+β+2ε}) + α + β + 2ε. Since this relation holds for all closed sets F and numbers ε > 0 it implies relation iii.). We show that d(μ_{n}, μ) → 0 if and only if μ_{n} ⇒ μ. If d(μ_{n}, μ) → 0, then lim sup_{n→∞} μ_{n}(F) ≤ μ(F^{ε})+ε for all closed sets F and numbers ε > 0. As F = ⋂_{ε→0} F^{ε},

lim_{ε→0} (μ(F^{ε}) + ε) = μ(F). This relation implies the inequality lim sup_{n→∞} μ_{n}(F) ≤ μ(F)

for all closed sets F, and this is equivalent to the statement μ_{n} ⇒ μ.

To prove the other direction of the statement first we show that for all ε > 0 there exists an integer N = N(ε) > 0 and a partition V_{1}, …, V_{N}, V_{N+1} of the space X which satisfies the following conditions: μ(∂V_{k}) = 0, k = 1, …, N + 1, d̄(V_{k}) < ε^{2}, k = 1, …, N, and μ(V_{N+1}) ≤ \frac{ε}{2}, where ∂A denotes the boundary of the set A and d̄(A) its diameter. Indeed, let x_{1}, x_{2}, … be an everywhere dense set in the space X. For all x_{k} let us choose a ball G(x_{k}, δ_{k}) in the space X of center x_{k} and radius δ_{k} with some δ_{k} such that \frac{ε^{2}}{2} < δ_{k} < ε^{2} for which μ (∂G(x_{k}, δ_{k})) = 0. The union of these balls covers the whole space X. Let us choose such a number

N = N(ε) for which μ ( ⋃_{k=1}^{N} G(x_{k}, δ_{k})) ≤ \frac{ε}{2}. Let V_{N+1} = X \ ( ⋃_{k=1}^{N} G(x_{k}, δ_{k})) and

V_{k} = G(x_{k}, δ_{k}) \ ( ⋃_{j=1}^{k=1} G(x_{j}, δ_{j})), k = 1, …, N. These sets satisfy the conditions

we have imposed. For all closed sets F ⊂ X let us define the set B(F) = ⋃_{k: V_{k}∩F ≠∅} V_{k}. Let us observe

that F ⊂ B(F) ⊂ F^{ε} ∪ V_{N+1}. Further, lim_{n→∞} sup_{F closed set} |μ_{n}(B(F) − μ(B(F)| = 0,

because lim_{n→∞} μ_{n}(V_{k}) = μ(V_{k}) for all k = 1, …, N + 1, there are finitely many sets of the form B(F), and all of them are the union of finitely many sets V_{k}. Hence there exists a threshold index n = n(ε) independent of the closed set F such that

μ(F^{ε}) − μ_{n}(F) ≥ μ(B(F)) − μ(V_{N+1}) − μ_{n}(B(F)) ≥ −ε

for all closed sets F. This implies that d(μ_{n}, μ) ≤ ε, if n ≥ n_{0}(ε). Hence lim_{n→∞} d(μ_{n}, μ) = 0 as we claimed.

We show that the metric space (M, d) is separable. Let x_{1}, x_{2}, …, be an everywhere dense set in the space X, let M_{0} be the set of those discrete probability measures which are concentrated in the finite subsets of the set {x_{1}, x_{2}, … } and the measure of all points is a rational number. This is a countable set, hence it is enough to show that M_{0} is an everywhere dense subset of the set M. This can be seen for instance by a slight modification of the previous argument. This shows that for an arbitrary measure μ ∈ M and number ε > 0 we can choose a partition V_{1}, …, V_{N} of the set X and a number η > 0 for which the following statement holds: If a probability measure ν ∈ M satisfies the condition |μ(V_{k}) − ν(V_{k})| ≤ η for all numbers k = 1, …, N, then the measure ν also satisfies the relation d(μ, ν) < ε. Since for all μ ∈ M M_{0} contains such a measure ν, hence M_{0} is an everywhere dense subset of the set M. We show that if X is a complete separable space, then the same property holds for the space (M, d). It is enough to show that if

lim_{n→∞} sup_{m: m≥n} d(μ_{n}, μ_{m}) = 0,

then the series μ_{n}, n = 1, 2, … is relatively compact, i.e. it has a weakly convergent subsequence. To prove this statement it is enough to show that for all numbers ε > 0 there exists a compact set K ⊂ X, for which μ_{n}(K) ≥ 1 − ε for all indices n.

The statement from which we want to deduce the completeness of the space (M, d) can be slightly weakened. It is enough to show that for arbitrary ε > 0 there exists a compact set K = K(ε) whose neighbourhood of radius ε K^{ε} = {x: ρ(x, K) < ε} satisfies the inequality μ_{n}(K^{ε}) ≥ 1 − ε for all indices n = 1, 2, . . .. Indeed, let us consider such sets K (ε2^{−m}) with ε2^{−m} for all m = 1, 2, …, and let us define

the set K = ⋂_{m=1}^{∞}(K(ε2^{−m})^{ε2^{−m}}. Then μ_{n}(K) ≥ 1 − ∑_{m=1}^{∞} ε2^{−m} = 1 − ε. Hence

it is enough to prove that this set K is relatively compact, (that is, its closure is compact). To show this let us recall the result by which a subset A of a separable complete metric space is relatively compact if and only if this set A has a finite δ-net for all δ > 0, i.e. there exists a finite subset of the space X such that for arbitrary x ∈ A the distance of x from one of the points of this finite set is less than δ. This property holds for the above set K, since for all numbers δ > 0 there exists an integer m such that δ > ε2^{−m}. Further, the set K(ε2^{−m})^{ε2^{−m}} has a finite δ-net for this m, and this is also a finite δ-net for the original set K. This weakened statement can be proved in the following way: For a fixed number ε > 0 let us choose an index n_{0} = n_{0}(ε) such that the relation d(μ_{n_{0}}, μ_{n}) ≤ \frac{ε}{4} holds for all n ≥ n_{0}, and let K_{0} ⊂ X be a compact set such that μ_{n_{0}}(K_{0}) ≥ 1 − \frac{ε}{4}. Then μ_{n}(K_{0}^{ε/4}) ≥ μ_{n_{0}}(K_{0}) − \frac{ε}{4} ≥ 1 − \frac{ε}{2} for all numbers n ≥ n_{0}. Let us choose such a compact set K_{1}, for which μ_{n}(K_{1}) ≥ 1 − \frac{ε}{2} for all numbers n ≤ n_{0}. Then the set K = K_{1} ∪ K_{0} is compact, and μ_{n}(K^{ε}) ≥ 1 − ε for all numbers n = 1, 2, . . .. Indeed, μ_{n}(K^{ε}) ≥ μ_{n}(K_{0}^{ε/4}) ≥ 1 − ε, if n ≥ n_{0}, and μ_{n}(K^{ε}) ≥ μ_{n}(K_{1}) ≥ 1 − ε, if n ≤ n_{0}. The statements of problem 2 are proved.

3.) Let us observe that the space X has a partition X_{1} = {A_{1}, A_{2}, … } such that d̄(A_{j}) ≤ 1, and μ(∂A_{j}) = 0 for all indices j = 1, 2, . . .. Here d̄(A) denotes the diameter of the set A and ∂A its boundary. (This statement follows from the argument presented at the start of problem 2, when it was shown that the relation μ_{n} ⇒ μ implies that d(μ_{1}, μ_{2}) → 0.) By splitting further the elements of this partition we get a more and more refined sequence of partitions X_{1} ⊃ X_{2} ⊃ ⋯ X_{k} ⊃ ⋯ of the space X such that the elements of these partitions satisfy the relations d̄(A_{j_{1},...,j_{k}}) ≤ 2^{−k} and μ (∂A_{j_{1},...,j_{k}}) = 0. (A_{j_{1},...,j_{k}} ∈ X_{k}.) Let us define a similar sequence of more and more refined partitions Y_{1} ⊃ Y_{2} ⊃ ⋯ Y_{k} ⊃ ⋯ of the intervals (0, 1] (endowed with the Lebesgue measure) in the following way:

Put Y_{1} = {B_{1}, …, B_{k}, … }, B_{k} = (b_{k−1}, b_{k}], b_{k} = ∑_{j=1}^{k} μ(A_{j}), k = 1, 2, …, and if

the sets B_{j_{1},...,j_{k}} = (b_{j_{1},...,j_{k−1}}, b_{j_{1},...,j_{k}}], of the partition Y_{k} are already defined, and they are defined so that the indentity b_{j_{1},...,j_{k}} − b_{j_{1},...,j_{k−1}} = μ(A_{j_{1},...,j_{k}}) holds, then split all intervals B_{j_{1},...,j_{k}} into subsequent non-overlapping intervals

B_{j_{1},...,j_{k},s} = (b_{j_{1},...,j_{k},s−1}, b_{j_{1},...,j_{k},s}],

of length μ (A_{j_{1},...,j_{k},s}). These smaller intervals will be the elements of the partition Y_{k+1} of the interval [0, 1]. After the definition of these partitions let us fix for all integers k ≥ 1 and elements A_{j_{1},...,j_{k}} of the partition X_{k} a point x_{j_{1},...,j_{k}} ∈ A_{j_{1},...,j_{k}}.

Now for all k = 1, 2, … we define a random variable ξ_{k}(y) on the probability space ((0, 1], B, λ) with values on the space X by means of the following formula: Put ξ_{k}(y) = x_{j_{1},...,j_{k}} if y ∈ B_{j_{1},...,j_{k}}. We claim that the limit ξ(y) = lim_{k→∞} ξ_{k}(y) exists

for all y ∈ (0, 1], and it is a μ distributed random variable. The above limit really exists, because for all y ∈ (0, 1] a uniquely determined sequence of decreasing intervals B_{j_{1},...,j_{k}}, k = 1, 2, …, exists in such a way that y ∈ B_{j_{1},...,j_{k}}. This implies that the sequence of points ξ_{k}(y) ∈ A_{j_{1},...,j_{k}} is a Cauchy, hence also a convergent sequence. The union of the σ-algebras X_{k}, k = 1, 2, …, generates the Borel σ-algebra in the space (X, ρ). Hence to prove that the above defined random variable ξ has distribution μ it is enough to show that P (ξ ∈ A_{j_{1},...,j_{k}}) = μ (A_{j_{1},...,j_{k}}) for all numbers k = 1, 2, … and sets A_{j_{1},...,j_{k}}. It follows from the construction of the random variable ξ that if y ∈ B_{j_{1},...,j_{k}} then ξ(y) ∈ Ā_{j_{1},...,j_{k}}, where Ā denotes the closure of the set A. First we show that it follows from this fact and the relation

P (ξ(y) ∈ ∂A_{j_{1},...,j_{k}}) = 0 for all numbers k = 1, 2, … and indices j_{1}, …, j_{k}, (∗)

to be proven later that ξ is μ distributed. Indeed, these relations imply that

P (ξ(y) ∈ A_{j_{1},...,j_{k}}) ≥ P (ξ(y) ∈ Ā_{j_{1},...,j_{k}}) − P (ξ(y) ∈ ∂A_{j_{1},...,j_{k}})
≥ λ (B_{j_{1},...,j_{k}}) = μ (A_{j_{1},...,j_{k}}) ,

and summing up these inequalities we get that

1 = ∑_{j_{1},...,j_{k}} P (ξ(y) ∈ A_{j_{1},...,j_{k}}) ≥ ∑_{j_{1},...,j_{k}} μ (A_{j_{1},...,j_{k}}) = 1.

As a consequence, the above inequalities are actually identities, and the distribution of ξ is μ. To prove formula (∗) let us observe that since μ(∂A_{j_{1},...,j_{k}}) = 0 for all numbers ε > 0 there exists a number δ = δ(ε) > 0 such that the neighbourhood (∂A_{j_{1},...,j_{k}})^{δ} of radius δ of the set ∂A_{j_{1},...,j_{k}} satisfies the inequality μ ((∂A_{j_{1},...,j_{k}})^{δ}) < ε. Let us choose an integer s so large that the diameters of the elements of the partition X_{k} satisfy the inequality d̄(A_{j′_{1},...,j′_{s}}) < \frac{δ}{2} for all sets A_{j′_{1},...,j′_{s}}. Since ρ(ξ_{s}(y), ξ(y)) ≤

max_{j′_{1},...,j′_{s}} d̄(A_{j′_{1},...,j′_{s}}) ≤ \frac{δ}{2}, hence in the case ξ(y) ∈ ∂A_{j_{1},...,j_{k}} ρ (ξ_{s}(y), ∂A_{j_{1},...,j_{k}}) <

\frac{δ}{2}. This implies that if ξ(y) ∈ ∂A_{j_{1},...,j_{k}}, then the indices j′_{1}, …, j′_{s} for which y ∈ B_{j′_{1},...,j′_{s}} are such that ξ_{s}(y) ∈ A_{j′_{1},...,j′_{s}}, ρ (A_{j′_{1},...,j′_{s}}, ∂A_{j_{1},...,j_{k}}) < \frac{δ}{2}, hence A_{j′_{1},...,j′_{s}} ⊂ (∂A_{j_{1},...,j_{k}})^{δ}. This implies that

{y: ξ(y) ∈ ∂A_{j_{1},...,j_{k}}}
⊂ {y: ξ_{s}(y) ∈ A_{j′_{1},...,j′_{s}} ⊂ (∂A_{j_{1},...,j_{k}})^{δ} with some indices j′_{1}, …, j′_{s}} ,

and

λ {y: ξ(y) ∈ ∂A_{j_{1},...,j_{k}}} ≤ ∑_{(j′_{1},...,j′_{s}) : A_{j′_{1},...,j′_{s}} ⊂(∂A_{j_{1},...,j_{k}})^{δ}} λ (B_{j′_{1},...,j′_{s}})

= ∑_{(j′_{1},...,j′_{s}) : A_{j′_{1},...,j′_{s}} ⊂(∂A_{j_{1},...,j_{k}})^{δ}} μ (A_{j′_{1},...,j′_{s}}) ≤ μ ((∂A_{j_{1},...,j_{k}})^{δ}) ≤ ε.

Since this statement holds for all ε > 0, this implies relation (∗) and the statement of problem 3.

4.) We construct the random variables ξ_{n} with distribution μ_{n}, n = 1, 2, …, and the random variable ξ with distribution μ simultaneously by means of the construction of problem 3. The only novelty is that we apply the same partitions X_{1} ⊂ X_{2} ⊂ ⋯ in the construction of all random variables ξ_{n}, n = 1, 2, …, and ξ, and demand that the boundaries of the elements A_{j_{1},...,j_{k}} ∈ X_{k} of the partitions satisfy the relation μ(∂A_{j_{1},...,j_{k}}) = 0 and μ_{n}(∂A_{j_{1},...,j_{k}}) = 0 for all k = 1, 2, …, A_{j_{1},...,j_{k}} ∈ X_{k} and n = 1, 2, . . .. We remark that it causes no extra difficulty to find partitions X_{k} with such elements whose boundary have the above property. Indeed, we can for

instance introduce a new probability measure μ̄ = \frac{μ}{2} + ∑_{n=1}^{∞} 2^{−n−1}μ_{n} and construct

a sequence of more and more refined partitions of the space X in the same way as it was done in the construction of problem 3 with the only difference that we replace the measure μ by the measure μ̄. Then the boundaries of the partitions satisfy the desired requirement for all measures μ and μ_{n}, n = 1, 2, . . .. We claim that if μ_{n} ⇒ μ, then ξ_{n} → ξ with probability one for the random variables constructed in the above way. Let us observe that if μ_{n} ⇒ μ, then lim_{n→∞} μ_{n}(A_{j_{1},...,j_{k}}) = μ(A_{j_{1},...,j_{k}}) for all j_{1}, …, j_{k}, since the boundaries of these sets have zero μ measure. This relation and the structure of our construction imply that b_{j_{1},...,j_{k}}(n) → b_{j_{1},...,j_{k}} for all k = 1, 2, … and indices j_{1}, …, j_{k} as n → ∞, where b_{j_{1},...,j_{k}}(n) and b_{j_{1},...,j_{k}} denote the right-hand side end-points of the intervals B_{j_{1},...,j_{k}}(n) and B_{j_{1},...,j_{k}} which appear in the partitions Y_{k}(n) and Y_{k} of the intervals (0, 1] introduced during the definition of the random variables ξ_{n} and ξ. For a fixed small number ε > 0 let us choose a number k = k(ε) for which 2^{−k} < ε. Then the diameter of the elements A_{j_{1},...,j_{k}} of the partition X_{k} are less than 2^{−k} < ε. Let us choose a finite set D_{k} of k-tuples {j_{1}, …, j_{k}} for which

∑_{(j_{1},...,j_{k}) : (j_{1},...,j_{k})∈D_{k}} μ(A_{j_{1},...,j_{k}}) > 1 − \frac{ε}{2}. There exists an index n_{0} = n_{0}(ε) such

that the set

B(ε) = B(k, ε, n_{0}) = ⋃_{(j_{1},...,j_{k})∈D_{k}} ⋃_{n≥n_{0}}(B_{j_{1},...,j_{k}} △ B_{j_{1},...,j_{k}}(n))

satisfies the inequality λ(B(ε)) < \frac{ε}{2}, where A △ B = (A \ B) ∪ (B \ A) denotes the symmetric difference of two sets A and B. The above relations imply that the set

B_{1}(ε) = ⋃_{(j_{1},...,j_{k})∈D_{k}}(B_{j_{1},...,j_{k}} \ B(ε)) satisfy the relation λ(B_{1}(ε)) > 1 − ε. Define

the set B_{2}(ε) = B_{1}(ε) ∩ Y_{0} ∩ ⋂_{n=1}^{∞} Y_{0,n}, where Y_{0,n} = (0, 1) \ ⋃_{k=1}^{∞} ⋃_{j_{1},...,j_{k}}{b_{j_{1},...,j_{k}}(n)},

n = 1, 2, …, and Y_{0} = (0, 1) \ ⋃_{k=1}^{∞} ⋃_{j_{1},...,j_{k}}{b_{j_{1},...,j_{k}}(n)}. The inequality λ(B_{2}(ε)) >

1 − ε also holds, since the set B_{1}(ε) \ B_{2}(ε) is countable. Furthermore, if n > n_{0} and y ∈ B_{2}(ε), then ρ(ξ_{n}(y), ξ(y)) ≤ ε, since in this case ξ_{n}(y) and ξ(y) are in the closure of the same set A_{j_{1},...,j_{k}}. This implies that

λ (lim sup_{n→∞} |ξ_{n} − ξ| ≥ ε) < ε.

Since this relation holds for all ε > 0, it implies the statement of problem 3. 5.) Put X̄ = X × [0, 1], and let us define the measurable space (Ω, A) as Ω = X̄ ×

X × ⋯ × X × ⋯, and A is the product of the σ-algebras on the coordinate spaces X̄ and X. In the point ω = (x, u, x_{1}, x_{2}, …) ∈ Ω let us define the random variables ξ and ξ_{n} by the formulas ξ(ω) = x, ξ_{n}(ω) = x_{n}, n = 1, 2, . . .. The measure P will be defined with the help of the measure μ̄ = μ × λ introduced on the space X̄ and appropriately defined conditional distributions Q_{n}((x, u), A), n = 1, 2, …, where (x, u) ∈ X̄ = X×[0, 1], and A ⊂ X is a measurable subset of the space X. (The function Q_{n}((x, u), A) is called a conditional distribution function if Q_{n}((x, u), ·) is a probability measure on the space (X, A) for all points (x, u) ∈ X̄, and Q_{n}(·, A) is a measurable function for all sets A ∈ A.) The measure P will be defined in the following way: The distribution of the first coordinate (x, u) ∈ X̄ is μ̄, the coordinates x_{n} ∈ X, n = 1, 2, …, are conditionally independent for fixed (x, u), and the conditional distribution of the coordinate x_{n} under this condition is Q_{n}((x, u), ·). In a formal way, put

P (A × A_{1} × ⋯ × A_{n}) = ∫_{(x,u)∈A} Q_{1}((x, u), A_{1}) … Q_{n}((x, u), A_{n})) dμ(x) du

for all measurable sets A ⊂ X̄, A_{j} ⊂ X, j = 1, …, n.

(By some non-trivial results of the measure theory the above formula and its extension really defines a probability measure P. It is worth mentioning that this fact follows from such a result (the Tulcea–Ionescu theorem), which does not demand some nice topological properties of the space. This is the reason why this method can be applied in non-complete metric spaces which may not have good nice topological properties.) For all numbers k = 1, 2, …, let us define such a partition A_{k} = {A_{1,k}, A_{2,k}, … } of

X for which d̄(A_{j,k}) < \frac{1}{k}, and μ (∂A_{j,k}) = 0, j = 1, 2, …, where d̄(A) denotes the diameter and ∂A the boundary of the set A. Let us define for all k = 1, 2, … an

index m(k) such that μ ( ⋃_{j≥m(k)} A_{j,k}) ≤ \frac{1}{k^{2}} and μ(A_{j,k}) > 0 for all 1 ≤ j ≤ m(k).

(To satisfy this latter conditions we can re-index the sets A_{j,k} if this is necessary.) After this let us consider a series of numbers 1 = n_{1} < n_{2} < n_{3} < ⋯ such that

|μ_{n}(A_{j,k}) − μ(A_{j,k})| < \frac{μ(A_{j,k})}{k^{2}m(k)}, for all numbers 1 ≤ j < m(k)
and n_{k} ≤ n < n_{k+1}.

This is possible, since lim_{n→∞} μ_{n}(A_{j,k}) = μ(A_{j,k}) for all numbers k and j because of the relation μ(∂A_{j,k}) = 0. Let us introduce the numbers

λ_{j,k,n} = \frac{min (μ(A_{j,k}), μ_{n}(A_{j,k}))}{μ(A_{j,k})}, n_{k} ≤ n < n_{k+1}, j < m(k).

Clearly, 1− \frac{1}{k^{2}} ≤ λ_{j,k,n} ≤ 1. Let us define the conditional distributions Q_{n}((x, u), ·) first only to some pairs (x, u) ∈ X̄ and n which satisfy certain conditions. Put

Q_{n}((x, u), C) = \frac{μ_{n}(C ∩ A_{j,k})}{μ_{n}(A_{j,k})}, if n_{k} ≤ n < n_{k+1}, x ∈ A_{j,k}, 1 ≤ j < m(k),
and 0 ≤ u ≤ λ_{j,k,n} for all sets C ∈ A.

On the domain where we have not defined the conditional distributions Q_{n}(·, ·) yet we want to do this in such a way which guarantees that the projection of the measure P to the n-th coordinate is μ_{n}. To do this let us introduce the numbers

P_{n} = (1 − ∑_{j=1}^{m(k)−1} min [μ_{n}(A_{j,k}), μ(A_{j,k})]) , n_{k} ≤ n < n_{k+1}.

(This number is the μ measure of that part of the set X̄ = X × [0, 1] where we have still not defined the conditional distribution Q_{n}(·, ·)). Then let us also define the following probability measures μ̄_{n} on the space X:

μ̄_{n}(C) = \frac{1}{P_{n}} [μ_{n}(C) − ∑_{j=1}^{m(k)−1} min [μ_{n}(A_{j,k}), μ(A_{j,k})] \frac{μ_{n}(C ∩ A_{j,k})}{μ_{n}(A_{j,k})}] , C ∈ A,

and put

Q_{n}((x, u), C) = μ̄_{n}(C), if C ∈ A, n_{k} ≤ n < n_{k+1},
and x ∈ A_{j,k}, j ≥ m(k) or x ∈ A_{j,k}, j < m(k) and λ_{j,k,n} < u ≤ 1.

We claim that

∫ Q_{n}((x, u), C)μ( dx) du = μ_{n}(C), C ∈ A.  (+)

Indeed, if n_{k} ≤ n < n_{k+1}, then 1 ≤ j < m(k) and in the case C ∈ A

∫ Q_{n}((x, u), C ∩ A_{j,k})μ( dx) du = μ(A_{j,k})λ_{j,k,n} \frac{μ_{n}(C ∩ A_{j,k})}{μ_{n}(A_{j,k})} + μ_{n}(C ∩ A_{j,k})

− min (μ(A_{j,k}), μ(A_{j,k})) \frac{μ_{n}(C ∩ A_{j,k})}{μ_{n}(A_{j,k})} = μ_{n}(C ∩ A_{j,k}).

On the other hand, put B_{k} = X\( ⋃_{j=1}^{m(k)−1} A_{j,k}). Then the system of sets {A_{j,k}, 1 ≤

j < m(k), B_{k}} supplies a partition of the space X. In particular, A_{j,k} ∩ B_{k} = ∅ for all 1 ≤ j < m(k). Observe that

∫ Q_{n}((x, u), C ∩ B_{k})μ( dx) du = μ_{n}(C ∩ B_{k}).

By summing up these identities we get relation (+), which means that the random variables ξ_{n} have the prescribed distribution μ_{n} for all numbers n = 1, 2, . . .. On the other hand,

P ( sup_{n_{k}≤n<n_{k+1}} ρ(ξ_{n}, ξ) ≥ \frac{1}{k} | ξ̄ = (x, u)) = 0

if (x, u) ∉ X_{1}(k) ⊂ X̄, where ξ̄(x, u, x_{1}, x_{2}, …) = (x, u), and

X_{1}(k) = B_{k} × [0, 1] ∪ ⋃_{j=1}^{m(k)−1} {(x, u): x ∈ A_{j,k}, inf_{n_{k}≤n<n_{k+1}} λ_{j,k,n} ≤ u ≤ 1} .

Hence

P ( sup_{n_{k}≤n<n_{k}} ρ(ξ_{n}, ξ) > \frac{1}{k} ) ≤ μ × λ(X_{1}(k))

= ∑_{j=1}^{m(k)} (1 − min_{n_{k}≤n<n_{k+1}} λ_{j,k,n}) μ(A_{j,k}) + μ(B_{k}) ≤ \frac{2}{k^{2}} .

Since

∑_{k=1}^{∞} P ( sup_{n_{k}≤n<n_{k}} ρ(ξ_{n}, ξ) > \frac{1}{k} ) ≤ ∑_{k=1}^{∞} \frac{2}{k^{2}} < ∞

it follows from the Borel–Cantelli lemma that ξ_{n} → ξ with probability one if n → ∞. 6.) Let F be an arbitrary closed set. As F = ⋂_{δ→0} F^{δ} = F, where F^{δ} denotes the open

neighbourhood of radius δ of the set F, hence for all ε > 0 there exists a δ = δ(ε) > 0 such that μ(F^{δ}) < μ(F) + ε. As ξ_{n} ⇒ ξ stochastically, hence for all δ > 0 and ε > 0 there exists such an index n_{0} = n_{0}(ε, δ) for which P (ρ(ξ, ξ_{n}) > δ) < ε. Furthermore, {ω: ξ(ω) ∉ F^{δ}} ⊂ {ω: ξ_{n}(ω) ∉ F } ∪ {ω: ρ(ξ_{n}(ω), ξ(ω)) > δ}, hence 1 − μ(F^{δ}) ≤ 1 − μ_{n}(F) + ε, and μ(F) + ε ≥ μ(F^{δ}) ≥ μ_{n}(F) − ε, if n ≥ n_{0}. This implies that lim sup_{n→∞} μ_{n}(F) ≤ μ(F) + 2ε. Since this inequality holds for all ε > 0,

this implies that lim sup_{n→∞} μ_{n}(F) ≤ μ(F) for all closed sets F, i.e. μ_{n} ⇒ μ.

7.) To prove that ξ = F^{−1}(η) is F distributed it is enough to show that

{ω: η(ω) < F (x)} ⊂ {ω: F^{−1}(η)(ω) < x} ⊂ {ω: η(ω) ≤ F (x)}.

The middle term is contained in the right-hand side term. Indeed, if F^{−1}(η)(ω) < x then there exists such a number h > 0 for which F^{−1}(η)(ω) = sup{u: F (u) < η(ω)} < x − h. But this implies that η(ω) ≤ F (x). Indeed, if the relation F (x) < η(ω) held, then the number x would be in the set of numbers u whose supremum defines the quantity F^{−1}(η), and this contradicts to the inequality F^{−1}(η)(ω) < x − h. To prove the left-hand side of this relation observe that if η(ω) < F (x), then η(ω) = F (x)−h, and F^{−1}(η(ω)) = F^{−1}(F (x)−h)) = sup{v: F (v) < F (x)−h} with an appropriate number h > 0. On the other hand, sup{v: F (v) < F (x) − h} < x, because F (x) is a function continuous from the left, and as a consequence F (v) < F (x) − h implies that there exists such a number δ = δ(h) > 0, for which v < x − δ, that is F^{−1}(η(ω)) = sup{v: F (v) < F (x)−h} ≤ x−δ < x. Hence also the left-hand side part of the above relation holds. To prove that F̃(ξ, ε) is uniformly distributed in the interval [0, 1], let us define the quantity z(x) = sup{y: F (y) < x} for all real numbers x. As the distribution function F (x) is continuous from the left, hence F (z) ≥ x. Let us consider the cases F (z) = x and F (z) < x separately. If F (z) = x, then F (u + 0) < x for all numbers u < z, and {ω: F̃(ξ(ω), ε(ω)) < x} = {ω: ξ(ω) < z}. Hence P (F̃(ξ, ε) < x) = P (ξ < z) = F (z) = x. If F (z) < x, then F (z + 0) ≥ x, and

{ω: F̃(ξ(ω, ε(ω)) < x}
= {ω: ξ(ω) < z} ∪ {ω: ξ(ω) = z, F (z) + ε(ω)[F (z + 0) − F (z)] < x}.

Hence

P (F̃(ξ, ε) < x) = P (ξ < z) + P (ξ(ω) = z) P (ε(ω)[F (z + 0) − F (z)] < x − F (z))

= F (z) + [F (z + 0) − F (z)]\frac{x − F (z)}{F (z + 0) − F (z)} = x.

This implies the second statement of problem 7. 8.) The results of problem 7 imply that the distribution of the random variable ξ̄ is

F, and the distribution of η̄ is G. Furthermore F̃(¯ξ̄, ε) is uniformly and ¯ η̄ is G distributed random variable. To show that the distribution of the vectors (ξ̄, η̄) and (¯ξ̄, ¯ η̄ agree, it is enough to show that F^{−1}(F̃(¯ξ̄, ε)) = ¯ ξ̄ with probability one. Indeed, this means that both random vectors can be represented (with the exception of a set of measure zero) as the transformation of an appropriate in the interval [0, 1] uniformly distributed random variable, (both coordinates of the vectors are obtained as the transform of the same random variable) and the representation of both vectors applies the same transformation. The statement from which we can deduce the statement of problem 8 can be even weakened a little bit. It is enough to show that P (F^{−1}(F̃(¯ξ̄, ε)) ≤ ¯ ξ̄) = 1, since if one random variables is larger than another random variable with the same distribution functions with probability one, then these two random variables equal with probability one. If ¯ ξ̄(ω) = x, then

F^{−1}(F̃(¯ξ̄(ω), ε(ω))) = sup{u: F (u) < F̃(x, ε(ω))},

and since F (v) ≥ F̃(x, ε(ω)) if v > x, this implies that F^{−1}(F̃(¯ξ̄(ω), ε(ω))) ≤ x = ¯ξ̄(ω) in this case. Problem 8 is solved.

9.) Let us remark that if ξ and η are defined by the formula ξ = F^{−1}(ζ) and η = G^{−1}(ζ), where ζ is a random variable with uniform distribution in the interval [0, 1], that is these random variables are defined by means of the quantile transform, then the two sides of the inequality investigated in this problem are equal. Let us first prove this inequality in the special case when the distributions of both random variables ξ and η are concentrated in a finite subset X = {x_{1}, …, x_{n}}, x_{1} < x_{2} < ⋯ < x_{n} of the real line. Put p_{j} = P (ξ = x_{j}), q_{k} = P (η = x_{k}), and let us consider the joint distribution of the random variables ξ and η r(x_{j}, y_{k}) = P (ξ = x_{j}, η = x_{k}), 1 ≤ j, k ≤ n. Let us introduce the quantities

r(x_{j}, x_{k}, y_{j}, y_{k}) = min (r(x_{j}, y_{k}), r(x_{k}, y_{j})) ,
r = max_{\begin{matrix}\{x_{j},x_{k},y_{j},y_{k}\}∈X×X×X×X \\ x_{j}<x_{k}, y_{j}<y_{k} \end{matrix}} r(x_{j}, x_{k}, y_{j}, y_{k})

Let us observe that if the vector (ξ, η) is constructed by means of the quantile transform, then r = 0 for the above defined number r. Furthermore, the condition r = 0 and the distribution F of the random variable ξ together the distribution G of the random variable η also determine the joint distribution of the vector (ξ, η), i.e. the property r = 0 characterizes the quantile transform. Indeed, we may assume without violating the generality that the probability space (Ω, A, P), where the random vector (ξ, η) is defined has the following structure: Ω = X × X, A is the discrete σ-algebra on X × X, and the random variables are defined as ξ(x_{j}, x_{k}) = x_{j} η(x_{j}, x_{k}) = x_{k}, 1 ≤ j, k ≤ n. In this space the measure P with the property r = 0 we are looking for can be represented as the solution of the following “transport problem”: Let us consider the bipartitated graph consisting of the pairs (x_{j}, x_{k}), 1 ≤ j, k ≤ n, attach the weights p(x_{j}) = p_{j} = P (ξ = x_{j}) to the first coordinates and the weights q(x_{k}) = q_{k} = P (η = x_{k}), 1 ≤ j, k ≤ n to the second coordinates. Then let us consider such a transports where weights p_{j} are sent from the first coordinates x_{j}, and weights q_{k} arrive to the second coordinates Let r(j, k) denote the mass transported from the point x_{j} to x_{k}. Then P (ξ = x_{j}, η = x_{k}) = r(j, k) denotes a joint distribution with the prescribed marginal distributions, and all joint distributions with such marginal distributions can be presented in such a way. The condition r = 0 means that the transport of the weights p_{j} to weights q_{k} is done in the following way: We transport the mass p_{1} from the point x_{1} first to the place x_{1}, then if some mass is still left to the point x_{2}, then to the point x_{3}, e.t.c. After this we transport the mass p_{2} from the point x_{2} coordinate to the smallest point where some empty space is still left, then to the next smallest space, e.t.c. Then we fill the smallest places where not all masses are sent to from the points x_{3}, x_{4}, e.t.c. This means in particular, that the condition r = 0 and the marginal distributions of the random variables ξ and η determine the joint distribution of the random vector (ξ, η). We claim that

min_{ξ is F distributed η is G distributed} EΦ(ξ − η) = EΦ(ξ̄− η̄),  (b)

where (ξ̄, η̄) is a random vector with marginal distributions F and G such that r = 0. Indeed, if the distribution of the random vector (ξ, η) is such that r ≠ 0, then there exists a quadruple (x_{j}, x_{k}, y_{j}, y_{k}), x_{j} < x_{k} and y_{j} < y_{k} such that

r̃ = r(x_{j}, x_{k}, y_{j}, y_{k}) = min (r(x_{j}, y_{k}), r(x_{k}, y_{j})) > 0.

We show that in this case a new joint distributions r̃(x_{j}, x_{k}), 1 ≤ j, k ≤ n, can be introduced in such a way that the marginal distribution of a random vector (ξ̃, η̃) with this distribution has marginal distributions F and G, and EΦ(ξ − η) ≤ EΦ(ξ̃ − η̃). Furthermore, if Φ is a strictly convex function then there is a strict inequality in the last relation. We shall define this probabilities in the following way.

r̃(x_{j}, y_{j}) = r(x_{j}, y_{j}) + r̃
r̃(x_{k}, y_{k}) = r(x_{k}, y_{k}) + r̃
r̃(x_{j}, y_{k}) = r(x_{j}, y_{k}) − r̃
r̃(x_{k}, y_{j}) = r(x_{k}, y_{j}) − r̃
r̃(x, y) = r(x, y) otherwise.

Then the marginal distributions of the random vector (ξ̃, η̃) are the prescribed ones, and

EΦ(ξ̃− η̃) − EΦ(ξ − η) = r̃(Φ(x_{j} − y_{j}) + Φ(x_{k} − y_{k}) − Φ(x_{j} − y_{k}) − Φ(x_{k} − y_{j})) .

This expression is non-negative. Moreover, it is strictly positive, if the function Φ(·) is strictly convex. Indeed,

x_{j} − y_{k} < \begin{matrix}x_{j} − y_{j} \\ x_{k} − y_{k} \end{matrix} < x_{k} − y_{j},

hence the convexity of the function Φ implies that

Φ(x_{j} − y_{j}) + Φ(x_{k} − y_{k}) ≤ Φ(x_{j} − y_{k}) + Φ(x_{k} − y_{j}),

(here we also exploit that (x_{j} − y_{j}) + (x_{k} − y_{k}) = (x_{j} − y_{k}) + (x_{k} − y_{j}),) and there is a strict inequality if Φ is a strictly convex function. We show that the above relations imply formula (b). The proof of this statement is simpler in the case when Φ(·) is a strictly convex function. Indeed, the function EΦ(ξ−η) takes its minimum somewhere if such pairs of vectors (ξ, η) are considered which are prescribed at the left-hand of formula (b). By the results of the previous paragraph this minimum is taken in the case r = 0. If the function Φ(·) is convex, but not necessarily strictly monotone, then for all ε > 0 let us define the function Φ_{ε}(x) = Φ(x) + εx^{2}. Then Φ_{e}(·) is a strictly convex function, and we get by letting ε → 0 the relation

Φ(ξ − η) = lim_{ε→ε} Φ_{ε}(ξ − η) ≥ lim_{ε→ε} Φ_{ε}(ξ̄− η̄) = Φ(ξ̄− η̄).

This implies the statement of problem 9 in the case when the distribution of the random variables ξ and η are concentrated in finitely many points. If F and G are two distribution functions concentrated to a finite interval, then it is useful to approximate these distributions by the discrete distributions F_{n}(x) = F (\frac{[nx]}{n}) and G_{n}(x) = G (\frac{[nx]}{n}). More precisely, it is worthwhile to approximate the two dimensional distribution H(x, y) with marginal distributions F (x) and G(y) by the distribution H_{n}(x, y) = H (\frac{[nx]}{n}, \frac{[ny]}{n}), where [u] denotes the integer part of the number u. By applying the result of problem 9 in the already proven case and letting n → ∞ we get the desired results in this case. The general case can be reduced to the previous case by means of an appropriate limiting procedure. Let us truncate our random variables at the level ±u. We do this truncation in such a way that if the vector (ξ, η) takes its value outside the square [−u, u] × [−u, u], then the truncated version of this vector has its value in the origin. Then carrying out the limit procedure u → ∞ we can get the result of problem 9 in the general case. We make some comments which may be useful when carrying out this limit procedure. The convexity of the function Φ implies that Φ(x) ≥ Ax + B for all real numbers x with appropriate constants A and B, hence EΦ(ξ − η) ≥ −|A|E(|ξ| + |η| − |B| > −∞ under the conditions of problem 9. Let us remark that by adding an appropriate linear function to Φ(x) we can reduce the problem to the case when Φ(x) ≥ 0 for all real numbers x, and Φ(0) = 0.

We may also assume that EΦ(ξ − η) < ∞, since the statement of problem 9 is otherwise trivial. These remarks may simplify the limit procedure. At the lefthand side of the inequality we can apply the monotone convergence theorem, and at the right-hand side the lemma Fatou. We omit the details.

9a.) As f(x) = |x| is a convex function, the result of problem 9 can be applied in this case. To finish the proof it is enough to show the identity

∫_{0}^{1} |F^{−1}(x) − G^{−1}(x)| dx = ∫_{−∞}^{∞} |F (x) − G(x)| dx.

This relation can be seen for instance by considering the domain

D = {(x, y): − ∞ < x < ∞, min(F (x), G(x)) < y ≤ max(F (x), G(x))} ⊂ R^{2},

and calculating the area of this domain first by integrating with respect to the variable y to get the left-hand side and then to integrate first with respect to the variable x to get the right-hand side of this identity. (Observe, that the intersection of the domain D with the horizontal line y = u is an interval whose end-points are min(F^{−1}(u), G^{−1}(u)) and max(F^{−1}(u), G^{−1}(u)).)

10.) Let γ be the projection of the measure μ or (what is equivalent because of the conditions of the problem) of the measure ν to the space X_{2}. Furthermore, let P (x, A) be the conditional distribution of the measurable sets of the form A × X_{2} with respect to prescribed value x ∈ X_{2} on the space (X_{1} × X_{2}, A_{1} × A_{2}, μ), and Q(x, C) the conditional distribution of the measurable sets of the form X × C with respect to prescribed values x ∈ X_{2} on the space (X_{2} × X_{3}, A_{2} × A_{3}, ν). That is, let μ(A × B) = ∫_{B} P (x, A)γ( dx) for all measurable sets A ∈ A, and ν(B × C) = ∫_{B} Q(x, C)γ( dx) for all sets C ∈ A_{3}. (Such conditional distributions exist on complete separable metric spaces.) Let us define the measure of measurable sets of the form A × B × C in the space X_{1} × X_{2} × X_{3} by means of the formula P (A × B × C) = ∫_{B} P (x, A)Q(x, C)γ( dx). This measure can be extended to the whole space az (X_{1} × X_{2} × X_{3}, A_{1} × A_{2} × A_{3}), and it has the required properties.

11.) Let P (x, A), where x ∈ X, A is a measurable subset of the space X, the conditional distribution of the second coordinate of the space X ×X endowed with the measure ν with respect to the first coordinate, that is let P (x, ·) be a probability measure on the measurable sets of the space X, P (·, A) a measurable function for all measurable sets A ⊂ X, and ν(A × B) = ∫_{A} P (x, B)μ( dx) for all measurable sets A ⊂ X and B ⊂ X. By a classical result of the probability theory (measure theory) such a conditional distribution exists. Let us consider the probability space (Q, B, λ), where Q = [0, 1], B is the Borel σalgebra on the interval [0, 1], and λ is the Lebesgue measure on the σ-algebra B of the interval [0, 1]. We claim that a set of random variables ζ(x, u), u ∈ Q = [0, 1], x ∈ X indexed by a parameter x ∈ X can be constructed on the probability space (Q, B, λ) in such a way that ζ(x, ·) is a random variable with distribution P (x, ·) for all points x ∈ X, where P (x, A) is the conditional distribution defined in the previous paragraph, and ζ(·, ·) is a measurable function on the product space X×[0, 1] with the natural product σ-algebra. Actually we shall prove only a slightly weaker statement. We only claim the distribution of the random variable ζ(x, ·) agrees with the formerly given measure P (x, ·) for almost all points x with respect to the measure μ. But this is not a real restriction. If we replace the measures P (x, ·) by some other probability measures on a set of the points x with μ measure zero we get an equivalent version of the conditional distribution P (x, A).

The above statement can be proved by a natural adaptation of the construction given in the solution of problem 3. In that problem we have described a possible construction of a random variable on the probability space (Q, B, λ) with prescribed distribution on a separable complete metric space (X, ρ). We want to show that by applying this method we can construct a measurable function ζ(x, u), x ∈ X, u ∈ [0, 1] on the product space X ×[0, 1] in such a way that for a fixed x ∈ X ζ(x, ·) is a μ = P (x, ·) distributed random variable on the probability space ([0, 1], B, λ), where B denotes the Borel σ-algebra and λ the Lebesgue measure on the unit interval [0, 1]. We construct such a function ζ(x, u) by applying the method of construction described in the solution of problem 3 with the following modification. We choose such partitions X_{k} whose elements A_{j_{1},...,j_{k}} has such boundaries for which the condition μ̄(∂A_{j_{1},...,j_{k}}) = 0 is satisfied, where the measure μ̄ is the projection of the measure ν to the second coordinate of the space X ×X. Then the properties of the conditional distributions imply that P (x, (∂A_{j_{1},...,j_{k}})) = 0 for all partitions X_{k} and all (countably many) sets A_{j_{1},...,j_{k}} in these partitions except a measurable set of x ∈ X with μ measure zero. Let us apply the construction described in problem 3 for all such points x for which the boundaries of all elements in the partitions have zero P (x, ·) probabilities. For the sake of a complete construction let us define ζ(x, u) = x_{0}, on the exceptional set of points x, where x_{0} ∈ X is an arbitrary fixed point. Let us observe that by applying this construction we get the function ζ(x, u) as the limit of discrete valued measurable functions. Then the limit of these functions is also measurable. The random variables ζ(x, u) constructed in such a way have the desired properties.

Define η(ω) = ζ(ξ(ω), χ(ω)) with the help of the above function ζ(x, u) and the independent random variables ξ(ω) and χω) appearing in the formulation of problem 11. (The idea behind this definition is that P (ζ(ξ(ω), χ(ω)) ∈ B|ξ(ω) = x) = P (ζ(x, χ(ω) ∈ B) = P (x, B).) We claim that this random variable η satisfies the statement of the problem, that is P (ξ(ω) ∈ A, η(ω) ∈ B) = ν(A × B) for all measurable sets A ⊂ X and B ⊂ X. Indeed, since the distribution of the random vector (χ(ω), ξ(ω)) is dv μ(dx) on the space [0, 1] × X, hence we get that

P (ξ(ω) ∈ A, η(ω) ∈ B) = E (I(ξ(ω) ∈ A)I(ζ(ξ(ω), χ(ω)) ∈ B))
= ∫ (∫ I (x ∈ A) I(ζ(x, v) ∈ B) dv) μ( dx)
= ∫ I(x ∈ A)P (x, B)μ( dx)

= ∫_{A} P (x, B)μ( dx) = ν(A × B),

where I(C) is the indicator function of the set C. In such a way we have solved problem 11.

12.) The measures μ and ν have a decomposition of the following form: μ = γ + μ_{1}, ν = γ + ν_{1}, where the measure γ is the “joint part” of the measures μ and ν, the measures μ_{1} and ν_{1} are singular to each other. This means that there exists such a set C ∈ A, for which the measure μ_{1} is concentrated to the set C and the measure ν_{1} is concentrated to the set X \ C, that is μ_{1}(X \ C) = 0, and ν_{1}(C) = 0. To see that such a decomposition exists let us consider a measure dominating both measures μ and ν (we can choose for instance the measure \frac{μ+ν}{2} as this dominating measure), let f(x) be the density function of the measure μ and g(x) the density function of the measure ν with respect to this dominating measure. Let us define the measure γ as the measure with density function min(f(x), g(x)), the measure μ_{1} as the measure with density function f(x) − min(f(x), g(x)) the measure ν_{1} as the measure with density function g(x)−min(f(x), g(x)) with respect to the dominating measure. Finally, define the set C by the formula C = {x: f(x) ≥ g(x)}. This decomposition satisfies the requested properties. Beside this, μ(A)−ν(A) ≤ μ(C)− ν(C) for all sets A ∈ A. Let us observe that μ(C) − ν(C) = μ(C) − γ(C) = μ_{1}(C) = μ_{1}(X) = 1 − γ(X), which implies that sup_{A∈A} (μ(A) − ν(A)) = 1 − γ(X).

The quantities ν(A) − μ(A) can be estimated similarly. As a consequence, we get that Var (μ, ν) = sup_{A∈A} |μ(A) − ν(A)| = 1 − γ(X). If ξ and η are μ respectively ν

distributed random variables, then

P (ξ ≠ η) ≥ P ({ξ ∈ C} ∩ {η ∉ C}) ≥ μ(C) − ν(C) = Var (μ, ν).

To make such a construction where the two sides of the above inequality are equal let us define the following probability space (Ω, B, P). Put Ω = X ∪ (X × X), and let B be the natural σ-algebra on the space Ω whose restriction to the set X is A, and to the set X × X A × A. Let us define the measure P in the following way. Let the restriction of the measure μ P to the set X γ, and to the set X × X D · μ_{1} × ν_{1}, where D^{−1} = μ_{1}(X) = ν_{1}(X), that is D is the natural norming factor. Let us define the random variables ξ and η in the following way: If ω = x ∈ X, than ξ(ω) = η(ω) = x, if ω = (x_{1}, x_{2}) ∈ X × X, then ξ(ω) = x_{1}, η(ω) = x_{2}. With such a definition the random variable ξ is μ and the random variable η is ν distributed random variable. Furthermore, P (ξ = η) = γ(X) = 1 − Var (μ, ν), since the restriction of the measure P to the set X × X is concentrated on the set C × (X \ C), where ξ(ω) ≠ η(ω). We have solved problem 12.

Remark: It had some technical reasons why the random variables which yield identity in the inequality of problem 12 were constructed on the probability space Ω = X ∪(X ×X) and not on the space Ω_{1} = X × X, which might have been a more natural choice. But if we had worked in the probability space Ω_{1}, then the measure γ should have been concentrated to the diagonal D = {(x, x): x ∈ X}. On the other hand, there are cases when this diagonal D is a non-measurable subset of the space Ω_{1} = X × X, and this causes some problems. We wanted to avoid this difficulty and make a construction which also works in such cases.

13.) It is enough to prove that under the conditions of the central limit theorem a triangular array ξ̃_{k,j}, k = 1, 2…., 1 ≤ j ≤ n_{k}, and Wiener processes W_{k}(t), 0 ≤ t ≤ 1, k = 1, 2, …, can be constructed in such a way that the distribution of the random variables ξ̃_{k,j} and ξ_{k,j} agree, and the random broken line S̃_{k,j}(·) defined with the help of the random variables ξ̃_{k,j} in the same way as the random broken line S_{k}(t) with the help of the random variables ξ_{k,j} satisfy, together with the constructed Wiener processes W_{k}(t), the relation sup_{0≤t≤1} |S̃_{k}(t) − W_{k}(t)| ⇒ 0 as

k → ∞, where ⇒ denotes stochastic convergence.

Let us observe that the Lindeberg condition implies that lim_{k→∞} sup_{1≤j≤n_{k}} σ_{k,j}^{2} = 0,

where σ_{k,j}^{2} = Eξ_{k,j}^{2}. Let us consider the sequences u_{k,l} = ∑_{j=1}^{l} σ_{k,j}^{2}, fix some ε > 0,

of the form ε = \frac{1}{M}, where M is a positive integer, and define for all k = 1, 2, …, the subsequence 0 = m_{k,0} < m_{k,1} < ⋯ < m_{k,s}, m_{k,r} = m_{k,r}(ε), 1 ≤ r ≤ s, s = s(k, ε), of the sequence 0, 1, 2, …, n_{k} in the following way: Put m_{k,0} = 0, and if m_{k,r} is already defined, then the number m_{k,r+1} is defined as the number L > m_{k,r} for which u_{k,L}−u_{k,m_{k,r}} ≥ ε, u_{k,L−1}−u_{,mk,r} < ε if u_{k,n_{k}} −u_{k,m_{k,r}} ≥ ε, and m_{k,r+1} = n_{k}

and r + 1 = s(k, ε) is otherwise. Put ū_{k,j} = \frac{u_{k,j}}{u_{k,n_{k}}}, 1 ≤ j ≤ n_{k}. Let us observe

that lim_{k→∞} sup_{1≤r≤s(k,ε)} \frac{|ū_{k,m_{r}} − ū_{k,m_{r−1}} − ε|}{ε} = 0, and the random variables T_{k,j} =

\frac{S_{k,m_{k,r_{j}}} − S_{k,m_{k,r_{j−1}}}}{\sqrt{ū_{k,m_{k,j}} − ū_{k,m_{k,j−1}}}} satisfy the central limit theorem with arbitrary indices j for

which 1 ≤ r_{j} ≤ s(k, ε), and S_{k,r} = ∑_{j=1}^{r} ξ_{k,j}. Let us also observe that s(k, ε) ≤ ε^{−1}.

The above results together with the coupling results of this paper (e.g.problem 2 or Statement A can be applied) imply that such pairs of independent random variables (T̃_{k,j}, X_{k,j}), 1 ≤ j ≤ s(k, ε) can be constructed for all k = 1, 2, … for which the random variables X_{k,j} have standard normal distribution, the distributions of the random variables T_{k,j} and T̃_{k,j} agree, and sup_{1≤j≤s(k,ε)} |T̃_{k,j} − X_{k,j}| ⇒ 0, where

⇒ denotes convergence in probability. Let Z_{k,l,ε} = ∑_{j=1}^{l} \sqrt{ū_{k,m_{k,j}} − ū_{k,m_{k,j−1}}} T̃_{k,j},

Y_{k,l,ε} = ∑_{j=1}^{l} \sqrt{ū_{k,m_{k,j}} − ū_{k,m_{k,j−1}}}X_{k,j}, 1 ≤ l ≤ s(k, ε), and put Z_{k,0,ε} = 0 and

Y_{k,0,ε} = 0, Then the relation sup_{1≤l≤s(k,ε)} |Z_{k,l,ε} − Y_{k,l,ε}| ⇒ 0 also holds. Since this relation holds for all numbers ε of the form ε = \frac{1}{M}, the relation

sup_{1≤l≤s(k,ε_{k})} |Z_{k,l,ε_{k}} − Y_{k,l,ε_{k}}| ⇒ 0, and ε_{k} → 0 if k → ∞  (1)

also holds with an appropriate sequence ε_{k}, k = 1, 2, . . .. Because of the distribution of the sequences (Z_{k,j,ε_{k}}, 1 ≤ j ≤ s(k, ε_{k})), (Y_{k,j,ε_{k}}, 1 ≤ j ≤ s(k, ε_{k}) and the result of Problem 10 a triangular array S̃_{k,j} and a sequence of Wiener processes W_{k}(t) can be constructed in such a way that the distribution of the sequences ξ̃_{k,j} and ξ_{k,j}, 1 ≤ j ≤ n_{k}, agree for a fixed k = 1, 2, …, and beside this the partial sums

S̃_{k,l} = ∑_{j=1}^{l} ξ̃_{k,j} satisfy the identity S̃_{k,m_{k,l}} = Z_{k,l,ε_{k}}, W_{k}(ū_{k,m_{k,l}}) = Y_{k,l,ε_{k}}, 1 ≤ l ≤

s(k, ε_{k}). (Actually we construct directly the partial sums S̃_{k,j} and not the random variables ξ_{k,j}. We do this under the condition that their values are prescribed for certain indices and their distributions must agree with the distribution of the corresponding partial sums of the random variables ξ_{k,j}. The Wiener processes W_{k}(·) can be constructed in a simpler way by using its Markov property and some basic facts about Wiener processes.) We claim that the random broken lines S̃_{k}(t) determined by the above constructed triangular array ξ̃_{k,j}, k = 1, 2, …, 1 ≤ j ≤ n_{k} together with the Wiener processes W_{k}(t) constructed together with it satisfy the relation sup_{0≤t≤1} |S̃_{k}(t) − W_{k}(t)| ⇒ 0.

It follows from the construction and relation (1) that

sup_{1≤r≤s(k,ε_{k})} |S̃_{k}(ū_{k,m_{k,r}}) − W_{k}(ū_{k,m_{k,r}})| ⇒ 0,

and beside this lim_{k→∞} sup_{1≤r≤s_{k}} (ū_{i,m_{k,r}} − ū_{k,m_{k,r−1}}) = 0. Hence to prove the functional

central limit theorem it is enough to prove that

P ( sup_{0≤r<s(k,ε_{k})} sup_{ū_{k,m_{k,r}} ≤u≤ū_{k,m_{k,r+1}}} |W_{k}(u) − W_{k}(ū_{k,m_{k,r}})| > ε)

≤ ∑_{0≤r<s(k,ε_{k})} P (  sup_{ū_{k,m_{k,r}} ≤u≤ū_{k,m_{k,r+1}}} |W_{k}(u) − W_{k}(ū_{k,m_{k,r}} | > ε) → 0(2a)

P ( sup_{0≤r<s(k,ε_{k})} sup_{ū_{k,m_{k,r}} ≤u≤ū_{k,m_{k,r+1}}} |S̃_{k}(u) − S̃_{k}(ū_{k,m_{k,r}})| > ε)

≤ ∑_{0≤r<s(k,ε_{k})} P (  sup_{ū_{k,m_{k,r}} ≤u≤ū_{k,m_{k,r+1}}} |S̃_{k}(u) − S̃_{k}(ū_{k,m_{k,r}})| > ε) → 0 (2b)

as k → ∞ for all ε > 0. Relation (2.2b) can be rewritten because of the structure of the random broken lines S̃_{k}(t) as

∑_{0≤r<s(k,ε_{k})} P (  sup_{m_{k,r}+1≤p≤m_{k,r+1}} | ∑_{j=m_{k,r}+1}^{p} ξ̃_{k,j}| > ε) → 0 for all ε > 0. (2c)

The proof of relation (2a) is relatively simple, since the probabilities at its righthand side can be calculated explicitly. Indeed,

P ( sup_{ū_{k,m_{k,r}} ≤u≤ū_{k,m_{k,r+1}}} |W_{k}(u) − W_{k}(ū_{k,m_{k,r}} | > ε)

= P ( sup_{0≤u≤1} |W_{k}(u)| > \frac{ε}{\sqrt{ū_{k,m_{k,r+1}} − ū_{k,m_{k,r}}}} )

≤ 4 (1 − Φ (\frac{ε}{\sqrt{ū_{k,m_{k,r+1}} − ū_{k,m_{k,r}}}} )) ,

where Φ(·) denotes the standard normal distribution function. Because of the

relation lim_{k→∞} sup_{1≤r<s(k,ε_{k})}(ū_{k,m_{k,r+1}} − ū_{k,m_{k,r}}) = 0 we have

lim_{k→∞} \frac{(1 − Φ (\frac{ε}{\sqrt{ū_{k,m_{k,r+1}} − ū_{k,m_{k,r}}}} ))}{ū_{k,m_{k,r+1}} − ū_{k,m_{k,r}}} = 0.

The above relations together with the identity ∑_{r=1}^{s(k,ε_{k})}(ū_{k,m_{k,r+1}} −ū_{k,m_{k,r}}) = 1 imply

formula (2a). The proof of formula (2c) needed to complete the proof of the functional central limit theorem is more difficult. We describe one possible proof. Let us first observe that because of the Lindeberg condition there exists some sequence δ_{k} of positive

numbers, k = 1, 2, …, such that lim_{k→∞} δ_{k} = 0 and lim_{k→∞} ∑_{j=1}^{n_{k}} Eξ̃_{k,j}^{2}I(|ξ̃_{k,j}| > δ_{k}) = 0.

Let us fix such a sequence δ_{k}, and let us choose the decomposition ξ̃_{k,j} = ξ̄_{k,j} + ¯ ξ̄_{k,j} with ξ̄_{k,j} = ξ̃_{k,j}I(|ξ̃_{k,j}| > δ_{k}) − Eξ̃_{k,j}I(|ξ̃_{k,j}| > δ_{k}) and ¯ ξ̄_{k,j} = ξ̃_{k,j}I(|ξ̃_{k,j}| ≤ δ_{k}) −

Eξ̃_{k,j}I(|ξ̃_{k,j}| ≤ δ_{k}). Then lim_{k→∞} ∑_{j=1}^{n_{k}} Eξ̄_{k,j}^{2} = 0, lim_{k→∞} ∑_{j=1}^{n_{k}} E¯ξ̄_{k,j}^{2} = 1, E¯ξ̄_{k,j}^{4} ≤ δ_{k}^{2}E¯ξ̄_{k,j}^{2},

and to prove relation (2c) it is enough to show that

∑_{0≤r<s(k,ε_{k})}P (  sup_{m_{k,r}+1≤p≤m_{k,r+1}} | ∑_{j=m_{k,r}+1}^{p} ξ̄_{k,j}| > ε) → 0 for all ε > 0, (3a)

∑_{0≤r<s(k,ε_{k})}P (  sup_{m_{k,r}+1≤p≤m_{k,r+1}} | ∑_{j=m_{k,r}+1}^{p} ¯ ξ̄_{k,j}| > ε) → 0 for all ε > 0. (3b)

We can write P ( sup_{m_{k,r}+1≤p≤m_{k,r+1}} | ∑_{j=m_{k,r}+1}^{p} ξ̄_{k,j}| > ε) ≤ ^{\frac{∑_{j=m_{k,r} +1}^{m_{k,r+1}} Eξ̄_{k,j}^{2}}{ε^{2}}} by the Kol-

mogorov inequality. We get relation (3.1) by summing up this relation for 0 ≤ r ≤ s(k, ε_{k}) and applying the relation lim_{k→∞} ∑_{j=1}^{n_{k}} Eξ̄_{k,j}^{2} = 0.

The proof of relation (3b) demands a more intricate argument. Let us observe that the following version of the Kolmogorov inequality holds.

P ( sup_{m_{k,r}+1≤p≤m_{k,r+1}} | ∑_{j=m_{k,r}+1}^{p} ¯ ξ̄_{k,j}| > ε) ≤ \frac{E ( ∑_{j=m_{k,r}+1}^{m_{k,r+1}} ¯ ξ̄_{k,j})^{4}}{ε^{4}} .

Indeed, the sequence of the random variables ( ∑_{j=m_{k,r}+1}^{p} ¯ ξ̄_{k,j})^{4}, p = m_{k,r} + 1, …,

m_{k,r+1}, is a semimartingale. (This follows for instance from the fact that the convex function of a martingale is a semimartingale.) Then the above inequality can be proved similarly to the proof of the Kolmogorov inequality with the help of this fact.

We can prove formula (3b) with the help of a good estimate on E ( ∑_{j=m_{k,r}+1}^{m_{k,r+1}} ¯ ξ̄_{k,j})^{4}.

Indeed, we have

E ( ∑_{j=m_{k,r}+1}^{m_{k,r+1}} ¯ ξ̄_{k,j})^{4} ≤ ∑_{j=m_{k,r}+1}^{m_{k,r+1}} E¯ξ̄_{k,j}^{4} + 3 ( ∑_{j=m_{k,r}+1}^{m_{k,r+1}} E¯ξ̄_{k,j}^{2})^{2}

≤ (δ_{k}^{2} + 3 sup_{0≤r<s(,ε_{k})} (u_{k,m_{k,r+1}} − u_{k,m_{k,r}})) ( ∑_{j=m_{k,r}+1}^{m_{k,r+1}}E¯ξ̄_{k,j}^{2}) .

(Here we have exploited that because of the relation E¯ξ̄_{k,j} = 0 and the independence of the random variables ¯ ξ̄_{k,j} by carrying out the multiplications in the

expression E ( ∑_{j=m_{k,r}+1}^{m_{k,r+1}} ¯ ξ̄_{k,j})^{4} we get a sum whose summands are the expected

value of products of the random variables ξ_{k,j}. Those summands which contain a term with power one equal zero.) The above relations imply that

∑_{0≤r<s(k,ε_{k})}P (  sup_{m_{k,r}+1≤p≤m_{k,r+1}} | ∑_{j=m_{k,r}+1}^{p} ¯ ξ̄_{k,j}| > ε)

≤ \frac{(δ_{k}^{2} + 3 sup_{0≤r<s(,ε_{k})} (u_{k,m_{k,r+1}} − u_{k,m_{k,r}})) ( ∑_{j=1}^{n_{k}} E¯ξ̄_{k,j}^{2})}{ε^{4}}.

Formula (3b) follows from this inequality, since lim_{k→∞} E ∑_{j=1}^{n_{k}} ¯ ξ̄_{k,j}^{2} = 1, lim_{k→∞} δ_{k} = 0,

and lim_{k→∞} sup_{0≤r<s(k,ε_{k})} (u_{k,m_{k,r+1}} − u_{k,m_{k,r}}) = 0.

14.) Let us consider a sequence of random variables ξ_{n} with distribution μ_{n}, n = 0, 1, 2, …, on the space (X, ρ) such that the random variables ξ_{n} converge with probability one to the random variable ξ_{0} as n → ∞. This is possible by the result of Problem 5. Then also the Fμ_{n} distributed random variables η_{n} = Fξ_{n} converge to the Fμ_{0} distributed random variable η_{0} = Fξ_{0} with probability one. This implies the statement of Problem 14.

Appendix

The proof of the König–Hall theorem. The necessity of the condition is obvious. We prove sufficiency by induction with respect to the size of the set Y. If |Y | = 1, then the statement is obvious. Let us assume that we know the sufficiency of the condition for |Y | = k < n, and let us prove it for |Y | = n. We distinguish two cases:

a.) There exists a set A ⊂ Y such that 0 < |A| = k < n, and |B(A)| = |A|. b.) For all sets A ⊂ Y such that 0 < |A| < n |B(A)| > |A|.

In case a.) we claim that the conditions of the theorem hold for both pairs of sets Ȳ = A, Z̄ = B(A) and Ȳ = Y \ A, Z̄ = Z \ B(A) and the restriction of the function d(y, z) to these sets Ȳ × Z̄. Then the inductive hypothesis implies the sufficiency of the condition in case a.) In case Ȳ = A, Z̄ = B(A) this statement is obvious. If Ȳ = Y \ A and Z̄ = Z \B(A) let us consider the set C ⊂ Y \A. Put C̄ = C ∪A. Then |C| = |C̄|−k, |B(C̄)| ≥ |C̄|, and B(C) ∩ Z̄ ⊃ B(C̄) \ B(A). Hence |B(C) ∩ Z̄| ≥ |B(C̄)| − k ≥ |C̄| − k, and |B(C) ∩ Z̄| ≥ |C|, as we have claimed.

In case b.) let us consider a point z_{j} ∈ Z, for which d(y_{1}, z_{j}) = 1. Let us pair the point y_{1} with the point z_{j}. To complete the proof of the theorem it is enough to show that the sets Ȳ = Y \ {y_{1}} and Z̄ = Z \ {z_{j}} satisfy the conditions of the theorem in case b.). But this is obvious, since in case b.) |B(A) ∩ Z̄| ≥ |B(A)| − 1 ≥ |A| for all sets A ⊂ Z.

The proof of the continuous version of the König–Hall theorem. The necessity of the condition is obvious also in this case. We prove the sufficiency of the conditions by means of the original König–Hall theorem.

Let us first consider the special case when there is an integer N such that u(y_{j}) = \frac{k_{j}}{N}

for all y_{j} ∈ Y and v(z_{l}) = \frac{p_{l}}{N} for all z_{l} ∈ Z, where k_{j} and p_{l} are integers. In this case

let us define the following bipartitated graph: Ȳ = {(y_{j}, m(j)), y_{j} ∈ Y, 1 ≤ m(j) ≤ k_{j}}, Z̄ = {(z_{l}, n(l)), z_{l} ∈ Z, 1 ≤ n(l) ≤ p_{l}}, d̄((y_{j}, m(j)), (z_{l}, n(l))) = d(y_{j}, z_{l}). Then the bipartitated graph (Ȳ , Z̄, d̄(·, ·)) satisfies the conditions of the König–Hall theorem. Indeed, it is enough to check the conditions of the König–Hall theorem for those sets A ⊂ Ȳ for which in the case ȳ = (y_{j}, m(j)) ∈ A with some points (y_{j}, m(j)) ∈ Ȳ also the relation (y_{j}, k) ∈ A holds for all points (y_{j}, k), 1 ≤ k ≤ k_{j}. On the other hand, this condition agrees with the relation ∑_{z∈B(A)} v(z) ≥ ∑_{y∈A} u(y) for all A ∈ Y.

Hence there exists such a pairing of the elements of the sets Ȳ and Z̄, in which the points ȳ and z̄ in a pair satisfy the relation d̄(ȳ, z̄) = 1. Put w̄(ȳ, z̄) = 1, if ȳ and z̄ are in a pair, and w̄(ȳ, z̄) = 0 otherwise. Then the function w(y_{j}, z_{l}) =

\frac{1}{N} ∑_{\begin{matrix}ȳ=(y_{j},m(j)),1≤m(j)≤k_{j} \\ z̄=(z_{l},n(l)),1≤n_{l}≤p_{l} \end{matrix}} w̄(ȳ, z̄) satisfies the statement of the theorem in this special

case.

The general case can be reduced to the already proved situation with an appropriate approximation. We can assume without violating the generality that ∑_{y∈Y} u(y) =

∑_{z∈Z} v(z) = 1. For all N = 1, 2, … let us define the following system approximating the

original one. Put Ȳ = Ȳ_{N} = Y ∪ {r + 1}, Z̄ = Z̄_{N} = Z ∪ {s + 1}, d̄(y, z) = d̄_{N}(y, z) = d(y, z), if y ∈ Y, z ∈ Z, and d̄(y_{r+1}, z) = d̄_{N}(y_{r+1}, z) = d̄(y, z_{s+1}) = d̄_{N}(y, z_{s+1}) = 1, (this means that the points y_{r+1} and z_{s+1} are connected to all points of the other set),

ū_{N}(y) = \frac{[Nu(y)]}{N}, if y ∈ Y, v̄_{N}(z) = \frac{[Nv(z)]}{N}, if z ∈ Z, where [u] denotes the integer part of the number u, beside this ū_{N}(y_{r+1}) = ∑_{y∈Y} (u(y) − ū_{N}(y)) = 1 − ∑_{y∈Y} ū_{N}(y),

and v̄_{N}(y_{s+1}) = ∑_{z∈Z} (v(z) − v̄_{N}(z)) = 1 − ∑_{z∈Z} v̄_{N}(z). Let us observe that this new

system also satisfies the conditions of the theorem. Indeed, if A ⊂ Y_{N}, then the set of points B_{N}(A) of Z̄_{N} connected to a set A ⊂ Y_{N} is B̄_{N}(A) = B(A) ∪ {z_{s+1}}, and

∑_{y∈A} ū_{N}(y) ≤ ∑_{y∈A} u(y) ≤ ∑_{z∈B(A)} v(z) ≤ ∑_{z∈B(A)} v̄_{N}(z) + v̄_{N}(z_{s+1}) ≤ ∑_{z∈B̄(A)} v̄_{N}(z). If

y_{r+1} ∈ A, then B̄_{N}(A) = Z̄_{N}, and ∑_{y∈A} ū_{N}(y) ≤ 1 = ∑_{z∈Z̄_{N}} v̄_{N}(z). Hence the already

proved part of the Theorem can be applied in this case.

Let us consider for all N = 1, 2, … a “transport function” w̄_{N}(y, z), y ∈ Ȳ, z ∈ Z̄ satisfying the theorem. As 0 ≤ w̄_{N}(y, z) ≤ 1 for all points y ∈ Ȳ, z ∈ Z̄, and numbers N = 1, 2, … a subsequence N_{k} → ∞ of the integers can be chosen in such a way that the limit w(y, z) = lim_{k→∞} w_{N_{k}}(y, z) exists for all points y ∈ Ȳ and z ∈ Z̄. This function

w(y, z) satisfies the theorem.