目录

一，二叉树场景

1，求存在长度为n的路径的概率的递推式

2，根据递推式，用不动点法求极限

二，阿米巴的生存

三，网格图场景

1，问题背景

2，感性认知

---

原文链接：AMS :: Feature Column from the AMS

在一个无限大的图中，每条边都有p的概率是可通行的，有1-p的概率是不可通行的，问从起点出发存在无限长路径的概率。

一，二叉树场景

Let's begin with a simple example that illustrates some general principles. We will study percolation on the infinite binary tree, a portion of which is shown below.

  

在一个无限大的二叉树中，每条边都有p的概率是可通行的，有1-p的概率是不可通行的，问从根节点出发存在无限长路径的概率。

1，求存在长度为n的路径的概率的递推式

If p is the probability that each edge is open, we want to find θ(p), the probability that there is an infinite open path containing the root of the tree v0. We begin by letting Pn be the probability that there is an open path from v0 to a vertex n levels below. Notice that we have P0 = 1. Shown in red below is a path from v0 to a vertex three levels below.

This path moves through another vertex v1. The probability that an open path from v0 to a vertex n levels below passes through v1 is pPn-1, the probability p that the edge from v0 to v1 is open times the probability Pn-1 that a path from v1 to a vertex n - 1 levels below it is open. Therefore, the probability that there is no open path from v0 to a vertex n levels below passing through v1 is 1 - pPn-1.

Since any path from v0 to a vertex n levels below must pass through one of the children of v0, we find that the probability that there is not an open path from v0 to a vertex n levels below is  

至此，我们就得到递推式 

2，根据递推式，用不动点法求极限

If we define the function fp(x) = 1 - (1 - px)2, we have Pn = fp(Pn-1). The graph of fp is shown below in two different cases, depending on the derivative fp'(0) = 2p.

In the first case, 2p > 1 , we see that there is a fixed point

 

 

Here we see that the critical probability, pc = 1/2; above pc, θ(p) > 0 and we have percolation. Below the critical probability, θ(p) = 0 and there is no percolation.

结论就是上面的分段函数θ(p) ，p大于1/2时有概率θ(p) 存在无限长路径，p小于1/2时存在无限长路径的概率为0

This example is unusual in that it is difficult to compute the critical probability and θ(p) exactly for most combinatorial graphs. As we'll see toward the end of this article, however, it is thought that the specific form that θ(p) takes here shares features with that from other graphs.

二，阿米巴的生存

原文链接

在每一代的繁殖中，单个的阿米巴原虫有3/4的概率分裂成两个，有1/4的概率死亡（而不产生下一代）。初始时只有一个阿米巴原虫，求阿米巴原虫会无限繁殖下去的概率。

这个问题和Percolation问题的二叉树场景并不完全相同，但是非常相似。

令p为单个阿米巴原虫分裂的概率（题目中等于3/4），令P为我们要求的概率（无限繁殖的概率）。    初始时的那个阿米巴原虫有p的概率分裂为两个，至少有一个可以无限生存下去的概率为1-(1-P)^2。那么，我们得到式子：      P = p*( 1 – (1-P)^2 )

所以P = (2p-1)/p，p大于1/2时有概率P无限繁殖下去，p小于1/2时无限繁殖下去的概率为0

三，网格图场景

在一个无限大的网格图中，每个节点有上下左右4个邻居，即4条边，每条边都有p的概率是可通行的，有1-p的概率是不可通行的，问从起点出发存在无限长路径的概率。

1，问题背景

My backyard has an area where the soil is mainly clay and another where it's mainly sand. The day after a hard rain, the sandy region is usually dry while the clay region is still damp. The process by which water moves through a medium, like sand or clay, is called percolation and is currently the focus of significant mathematical activity, some of which we'll describe in this article.

Geoffrey Grimmett begins his book Percolation with the question: "Suppose we immerse a large porous stone in a bucket of water. What is the probability that the centre of the stone is wetted?" To begin creating a mathematical model, we will imagine a two-dimensional lattice of channels running through the rock (a more realistic three-dimensional model can wait).

This is known as the square lattice, and we will denote it by Z2. We choose a parameter p between 0 and 1 and declare that each edge is open with probability p. Think of an open edge as a channel that is large enough to conduct water through it. Here are examples for two different values of p.

If we imagine that the size of the channels is much smaller than the size of the rock, it is reasonable to assume that the lattice is infinite in extent. To rephrase Grimmett's question, we may ask, "What is the probability that there is a path of open edges from the origin that travels infinitely far?

We can easily make two statements. When p = 0, every edge is closed so there will be no infinite open path containing the origin. However, when p = 1, every edge will be open so there must be an infinite open path.

What happens for intermediate values of p? For small p, there will be few open channels so any open paths will most likely be short. However, as p increases, there are more open channels, and eventually it is likely that there is an infinite open path starting at the origin. If there is a positive probability of having such an infinite path, we say that percolation occurs. We will see that there is a critical probability, that we denote pc, representing a threshold; percolation occurs above pc but not below. A result due to Harris and Kesten, which we'll outline later, states that the critical probability for the square lattice is pc = 1/2.

The existence of a critical probability makes percolation a mathematically interesting and rich subject. On either side of the critical probability, the system behaves in fundamentally different ways (as water drains easily through sandy soil but not through clay). As such, it serves as a model for more complex systems that experience a phase transition when some parameter, such as temperature, passes through a critical value. Percolation provides a model that is simple enough to be mathematically accessible while still displaying many of the features of more complex systems.

Percolation theory was introduced to mathematicians by Broadbent and Hammersley in 1957. For two decades, work in this new field concentrated mainly on finding critical probabilities. For instance, Broadbent and Hammersley showed that the critical probability for the square lattice Z2, shown below, is between 1/3 and 2/3.

On the basis of Monte Carlo simulations, Hammersley later suggested that this probability should be 1/2. Indeed, through work of Harris and later Kesten, it was eventually proven that pc = 1/2. We will outline the proof of this theorem later. 

2，感性认知

For now, let's develop a feel for how configurations behave for various values of p.

Here is one configuration of open edges that results when p = 0.4.

Given a configuration of open edges and a vertex v in the lattice, the cluster Cv will denote the collection of vertices connected to v by open edges.

Below we show a configuration when p = 0.3 and C0, the cluster containing the origin, in blue.

Remember that θ(p) is the probability that there is an infinite path containing the origin, which is the same event as the cluster C0 being infinite. Here's what happens as we increase p.

p=0.2

 p=0.3

 

Based on these examples, two things can be observed. First, if we look at a fixed value of p, we see that the size of the clusters is relatively small for small values of p. A theorem of Menshikov allows us to state this quantitatively.

If E is some event, we will use Pp(E) to denote the probability that E holds when the edges are open with probability p. By Sx,n, we will denote the event that there is an open path from a vertex x to another vertex whose distance from x, measured in the lattice, is n. (We measure distances in the lattice as the number of edges in the shortest possible path between the two vertices.) Though proven in considerably more generality, Menshikov's theorem roughly says that

For a given p < pc, there is a constant a such that .

This means that the probability of having an open path decreases exponentially as the distance traveled by the path increases.

3，The Harris-Kesten Theorem

For our second observation, imagine increasing p as we consider the size of the cluster C0. It is relatively small for small values of p, but around p = 0.45, its size begins to grow significantly. This leads us to suspect that the critical probability pc, the probability that marks the transition from θ(p) = 0 to θ(p) > 0 occurs around 1/2.

In fact, one of the first significant results in percolation theory is the Harris-Kesten Theorem

For the square lattice, pc = 1/2.

（1）证明过程概述

In what follows, we will outline a proof of this theorem, which divides naturally into two parts. The first half, originally proven by Harris in 1960, states that θ(1/2) = 0. In particular, this implies that pc ≥ 1/2. The second half, proven later by Kesten in 1982, says that pc ≤ 1/2. The result that pc = 1/2 naturally follows.

（2）对偶网格图

We'll begin outlining an argument for Harris' theorem by considering the dual of the square lattice. This graph is formed from the square lattice by placing one vertex in the center of each square and joining vertices with an edge when their corresponding squares in the square lattice share an edge.

黑色网格图和灰色网格图互为对偶，其实就是相当于把所有的边以重心为中心旋转90度。

Notice that if we are given an edge in the lattice, there is exactly one edge crossing it in the dual. Also, the dual lattice is a copy of the square lattice translated so that the vertices are in the centers of the squares. For this reason, we say the square lattice is self-dual.

（3）反对偶图

反对偶图就是在对偶图的基础上，再把开边（可通行的）变成关边，把关边变成开边。

如果所有的边都是开的，那我们称之为全图。

图A的反对偶图和图A的对偶图是互补的关系，没有交集，合起来是全图。

Suppose we are given a configuration of open edges in the square lattice. We will consider an edge in the dual lattice to be open exactly when the edge it crosses in the square lattice is closed. Shown below in red is a configuration for the square lattice and, in blue, the corresponding configuration in the dual lattice.

此图我做了修改，补充了几条线，原图我觉得有遗漏。

上面的红色图和蓝色图就是互为反对偶图。

In this way, requiring that the edges in the square lattice are open with probability p is the same as requiring that edges in the dual lattice are open with probability 1 - p.

Now consider C0, the cluster in the square lattice containing the origin. If p < pc, then this cluster is almost surely finite. As the figure below shows, this means that there is almost surely an open cycle in the dual lattice containing the origin in its interior (shown in green).