Sharpness
Bernoulli percolation的sharpness。有很多種證明，再加上直接推論，這里寫個筆記。
幾張圖，找到關(guān)于cluster的一些直觀的感覺。
Bernoulli percolation的sharpness是一個很基本的結(jié)論（可以說兩大基本結(jié)論就是：infinite cluster的唯一性和相變的sharpness）。其表述如下：
在subcritical phase，“遠程關(guān)聯(lián)”指數(shù)衰減，即存在c(p)使得
在supercritical phase，\theta(p)突變性上升，即存在c使得
也就是說有一個線性的mean-field lower bound。這里沒有說這個c(>0)具體是多少。其實有更加具體的結(jié)論，就是：
畫出圖像來大概是這樣的：
可以看出還是個相當好的bound。
為什么把這個定理叫做sharpness呢？可以這樣理解。
在subcritical phase，滿足Ising模型中所謂的EXP性質(zhì)，遠程關(guān)聯(lián)指數(shù)衰減，cluster大小限定在比較小。
在subcritical phase到supercritical phase的過渡中，越過p_c，有一個dramatic的突變，\theta(p)不是平滑地上升到非0，而是不可微地上去的。0與無窮遠點的關(guān)聯(lián)，從0突然蹦上去。（當然這一點是不是連續(xù)對于3，4，5維還不知道，只是人們猜測是連續(xù)的）至少是不可微的，所以叫sharpness。
這個定理同時刻畫了subcritical和supercritical，非常有用。
從物理的角度看：我們猜想\theta(p)是連續(xù)的，于是percolation沒有零階的phase transition。但是這個sharpness告訴我們，有一階的phase transition，導數(shù)不連續(xù)。
EXP的確成立。會不會比EXP衰減地更加快？不可能，因為
所以衰減就是指數(shù)速度。當然具體的c是不是漸進的一個值，還是只有上下界，那我還不知道了。
這個定理的證明很多。下面給出幾個。
在此之前，首先插一條要用到的公式。假設(shè)f是依賴于有限邊的函數(shù)，則f的期望值隨p的導數(shù)是可以表示出來的。因為期望可以直接寫出來，然后求導就得到
這個公式還是相當簡潔的。它可以用來推Russo公式，雖然Russo公式直接用increasing coupling可以直接證明出來。
第一個證明非常神奇。它用的是理論計算機科學中的隨機化算法。
首先引入決策樹的概念。它跟日常生活中所說的決策樹其實是一回事。Formally，它可以看成想要從一個長度為n的01串（比如010001001011110100101001）中提取出一個信息（“序列是否滿足某個性質(zhì)”）。它包含「讀取規(guī)則」（相當于說這個樹在每一步如何分岔）和「停止規(guī)則」（相當于判斷是否已經(jīng)有了結(jié)論，不用再繼續(xù)分岔下去）。每一步會讀取序列中的一個分量，然后根據(jù)讀取的值選擇下一次讀取哪個坐標；一直讀取到停止規(guī)則被滿足，這個停止規(guī)則可以用一個Boolean function f來表示，如果f不依賴于剩下未被讀取的分量，則停止。比如說，f表示indicator function 1_{1的數(shù)目超過3個}，那么只要讀取到3個，就可以停下來了，接下來讀取的值不影響f了。
更加形式的定義是這樣的：首先讀取e_1坐標，接下來的讀取按照「讀取規(guī)則」來決定：
而停止時間記為\tau，跟停時一樣（它自己當然就是個停時）。
這樣一個決策樹記為（T,f）。經(jīng)典的算法味道。
然后引入OSSS不等式。
在隨機化算法中，OSSS不等式指的是這樣一類不等式：對一個決策樹(T,f)，f（一個indicator function）的方差與計算復雜度的關(guān)系。方差越大，復雜度越大。大致可以這樣理解：如果停止規(guī)則比較含混，計算時間就要變長？具體的式子是這樣的：對于Bernoulli percolation的有限條邊，f只依賴于這些邊，另外有一個算法T，則
其中
刻畫了算法的復雜度，越復雜，越有可能在結(jié)束前經(jīng)過e，概率越大。
OSSS不等式的證明略去。
我們接下來看一看，把OSSS不等式用在滲流里面，能不能在sharpness上做出一點進展。
首先約定一些記號：
（刻畫遠程關(guān)聯(lián)性）
\theta_n(p)是個多項式函數(shù)，其極限就是我們希望的\theta(p)（所以它是右連續(xù)的；這說遠了）。
【這里多嘴一句：\theta(p)另外一種理解方式就是「唯一存在的無限大cluster C的密度」】
我們的目的是建立這樣一個微分不等式：
很神奇的是，如果這樣一個微分不等式成立，那么f_n的極限函數(shù)就滿足sharpness，即存在一個x*，對于小于它的x，f_n(x)隨n指數(shù)衰減；而對于大于它的x，f(x)>=x-x*。這就是我們期待的性質(zhì)（sharpness）。
這個分析結(jié)論的證明就略去了。但是我們還是要做點評述。這個微分不等式到底是咋回事兒？它是有點來頭的，來自abstract sharp threshold theorems，還有一系列類似的結(jié)果。
為了達到這個目的，我們看看怎么構(gòu)造算法(T,f)。
我們想要決定的事件是0與\partial\Lambda_n相連。用什么算法可以鑒定這一點呢？最naive的算法就是一條一條邊算過去。但我們發(fā)現(xiàn)這個算法得到的bound太弱了，無法得到上面的不等式。下面構(gòu)造復雜度更低的算法。目標是讓\delta盡可能小，即算法停止之前盡可能不要reveal到e這條邊。
構(gòu)造方法是這樣的。先uniformly在1-n中選出一個k，然后分別向內(nèi)和向外做floodfill算法。這樣對于每個k，都顯然有
對于n個k取平均之后，結(jié)合OSSS不等式就得到
這個微分不等式就足以證明sharpness。
第二個證明則是老老實實從滲流的圖像出發(fā)做，沒有什么花里胡哨的。
要證明的有兩件事情：一是subcritical phase的\theta_n指數(shù)衰減，二是supercritical phase \theta_n'(p)>=c(一個uniform的bound)。前者并不難辦，因為是指數(shù)衰減，大概用歸納盒子套盒子就可以推出來。后者的話，就必須要研究\theta_n'(p)（所以兩種sharpness的證明都歸結(jié)到微分不等式上面）。
引入這樣一個量：
它微妙的地方在于，如果存在S使得這個量小于1，則指數(shù)衰減成立；如果這個量恒大于1，則一定是supercritical phase。
首先是指數(shù)衰減。直接上FKG即可，不多說。
然后是mean-field lower bound。Russo公式直截了當?shù)亟o出了：
其中S為\Lambda_n內(nèi)不與邊界相連的點。如果\phi恒大于1，則\theta_n(p)滿足mean-field lower bound，于是這一定是supercritical phase；反過來，我們又返回去證明了對于subcritical phase，存在S使得這個量小于1，這就補完了指數(shù)衰減的證明。所以剛剛好就有sharpness。這個證明直截了當。
Sharpness的一個直接推論就是二維滲流的相變點1/2，這個結(jié)論也叫做Kesten定理。
Kesten定理基于以下observation：p=1/2時，[0,n]*[0,n-1]左右互通的概率為1/2。這是個很顯然的結(jié)論，它來自二維的自對偶性質(zhì)。
這個observation非常微妙：它是一個scaling-invariant的結(jié)論，跟n無關(guān)。設(shè)想把一個（近似的）方塊放大到非常大，左右距離非常遠，左右互通的概率仍然為1/2，總是藕斷絲連地黏著。我們馬后炮地說，當然知道這是critical phase的特性，不只是scaling-invariant的，而且是conformal-invariant的。RSW理論說的也是同一回事。不過這扯得有點遠。我們還是回到Kesten定理。在subcritical phase，[0,n]*[0,n-1]左右互通的概率應(yīng)該會隨著n增大趨向于0，因為cluster大小都是有限的，而且都局限在比較小的范圍里（sharpness的前半部分）；在supercritical phase，[0,n]*[0,n-1]左右互通的概率應(yīng)該會隨著n增大趨向于1，因為有一個無限大的cluster，這個方塊遲早要跟它交在一起。只有critical phase【微妙地】恰恰夾在二者之間，概率保持為1/2，不會趨于0也不會趨于1。這就強烈地暗示了p=1/2是critical point。
直白的說法：subcritical phase（在大尺度上）是“完全斷絕”，supercritical phase（在大尺度上）是“完全連接”，而critical phase則是“藕斷絲連”。
這是兩個直觀的論斷，我們想想辦法能不能嚴格化。[0,n]*[0,n-1]左右互通這個事件記為H_n。
【第一個論斷】在subcritical phase，P_p(H_n)->0。簡單做一個估計就知道了：
P_p(H_n)<=nP((0,k)與右側(cè)相連)
<=nP(0<->\Lambda_n)
<ne^{-cn}->0。這就證完了。
【第二個論斷】在supercritical phase，P_p(H_n)->1。這個證明就不那么顯然。利用無窮大cluster C的存在性來搞。
\Lambda_n很大時，可以與C相交（概率->1，這個不用多想，直接用概率的連續(xù)性就可以看出來的）。但是僅僅相交并不能說左右相連，所以還要做一些技術(shù)上的工作。關(guān)鍵在于square-root-trick。
我們知道\Lambda_n大概率與C相交。把它套在一個更大的方塊\Lambda_m里面，看看這個交出去的cluster能不能把\Lambda_m的左右連起來？
根據(jù)square-root-trick的思想，\Lambda_n同時與\Lambda_m的左右連接的概率接近于1（具體式子不寫了，但是square-root-trick的思想一定要記?。篿ncreasing events的并概率接近于1，則其中最大的那個概率也接近于1）。
接下來的問題是：這兩個cluster是不是連在一起？不連在一起這個事件在m很大時接近于說有兩個infinite cluster，概率接近0（嚴格不去寫了）。結(jié)論就是，P_p(H_n)->1。
總的來說，滲流的證明經(jīng)常要用這樣的幾何直覺、操作和不等式估計。
綜上，我們就證明了Kesten定理。其實非常簡單。
對于更高的維度，對偶不再有了，所以用上面的辦法求critical point就無能為力了。它們迄今還沒有解析的形式，只有數(shù)值結(jié)果：
這些結(jié)果在wikipedia的Percolation threshold頁面可以找到。想想大概并不是能輕輕松松做出來的數(shù)值結(jié)果。在二維還可以偶爾找到一些別的精確解。高維就根本找不到了。
再順帶一提。Sharpness用來證明Kesten定理有點大材小用了。它只用上了一半，而且只用上了d=2。
我們回到之前那個微妙的“藕斷絲連”結(jié)論：p=1/2時，[0,n]*[0,n-1]左右互通的概率為1/2。它反映了critical percolation的sclaing-invariant。我們想從中挖出更多的東西來，而不只是Kesten定理。這方面的研究叫做RSW理論。
想一想[a,b]*[c,d]左右互聯(lián)的概率。它估計不再剛好是一個常數(shù)了，不過根據(jù)scaling invariant性質(zhì)，它會在n->\infty的時候收斂到一個(0,1)之內(nèi)的常數(shù)。我們還可以想，對于有限的n，它會uniformly bounded in [c,1-c]，不會跑去0，也不會跑去1。寫出來就是：
證明是這樣的。對于“更窄”的左右相連，那當然不用說。對于“更寬”的左右相交，按照這樣的“重疊”方式把事件做放縮即可：
不過，如果要讓這個放縮成立，必須要有一個k>1的uniform bound P(H(kn,n))，而這點我們還是缺失的。好在RSW-type theorem中有一系列結(jié)論，比如說：
利用它就可以補完前面的證明了。這個證明先不管。
我們在sharpness中知道了，\theta_n在subcritical phase是（恰好）指數(shù)衰減的，而在supercritical phase會趨近于一個正常數(shù)。那么在critical phase會怎樣呢？首先我們知道二維相變的連續(xù)性，所以\theta_n一定是衰減到0的；但是它肯定衰減地很慢，比任何指數(shù)衰減（短距）都慢。實際上結(jié)果是，它是冪次衰減的（長程）。很微妙，在指數(shù)衰減和不衰減之間，臨界狀態(tài)是冪次衰減。
具體來說，
證明很簡單，利用“藕斷絲連”。對于下界，聯(lián)系以下[0,n]*[0,n-1]左右互通概率即可。對于上界，用“遞推”：
P_p(0與\partial\Lambda_{n^k}相連)<=P_p(0與\partial\Lambda_n相連)P_p(n與\partial\Lambda_{n^2}相連)...
然后畫四個長方形夾在兩個嵌套的方形中間，利用RSW定理即可。
綜上，冪次衰減獲證。
實際上具體的衰減速度也是知道的：
這屬于恰好在臨界點能算出的具體值。
關(guān)于二維的critical percolation，其實還有很多別的要說的事情。比如說，
這個臨界指數(shù)也是算得出來的。
另外一個是Cardy公式，它是我們喜聞樂見的“能算出精確結(jié)果”的一個玩意兒。（當然，也僅限于critical phase的特殊性）（回想我們的工具箱里面，大部分是不等式估計，能做出精確結(jié)果的也會有increasing coupling了）。考慮critical percolation的“scaling limit”，即趨近于一個“連續(xù)”的percolation（只有critical的時候有這種事情；subcritical phase, for example, 不是scaling invariant的，隨著尺度變大，遠大于特征長度，就看不到cluster了）?？紤]二維平面上這樣一個區(qū)域
兩條紅色區(qū)域相連的概率為
其中u為交比
這個公式是從conformal invariance推出來的。
不妨試驗一下這個結(jié)論對不對。Matlab代碼為：
z1=1;
z2=-1i;
z3=-1;
z4=1i;
u=(z4-z3)*(z2-z1)/((z3-z1)*(z4-z2));
3*u^(1/3)*hypergeom([1/3,2/3],4/3,u)*gamma(2/3)/gamma(1/3)^2
對于正方形的左右相連概率，算出來正好是0.5，跟RSW理論吻合。（其實直接由高斯原理/范德蒙恒等式推就行了）
對于H(3n,2n)，算出來為（n->\infty的極限）0.4053。RSW理論說，對于任意n，它都大于1/128。這當然是一個比較弱的bound，畢竟它跟正方形差不多，概率應(yīng)該不會離0.5很遠。
對于比較窄的方塊，概率就會比較小了。比如說10*1的，算出來極限的概率為0.1217。
畫一下n*1的曲線看看。
剛好經(jīng)過(1,0.5)。衰減看起來不是很快。
另一個推論是關(guān)于cluster的大小。
之前我們知道“長程關(guān)聯(lián)”的指數(shù)衰減：
它看起來是說，0所在的cluster C的大小也是指數(shù)衰減的。但是直接推過來不可行，因為sharpness只能直接得到
這是一個亞指數(shù)的衰減。但是我們想要的結(jié)論是
這個結(jié)論比sharpness要更強一點，有一個gap，所以需要額外的手段去證明。這里用coarse-graining方法。
想法是這樣的。在subcritical phase，關(guān)聯(lián)長度是有限的。我們在原先的尺度上沒法看出C很大會有什么毛病，因為此時靠得近的點之間關(guān)聯(lián)還挺大。但是如果離遠了看，尺度遠大于關(guān)聯(lián)長度，則鄰近的點關(guān)聯(lián)也變得很小，此時一個巨大的cluster是很矛盾的，矛盾于是乎暴露出來了，于是就能干活了。
所以，怎么“離遠了看”呢？做法是：把格點變成kZ^d（k需要蠻大的，之后再考慮），每個格點看成一個大小為k的“像素點”（自己畫出圖來看看），這樣就變成一個site percolation。問題是，怎么定義一個site是open還是closed？采取如下定義：\Lambda_k與\partial \Lambda_{2k}如果連通，則記這個site是open的。
然后我們摘下眼鏡，只看到了一個個大的像素點。此時一個巨大的cluster概率是很小的，簡單做一下估計就知道了：
P(|C|>n)
<=P(存在一個包含0的大小為[n/k^2]的cluster)
<=\sum_{對所有包含0的大小為[n/k^2]的animal?A}P(A上的所有site均為open)
<= C^{n/k^2}P(A上不相鄰的最多的點為open)
<= C^{n/k^2}P(\Lambda_k與\partial \Lambda_{2k}連通)^{n/D}
<=e^{-cn}（選取足夠大的k）
關(guān)于關(guān)聯(lián)長度。這時候我們終于有一點具體的“解析”的“數(shù)字”了？之前我們只知道指數(shù)衰減，但不知道具體衰減多快?，F(xiàn)在想要研究的就是衰減多快。這個概念也很物理啊，Ising模型之類的都有，也很直觀，相當于對系統(tǒng)特征尺度的一個刻畫。如果這個特征尺度是有限的，當然不存在scaling-invariant了。Critical phase的特征尺度就是無限大，所以在任意放縮下看起來沒有區(qū)別。
關(guān)聯(lián)長度，顧名思義，刻畫的是兩個點之間的關(guān)聯(lián)。它定義為
左邊的n表示(n,0,...,0)這個點。
問題來了，這個1/n ln P(0<->n)的極限存在嗎？實際上用FKG+Fekete就可以證明，讀者應(yīng)該一眼就能看出來。
這里有個數(shù)值模擬的結(jié)果。
隨著p接近臨界點，關(guān)聯(lián)長度逐漸發(fā)散。
回顧以下到目前為止的percolation。在toolbox里面，我們有：兩個方向的FKG不等式和BK不等式，常用的square-root trick，一個巨大的increasing coupling measure，ergodicity，以及對于二維特有的duality。在基本性質(zhì)上，分為non-critical phase和critical phase。對于前者，uniqueness和sharpness是關(guān)鍵，另外連續(xù)性是increasing coupling的簡單推論；而對于后者，基于scaling-invariant甚至conformal invariant可以做出很多微妙的結(jié)果。
題圖こぼれる薄香色の息吹（80056132）by?Atha（アサ）。
