What is Menshikov's Theorem and How Does it Relate to Percolation?

[ddriver1]

Hi,

I am trying to learn some stuff about percolation, specifically what Menshikov's theorem is about. On wiki http://en.wikipedia.org/wiki/Percolation_theory it says:

"when p<pc, the probability that a specific point (for example, the origin) is contained in an open cluster of size r decays to zero exponentially in r."

And in http://www.ams.org/samplings/feature-column/fcarc-percolation it says something similar:

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


Now in the image below:

it seems as though the vast majority of the grid's squares (sites) are members of fairly large clusters. So, if I were to pick a site at random, it seems that chances are it would be in one of these fairly large clusters. However, the wikipedia statement would suggest the randomly picked point would be most likely to be found in a very small cluster (small r), and not one of these large ones.

Can anyone tell me what I am misunderstanding?

Thanks

 

[mfb]

The large clusters are just more visible (as they are larger :D).
In addition, I think this exponential decay is the limit for large cluster sizes. The closer p is to pc, the larger the cluster sizes where you see this exponential decay.

 

[ddriver1]

The large clusters are just more visible (as they are larger :D).
In addition, I think this exponential decay is the limit for large cluster sizes. The closer p is to pc, the larger the cluster sizes where you see this exponential decay.

Hmm. But the large clusters are taking up a visibly large amount of area. So if for example the area of the whole lattice is 1000x1000 = 1000000, and one of the clusters is of size 300000, then there is
a 30% chance that an arbitrarily picked site is in a cluster with size 300000. Maybe the wiki definition is saying that there is close to 0% chance of it being in a cluster of size exactly 300000 (as opposed to say, 300001)? If so, it kind of makes sense when you consider that the image shown is just one specific instance.

But then the second definition confuses me, as surely if most of the clusters are fairly large, then the chances of there being a path of distance 1 is going to be almost the same as the chances of a path of distance 2. Would it be possible that by "decreases exponentially" he means only after a certain value of r, like in the graph I've attached?

 

[BruceW]

I think in the image, it is just easier to see the larger clusters as mfb says. It seems possible to me that truly the cluster size does obey exponential decay, it is just hard to see it. In Kesten's paper, the theorem (as he wrote it) is like this:
For any $p<1/2$ there exists a constant $C_1(p)>0$ such that for all n
$$P_p ( \text{W contains vertices at a distance} \geq \text{n from the origin} ) \leq 2e^{-C_1(p)n}$$
And he explains earlier that $W$ is the open cluster that contains the origin. So, it really does seem like it is an exponential decay, for any distance from the origin. So (I think) even the small clusters obey this exponential decay law. Well, it is an inequality, not truly an equation giving the exact value of the probability.

edit: also, since it is saying the probability is less than or equal to that amount, it means that the decay is at least exponential. So we are guaranteed that the probability of size of cluster decays at least exponentially with the cluster size. In other words, it could decay even faster, but not slower, than exponential.

 

[ddriver1]

I think in the image, it is just easier to see the larger clusters as mfb says. It seems possible to me that truly the cluster size does obey exponential decay, it is just hard to see it. In Kesten's paper, the theorem (as he wrote it) is like this:
For any $p<1/2$ there exists a constant $C_1(p)>0$ such that for all n
$$P_p ( \text{W contains vertices at a distance} \geq \text{n from the origin} ) \leq 2e^{-C_1(p)n}$$
And he explains earlier that $W$ is the open cluster that contains the origin. So, it really does seem like it is an exponential decay, for any distance from the origin. So (I think) even the small clusters obey this exponential decay law. Well, it is an inequality, not truly an equation giving the exact value of the probability.

edit: also, since it is saying the probability is less than or equal to that amount, it means that the decay is at least exponential. So we are guaranteed that the probability of size of cluster decays at least exponentially with the cluster size. In other words, it could decay even faster, but not slower, than exponential.

You are right, if we say have 1000 clusters in total, we will have many clusters of size 1, fewer clusters of size 2, fewer sizes of size 3 etc. But of course there will be a few very large clusters.
So the text I quoted from Wiki:

"when p<pc, the probability that a specific point (for example, the origin) is contained in an open cluster of size r decays to zero exponentially in r."

makes sense, as the probability of a site being in a cluster of size 1 is much higher than it being in
a cluster of size, say, 26845.

Now that you rephrased Kesten's paper, it seems like you are saying that sites near the origin are very likely to be members of the cluster, and as you consider vertices which are further away they are exponentially less likely to be in that cluster. This would make sense, and would apply to any cluster, regardless of its size.


However, in that case the two statements are saying different things, and they are both supposed to be based off Menshikov's theorem (or are they?) One is saying that you get many small clusters and fewer large clusters, while the theorem you mentioned is talking about points in clusters and not anything to do with cluster sizes themselves.

Sorry about this, hope I made some sense!

 

[BruceW]

I am pretty sure that wikipedia is trying to say the exact same thing as Kesten. I am almost certain that when wikipedia says "when p<pc, the probability that a specific point (for example, the origin) is contained in an open cluster of size r decays to zero exponentially in r." They actually mean what I wrote in the post above. When they say "...an open cluster of size r..." I think they just mean that since the point would be distance r from the origin, the cluster will have 'size' of at least r. I don't think they mean size to be the actual area which is taken up by the cluster.

Maybe there is a theorem specifically about the area of the cluster. But I have not been able to find it. In Kesten's paper "The critical probability of bond percolation on the square lattice equals 1/2", it does not seem to specifically mention anything about the area of the clusters. But maybe I did not read it carefully enough. p.s. Kesten seems to be the guy who proved this theorem in 2d. I think that Menshikov proved it in 3d.

edit: you might be able to find something about the area of clusters if you search through the related papers. I don't know. Also, maybe in some related papers they will talk about the fractal dimension of this object. But I would guess that such a thing is only an approximation in the limit that you 'zoom out' from the lattice, since clearly it can't be a true fractal, once you zoom in on the lattice, you see that the smallest lines are of the size of one link on the lattice.

 

[mfb]

I think we canmot see any deviation from an exponential law just by looking at the image. If the exponential is falling slowly, the propability to be in a cluster of size 10 is close to the probability to be in a cluster of size 1000. But we don't look at the image for linear cluster sizes. We compare the clusters with sizes 1 to 100 with the clusters of size 100 to 10000. The latter group will win by a factor of nearly 100 just because it has more integers in its range. You expect to be most points in "large" clusters, as the definition of "large" is roughly following a logarithmic scaling.

 

[BruceW]

yeah. If the $C_1(p)$ constant is small, and we are zoomed into a relatively small part of the lattice, then the probability of larger clusters and smaller clusters will not be very different. To be honest, the people who made that picture probably chose a zoom scale and value for $p$ such that it would be possible to see some larger clusters as well as the smaller clusters. If they chose values such that you could only see small clusters, then it would make a pretty boring picture.