Coupling (stochastics)

Coupling (of English. Coupling ) is a method of proof in the mathematical sub-region of the probability theory . A coupling of two random variables and is a random vector whose marginal distributions exactly correspond to the distributions of and . The method was developed in 1938 by Wolfgang Doeblin in connection with Markow chains , it was not until around 1970 that Frank Spitzer introduced the term coupling . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

definition

Note: Only real random variables are considered here. However, the concept can be transferred to any measurable functions .

Let and two random variables. The two probability spaces need not necessarily be the same. By one is probability measure on the measurement space of real numbers with the provided Borel σ-algebra explained. This is called the image dimension or distribution of , in characters . The same applies to. ${\displaystyle X\colon (\Omega _{1},{\mathcal {A}}_{1},\mu )\to \mathbb {R} }$ ${\displaystyle Y\colon (\Omega _{2},{\mathcal {A}}_{2},\nu )\to \mathbb {R} }$ ${\displaystyle \mu _{X}=\mu \circ X^{-1}}$ ${\displaystyle (\mathbb {R} ,{\mathcal {B}}(\mathbb {R} ))}$ ${\displaystyle X}$ ${\displaystyle X\sim \mu _{X}}$ ${\displaystyle \nu _{Y}=\nu \circ Y^{-1}}$

A coupling of and is a common probability space with two variables such that and holds. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle (\Omega ,{\mathcal {A}},\gamma )}$ ${\displaystyle {\hat {X}},{\hat {Y}}\colon \Omega \to \mathbb {R} }$ ${\displaystyle {\hat {X}}\sim \mu _{X}}$ ${\displaystyle {\hat {Y}}\sim \nu _{Y}}$

One also writes and to indicate that the new random variables are distributed in the same way as the original ones. ${\displaystyle {\hat {X}}\,{\stackrel {\mathcal {D}}{=}}\,X}$ ${\displaystyle {\hat {Y}}\,{\stackrel {\mathcal {D}}{=}}\,Y}$

Conventions

For most applications it is sufficient to use the Cartesian product and the product σ-algebra . If and are the respective projections on the first or second factor, then the variables and are also available . The measure must then be chosen so that the one-dimensional marginal distributions of the common distribution of the vector are the distributions of and of . Such a measure is usually not clear. The core of the proof technique consists precisely in choosing suitable for the respective purpose. ${\displaystyle \Omega =\Omega _{1}\times \Omega _{2}}$ ${\displaystyle {\mathcal {A}}={\mathcal {A}}_{1}\otimes {\mathcal {A}}_{2}}$ ${\displaystyle \pi _{1}}$ ${\displaystyle \pi _{2}}$ ${\displaystyle {\hat {X}}=X\circ \pi _{1}}$ ${\displaystyle {\hat {Y}}=Y\circ \pi _{2}}$ ${\displaystyle \gamma }$ ${\displaystyle ({\hat {X}},{\hat {Y}})}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \gamma }$

Examples

independence

A trivial coupling results from the assumption that the variables and are stochastically independent . The distribution of is then uniquely determined by for all Borel sets . If one withdraws this distribution to the archetype space , the product measure of and results . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle ({\hat {X}},{\hat {Y}})}$ ${\displaystyle P[({\hat {X}},{\hat {Y}})\in A_{1}\times A_{2}]=\mu _{X}(A_{1})\cdot \nu _{Y}(A_{2})}$ ${\displaystyle A_{1},A_{2}\in {\mathcal {B}}(\mathbb {R} )}$ ${\displaystyle \Omega =\Omega _{1}\times \Omega _{2}}$ ${\displaystyle \gamma =\mu \otimes \nu }$ ${\displaystyle \mu }$ ${\displaystyle \nu }$

This coupling is seldom used because most evidence requires some kind of dependency between the coupled variables.

Unfair coins

Let be two real numbers. Suppose you have two coins, the first one with probability heads, the other with probability . So, intuitively, the second coin should show its head "more often". More precisely, it has to be proven that, for each toss, the probability that the first coin will be heads is smaller than the probability of the same occurrence for the second coin. It can be quite difficult to show this with classic counting arguments. A simple coupling, on the other hand, does what you want. ${\displaystyle 0\leq p<q\leq 1}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle k\leq n}$ ${\displaystyle k}$

Let be the indicator variables for the heads toss of the first coin and those of the second. The first sequence of random variables is taken over unchanged . However, the following applies to them: ${\displaystyle X_{1},X_{2}\dots ,X_{n}}$ ${\displaystyle Y_{1},Y_{2},\dots ,Y_{n}}$ ${\displaystyle {\hat {X}}_{i}=X_{i}}$ ${\displaystyle {\hat {Y}}_{i}}$

• If so, sit up . ${\displaystyle X_{i}=1}$ ${\displaystyle {\hat {Y}}_{i}}$ ${\displaystyle 1}$
• If , put on by chance , on otherwise . ${\displaystyle X_{i}=0}$ ${\displaystyle {\hat {Y}}_{i}}$ ${\displaystyle 1}$ ${\displaystyle {\tfrac {q-p}{1-p}}}$ ${\displaystyle 0}$

The values ​​of now really depend on the output of (and thus of ), they are coupled. Nevertheless , so . The are but at least every time when the are so ${\displaystyle {\hat {Y}}_{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle {\hat {X}}_{i}}$ ${\displaystyle P[{\hat {Y}}_{i}=1]=q=P[Y_{i}=1]}$ ${\displaystyle {\hat {Y}}_{i}\,{\stackrel {\mathcal {D}}{=}}\,Y_{i}}$ ${\displaystyle {\hat {Y}}_{i}}$ ${\displaystyle 1}$ ${\displaystyle {\hat {X}}_{i}}$

${\displaystyle P[{\hat {X}}_{1}+{\hat {X}}_{2}+\dots +{\hat {X}}_{n}\geq k]\leq P[{\hat {Y}}_{1}+{\hat {Y}}_{2}+\dots +{\hat {Y}}_{n}\geq k]}$.

In the language of probability theory it is almost certain that H. . In this case one speaks of a monotonous coupling . ${\displaystyle {\hat {X}}_{i}\leq {\hat {Y}}_{i}}$ ${\displaystyle P[{\hat {X}}_{i}\leq {\hat {Y}}_{i}]=1}$

Set of roads

In the theory of stochastic order , Strassen's theorem generalizes the last example. It says that one random variable stochastically dominates another if and only if there is a monotonous coupling between them. The decisive direction of equivalence is towards coupling. Your proof provides an example where there is no product space. ${\displaystyle \Omega }$

The distribution of a real random variable over any probability space can be described by its distribution function: ${\displaystyle X}$ ${\displaystyle F_{X}}$

${\displaystyle F_{X}(x)=P[X\leq x]=\mu _{X}((-\infty ,x])}$for everyone . ${\displaystyle x\in \mathbb {R} }$

${\displaystyle X}$ie from dominates stochastically ${\displaystyle Y}$ , if always applies. (Note the inversion of the relation sign.) ${\displaystyle X\preccurlyeq _{st}Y}$ ${\displaystyle F_{X}(x)\geq F_{Y}(x)}$

The unit interval , provided with the Borel σ-algebra and the Lebesgue-Borel measure , which assigns its length to each sub-interval, serves as the common probability space . The random variable is set ${\displaystyle \Omega =[0,1]}$ ${\displaystyle {\mathcal {A}}={\mathcal {B}}([0,1])}$ ${\displaystyle \gamma =\lambda }$

${\displaystyle {\hat {X}}(\omega )=\inf \,\{x\mid \omega \leq F_{X}(x)\}}$for everyone . ${\displaystyle \omega \in [0,1]}$

Likewise, also from derived. According to construction applies to all and ${\displaystyle {\hat {Y}}}$ ${\displaystyle F_{Y}}$ ${\displaystyle \omega \in [0,1]}$ ${\displaystyle x\in \mathbb {R} }$

${\displaystyle \omega \leq F_{X}(x)\Leftrightarrow {\hat {X}}(\omega )\leq x}$.

The two functions are therefore the same, so the distributions must be too . follows analogously. Also, this implies equivalence along with ultimately as desired. ${\displaystyle F_{\hat {X}}=F_{X}}$ ${\displaystyle {\hat {X}}\,{\stackrel {\mathcal {D}}{=}}\,X}$ ${\displaystyle {\hat {Y}}\,{\stackrel {\mathcal {D}}{=}}\,Y}$ ${\displaystyle F_{X}(x)\geq F_{Y}(x)}$ ${\displaystyle {\hat {X}}(\omega )\leq {\hat {Y}}(\omega )}$

Individual evidence

1. ^ ^{A b} Geoffrey Grimmett, David Stirzaker: Probability and Random Processes . 3. Edition. Oxford University Press, Oxford / New York 2001.
2. ↑ Devdatt Dubhashi, Alessandro Panconesi: Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge University Press, Cambridge / New York 2009.

literature

• Hans-Otto Georgii: Stochastics - Introduction to probability theory and statistics . 4th, revised edition. De Gruyter, Berlin 2009.
• Torgny Lindvall: Lectures on the Coupling Method . Wiley, New York 1992.
• Hermann Thorisson: Coupling, Stationarity, and Regeneration . Springer, New York 2000.