Sharpness
Bernoulli percolation的sharpness。有很多种证明，再加上直接推论，这里写个笔记。
几张图，找到关于cluster的一些直观的感觉。
Bernoulli percolation的sharpness是一个很基本的结论（可以说两大基本结论就是：infinite cluster的唯一性和相变的sharpness）。其表述如下：
在subcritical phase，“远程关联”指数衰减，即存在c(p)使得
在supercritical phase，\theta(p)突变性上升，即存在c使得
也就是说有一个线性的mean-field lower bound。这里没有说这个c(>0)具体是多少。其实有更加具体的结论，就是：
画出图像来大概是这样的：
可以看出还是个相当好的bound。
为什么把这个定理叫做sharpness呢？可以这样理解。
在subcritical phase，满足Ising模型中所谓的EXP性质，远程关联指数衰减，cluster大小限定在比较小。
在subcritical phase到supercritical phase的过渡中，越过p_c，有一个dramatic的突变，\theta(p)不是平滑地上升到非0，而是不可微地上去的。0与无穷远点的关联，从0突然蹦上去。（当然这一点是不是连续对于3，4，5维还不知道，只是人们猜测是连续的）至少是不可微的，所以叫sharpness。
这个定理同时刻画了subcritical和supercritical，非常有用。
从物理的角度看：我们猜想\theta(p)是连续的，于是percolation没有零阶的phase transition。但是这个sharpness告诉我们，有一阶的phase transition，导数不连续。
EXP的确成立。会不会比EXP衰减地更加快？不可能，因为
所以衰减就是指数速度。当然具体的c是不是渐进的一个值，还是只有上下界，那我还不知道了。
这个定理的证明很多。下面给出几个。
在此之前，首先插一条要用到的公式。假设f是依赖于有限边的函数，则f的期望值随p的导数是可以表示出来的。因为期望可以直接写出来，然后求导就得到
这个公式还是相当简洁的。它可以用来推Russo公式，虽然Russo公式直接用increasing coupling可以直接证明出来。
第一个证明非常神奇。它用的是理论计算机科学中的随机化算法。
首先引入决策树的概念。它跟日常生活中所说的决策树其实是一回事。Formally，它可以看成想要从一个长度为n的01串（比如010001001011110100101001）中提取出一个信息（“序列是否满足某个性质”）。它包含「读取规则」（相当于说这个树在每一步如何分岔）和「停止规则」（相当于判断是否已经有了结论，不用再继续分岔下去）。每一步会读取序列中的一个分量，然后根据读取的值选择下一次读取哪个坐标；一直读取到停止规则被满足，这个停止规则可以用一个Boolean function f来表示，如果f不依赖于剩下未被读取的分量，则停止。比如说，f表示indicator function 1_{1的数目超过3个}，那么只要读取到3个，就可以停下来了，接下来读取的值不影响f了。
更加形式的定义是这样的：首先读取e_1坐标，接下来的读取按照「读取规则」来决定：
而停止时间记为\tau，跟停时一样（它自己当然就是个停时）。
这样一个决策树记为（T,f）。经典的算法味道。
然后引入OSSS不等式。
在随机化算法中，OSSS不等式指的是这样一类不等式：对一个决策树(T,f)，f（一个indicator function）的方差与计算复杂度的关系。方差越大，复杂度越大。大致可以这样理解：如果停止规则比较含混，计算时间就要变长？具体的式子是这样的：对于Bernoulli percolation的有限条边，f只依赖于这些边，另外有一个算法T，则
其中
刻画了算法的复杂度，越复杂，越有可能在结束前经过e，概率越大。
OSSS不等式的证明略去。
我们接下来看一看，把OSSS不等式用在渗流里面，能不能在sharpness上做出一点进展。
首先约定一些记号：
（刻画远程关联性）
\theta_n(p)是个多项式函数，其极限就是我们希望的\theta(p)（所以它是右连续的；这说远了）。
【这里多嘴一句：\theta(p)另外一种理解方式就是「唯一存在的无限大cluster C的密度」】
我们的目的是建立这样一个微分不等式：
很神奇的是，如果这样一个微分不等式成立，那么f_n的极限函数就满足sharpness，即存在一个x*，对于小于它的x，f_n(x)随n指数衰减；而对于大于它的x，f(x)>=x-x*。这就是我们期待的性质（sharpness）。
这个分析结论的证明就略去了。但是我们还是要做点评述。这个微分不等式到底是咋回事儿？它是有点来头的，来自abstract sharp threshold theorems，还有一系列类似的结果。
为了达到这个目的，我们看看怎么构造算法(T,f)。
我们想要决定的事件是0与\partial\Lambda_n相连。用什么算法可以鉴定这一点呢？最naive的算法就是一条一条边算过去。但我们发现这个算法得到的bound太弱了，无法得到上面的不等式。下面构造复杂度更低的算法。目标是让\delta尽可能小，即算法停止之前尽可能不要reveal到e这条边。
构造方法是这样的。先uniformly在1-n中选出一个k，然后分别向内和向外做floodfill算法。这样对于每个k，都显然有
对于n个k取平均之后，结合OSSS不等式就得到
这个微分不等式就足以证明sharpness。
第二个证明则是老老实实从渗流的图像出发做，没有什么花里胡哨的。
要证明的有两件事情：一是subcritical phase的\theta_n指数衰减，二是supercritical phase \theta_n'(p)>=c(一个uniform的bound)。前者并不难办，因为是指数衰减，大概用归纳盒子套盒子就可以推出来。后者的话，就必须要研究\theta_n'(p)（所以两种sharpness的证明都归结到微分不等式上面）。
引入这样一个量：
它微妙的地方在于，如果存在S使得这个量小于1，则指数衰减成立；如果这个量恒大于1，则一定是supercritical phase。
首先是指数衰减。直接上FKG即可，不多说。
然后是mean-field lower bound。Russo公式直截了当地给出了：
其中S为\Lambda_n内不与边界相连的点。如果\phi恒大于1，则\theta_n(p)满足mean-field lower bound，于是这一定是supercritical phase；反过来，我们又返回去证明了对于subcritical phase，存在S使得这个量小于1，这就补完了指数衰减的证明。所以刚刚好就有sharpness。这个证明直截了当。
Sharpness的一个直接推论就是二维渗流的相变点1/2，这个结论也叫做Kesten定理。
Kesten定理基于以下observation：p=1/2时，[0,n]*[0,n-1]左右互通的概率为1/2。这是个很显然的结论，它来自二维的自对偶性质。
这个observation非常微妙：它是一个scaling-invariant的结论，跟n无关。设想把一个（近似的）方块放大到非常大，左右距离非常远，左右互通的概率仍然为1/2，总是藕断丝连地黏着。我们马后炮地说，当然知道这是critical phase的特性，不只是scaling-invariant的，而且是conformal-invariant的。RSW理论说的也是同一回事。不过这扯得有点远。我们还是回到Kesten定理。在subcritical phase，[0,n]*[0,n-1]左右互通的概率应该会随着n增大趋向于0，因为cluster大小都是有限的，而且都局限在比较小的范围里（sharpness的前半部分）；在supercritical phase，[0,n]*[0,n-1]左右互通的概率应该会随着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)与右侧相连)
<=nP(0<->\Lambda_n)
<ne^{-cn}->0。这就证完了。
【第二个论断】在supercritical phase，P_p(H_n)->1。这个证明就不那么显然。利用无穷大cluster C的存在性来搞。
\Lambda_n很大时，可以与C相交（概率->1，这个不用多想，直接用概率的连续性就可以看出来的）。但是仅仅相交并不能说左右相连，所以还要做一些技术上的工作。关键在于square-root-trick。
我们知道\Lambda_n大概率与C相交。把它套在一个更大的方块\Lambda_m里面，看看这个交出去的cluster能不能把\Lambda_m的左右连起来？
根据square-root-trick的思想，\Lambda_n同时与\Lambda_m的左右连接的概率接近于1（具体式子不写了，但是square-root-trick的思想一定要记住：increasing events的并概率接近于1，则其中最大的那个概率也接近于1）。
接下来的问题是：这两个cluster是不是连在一起？不连在一起这个事件在m很大时接近于说有两个infinite cluster，概率接近0（严格不去写了）。结论就是，P_p(H_n)->1。
总的来说，渗流的证明经常要用这样的几何直觉、操作和不等式估计。
综上，我们就证明了Kesten定理。其实非常简单。
对于更高的维度，对偶不再有了，所以用上面的办法求critical point就无能为力了。它们迄今还没有解析的形式，只有数值结果：
这些结果在wikipedia的Percolation threshold页面可以找到。想想大概并不是能轻轻松松做出来的数值结果。在二维还可以偶尔找到一些别的精确解。高维就根本找不到了。
再顺带一提。Sharpness用来证明Kesten定理有点大材小用了。它只用上了一半，而且只用上了d=2。
我们回到之前那个微妙的“藕断丝连”结论：p=1/2时，[0,n]*[0,n-1]左右互通的概率为1/2。它反映了critical percolation的sclaing-invariant。我们想从中挖出更多的东西来，而不只是Kesten定理。这方面的研究叫做RSW理论。
想一想[a,b]*[c,d]左右互联的概率。它估计不再刚好是一个常数了，不过根据scaling invariant性质，它会在n->\infty的时候收敛到一个(0,1)之内的常数。我们还可以想，对于有限的n，它会uniformly bounded in [c,1-c]，不会跑去0，也不会跑去1。写出来就是：
证明是这样的。对于“更窄”的左右相连，那当然不用说。对于“更宽”的左右相交，按照这样的“重叠”方式把事件做放缩即可：
不过，如果要让这个放缩成立，必须要有一个k>1的uniform bound P(H(kn,n))，而这点我们还是缺失的。好在RSW-type theorem中有一系列结论，比如说：
利用它就可以补完前面的证明了。这个证明先不管。
我们在sharpness中知道了，\theta_n在subcritical phase是（恰好）指数衰减的，而在supercritical phase会趋近于一个正常数。那么在critical phase会怎样呢？首先我们知道二维相变的连续性，所以\theta_n一定是衰减到0的；但是它肯定衰减地很慢，比任何指数衰减（短距）都慢。实际上结果是，它是幂次衰减的（长程）。很微妙，在指数衰减和不衰减之间，临界状态是幂次衰减。
具体来说，
证明很简单，利用“藕断丝连”。对于下界，联系以下[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定理即可。
综上，幂次衰减获证。
实际上具体的衰减速度也是知道的：
这属于恰好在临界点能算出的具体值。
关于二维的critical percolation，其实还有很多别的要说的事情。比如说，
这个临界指数也是算得出来的。
另外一个是Cardy公式，它是我们喜闻乐见的“能算出精确结果”的一个玩意儿。（当然，也仅限于critical phase的特殊性）（回想我们的工具箱里面，大部分是不等式估计，能做出精确结果的也会有increasing coupling了）。考虑critical percolation的“scaling limit”，即趋近于一个“连续”的percolation（只有critical的时候有这种事情；subcritical phase, for example, 不是scaling invariant的，随着尺度变大，远大于特征长度，就看不到cluster了）。考虑二维平面上这样一个区域
两条红色区域相连的概率为
其中u为交比
这个公式是从conformal invariance推出来的。
不妨试验一下这个结论对不对。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，毕竟它跟正方形差不多，概率应该不会离0.5很远。
对于比较窄的方块，概率就会比较小了。比如说10*1的，算出来极限的概率为0.1217。
画一下n*1的曲线看看。
刚好经过(1,0.5)。衰减看起来不是很快。
另一个推论是关于cluster的大小。
之前我们知道“长程关联”的指数衰减：
它看起来是说，0所在的cluster C的大小也是指数衰减的。但是直接推过来不可行，因为sharpness只能直接得到
这是一个亚指数的衰减。但是我们想要的结论是
这个结论比sharpness要更强一点，有一个gap，所以需要额外的手段去证明。这里用coarse-graining方法。
想法是这样的。在subcritical phase，关联长度是有限的。我们在原先的尺度上没法看出C很大会有什么毛病，因为此时靠得近的点之间关联还挺大。但是如果离远了看，尺度远大于关联长度，则邻近的点关联也变得很小，此时一个巨大的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）
关于关联长度。这时候我们终于有一点具体的“解析”的“数字”了？之前我们只知道指数衰减，但不知道具体衰减多快。现在想要研究的就是衰减多快。这个概念也很物理啊，Ising模型之类的都有，也很直观，相当于对系统特征尺度的一个刻画。如果这个特征尺度是有限的，当然不存在scaling-invariant了。Critical phase的特征尺度就是无限大，所以在任意放缩下看起来没有区别。
关联长度，顾名思义，刻画的是两个点之间的关联。它定义为
左边的n表示(n,0,...,0)这个点。
问题来了，这个1/n ln P(0<->n)的极限存在吗？实际上用FKG+Fekete就可以证明，读者应该一眼就能看出来。
这里有个数值模拟的结果。
随着p接近临界点，关联长度逐渐发散。
回顾以下到目前为止的percolation。在toolbox里面，我们有：两个方向的FKG不等式和BK不等式，常用的square-root trick，一个巨大的increasing coupling measure，ergodicity，以及对于二维特有的duality。在基本性质上，分为non-critical phase和critical phase。对于前者，uniqueness和sharpness是关键，另外连续性是increasing coupling的简单推论；而对于后者，基于scaling-invariant甚至conformal invariant可以做出很多微妙的结果。
题图こぼれる薄香色の息吹（80056132）by Atha（アサ）。
