Lectures on the Coupling Method
()
About this ebook
Related to Lectures on the Coupling Method
Titles in the series (100)
A History of Mathematical Notations Rating: 4 out of 5 stars4/5Analytic Inequalities Rating: 5 out of 5 stars5/5First-Order Partial Differential Equations, Vol. 2 Rating: 0 out of 5 stars0 ratingsInfinite Series Rating: 4 out of 5 stars4/5Laplace Transforms and Their Applications to Differential Equations Rating: 5 out of 5 stars5/5Theory of Approximation Rating: 0 out of 5 stars0 ratingsMethods of Applied Mathematics Rating: 3 out of 5 stars3/5A Catalog of Special Plane Curves Rating: 2 out of 5 stars2/5Dynamic Probabilistic Systems, Volume II: Semi-Markov and Decision Processes Rating: 0 out of 5 stars0 ratingsMathematics in Ancient Greece Rating: 5 out of 5 stars5/5The Calculus Primer Rating: 0 out of 5 stars0 ratingsFirst-Order Partial Differential Equations, Vol. 1 Rating: 5 out of 5 stars5/5History of the Theory of Numbers, Volume II: Diophantine Analysis Rating: 0 out of 5 stars0 ratingsAdvanced Calculus: Second Edition Rating: 5 out of 5 stars5/5Calculus Refresher Rating: 3 out of 5 stars3/5Calculus: An Intuitive and Physical Approach (Second Edition) Rating: 4 out of 5 stars4/5Differential Geometry Rating: 5 out of 5 stars5/5Topology for Analysis Rating: 4 out of 5 stars4/5An Introduction to Lebesgue Integration and Fourier Series Rating: 0 out of 5 stars0 ratingsNumerical Methods Rating: 5 out of 5 stars5/5Theory of Games and Statistical Decisions Rating: 4 out of 5 stars4/5Mathematics for the Nonmathematician Rating: 4 out of 5 stars4/5Differential Forms with Applications to the Physical Sciences Rating: 5 out of 5 stars5/5Geometry: A Comprehensive Course Rating: 4 out of 5 stars4/5Fourier Series and Orthogonal Polynomials Rating: 0 out of 5 stars0 ratingsElementary Matrix Algebra Rating: 3 out of 5 stars3/5The History of the Calculus and Its Conceptual Development Rating: 4 out of 5 stars4/5Applied Multivariate Analysis: Using Bayesian and Frequentist Methods of Inference, Second Edition Rating: 0 out of 5 stars0 ratingsVectors and Their Applications Rating: 0 out of 5 stars0 ratingsAn Adventurer's Guide to Number Theory Rating: 4 out of 5 stars4/5
Related ebooks
Stochastic Control by Functional Analysis Methods Rating: 0 out of 5 stars0 ratingsTheory of Approximation Rating: 0 out of 5 stars0 ratingsRadically Elementary Probability Theory. (AM-117), Volume 117 Rating: 4 out of 5 stars4/5Studies in the Theory of Random Processes Rating: 0 out of 5 stars0 ratingsStochastic Differential Equations and Diffusion Processes Rating: 0 out of 5 stars0 ratingsIntegration, Measure and Probability Rating: 0 out of 5 stars0 ratingsSemi-Simple Lie Algebras and Their Representations Rating: 4 out of 5 stars4/5Lectures on Homotopy Theory Rating: 0 out of 5 stars0 ratingsHarmonic Analysis and the Theory of Probability Rating: 0 out of 5 stars0 ratingsThe Elements of Integration and Lebesgue Measure Rating: 0 out of 5 stars0 ratingsDynamic Programming and Its Application to Optimal Control Rating: 0 out of 5 stars0 ratingsStatistical Inference via Convex Optimization Rating: 0 out of 5 stars0 ratingsMultiobjective Programming and Planning Rating: 0 out of 5 stars0 ratingsStochastic Integration Rating: 0 out of 5 stars0 ratingsMarkov Processes: An Introduction for Physical Scientists Rating: 1 out of 5 stars1/5Stochastic Analysis of Mixed Fractional Gaussian Processes Rating: 0 out of 5 stars0 ratingsBayesian Analysis of Stochastic Process Models Rating: 0 out of 5 stars0 ratingsSingular Optimal Control Problems Rating: 0 out of 5 stars0 ratingsQuadratic Form Theory and Differential Equations Rating: 0 out of 5 stars0 ratingsGeneralized Functions: Theory and Technique Rating: 5 out of 5 stars5/5Real Analysis: A Historical Approach Rating: 0 out of 5 stars0 ratingsTheory of Markov Processes Rating: 0 out of 5 stars0 ratingsModern Dimension Theory Rating: 0 out of 5 stars0 ratingsMachine Learning Proceedings 1991: Proceedings of the Eighth International Workshop (ML91) Rating: 0 out of 5 stars0 ratingsGeneral Theory of Markov Processes Rating: 0 out of 5 stars0 ratingsIntroduction to Real Analysis: An Educational Approach Rating: 0 out of 5 stars0 ratingsTheory of Groups of Finite Order Rating: 0 out of 5 stars0 ratingsStochastic Integrals Rating: 0 out of 5 stars0 ratingsSubmodular Functions and Optimization Rating: 0 out of 5 stars0 ratingsOperational Calculus Rating: 0 out of 5 stars0 ratings
Mathematics For You
Introducing Game Theory: A Graphic Guide Rating: 4 out of 5 stars4/5Basic Math & Pre-Algebra For Dummies Rating: 4 out of 5 stars4/5Calculus For Dummies Rating: 4 out of 5 stars4/5Algebra - The Very Basics Rating: 5 out of 5 stars5/5Geometry For Dummies Rating: 5 out of 5 stars5/5Basic Math Notes Rating: 5 out of 5 stars5/5Quantum Physics for Beginners Rating: 4 out of 5 stars4/5Game Theory: A Simple Introduction Rating: 4 out of 5 stars4/5My Best Mathematical and Logic Puzzles Rating: 5 out of 5 stars5/5Algebra I Workbook For Dummies Rating: 3 out of 5 stars3/5The Everything Guide to Algebra: A Step-by-Step Guide to the Basics of Algebra - in Plain English! Rating: 4 out of 5 stars4/5Mental Math Secrets - How To Be a Human Calculator Rating: 5 out of 5 stars5/5The Everything Everyday Math Book: From Tipping to Taxes, All the Real-World, Everyday Math Skills You Need Rating: 5 out of 5 stars5/5See Ya Later Calculator: Simple Math Tricks You Can Do in Your Head Rating: 4 out of 5 stars4/5Calculus Made Easy Rating: 4 out of 5 stars4/5The Elements of Euclid for the Use of Schools and Colleges (Illustrated) Rating: 0 out of 5 stars0 ratingsThe Golden Ratio: The Divine Beauty of Mathematics Rating: 5 out of 5 stars5/5Is God a Mathematician? Rating: 4 out of 5 stars4/5ACT Math & Science Prep: Includes 500+ Practice Questions Rating: 3 out of 5 stars3/5The Thirteen Books of the Elements, Vol. 1 Rating: 0 out of 5 stars0 ratingsRelativity: The special and the general theory Rating: 5 out of 5 stars5/5A Mind for Numbers | Summary Rating: 4 out of 5 stars4/5GED® Math Test Tutor, 2nd Edition Rating: 0 out of 5 stars0 ratingsAlgebra I For Dummies Rating: 4 out of 5 stars4/5
Reviews for Lectures on the Coupling Method
0 ratings0 reviews
Book preview
Lectures on the Coupling Method - Torgny Lindvall
Index
Introduction
1. Three examplesbe a Markov chain with a countable state space (equal to ℤ+ = the nonnegative integers), governed by a transition matrix P = (pij), making it aperiodic, irreducible, and positive recurrent. It is a classical result that X approaches stationarity as n → ∞, regardless of the initial distribution λ (that of X0):
(1.1)
is the unique stationary distribution, satisfying π = πPis the n, independent of X, governed by P have distribution πby
where
We thus make a coupling of X and X’ at T and call that the coupling time. At this instant you should not hesitate to believe that X and X" are equally distributed (this is due to the strong Markov property). This implies that for each j ∈ ℤ+,
(1.2)
. Hence
∣P(Xn = j)–πj∣ ≤ 2 · P(T > n),
so (1.1) follows if the coupling is successful (i.e., if T < ∞ a.s.). Actually, this inequality holds without that 2
since
But (1.2) has more to give; a summation on both sides of that inequality renders
(now that 2
must be included!) which we may write in a more compact form as
(1.3)
or
∥λPn–π∥ ≤ 2 ·P(T > n).
corresponding row vectors (ν0, ν1, . . .), and bounded signed measures on ℤ+, and define
So if we can prove that the coupling is successful, uniform convergence toward stationarity is established effortlessly.
A number of questions should now be in your mind. For example:
Is it easy to prove that the coupling is successful?
Does (1.3) yield new results?
Is there an interesting class of Markov chains with general state space to which the coupling method is applicable?
The common answer is: yes.
with state space ℤ+. Assume here that the intensities render X nonexplosive and recurrent. With pij(t) short for Pi(Xt = j), where the i indicates that X0 = i and Pt = (pij(t)) for t ≥ 0, the distribution of Xt becomes λPt if that of X0 is λ.
To investigate the asymptotics of X, introduce the parallel process X’, governed by the same intensities as and independent of X, and with initial distribution μ, say. Now letting
and
(1.4)
we may proceed as in (1.2) to obtain
(1.5)
But since the path of a birth and death process is skip-free and hence two independent paths cannot cross without meeting, it is easy to understand that
where τare the times when X, X’ hit the state 0. Due to the recurrence assumption, we certainly have τa.s., so the coupling is successful and (1.5) yields
(1.6)
for any initial distributions λ, μ. Notice that we have not assumed positive recurrence, so a stationary distribution may not exist. If it does, call it π again and put μ = π in (1.6) to obtain
(1.7)
While (1.7) is a result on tendency toward stationarity (or equilibrium, as some prefer to say), the statement (1.6) means that a recurrent birth and death process forgets its initial distribution. The term ergodic
is used in a number of ways in the literature; in this book we reserve it for results of the type (1.6).
If X0 = 0, then regardless of μ,
(1.8)
again due to the skip-free paths. Since X and X" are equally distributed, we may deduce from (1.8) that
if g: ℤ+ → ℝ is nondecreasing. In particular,
(What alternative proof of that do you support?) Hence the coupling method serves us well also for establishing inequalities: You will see many examples of that use below.
How far-reaching are the consequences of the observation that crossing paths produce a coupling? Very far. In fact, it has made the coupling method an indispensable tool in the study of the Markov processes of birth and death type with state space, for example, {0, 1}S (S countable), that are used to model interacting particle systems.
For the final example, let Y1, . . . , Yn be independent 0–1 variables with
P(Yi = 1) = pi
.When all pi values are small, X is approximately
, as is well known. To illuminate that, we search for a bound of
where pλ (i) = exp (–λ) · λi/i! for i . Now suppose that we can find a variable X’ with distribution pλ such that X = X’ with high probability. Then
(1.9)
hence
(1.10)
so if P(X ≠ X’) is small, we get a good Poisson approximation.
But how is such a variable X’ produced? For one possible answer, let (Yi) be independent for 1 ≤ i ≤ n and such that
(1.11)
and
Then Yi is a 0–1 variable with P(Yi = 1) = piis Poisson distributed with parameter pi. has the required distribution, and (1.10) renders
But
and we have proved that
(1.12)
which is good enough for many applications.
The use of couplings for approximations such as (1.12) will be only a minor theme of this book. However, there are topics that should not be withheld; among them is a result on Poisson approximation for sums of weakly dependent 0–1 variables, sharp enough to generalize the remarkable Le Cam’s theorem.
2. An outline. To know a method is to have learned how it works. What we have ahead of us is essentially a collection of applications of a few basic ideas consisting largely of topics of wide common interest with an attempt to maximize diversity. References to specialized studies are given in the Notes at the ends of chapter parts.
In Chapter I a number of cornerstones are laid. The term coupling
is defined, and the coupling inequality, of which (1.3), (1.5), and (1.12) are applications, is settled and elaborated.
Renewal theory is a main theme of the book. Part 1 of Chapter II is dedicated to a detailed account of coupling of discrete-time renewal processes. The ideas and results here are used repeatedly, with consequences of type (1.3) for Markov chains discussed in the second parts of Chapters II and III, so this is basic. Skill is gained from learning how to couple discrete random walks, shuffle cards, and make Poisson approximations in the remaining parts of Chapter II.
New challenges face us as soon as we go beyond the discrete models. In Chapter III we meet some of them; the first concerns coupling of continuous-time renewal processes. It turns out that virtually all asymptotic results for such processes may be obtained by suitable couplings, as shown in Part 1. Coupling and related methods have had a strong impact on the asymptotics theory of Markov chains with a general state space. Part 2 is an account of that.
At this stage it is natural to answer some questions that have emerged. Is there a best possible coupling of two random sequences? Can we generalize our results from renewal to regenerative processes? Are there particular observations to make concerning coupling of Markov processes? Affirmative answers are provided in Parts 3 and 4. In Part 5 of Chapter III we sum up many of our findings about Markov chain ergodicity and coupling in one major theorem.
Relation (1.8) and its consequences is a simple example of how to use coupling to establish inequalities. That use is the theme of Chapter IV, which has Strassen’s theorem as a basic result. However, many interesting inequalities may be proved by simpler means, in terms of independent, uniformly distributed variables, for example; the last section is a gallery of such inequalities.
The coupling method is a fine tool in the study of Markov processes which are defined in terms of transition intensities. The first three parts of Chapter V show its use in a range of examples, from birth and death processes, through models for queueing networks and epidemics, to interacting particle systems. The possibilities of embedding in a bivariate Poisson process are demonstrated in Parts 4 and 5; among other things, we find that device useful for urn models and renewal theory.
Chapter VI is devoted to diffusions. In several cases, coupling of one-dimensional diffusions is easy, due to the path continuity. The multidimensional case is in general difficult, but there are interesting exceptions; it turns out, for example, that Brownian motions may efficiently and easily be coupled.
We finish with a bit of history of the method in the Appendix, where a tribute is paid to its inventor, Wolfgang Doeblin.
3. Notes. The reader is supposed to be familiar with probability theory based on measures and Lebesgue integrals learned from, for example, Ash [9], Billingsley [27], Chung [39], Dudley [55], Durrett [58] or Williams [160]. And there are few readers with this background who do not have the slight acquaintance with Markov chains, random walk, Brownian motion, and so on, required, learned either from one of these references or from an undergraduate textbook such as Grimmett and Stirzaker [69]. A few standard results are used without comment; they are easily found in some of the references noted above.
The enumeration is a standard one: By (3.2)
we refer to the second enumerated item in § 3 in the same chapter; (IV 3.2)
indicates a reference to another chapter; § IV.3 designates § 3 in Chapter IV The sign =
is used not only to mean equal to
but also occasionally be defined by
and even which we abbreviate to
.
denote the class of measurable mappings from E to Eequals (ℝ, ℛ), the real numbers with the Borel sets, we simply write f in order to say that f is a measurable real-valued function.
For a class of functions, the prefixes b, c, and i means that f is an increasing (= nondecreasing) and bounded measurable function. The prefix i requires that E be ordered in some way, while c can be used when E has a topology. The prefix b is also used for measures.
CHAPTER I
Preliminaries
1. What is a coupling? .
(1.1) A coupling of the probability measures P and P’ on a measurable space is a probability measure on such that
where π(x, x′) = x, π′(x, x′) = x′ for (x, x′) ∈ E² .
Thus P and P′ .
Now typical uses of the coupling method are those demonstrated in § Int.1, and we find that our definition (1.1) is not well fit for immediate use. Once again we understand that probability theory is not animated measure theory, but rather, a mathematical discipline in its own right, concerned with random elements.
to be a quadruple
(Ω, ℱ, P, X),
where (Ω, ℱ, P) is the underlying probability space (the sample space) and X , the class of measurable mappings from Ω to E. (1.2) By a coupling of the random elements (Ω, ℱ, P, X) and (Ω′, ℱ′, P′, X′) in we mean a random element in such that
is a coupling of PX–1 and P′X′–1 in the sense of (1.1).
as a coupling of the random elements X and X’. When no clarity is lost, we omit superscripts (^ , etc.) on Ω, ℱ, and P.
For the random elements involved, the superscripts will vary; you will meet X" , , and so on. In the first example of § Int.1 we produced a coupling (X", X’) of the random elements X and X’ ,and the second example was similar in nature. The third, concerning Poisson approximation, is a case where for a comparison of two probability measures P and P’ , a random element (Ω, ℱ, P, (X, Xis constructed. We shall refer to such a construction as a coupling solution of
or a coupling approach to
a certain problem. Notice that the definitions (1.1) and (1.2) may be extended directly to be valid for any class of probability measures or random elements.
When should the term coupling
be used? There is no general agreement about that; some prefer a usage restricted to topics of the type presented in § Int.1; others find it suitable in any situation where for the comparison of probability measures, a common probability space is constructed. From the latter point of view, embeddings in Brownian motion, for examples, are actually couplings; notice that the definition (1.2) does not reject the use of the term in such connections.
If you prefer a restrictive usage, you soon find yourself in trouble when trying to state a definition. But there is no urgent need for any.
2. The coupling inequality. , that norm is defined by
(2.1)
such that v(∙ ∩ D) and–v( ∙ ∩ Dc) are positive measures, v+ and v–, say. We have v = v+ –v–,
(2.2)
and find that
(2.3)
. If v has total mass 0, then v+(E) = v–(E), so if P and P’ then (2.2–2.3) renders
(2.4)
There are further details about bℳs and ∥∙∥ in App.2.
Now suppose that the random element (Ω, ℱ, P, (Z, Z’)) is a coupling in order to estimate ∥P–P′∥. Using (2.4), we obtain
But
(2.5)
so
(2.6)
This is the (basic) coupling inequality. Before proceeding, notice that we must have {Z = Z′} E , so {Z = Z’} = {(Z, Z′) ∈ ∆} ∈ ℱ.
, where Xn. If there is a random time T ∈ ℤ+ such that
(2.7)
then we call T a coupling time and obtain from (2.6) that
(2.8)
.
, define the shift θn: E∞ → E∞ by
(2.9)
for x = (x0, x1, x2,...) ∈ E∞, where z is a fixed element in E. Notice that Ewith the same coupling times T , and we obtain that (2.8) actually improves itself, to the inequality
(2.10)
Consider the space of functions DE[0, ∞), with values in a Polish space E and defined on [0, ∞), which are right-continuous and have left-hand limits at all arguments t. Endowed with the Skorohod topology, that space, which we abbreviate as DE, becomes a Polish space. This is the most general type of path space we shall use; hence we shall not violate the Polish assumption even in our investigations of continuous-time processes. The σ-field on DE ; see also § App.1.
where X and X’ are DE valued. We call the random time T ∈ ℝ+ a coupling time if
(2.11)
The analogs of (2.8) and (2.10) are
(2.12)
and
(2.13)
where the shift θt is defined in the obvious way:
(2.14)
for x ∈ DE, where z is a fixed element ∈ E. For (2.12)–(2.13), notice that we must know that θtX and θtX’ , in order to use the argument (2.5) again. But they are; in order that a mapping into DE, h say, shall be measurable, it suffices that h(t) is a measurable mapping into E for each t > 0, as is well known to a reader familiar with the Skorohod topology.
Let Z and Z′ . From (2.4) we obtain
(2.15)
is a coupling of Z and Z′, a