AENC/resampling_chain Changeset - 9e5ac6b49d57 · Centrum Wiskunde & Informatica (CWI)

Changeset - 9e5ac6b49d57

Parent rev.

Child rev.

[Not reviewed]

0 1 0

András Gilyén - 8 years ago 2017-09-14 00:15:32
gilyen@cwi.nl

General distance-degree lemma

1 file changed with 7 insertions and 7 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

 	The proof goes by induction on $d(X,Y)$. The statement is trivial for $d(X,Y)=0$, and is easy to check for $d(X,Y)=1$, by looking at resample sequences that reach the all $1$ state in at most $0$ step (which is simply the case when everything is sampled to $1$ initially).
 	Now we show the inductive step, assuming we know the statement for $d$, and that $d(X,Y)=d+1$.
-	First we assume, that $\NZ{X}\subseteq\overline{A^X}$, i.e., $A^X=A^X\cap \Z{X}$.
+	First we assume, that $\NZ{X}\subseteq\overline{A^X}$, i.e., $A^X\subseteq \Z{X}$.
 	For $i\in[d]$ we define $A_i^X:=A^X\cap{\NZ{\overline{\partial}(X,i)}}\cap\bigcap_{j\in[i-1]}\Z{\overline{\partial}(X,j)}$,
 	and define $A_{d+1}^X:=A^X\cap\bigcap_{j\in[d]}\Z{\overline{\partial}(X,j)}$,
 	it is easy to see that it is partition $A^X=\dot\bigcup_{i\in [d+1]}A_i^X$.
 	Also it is easy to see that for all $i\in[d+1]$ we have $A_{i}^X\subseteq\Z{X}\cap\bigcap_{j\in[i-1]}\Z{\overline{\partial}(X,j)}$, and therefore
 	so that they form a partition $A^X=\dot\bigcup_{i\in [d+1]}A_i^X$.
 	It is easy to see that for all $i\in[d+1]$ we have $A_{i}^X\subseteq\Z{X}\cap\bigcap_{j\in[i-1]}\Z{\overline{\partial}(X,j)}$, and therefore
 	\begin{equation}\label{eq:AXorder}
 		\P^G(A_{i}^X)=\bigO{p^{i}}.
 	\end{equation}
 	Now we use the Splitting lemma~\ref{lemma:splitting} to show that for all $i\in[d]$
 	\begin{align}
 		\P^G(A_{i}^X)
 		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus B(X,i)}(X,i)(\NZ{\overline{\partial}(X,i)}) \tag{by Lemma~\ref{lemma:splitting}}\\
 		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \left(\P^{G\setminus Y\setminus B(X,i)}(X,i)(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1-i}}\right) \tag{by induction}\\
 		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus Y\setminus B(X,i)}(X,i)(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1}} \tag{by equation \eqref{eq:AXorder}}\\
 		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus B(X,i-1)}(X,i)(\NZ{\overline{\partial}(X,i)}) \tag{by Lemma~\ref{lemma:splitting}}\\
 		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \left(\P^{G\setminus Y\setminus B(X,i-1)}(X,i)(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1-i}}\right) \tag{by induction}\\
 		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus Y\setminus B(X,i-1)}(X,i)(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1}} \tag{by equation \eqref{eq:AXorder}}\\
 		&=\P^{G\setminus Y}(A_{i}^X)+\bigO{p^{d+1}} \tag{by Lemma~\ref{lemma:splitting}}\\
 		&=\P^{G\setminus Y}(A_{i}^X)+\bigO{p^{d(Y,Y)}}. \label{eq:indStep}
 	\end{align}
 	\overset{\eqref{eq:AXorder}}{=}\P^{G\setminus Y}(A^X)+\bigO{p^{d(Y,Y)}}.
 	$$
 	We finish the proof by observing that if $\NZ{X}\nsubseteq\overline{A^X}$,
-	then we necessarily have $\NZ{X}\subseteq A^X$, and therefore we can use the above proof with $B^X:=\overline{A^X}$ and using that $\P(A^X)=1-\P(B^X)$.
+	then we necessarily have $\NZ{X}\subseteq A^X$, and therefore we can use the above proof with $B^X:=\overline{A^X}$ and use that $\P(A^X)=1-\P(B^X)$.
 \end{proof}
 	\begin{theorem} If $2< 2m\leq n$ and $m\leq M$, then $R^{(n)}=\E^{[-M,M]}(\Res{0})+\bigO{p^{m}}$.

0 comments (0 inline, 0 general)