Changeset - 29be8ea7ee3c
[Not reviewed]
0 1 0
András Gilyén - 8 years ago 2017-09-07 02:44:49
gilyen@cwi.nl
simplified proof
1 file changed with 1 insertions and 1 deletions:
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -657,25 +657,25 @@ The intuition of the following lemma is that the far right can only affect the z
 
 	\begin{lemma}\label{lemma:independenetSidesNew}	
 
 		$$\P^{[k]}(\Z{1}\cap \Z{k})=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})+\mathcal{O}(p^{k})=\left(\P^{[k]}(\Z{1})\right)^2+\mathcal{O}(p^{k}).$$
 
 	\end{lemma}   
 
 	Note that using De Morgan's law and the inclusion-exclusion formula we can see that this is equivalent to saying:
 
 	$$\P^{[k]}(\NZ{1}\cap \NZ{k})=\P^{[k]}(\NZ{1})\P^{[k]}(\NZ{k})+\mathcal{O}(p^{k}).$$
 
 	\begin{proof}
 
 		We proceed by induction on $k$. For $k=1,2$ the statement is trivial.
 
 		
 
 		Now observe that:
 
 		$$\P^{[k]}(\Z{1})=\sum_{P\text{ patch}\,:\,1\in P}\P^{[k]}(P\in\mathcal{P})$$
 
 		$$\P^{[k]}(\Z{k})=\sum_{P\text{ patch}\,:\,k\in P}\P^{[k]}(P\in\mathcal{P})$$
 
 		
 
 		Suppose we proved the statement up to $k-$, then we proceed using induction similarly to the above
 
 		Suppose we proved the statement up to $k-1$, then we proceed using induction similarly to the above
 
 		\begin{align*}
 
 		&\P^{[k]}(\Z{1}\cap \Z{k})=\\
 
 		&=\sum_{\ell, r\in [k]: \ell<r-1}\P^{[k]}([\ell],[r,k]\in\mathcal{P})
 
 		+\P^{[k]}([k]\in\mathcal{P})\\
 
 		&=\sum_{\ell, r\in [k]: \ell<r-1}\P^{[k]}([\ell],[r,k]\in\mathcal{P})
 
 		+\mathcal{O}(p^{k})\\
 
 		&\overset{Lemma~\ref{lemma:eventindependenceNew}}{=}\sum_{\ell, r\in [k]: \ell<r-1}
 
 		\P^{[\ell+1]}([\ell]\in\mathcal{P})
 
 		\P^{[\ell+1,r-1]}(\NZ{\ell+1}\cap \NZ{r-1})
 
 		\P^{[r-1,k]}([r,k]\in\mathcal{P})/(1-p)^2
 
 		+\mathcal{O}(p^{k})\\
 
 		&\overset{\text{induction}}{=}\sum_{\ell, r\in [k]: \ell<r-1}
0 comments (0 inline, 0 general)