diff --git a/diagram_groups.pdf b/diagram_groups.pdf index 2a0521608bfcc2468ae3f271edb6c6681cfffd64..61b94022e85196e7e382b7d4e7694a113e2f8219 100644 GIT binary patch delta 3930 zcmV-g52f(>rU8qm0gxmDF*uVhs`t-+!G9R`q_#}26gWW!F3AS!`Q3th&U2L!T-R$1Us5WVK=e2R$V|#x(7&*TO z<-K9PJLQz!5YS2pzsX%{9rac<6yTP%3g@kDLUy+{hS1bBK;#kSJ5-6H1ISF!PgT~_ z#LAMPTXQoC$K0vi2j?QhP25EcMr{gxZ(J;H<7Cl>5N$9E(C#WmFO%sy1nCnJgx7Iv z+6r>ZQ%G%{?ZhXi^_M(bdcsi7G#=(F24)G#V$2``u zM(#=}9hRV%#;m%&)j6OmaLX3W zVPBU{H%m9+o%hDUIq!cpRVLAr_hT(b6XF1Nd9!BHDIHbhmZzAKR+rc2OjjmM<2vxl zn?(~zw-veNh0a;IvuDob-GujrJC4b72*D~iXF*akd#sd9wm#M`xH4KnfheKnISuT< ztBSLgzkazT6D9$ogPZA2Z9iB)CGRa#Ce_yro{!0v_n$~gz;&E%d{dFQ2RI-Aim?E%e=z@<>2nHFd|1~#byO@2T#Byfoo zXubuSlz~m&_l0i`)|uJGJSSa9)0#S?xu^oIp}>}XAnX7LfdIA+1FhFUYC5o`A1Flt z$|Hc~8~2rK4$gm<$vLZLiI*lNb_UM~0$Ngm<*7jVEKt%59CHLpFo9ABVA(2ARtuE+ z0>_Z=3)dX1FSCdH_UrLQNm6r1wB$gbH5S;u3TXcYv`GWD)dA8G0p$|Fc2_{VFd&^8 zunpaP<(y;oJX41Wd_8Acc6+5m+%#g)M0=u9<8bC4L%_li+B4PYCm;4o zPd18ZGpDJfmd}9;bL3L*4*UUT08N?k=~%5(Qw*_^^%3H=mpIDg8Fvo;$Ujy7V=EMPH-RFbEWQ-4xE*Xq!w{p z6tZl&k8R3M+T2(b|5ax#HSS|pXbS2{FdT(a!* zFHN*;|2L-ZnXUA*53MItC;D@Or{#=%N6*>FT_7e&)6n}@m9isp4b4>B2(Nvv!J<{C+w z(fQneU-;%=o!Q@_O+l<@a3KI0ER8_yn;CmAuNTbGxwEi z4$hbT_3qsC@zSI?k6=B_qGgyT%-j(dW#E4-VP%*tLp^w^%#dn^d$T0{zHrUK`to(U zFn)YVke1>ZEr-Q((d9cp?ueFjlzaomv}z2|;CnyrK$Z4^3TzhD^}VGF^XD zR~OY;QlMK-Ue^MfU^A}#$k_X(WboZq-w=6T_?5igf%`<-=^IWjRPgD&5*Z!t1BKg4 z%Fr%V3UG#ni~>1L71FrR6fU}|DL{F(qkM-dQFH*A3HqtZdYag|;HIdV!@t(?1{bmK z9mqZ4)GQSDV4@ExtvDg|rX{jV%sqcCM^)rZZ#G)ovQ5nG+Iyv&riOHBv0@ITjF4N^ zq%3Y~+rM*g0k@pQ^P&n=S6#HsmaShmc#G@UR}9Eb7{D6qBn+GR|?+XJpNSze0b3~vjE+$9C8lncIlnY_uD3D*d9s^o4k6kVIJ0B3f%mQ|(d(yJz7;k9EKZ;Vc4{dHj&!ybS0Nu`C=;W9m9 ziCJ{FN~ZT*F=6DVp8oWoZ?D_<4s00@=~Y>eyv!+_%O@S*y*&Nx@7NAR>^IQJmtVI_ z<`Q}NdHeC*e}DP(`+MvM-u?3L_n@_Y_xrE!e|q@=2g+_BW_PVH;LkDtJSF_*Qo|9l z0J|9n_b-3LyS#03T;FrI`qO-<_Tz8Qm!;|VPaiKq49L|x0vdBwjJaF} zCG2??9ty+U^(!ZSHoLp zUEC96T5;N>m^H#)_F}=)PGHnk^fBC}23(Da=1LSd<ffPrRN<|rxJH(^*3gxJso(Mlmhf3 zHzkQn;IGb1?#zEo<`j}7Gj&ssdFise8h)lF2Xh}4= zt{^0$4e3S4m_2ko8T^t;3%9|DHcwgH1R1|Jeh42ox~wDkYubw-Y7| zjp;%q*6Y7*J7KR8(}`BV=oa0E8g|AhbBW~0|IZxxqs$ol*D|54^Z5%8ze6!IDeYL> zQ<#hMgcLCwqHnX^%RL={VvWJ)#hZSLToT#x&$H!&$V5i2RklT*hU0&~<-fo7e=q$H zvg0d9v)T%RLIg87Gc}W7O&gj?#F>KW*?#RxG-I zL0qgNkP-gIaUczdRv+~eJimSoECqH^U01+{Ff|zH1lXwXGkEg`#R0qizH-2>vV{xS zSyg&h`UVoh1#IG)YF+29K`!mZ*v*UVw0eXo#|t6i(8f{wYxFEYD>bT9RD|vwJiGn$ z`3nqUq+mJXpjBiq5>uCrjOr41!$B}1w=M~OC3Xh0{H);NYJHi%GKlT3(z9%n$> zB-D^#7Z}dTMxsMRa}^5E+MrBFg6>U%I?4#Vk77wyT4XGu&{70w85@vCB(XNM5D9~O zsYp*6(?-+o+nd-DzQb(eyA>N5@hVXivk@B{?o4|}yY^q{(9E_vjS4b!O-E6|5j~(vytLovH3F{ zzyI69uv|P-ilyA4L?nKLQpC3?X}wL!u{&0=nl%7dXc~LIVWpQ`s@Rg!RZ7R4RD_8)*DqJ;L!uaZXb)ezi((NyjYZfa=zPWd#>faYi+k&Q+hX^ zqyOOfpegpe>wWK-@@?kS6dV8j(Am_AhTlOzG^ZLGRBM_u0sE_%H~r*zsu=YvULFmr ze1OBC_Qy1l>4iU9p?WBe!FCGlUGY%(J?sYbJepjC82Lha&N6H)*=iAVVQuDKAAsyC z*~-S%+_4XhyIlKaQ4)j8l`BtjUsNSLP0POla49AslN(ZOQ8+R-F+)Z%Mno||H8M3q zGet8)F-0*sLohf*GB`m+Lp~rpI5IXdLq;)1L@_}%GBrXoMKeP&MKL);FgQdqI6*~2 zK3xhgOl59obZ8(rG$4~pPAPg7%C`-GKokVg{dj-a77!(nkP)5;=s%zkB$x}HW`mXV zMM_g-$RWE{QA1*KVMmBDz@f*80wp?BR=wd{+vY~nR~r_s^zw?AUTwyCyO>P{9gSZe%gcYx#gZ~1 zpcuanHdvfGs^DXEi&17>)4CJ|<@$z$Hsy3!*D4cKOc5<6Efvtmh;j`iQFOpK5wtTE zYpPT+xN2&bgk$b((Yxdx#C=rBM6;|;X%lQLE|X;Q3S4wy0!C$5=WJg1>hzW}vN@~c zQneN2c1)pTv|A(Ql#jaARDgdnUmjMlpi(q3EmcoY4i&Ayv;7#=leRxb|1Ku2O^*RNEvwmHCQr@{WEUQ<>YrBxH>-u)6w}`nav#BjQ z6B;!Qa?X~=5xC;c(%LLllU3-~)z#?=kjIft1*~=#O?-K$J0(}_lIMRACz&$nF_(2o zS*KBU25xyn&~GM92%70|Z$_@flxD*F z#2LHbJA^5MDW)G&*)iN&h;Dz0E`GBKK`Vurpy*>CnJANl>L~CaUSfzhAxRf2O1&-Z4}t5VYHFs%8chg0*Ns%RU^?B z;C2`~uyM1Tk-?kk?h|k9z26XlSx^pgW0vfpGf9dWkuK0Io-=_dVfi?ZBaE`PnCa=_ zmhB$|m=0m0J6rcIx+ptt!j2PZ9u+-Wq6c`0ff$OwLl$^kgBX7vz{3bwsDTuaz`_=I zXoI)~?la%)k~6b+X6am(W)#+gh3SCPA&9gIoL+%ZFbG5jjO~CkB8bchoMC~}Fi32D zpZH}L9hrSIDL*IDJcEwtkwSrIOc0Yiuv!3Exd39;1)iOOWpEG^J@A46c+~)6b#b4$ zW|w@Koipo+WNCk%Q%Cd+Az(=qgqjps;R?LC1+hv5UQGfo6hNv>ffumAt6UJP;rqlf zyXeWozfGIv#LK}f&tnXNU|v)NTX1FbleLK;j?O^nY*R@ zY9z_EODuot__7E3g^_;+&vqp+3^njXUdYY^TvISl#;w*ar&G01C2LJl_3(P6D<&E} zto&%F?rIoGduuNggDY(hxw=)_Hd_KmwxrA1Rc!Kl z&K|3icJ8jfl(IvcMR;bJb$cM3K|p(wFpFv?IA-+@D@k2W;Lx592uU8eB3?zbhY?M+ zAr~poo_%l;u1A{g&b_dU9%~P52R@dig|Hb>Du;(K6vI_0L3!}Y(IUi^5Pou?N(DEM ze0hJ5+-JVoC1az)EG=Z`9;IHNTj=9*pdW&4zN zZ0%%eo{oEz4y$OOsFj64o^B}<}IV#T;6BC*^k!?&NmXid|u8EfBi6{ z46V@8OimLtpyt(Wc?SiZEC!47YK`86b~_g6+{x#NMzDNn)K#cufr^&tsyZ^N&P#vL z?I5npKth{klrM$#zC{GzE%c7Z$BAEu6OBzPRKIQP+9=#Ram&wc{Oa*`TD4hYB0ViB z*JogOn>JHr&@slis^q#Z?`K?>K;IVyFwO$)G{qDG$y(CXtw(%4;|U*$FAx|N)`XvB z&?|3Je$t^8Zj6+cH6WF5Xe=o!z{!7Z&UkAZsh~^>$y7}hX=#x_i()6CUYZQDqsRP1 z^A+HBkoaX)0juSgBEG))8w5|dP&_*4TcQJL53%Sc`ECc5tyaZo2a_tc`P*$R78 z)&7<%nA$ouH|B{q2cB@G__n|pTP;@aHN_;mwS=6t;t&87BP?p#5|c2Bz!HCwEN}_A z9R=|i-?SROE57-@z!M%6pF&!#R-4utxG8Hk}xv!5|oPi&2t z!-6NISTzyQ_CW+Xlrq6BRg+aIt!PS}upoIL*;T-5dQrt!_{N(8Pq=Y-Qa%!O3l*Lg zNtrIr=6a9-ri7)0JdQ9*98!O(DW9{)hOe0dVHW;+z%%<5OI^R|ZHX#sr^D3*`Yoag z2{U+~bVxpLm(?fyV9;2Le-_e3$hq;*FD5l&S{WSKXu5zhT^@Bo8;ay*l9qtQpT%O4 z<|@G13Z52`P%)a+j4Qi#s^Em)ccPmLW|h`@TWfhpo;E1I+T$5ebSZzovTE=S>FZzn z`S!Z>ud@~fu;B*4NXSPl2d}@reD~?)Pk+IWNu_{m`Si&ia%0Cf6v*>AY(Y(#gkMrKH14*B!zOTohKjSgT!a z<#9w`zM^qZ29k0p+HcFgd|VC}SgXRe^v`Ymu-3f0t)Z$vPMxu*Hr2m2SM=T=p6BJ}J zmkV)e`IjNgC339(>$v(}W++rHL#v(V;_>fq$Ioy5C#8P_cFi5ev+4?hLIg26GdGiP zO&4jpd%22!cXAM8&U`2`uoy>xXR})5NB2CUFjQ07#E0%gVI9DB0T9di-LjtF!uTl!(RW{qsT*CKw&@*5HVq?a z*GVuoDh(AFtwJujB#p6AXu%{YuW<}fYzaX*Z6qcnwA3Mj zF_v^DLYCWv?r4i7k7C7ET4an-m~sSUnR-x0tVz=_g$OO}mF9cO+BTYY-%8??@f~It z->upp;dP=pW{Vpf?QARKUHj7}w3D4?Pb=uDh}uIM3NVt?btlb~yUwPBJj<7VxMF_qIS6Vh*Xer5%C|mW z6w{M(zHlTVLFV1V4a6!CpVqgGMly1r*W3a};#PbW-;TQg1_fQibhovC#b@yO;{56Z z@fpQ0v!M^QV}tbN{|`3uiA(xZE>-D-|5ojPvQhZ2*!-Cd-+y_P4YCZS{7HS3M4%$k z*JTn7sl+X%SgB`}n8a^TisTL@V|FPyaVIKKi$?r-MoS;kIxnZytSIN?vbei*^iJ`+ zHb#kTg$jV8qSdf9dKr}XF*(c&g|xc$?U99)-qXBs?E`bryU)_d?|b`#4vM<*OaRh< zBoOcN^#PIU_OY1x`-TU@i$(b-=g%8$&$ZfjZPFdroZgM+=s$QqXo@}WX5Txde3v;l z#m4`7?rdts^Y0)a9#sv`sufR~K>StAn)T>-su=ex36J{Kv`53B_QyPw`Gr4P()AFJ zA?+@Rcf~{D_plq#b~d?&FzSW$oaNLkvei83!rDx}bpWcXWUCuiGbcVY?sDZ9Mac{< zm##dS`l2e~X& zPAPd6%DWXnKo~^f`LW)tcMTF92!)P7] ({7*15}:\r-1) -- ({7*15}:\r-0.2); diff --git a/main.tex b/main.tex index db9c3e539fba76dbbc015bc58dff1d281a4a9196..7cc98f933bcf8334b4cfe2aff668004314d96c9c 100644 --- a/main.tex +++ b/main.tex @@ -426,14 +426,26 @@ we can do the same with the second term and this proves the claim. where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$. \newpage -\subsection{Proving the strong cancellation claim} -It is useful to introduce some new notation. Note that an \emph{event} is a subset of all possible paths of the Markov Chain. +\section{Proving the strong cancellation claim} +It is useful to introduce some new notation. We will consider variations of the Markov Chains: +\begin{itemize} + \item $\P^{(n)}$ refers to the original process on the length-$n$ cycle. + \item $\P^{[a,b]}$ or $\P^{[n]}$ refers to a similar Markov Chain but on a finite chain ($[a,b]$ or $[1,n]$). +\end{itemize} +The process on the finite chain has the following modification at the boundary: if a boundary site is resampled, it can not resample one of its neighbors so it ignores it and only draws two new bits. + +%Note that an \emph{event} is a subset of all possible paths of the Markov Chain. \begin{definition}[Events conditioned on starting state] \label{def:conditionedevents} For any state $b\in\{0,1\}^n$, define $\textsc{start}(b)$ as the event that the starting state of the chain is the state $b$. For any event $A$, define \begin{align*} \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \textsc{start}(b)) %\\ %R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \textsc{start}(b)) \end{align*} + Furthermore, for the Markov Chain on the finite chain, define + \begin{align*} + \P^{[n]}_{\partial=1}(A) &= \P^{[n]}(A \;|\; \text{boundary is initialized to }1) + \end{align*} + where the boundary of $[n]$ is site $1$ and site $n$, and the boundary of $[a,b]$ are $a$ and $b$. \end{definition} %Note that we have $\P^{(n)}(\textsc{start}(b)) = (1-p)^{|b|}p^{n-|b|}$ by definition of our Markov Chain. \begin{definition}[Vertex visiting event] \label{def:visitingResamplings} @@ -557,79 +569,26 @@ The lemma says that conditioned on $v$ and $w$ not being crossed, the two halves %Dividing by $\P^{(n)}_b(\mathrm{NZ}_{(v,w)},A_1,A_2)$ and using the first equality gives the desired result. \end{proof} -\begin{comment} -TEST: Although a proof of claim \ref{claim:expectationsum} was already given, I'm trying to prove it in an alternate way using claim \ref{claim:eventindependence}. - -~ - -Assume that $b_1$ ranges up to site $0$, the gap ranges from sites $1,...,k$ and $b_2$ ranges from site $k+1$ and onwards. For $j=1,...,k$ define the ``partial-zeros'' event $\mathrm{PZ}_j = \mathrm{Z}_1 \cap \mathrm{Z}_2 \cap ... \cap \mathrm{Z}_{j-1} \cap \mathrm{NZ}_j$ i.e. the first $j-1$ sites of the gap become zero and site $j$ does not become zero. Also define the ``all-zeros'' event $\mathrm{AZ} = \mathrm{Z}_1 \cap ... \cap \mathrm{Z}_k$, where all sites of the gap become zero. Note that these events partition the space, so we have for all $b$ that $\sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) = 1 - \mathbb{P}_b(\mathrm{AZ}) = 1 - \mathcal{O}(p^k)$. - -~ - -Furthermore, if site $j$ becomes zero when starting from $b_1$ it means all sites to the left of $j$ become zero as well. Similarly, from $b_2$ it implies all the sites to the right of $j$ become zero. -Because of that, we have -\begin{align*} - \mathbb{P}_{b_1}(\mathrm{PZ}_j) &= \mathbb{P}_{b_1}(\mathrm{Z}_{j-1} \cap \mathrm{NZ}_j) = \mathcal{O}(p^{j-1}) \\ - \mathbb{P}_{b_2}(\mathrm{NZ}_j) &= 1 - \mathbb{P}_{b_2}(\mathrm{Z}_j) = 1 - \mathcal{O}(p^{k-j+1}) -\end{align*} -Following the proof of claim \ref{claim:eventindependence} we also have -\begin{align*} - \mathbb{P}_b(\mathrm{PZ}_{j}) - &= - \mathbb{P}_{b_1}(\mathrm{PZ}_{j}) - \; \cdot \; - \mathbb{P}_{b_2}(\mathrm{NZ}_{j}) \\ - R_{b,\mathrm{PZ}_{j}} - &= - R_{b_1,\mathrm{PZ}_{j}} - \; + \; - R_{b_2,\mathrm{NZ}_{j}} -\end{align*} - - -Now observe that -\begin{align*} - R_b &= \sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) R_{b,\mathrm{PZ}_j} + \mathbb{P}_b(\mathrm{AZ}) R_{b,\mathrm{AZ}} \\ - &= \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{NZ}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} - + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j} - + \mathcal{O}(p^k) \\ - &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} - - \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{Z}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} - + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j} - + \mathcal{O}(p^k) \\ - &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} - + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j} - + \mathcal{O}(p^k) \\ - &= R_{b_1} - + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j} - + \mathcal{O}(p^k) \\ - &\overset{???}{=} R_{b_1} + R_{b_2} + \mathcal{O}(p^k) -\end{align*} -\end{comment} - -Consider the chain (instead of the cycle) for simplicity with vertices identified by $\mathbb{Z}$. \begin{definition}[Starting state dependent probability distribution.] Let $I\subset\mathbb{Z}$ be a finite set of vertices. - Let $b_I$ be the initial state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. Define $P_I(A)=P_{b_I}(A)$ where the latter is defined in Definition \ref{def:conditionedevents}, i.e. the probability of seeing a resample sequence from $A$ when the whole procedure started in state $b_I$. + Let $b_I$ be the state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. Define $\P^{(n)}_I(A)=\P^{(n)}_{b_I}(A)$ which is defined in Definition \ref{def:conditionedevents}. \end{definition} -New: - -\begin{lemma}[Conditional independence] \label{lemma:eventindependenceNew} - Let $i\neq j\in [n]$, and let $A_1$ be any event that depends only on the sites $[i,j]$ (meaning the initialization and resamples) and similarly $A_2$ an event that depends only on the sites $[j,i]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled at least $k$ times'' for an $s$ on the correct interval). Then we have +\begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNew} + Let $v\neq w\in [n]$, and let $A_1$ be any event that depends only on the sites $[v,w]$ (meaning the initialization and resamples) and similarly $A_2$ an event that depends only on the sites $[w,v]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled at least $k$ times'' for an $s$ in the correct interval). Then we have \begin{align*} - \P^{(n)}(\mathrm{NZ}^{(i,j)}\cap A_1\cap A_2) + \P^{(n)}(\mathrm{NZ}^{(v,w)}\cap A_1\cap A_2) &= - \P^{[i,j]}(\mathrm{NZ}^{(i,j)}\cap A_1) + \P^{[v,w]}(\mathrm{NZ}^{(v,w)}\cap A_1) \; \cdot \; - \P^{[j,i]}(\mathrm{NZ}^{(i,j)}\cap A_2)/(1-p)^2 \\ - \P^{(n)}(A_1\cap A_2|\mathrm{NZ}^{(i,j)}) + \P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap A_2)/(1-p)^2 \\ + \P^{(n)}(A_1\cap A_2|\mathrm{NZ}^{(v,w)}) &= - \P^{[i,j]}(A_1|\mathrm{NZ}^{(i,j)}) + \P^{[v,w]}(A_1|\mathrm{NZ}^{(v,w)}) \; \cdot \; - \P^{[j,i]}(A_2|\mathrm{NZ}^{(i,j)}) + \P^{[w,v]}(A_2|\mathrm{NZ}^{(v,w)}) \end{align*} - up to any order in $p$. + where there is no longer a condition on the starting state. \end{lemma} The intuition of the following lemma is that the far right can only affect the zero vertex if there is an interaction chain forming, which means that every vertex should get resampled to $0$ at least once.