This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
world:reflectional_coupling [2019/05/23 07:15] douc |
world:reflectional_coupling [2022/04/11 13:42] rdouc ↷ Page moved from mynotes:reflectional_coupling to world:reflectional_coupling |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | {{page>:defs}} | ||
+ | |||
+ | ====== Reflection coupling ====== | ||
+ | |||
+ | Let $I$ be the identity matrix with $d$ components. | ||
+ | |||
+ | We want to find a coupling of $N(0,I)$ and $N(a,I)$ where $a \in \rset^d$. For all $b \in \rset^d$, denote $f_b$ the density of $N(b,I)$. The reflection coupling is based on the following result: Set $R_a=\Id -2 \frac{aa^T}{\|a\|^2}$ as the orthogonal reflection wrt to $\{\rset a\}^\perp$. | ||
+ | |||
+ | <WRAP center round box 80%> | ||
+ | __**Lemma**__ | ||
+ | * draw independently $X \sim N(0,I)$ and $U \sim \unif(0,1)$ | ||
+ | * set | ||
+ | * $Y=X$ if $U \leq \frac{f_0\wedge f_a(X)}{f_0(X)}$ | ||
+ | * $Y=a+R_aX$ otherwise. | ||
+ | Then, $Y \sim N(a,I)$. | ||
+ | </WRAP> | ||
+ | |||
+ | |||
+ | ===== Proof ===== | ||
+ | |||
+ | Since $R_a^2=\Id$, we get $R_a=R_a^{-1}$. Then, $y=a+R_a x$ is equivalent to $R_a(y-a)=x$. Moreover, $(\det R_a)^2=\det R_a^2=1$ so that $|\det R_a|=1$. Then, | ||
+ | \begin{align*} | ||
+ | \PE\lrb{h(Y)}&=\int h(x) \ f_0\wedge f_a(x)\ \rmd x+\int h(a+R_ax) (f_0- f_a)^+(x) \rmd x\\ | ||
+ | &=\int h(x) \ f_0\wedge f_a(x)\ \rmd x+\int h(y) (f_0- f_a)^+(R_a(y-a)) \underbrace{|\det R_a|}_{1} \rmd y | ||
+ | \end{align*} | ||
+ | Now, noting that $R_a$ is an isometry and that $R_aa=-a$, we get | ||
+ | \begin{align*} | ||
+ | \|R_a(y-a)\|^2&=\|y-a\|^2\\ | ||
+ | \|R_a(y-a)-a\|^2&=\|R_ay\|^2=\|y\|^2 | ||
+ | \end{align*} | ||
+ | which implies that $f_0(R_a(y-a))=f_a(y)$ and $f_a(R_a(y-a))=f_0(y)$. Finally, | ||
+ | $$ | ||
+ | \PE\lrb{h(Y)}=\int h(x) \ f_0\wedge f_a(x)\ \rmd x+\int h(y) (f_a- f_0)^+(y)\rmd y =\int h(x) f_a(x)\rmd x | ||
+ | $$ | ||
+ | which concludes the proof. | ||
+ | |||
+ | ===== Corollary ===== | ||
+ | |||
+ | We now intend to construct a coupling of $N(x,h I)$ and $N(y,h I)$. We use the Lemma with $N(0,I)$ and $N(a,I)$ where $a=(y-x)/\sqrt{h}$ to construct a coupling $(Z,Z')$ and we set $X=x+\sqrt{h}Z$ and $Y=x+\sqrt{h}Z'$. This is is equivalent to the following coupling. Write $\varphi_{b,\Gamma}$ the density of $N(b,\Gamma)$, | ||
+ | * Draw independently $Z \sim N(0,I)$ and $U \sim \unif(0,1)$ | ||
+ | * Set $X=x+\sqrt{h}Z$ and set | ||
+ | * $Y=X$ if $U \leq \frac{f_0\wedge f_a(Z)}{f_0(Z)}=\frac{\varphi_{x,h I}\wedge \varphi_{y,h I}(X)}{\varphi_{x,h I}(X)}$ | ||
+ | * $Y=y+R_{y-x} (\sqrt{h}Z)$ otherwise. | ||
+ | |||