Changeset - 83372538681f
[Not reviewed]
0 1 0
András Gilyén - 8 years ago 2017-09-07 02:37:14
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
 
@@ -642,25 +642,25 @@ The intuition of the following lemma is that the far right can only affect the z
 
	\P^{[n+1]}(\Z{1})
 
	&=\sum_{k=1}^{n+1}\P^{[n]}([k]\in\mathcal{P}) \tag{the events are a partition}\\
 
	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P}) + O(p^{n})\\
 
	&=\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \P^{[n-k+1]}(\NZ{1})/(1-p)+ O(p^{n}) \tag{by Claim~\ref{lemma:eventindependenceNew}}\\
 
	&=\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \left(\P^{[n-k]}(\NZ{1})+O(p^{n-k})\right)/(1-p)+ O(p^{n}) \tag{by induction} \\	
 
	&=\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \P^{[n-k]}(\NZ{1})/(1-p)+ O(p^{n}) \\	
 
	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P})+ O(p^{n}) \tag{by Claim~\ref{lemma:eventindependenceNew}}\\
 
	&=\sum_{k=1}^{n}\P^{[n]}([k]\in\mathcal{P})+ O(p^{n}) \\
 
	&=\P^{[n]}(\Z{1})	+ O(p^{n}) 
 
	\end{align*}
 
\end{proof}
 
\begin{corollary}\label{cor:probIndepNew}
 
	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = O(p^{\min(n,m)})$. (Should be true with $O(p^{\min(n,m)+1})$ as well.)
 
	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = O(p^{\min(n,m)})$. (Should be true with $O(p^{\min(n,m)+1})$ too.)
 
\end{corollary}
 

	
 
 	\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})$$
0 comments (0 inline, 0 general)