Successful couplings and total variation convergence to equilibrium for time-homogeneous Markov processes
$begingroup$
Let
$(Omega,mathcal A,operatorname P)$ be a probability space
$I=mathbb N_0$ or $I=[0,infty)$
$(E,mathcal E)$ be a measurable space
$mu$ and $nu$ be probability measures on $(E,mathcal E)$
$X$ be an $(E,mathcal E)$-valued time-homogeneous Markov chain on $(Omega,mathcal A,operatorname P)$ with transition semigroup $(kappa_t)_{tin I}$
Assume $mu$ is invariant with respect to $(kappa_t)_{tin I}$ and $$left|mu-nukappa_tright|xrightarrow{ttoinfty}0tag1,$$ where the left-hand side denotes the total variation distance of $mu$ and $nukappa_t$ and $nukappa_t$ denotes the composition of $nu$ and $kappa_t$.
I want to show that there is a version $X^{(eta)}$ of $X$ with $operatorname Pleft[X^{(eta)}_0in;cdot;right]=eta$ for $etainleft{mu,nuright}$ with $$tau:=infleft{tin I:X^{(mu)}_s=X^{(nu)}_stext{ for all }sin Itext{ with }sge tright}<infty;;;operatorname Ptext{-almost surely}.tag2$$
As pointed out by E-A, the basic idea is the following: For any $tge0$, there is (see Theorem 2.12) a probability measure $eta_t$ (called a coupling of $mu$ and $nukappa_t$) on $(Etimes E,mathcal Eotimesmathcal E)$ with $$eta_t(Btimes E)=mu(B)text{ and }eta_t(Etimes B)=(nukappa_t)(B);;;text{for all }Binmathcal Etag3$$ and $$left|mu-nukappa_tright|=eta_t(Delta^c),tag4$$ where $$Delta:=left{(x,x):xin Eright}.$$
Clearly, if we would be able to show (are we?) that there is a $(mathcal A,mathcal Eotimesmathcal E)$-measurable $Y_t:Omegato Etimes E$ with distribution $eta_t$ under $operatorname P$, we would obtain $$eta_t(Delta^c)=operatorname Pleft[(Y_t)_1ne(Y_t)_2right]tag5.$$ However, even when we can show this, why can we choose $(Y_t)_{tge0}$ such that $X^{(mu)}:=((Y_t)_1)_{tge0}$ and $X^{(nu)}:=((Y_t)_2)_{tge0}$ are versions of $X$?
probability-theory stochastic-processes markov-chains markov-process coupling
$endgroup$
add a comment |
$begingroup$
Let
$(Omega,mathcal A,operatorname P)$ be a probability space
$I=mathbb N_0$ or $I=[0,infty)$
$(E,mathcal E)$ be a measurable space
$mu$ and $nu$ be probability measures on $(E,mathcal E)$
$X$ be an $(E,mathcal E)$-valued time-homogeneous Markov chain on $(Omega,mathcal A,operatorname P)$ with transition semigroup $(kappa_t)_{tin I}$
Assume $mu$ is invariant with respect to $(kappa_t)_{tin I}$ and $$left|mu-nukappa_tright|xrightarrow{ttoinfty}0tag1,$$ where the left-hand side denotes the total variation distance of $mu$ and $nukappa_t$ and $nukappa_t$ denotes the composition of $nu$ and $kappa_t$.
I want to show that there is a version $X^{(eta)}$ of $X$ with $operatorname Pleft[X^{(eta)}_0in;cdot;right]=eta$ for $etainleft{mu,nuright}$ with $$tau:=infleft{tin I:X^{(mu)}_s=X^{(nu)}_stext{ for all }sin Itext{ with }sge tright}<infty;;;operatorname Ptext{-almost surely}.tag2$$
As pointed out by E-A, the basic idea is the following: For any $tge0$, there is (see Theorem 2.12) a probability measure $eta_t$ (called a coupling of $mu$ and $nukappa_t$) on $(Etimes E,mathcal Eotimesmathcal E)$ with $$eta_t(Btimes E)=mu(B)text{ and }eta_t(Etimes B)=(nukappa_t)(B);;;text{for all }Binmathcal Etag3$$ and $$left|mu-nukappa_tright|=eta_t(Delta^c),tag4$$ where $$Delta:=left{(x,x):xin Eright}.$$
Clearly, if we would be able to show (are we?) that there is a $(mathcal A,mathcal Eotimesmathcal E)$-measurable $Y_t:Omegato Etimes E$ with distribution $eta_t$ under $operatorname P$, we would obtain $$eta_t(Delta^c)=operatorname Pleft[(Y_t)_1ne(Y_t)_2right]tag5.$$ However, even when we can show this, why can we choose $(Y_t)_{tge0}$ such that $X^{(mu)}:=((Y_t)_1)_{tge0}$ and $X^{(nu)}:=((Y_t)_2)_{tge0}$ are versions of $X$?
probability-theory stochastic-processes markov-chains markov-process coupling
$endgroup$
add a comment |
$begingroup$
Let
$(Omega,mathcal A,operatorname P)$ be a probability space
$I=mathbb N_0$ or $I=[0,infty)$
$(E,mathcal E)$ be a measurable space
$mu$ and $nu$ be probability measures on $(E,mathcal E)$
$X$ be an $(E,mathcal E)$-valued time-homogeneous Markov chain on $(Omega,mathcal A,operatorname P)$ with transition semigroup $(kappa_t)_{tin I}$
Assume $mu$ is invariant with respect to $(kappa_t)_{tin I}$ and $$left|mu-nukappa_tright|xrightarrow{ttoinfty}0tag1,$$ where the left-hand side denotes the total variation distance of $mu$ and $nukappa_t$ and $nukappa_t$ denotes the composition of $nu$ and $kappa_t$.
I want to show that there is a version $X^{(eta)}$ of $X$ with $operatorname Pleft[X^{(eta)}_0in;cdot;right]=eta$ for $etainleft{mu,nuright}$ with $$tau:=infleft{tin I:X^{(mu)}_s=X^{(nu)}_stext{ for all }sin Itext{ with }sge tright}<infty;;;operatorname Ptext{-almost surely}.tag2$$
As pointed out by E-A, the basic idea is the following: For any $tge0$, there is (see Theorem 2.12) a probability measure $eta_t$ (called a coupling of $mu$ and $nukappa_t$) on $(Etimes E,mathcal Eotimesmathcal E)$ with $$eta_t(Btimes E)=mu(B)text{ and }eta_t(Etimes B)=(nukappa_t)(B);;;text{for all }Binmathcal Etag3$$ and $$left|mu-nukappa_tright|=eta_t(Delta^c),tag4$$ where $$Delta:=left{(x,x):xin Eright}.$$
Clearly, if we would be able to show (are we?) that there is a $(mathcal A,mathcal Eotimesmathcal E)$-measurable $Y_t:Omegato Etimes E$ with distribution $eta_t$ under $operatorname P$, we would obtain $$eta_t(Delta^c)=operatorname Pleft[(Y_t)_1ne(Y_t)_2right]tag5.$$ However, even when we can show this, why can we choose $(Y_t)_{tge0}$ such that $X^{(mu)}:=((Y_t)_1)_{tge0}$ and $X^{(nu)}:=((Y_t)_2)_{tge0}$ are versions of $X$?
probability-theory stochastic-processes markov-chains markov-process coupling
$endgroup$
Let
$(Omega,mathcal A,operatorname P)$ be a probability space
$I=mathbb N_0$ or $I=[0,infty)$
$(E,mathcal E)$ be a measurable space
$mu$ and $nu$ be probability measures on $(E,mathcal E)$
$X$ be an $(E,mathcal E)$-valued time-homogeneous Markov chain on $(Omega,mathcal A,operatorname P)$ with transition semigroup $(kappa_t)_{tin I}$
Assume $mu$ is invariant with respect to $(kappa_t)_{tin I}$ and $$left|mu-nukappa_tright|xrightarrow{ttoinfty}0tag1,$$ where the left-hand side denotes the total variation distance of $mu$ and $nukappa_t$ and $nukappa_t$ denotes the composition of $nu$ and $kappa_t$.
I want to show that there is a version $X^{(eta)}$ of $X$ with $operatorname Pleft[X^{(eta)}_0in;cdot;right]=eta$ for $etainleft{mu,nuright}$ with $$tau:=infleft{tin I:X^{(mu)}_s=X^{(nu)}_stext{ for all }sin Itext{ with }sge tright}<infty;;;operatorname Ptext{-almost surely}.tag2$$
As pointed out by E-A, the basic idea is the following: For any $tge0$, there is (see Theorem 2.12) a probability measure $eta_t$ (called a coupling of $mu$ and $nukappa_t$) on $(Etimes E,mathcal Eotimesmathcal E)$ with $$eta_t(Btimes E)=mu(B)text{ and }eta_t(Etimes B)=(nukappa_t)(B);;;text{for all }Binmathcal Etag3$$ and $$left|mu-nukappa_tright|=eta_t(Delta^c),tag4$$ where $$Delta:=left{(x,x):xin Eright}.$$
Clearly, if we would be able to show (are we?) that there is a $(mathcal A,mathcal Eotimesmathcal E)$-measurable $Y_t:Omegato Etimes E$ with distribution $eta_t$ under $operatorname P$, we would obtain $$eta_t(Delta^c)=operatorname Pleft[(Y_t)_1ne(Y_t)_2right]tag5.$$ However, even when we can show this, why can we choose $(Y_t)_{tge0}$ such that $X^{(mu)}:=((Y_t)_1)_{tge0}$ and $X^{(nu)}:=((Y_t)_2)_{tge0}$ are versions of $X$?
probability-theory stochastic-processes markov-chains markov-process coupling
probability-theory stochastic-processes markov-chains markov-process coupling
edited Jan 3 at 0:25
user26857
39.3k124183
39.3k124183
asked Oct 27 '18 at 21:08
0xbadf00d0xbadf00d
1,91441532
1,91441532
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let me try this:
Coupling $rightarrow$ TV goes to 0:
We can argue that $P(tau > t) geq P(X_t not = Y_t)$, since if $X_t$ is not equal to $Y_t$, then $tau$ has to be greater than t. We also know that $P(X_t not = Y_t)$ is an upper bound on the TV (or rather, the TV is a lower bound on this quantity), since the $P(X_n not =Y_n) geq | mu(A) - nu(A) | $ for any $A$. (You can find the proof in a lot of sources; if I were to summarize it, you should write $P(X_t in A) = P(X_t = Y_t, X_t in A) + P(X_t not = Y_t, Y_t in A)$, and do the same for $Y_t$; the first terms will cancel. http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf; you can also graphically observe what the total variation distance is by drawing densities together and you note that it is the half of the not-overlapping area, and that gives you a pictorial proof of this statement, since you know that you can't set $X_t = Y_t$ in any of those areas.)
TV goes to 0 $rightarrow$ coupling:
Let us construct our coupling in the most natural sense: let $X_t = Y_t$ once $X_{t_0} = Y_{t_0}$ for some $t_0$. We need to start by arguing for $P(X_t not = Y_t | X_0, Y_0) leq 1-epsilon$ for some $t, epsilon$. Now, we know that we can construct a coupling such that $P(X_t not = Y_t) = TV(mu, nu_t)$ for some fixed $t$. (Proof is in the pdf posted above; Theorem 2.12; you can also argue it from the picture again). Since the TV is going to 0, you can find a $t, epsilon$ such that the claim is true. Now, you can repeat the same argument and invoke the time homogeneity of your Markov process to show that $P(X_{2t} not = Y_{2t} | X_t not = Y_t) leq 1 - epsilon$. Now, you can inductively show a geometric decay $P(X_{2t} not = Y_{2t}) leq (1 - epsilon)^k$, which is enough to show that this time is almost surely finite. (Adapted this proof from https://www2.cs.duke.edu/courses/fall15/compsci590.4/slides/lec5.pdf; Section 4, Theorem 1, I might have messed up in certain places)
Feel free to point things out if there is anything wrong/unclear/unjustified. The first one is I think OK (it is a fairly standard proof); the second one involves constructing the coupling, so not sure if all of my steps were completely justified)
$endgroup$
$begingroup$
Sorry for the late response. Can you tell me how $hat X$ and $hat X'$ in Theorem 2.12 of the first PDF are defined?
$endgroup$
– 0xbadf00d
Jan 2 at 0:02
$begingroup$
The first direction is now clear to me. Thank you very much. However, I'm struggling with the other direction. I guess $X$ is supposed to be $X^{(mu)}$ and your $Y$ is supposed to be $X^{(eta)}$, right? The first question I have is why $hat X$ and $hat X'$ (from my former comment) even exist. The second one is: Why are $X^{(mu)}$ and $X^{(nu)}$ versions of $X$? (I've upvoted your answer and will accept it, once we've (hopefully) solved the remaining questions.)
$endgroup$
– 0xbadf00d
Jan 3 at 0:12
$begingroup$
Still interested in an answer. Could you take a look at my comments?
$endgroup$
– 0xbadf00d
Jan 11 at 18:02
$begingroup$
Yes; feel free to re-label them. Their existence is essentially proof of Theorem 2.12 in that PDF; in your notation $X$ and $hat{X}$ are the same map from $Sigma rightarrow E$. It's just that one of them is defined with the measure $mu$ and the other one is defined with $nu$; the underlying space is otherwise the same. This also hopefully answers the second question too (they are fundamentally the same map). Feel free to ask a separate question about this though; I am not sure how technical of an answer I can give.
$endgroup$
– E-A
Jan 12 at 21:46
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2973927%2fsuccessful-couplings-and-total-variation-convergence-to-equilibrium-for-time-hom%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let me try this:
Coupling $rightarrow$ TV goes to 0:
We can argue that $P(tau > t) geq P(X_t not = Y_t)$, since if $X_t$ is not equal to $Y_t$, then $tau$ has to be greater than t. We also know that $P(X_t not = Y_t)$ is an upper bound on the TV (or rather, the TV is a lower bound on this quantity), since the $P(X_n not =Y_n) geq | mu(A) - nu(A) | $ for any $A$. (You can find the proof in a lot of sources; if I were to summarize it, you should write $P(X_t in A) = P(X_t = Y_t, X_t in A) + P(X_t not = Y_t, Y_t in A)$, and do the same for $Y_t$; the first terms will cancel. http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf; you can also graphically observe what the total variation distance is by drawing densities together and you note that it is the half of the not-overlapping area, and that gives you a pictorial proof of this statement, since you know that you can't set $X_t = Y_t$ in any of those areas.)
TV goes to 0 $rightarrow$ coupling:
Let us construct our coupling in the most natural sense: let $X_t = Y_t$ once $X_{t_0} = Y_{t_0}$ for some $t_0$. We need to start by arguing for $P(X_t not = Y_t | X_0, Y_0) leq 1-epsilon$ for some $t, epsilon$. Now, we know that we can construct a coupling such that $P(X_t not = Y_t) = TV(mu, nu_t)$ for some fixed $t$. (Proof is in the pdf posted above; Theorem 2.12; you can also argue it from the picture again). Since the TV is going to 0, you can find a $t, epsilon$ such that the claim is true. Now, you can repeat the same argument and invoke the time homogeneity of your Markov process to show that $P(X_{2t} not = Y_{2t} | X_t not = Y_t) leq 1 - epsilon$. Now, you can inductively show a geometric decay $P(X_{2t} not = Y_{2t}) leq (1 - epsilon)^k$, which is enough to show that this time is almost surely finite. (Adapted this proof from https://www2.cs.duke.edu/courses/fall15/compsci590.4/slides/lec5.pdf; Section 4, Theorem 1, I might have messed up in certain places)
Feel free to point things out if there is anything wrong/unclear/unjustified. The first one is I think OK (it is a fairly standard proof); the second one involves constructing the coupling, so not sure if all of my steps were completely justified)
$endgroup$
$begingroup$
Sorry for the late response. Can you tell me how $hat X$ and $hat X'$ in Theorem 2.12 of the first PDF are defined?
$endgroup$
– 0xbadf00d
Jan 2 at 0:02
$begingroup$
The first direction is now clear to me. Thank you very much. However, I'm struggling with the other direction. I guess $X$ is supposed to be $X^{(mu)}$ and your $Y$ is supposed to be $X^{(eta)}$, right? The first question I have is why $hat X$ and $hat X'$ (from my former comment) even exist. The second one is: Why are $X^{(mu)}$ and $X^{(nu)}$ versions of $X$? (I've upvoted your answer and will accept it, once we've (hopefully) solved the remaining questions.)
$endgroup$
– 0xbadf00d
Jan 3 at 0:12
$begingroup$
Still interested in an answer. Could you take a look at my comments?
$endgroup$
– 0xbadf00d
Jan 11 at 18:02
$begingroup$
Yes; feel free to re-label them. Their existence is essentially proof of Theorem 2.12 in that PDF; in your notation $X$ and $hat{X}$ are the same map from $Sigma rightarrow E$. It's just that one of them is defined with the measure $mu$ and the other one is defined with $nu$; the underlying space is otherwise the same. This also hopefully answers the second question too (they are fundamentally the same map). Feel free to ask a separate question about this though; I am not sure how technical of an answer I can give.
$endgroup$
– E-A
Jan 12 at 21:46
add a comment |
$begingroup$
Let me try this:
Coupling $rightarrow$ TV goes to 0:
We can argue that $P(tau > t) geq P(X_t not = Y_t)$, since if $X_t$ is not equal to $Y_t$, then $tau$ has to be greater than t. We also know that $P(X_t not = Y_t)$ is an upper bound on the TV (or rather, the TV is a lower bound on this quantity), since the $P(X_n not =Y_n) geq | mu(A) - nu(A) | $ for any $A$. (You can find the proof in a lot of sources; if I were to summarize it, you should write $P(X_t in A) = P(X_t = Y_t, X_t in A) + P(X_t not = Y_t, Y_t in A)$, and do the same for $Y_t$; the first terms will cancel. http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf; you can also graphically observe what the total variation distance is by drawing densities together and you note that it is the half of the not-overlapping area, and that gives you a pictorial proof of this statement, since you know that you can't set $X_t = Y_t$ in any of those areas.)
TV goes to 0 $rightarrow$ coupling:
Let us construct our coupling in the most natural sense: let $X_t = Y_t$ once $X_{t_0} = Y_{t_0}$ for some $t_0$. We need to start by arguing for $P(X_t not = Y_t | X_0, Y_0) leq 1-epsilon$ for some $t, epsilon$. Now, we know that we can construct a coupling such that $P(X_t not = Y_t) = TV(mu, nu_t)$ for some fixed $t$. (Proof is in the pdf posted above; Theorem 2.12; you can also argue it from the picture again). Since the TV is going to 0, you can find a $t, epsilon$ such that the claim is true. Now, you can repeat the same argument and invoke the time homogeneity of your Markov process to show that $P(X_{2t} not = Y_{2t} | X_t not = Y_t) leq 1 - epsilon$. Now, you can inductively show a geometric decay $P(X_{2t} not = Y_{2t}) leq (1 - epsilon)^k$, which is enough to show that this time is almost surely finite. (Adapted this proof from https://www2.cs.duke.edu/courses/fall15/compsci590.4/slides/lec5.pdf; Section 4, Theorem 1, I might have messed up in certain places)
Feel free to point things out if there is anything wrong/unclear/unjustified. The first one is I think OK (it is a fairly standard proof); the second one involves constructing the coupling, so not sure if all of my steps were completely justified)
$endgroup$
$begingroup$
Sorry for the late response. Can you tell me how $hat X$ and $hat X'$ in Theorem 2.12 of the first PDF are defined?
$endgroup$
– 0xbadf00d
Jan 2 at 0:02
$begingroup$
The first direction is now clear to me. Thank you very much. However, I'm struggling with the other direction. I guess $X$ is supposed to be $X^{(mu)}$ and your $Y$ is supposed to be $X^{(eta)}$, right? The first question I have is why $hat X$ and $hat X'$ (from my former comment) even exist. The second one is: Why are $X^{(mu)}$ and $X^{(nu)}$ versions of $X$? (I've upvoted your answer and will accept it, once we've (hopefully) solved the remaining questions.)
$endgroup$
– 0xbadf00d
Jan 3 at 0:12
$begingroup$
Still interested in an answer. Could you take a look at my comments?
$endgroup$
– 0xbadf00d
Jan 11 at 18:02
$begingroup$
Yes; feel free to re-label them. Their existence is essentially proof of Theorem 2.12 in that PDF; in your notation $X$ and $hat{X}$ are the same map from $Sigma rightarrow E$. It's just that one of them is defined with the measure $mu$ and the other one is defined with $nu$; the underlying space is otherwise the same. This also hopefully answers the second question too (they are fundamentally the same map). Feel free to ask a separate question about this though; I am not sure how technical of an answer I can give.
$endgroup$
– E-A
Jan 12 at 21:46
add a comment |
$begingroup$
Let me try this:
Coupling $rightarrow$ TV goes to 0:
We can argue that $P(tau > t) geq P(X_t not = Y_t)$, since if $X_t$ is not equal to $Y_t$, then $tau$ has to be greater than t. We also know that $P(X_t not = Y_t)$ is an upper bound on the TV (or rather, the TV is a lower bound on this quantity), since the $P(X_n not =Y_n) geq | mu(A) - nu(A) | $ for any $A$. (You can find the proof in a lot of sources; if I were to summarize it, you should write $P(X_t in A) = P(X_t = Y_t, X_t in A) + P(X_t not = Y_t, Y_t in A)$, and do the same for $Y_t$; the first terms will cancel. http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf; you can also graphically observe what the total variation distance is by drawing densities together and you note that it is the half of the not-overlapping area, and that gives you a pictorial proof of this statement, since you know that you can't set $X_t = Y_t$ in any of those areas.)
TV goes to 0 $rightarrow$ coupling:
Let us construct our coupling in the most natural sense: let $X_t = Y_t$ once $X_{t_0} = Y_{t_0}$ for some $t_0$. We need to start by arguing for $P(X_t not = Y_t | X_0, Y_0) leq 1-epsilon$ for some $t, epsilon$. Now, we know that we can construct a coupling such that $P(X_t not = Y_t) = TV(mu, nu_t)$ for some fixed $t$. (Proof is in the pdf posted above; Theorem 2.12; you can also argue it from the picture again). Since the TV is going to 0, you can find a $t, epsilon$ such that the claim is true. Now, you can repeat the same argument and invoke the time homogeneity of your Markov process to show that $P(X_{2t} not = Y_{2t} | X_t not = Y_t) leq 1 - epsilon$. Now, you can inductively show a geometric decay $P(X_{2t} not = Y_{2t}) leq (1 - epsilon)^k$, which is enough to show that this time is almost surely finite. (Adapted this proof from https://www2.cs.duke.edu/courses/fall15/compsci590.4/slides/lec5.pdf; Section 4, Theorem 1, I might have messed up in certain places)
Feel free to point things out if there is anything wrong/unclear/unjustified. The first one is I think OK (it is a fairly standard proof); the second one involves constructing the coupling, so not sure if all of my steps were completely justified)
$endgroup$
Let me try this:
Coupling $rightarrow$ TV goes to 0:
We can argue that $P(tau > t) geq P(X_t not = Y_t)$, since if $X_t$ is not equal to $Y_t$, then $tau$ has to be greater than t. We also know that $P(X_t not = Y_t)$ is an upper bound on the TV (or rather, the TV is a lower bound on this quantity), since the $P(X_n not =Y_n) geq | mu(A) - nu(A) | $ for any $A$. (You can find the proof in a lot of sources; if I were to summarize it, you should write $P(X_t in A) = P(X_t = Y_t, X_t in A) + P(X_t not = Y_t, Y_t in A)$, and do the same for $Y_t$; the first terms will cancel. http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf; you can also graphically observe what the total variation distance is by drawing densities together and you note that it is the half of the not-overlapping area, and that gives you a pictorial proof of this statement, since you know that you can't set $X_t = Y_t$ in any of those areas.)
TV goes to 0 $rightarrow$ coupling:
Let us construct our coupling in the most natural sense: let $X_t = Y_t$ once $X_{t_0} = Y_{t_0}$ for some $t_0$. We need to start by arguing for $P(X_t not = Y_t | X_0, Y_0) leq 1-epsilon$ for some $t, epsilon$. Now, we know that we can construct a coupling such that $P(X_t not = Y_t) = TV(mu, nu_t)$ for some fixed $t$. (Proof is in the pdf posted above; Theorem 2.12; you can also argue it from the picture again). Since the TV is going to 0, you can find a $t, epsilon$ such that the claim is true. Now, you can repeat the same argument and invoke the time homogeneity of your Markov process to show that $P(X_{2t} not = Y_{2t} | X_t not = Y_t) leq 1 - epsilon$. Now, you can inductively show a geometric decay $P(X_{2t} not = Y_{2t}) leq (1 - epsilon)^k$, which is enough to show that this time is almost surely finite. (Adapted this proof from https://www2.cs.duke.edu/courses/fall15/compsci590.4/slides/lec5.pdf; Section 4, Theorem 1, I might have messed up in certain places)
Feel free to point things out if there is anything wrong/unclear/unjustified. The first one is I think OK (it is a fairly standard proof); the second one involves constructing the coupling, so not sure if all of my steps were completely justified)
answered Nov 6 '18 at 2:38
E-AE-A
2,1121414
2,1121414
$begingroup$
Sorry for the late response. Can you tell me how $hat X$ and $hat X'$ in Theorem 2.12 of the first PDF are defined?
$endgroup$
– 0xbadf00d
Jan 2 at 0:02
$begingroup$
The first direction is now clear to me. Thank you very much. However, I'm struggling with the other direction. I guess $X$ is supposed to be $X^{(mu)}$ and your $Y$ is supposed to be $X^{(eta)}$, right? The first question I have is why $hat X$ and $hat X'$ (from my former comment) even exist. The second one is: Why are $X^{(mu)}$ and $X^{(nu)}$ versions of $X$? (I've upvoted your answer and will accept it, once we've (hopefully) solved the remaining questions.)
$endgroup$
– 0xbadf00d
Jan 3 at 0:12
$begingroup$
Still interested in an answer. Could you take a look at my comments?
$endgroup$
– 0xbadf00d
Jan 11 at 18:02
$begingroup$
Yes; feel free to re-label them. Their existence is essentially proof of Theorem 2.12 in that PDF; in your notation $X$ and $hat{X}$ are the same map from $Sigma rightarrow E$. It's just that one of them is defined with the measure $mu$ and the other one is defined with $nu$; the underlying space is otherwise the same. This also hopefully answers the second question too (they are fundamentally the same map). Feel free to ask a separate question about this though; I am not sure how technical of an answer I can give.
$endgroup$
– E-A
Jan 12 at 21:46
add a comment |
$begingroup$
Sorry for the late response. Can you tell me how $hat X$ and $hat X'$ in Theorem 2.12 of the first PDF are defined?
$endgroup$
– 0xbadf00d
Jan 2 at 0:02
$begingroup$
The first direction is now clear to me. Thank you very much. However, I'm struggling with the other direction. I guess $X$ is supposed to be $X^{(mu)}$ and your $Y$ is supposed to be $X^{(eta)}$, right? The first question I have is why $hat X$ and $hat X'$ (from my former comment) even exist. The second one is: Why are $X^{(mu)}$ and $X^{(nu)}$ versions of $X$? (I've upvoted your answer and will accept it, once we've (hopefully) solved the remaining questions.)
$endgroup$
– 0xbadf00d
Jan 3 at 0:12
$begingroup$
Still interested in an answer. Could you take a look at my comments?
$endgroup$
– 0xbadf00d
Jan 11 at 18:02
$begingroup$
Yes; feel free to re-label them. Their existence is essentially proof of Theorem 2.12 in that PDF; in your notation $X$ and $hat{X}$ are the same map from $Sigma rightarrow E$. It's just that one of them is defined with the measure $mu$ and the other one is defined with $nu$; the underlying space is otherwise the same. This also hopefully answers the second question too (they are fundamentally the same map). Feel free to ask a separate question about this though; I am not sure how technical of an answer I can give.
$endgroup$
– E-A
Jan 12 at 21:46
$begingroup$
Sorry for the late response. Can you tell me how $hat X$ and $hat X'$ in Theorem 2.12 of the first PDF are defined?
$endgroup$
– 0xbadf00d
Jan 2 at 0:02
$begingroup$
Sorry for the late response. Can you tell me how $hat X$ and $hat X'$ in Theorem 2.12 of the first PDF are defined?
$endgroup$
– 0xbadf00d
Jan 2 at 0:02
$begingroup$
The first direction is now clear to me. Thank you very much. However, I'm struggling with the other direction. I guess $X$ is supposed to be $X^{(mu)}$ and your $Y$ is supposed to be $X^{(eta)}$, right? The first question I have is why $hat X$ and $hat X'$ (from my former comment) even exist. The second one is: Why are $X^{(mu)}$ and $X^{(nu)}$ versions of $X$? (I've upvoted your answer and will accept it, once we've (hopefully) solved the remaining questions.)
$endgroup$
– 0xbadf00d
Jan 3 at 0:12
$begingroup$
The first direction is now clear to me. Thank you very much. However, I'm struggling with the other direction. I guess $X$ is supposed to be $X^{(mu)}$ and your $Y$ is supposed to be $X^{(eta)}$, right? The first question I have is why $hat X$ and $hat X'$ (from my former comment) even exist. The second one is: Why are $X^{(mu)}$ and $X^{(nu)}$ versions of $X$? (I've upvoted your answer and will accept it, once we've (hopefully) solved the remaining questions.)
$endgroup$
– 0xbadf00d
Jan 3 at 0:12
$begingroup$
Still interested in an answer. Could you take a look at my comments?
$endgroup$
– 0xbadf00d
Jan 11 at 18:02
$begingroup$
Still interested in an answer. Could you take a look at my comments?
$endgroup$
– 0xbadf00d
Jan 11 at 18:02
$begingroup$
Yes; feel free to re-label them. Their existence is essentially proof of Theorem 2.12 in that PDF; in your notation $X$ and $hat{X}$ are the same map from $Sigma rightarrow E$. It's just that one of them is defined with the measure $mu$ and the other one is defined with $nu$; the underlying space is otherwise the same. This also hopefully answers the second question too (they are fundamentally the same map). Feel free to ask a separate question about this though; I am not sure how technical of an answer I can give.
$endgroup$
– E-A
Jan 12 at 21:46
$begingroup$
Yes; feel free to re-label them. Their existence is essentially proof of Theorem 2.12 in that PDF; in your notation $X$ and $hat{X}$ are the same map from $Sigma rightarrow E$. It's just that one of them is defined with the measure $mu$ and the other one is defined with $nu$; the underlying space is otherwise the same. This also hopefully answers the second question too (they are fundamentally the same map). Feel free to ask a separate question about this though; I am not sure how technical of an answer I can give.
$endgroup$
– E-A
Jan 12 at 21:46
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2973927%2fsuccessful-couplings-and-total-variation-convergence-to-equilibrium-for-time-hom%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown