Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

I have on several occasions wondered how one might proceed in order to sample large subcritical Bernoulli bond-percolation clusters, say on the square lattice.

More precisely, let's consider the lattice $\mathbb{Z}^2$, and open each edge independently with probability $p<p_c=0.5$. I am interested in the event that the vertices $(0,0)$ and $(N,0)$ are connected by a path of open edges, when $N$ some large number ("large" meaning here "many times the correlation length").

It is well-known (rigorously) that this probability decays exponentially fast with $N$, and one has a lot of information about the geometry of the corresponding cluster (e.g., the corresponding cluster converges to a brownian bridge as $N\to\infty$ under diffusive scaling, it has a maximal "width" of order $\log N$, etc.).

Question: Are there (not too inefficient) algorithms that would sample typical clusters contributing to this event?

Edit: googling a bit, I have stumbled upon this paper. I have yet to read it (and to decide whether it is relevant to my question). What the author seems to be doing is growing his objects in a biased way, which helps create the very unlikely configurations he's after, but would result in the wrong final distribution. So he's at the same time correcting the bias (in a way I haven't yet understood by just browsing through the paper). As an example, he's sampling 18 disjoint crossing clusters for critical percolation on $\mathbb{Z}^3$ in a box of size $128\times128\times2000$, an event of probability of order $10^{-300}$. So:

Alternative question: does anybody know how this works? (I can also simply read the paper, but it might be useful for me and others if a nice self-contained description was given here by someone knowledgeable).

Apparently, looking more thoroughly, there is a lot of material that could be useful. It seems that relevant keywords here are: rare events simulation, importance sampling, splitting, etc.

share|improve this question
    
Yes, there is. I've been programming one ~ten years ago, but forgot the name. Will look up references and post an answer. –  Slaviks Oct 1 '11 at 6:56
    
"one has a lot of information about the geometry of the corresponding cluster (e.g., the corresponding cluster converges to a brownian bridge as N→∞ under diffusive scaling, it has a maximal "width" of order logN , etc.)." Perhaps the best bet is to understand where this information comes from and do the proofs suggest how a random cluster of the kind you want looks like. Also, you can use the known information to check suggestions for such samplings like the one in the editted part of the question. –  Gil Kalai Oct 3 '11 at 18:29
    
"As an example, he's sampling 18 disjoint crossing clusters for critical percolation on $Z^3$ in a box of size 128×128×2000 , an event of probability of order $10^{−300}$". Yvan, I see very little hope that this sampling is related to the distribution claimed to be sampled. (This reminds me the following joke: A person says he what to sell his dog, "for how much?" his friends ask, "for $10^{300}$ dollars" he says. The next day they ask him if he was successful. "Yes!, I sold it for 10 kittens worth $10^{299}$ dollars each!") –  Gil Kalai Oct 3 '11 at 18:40
    
@Gil Kalai: "Perhaps the best bet is to understand where this information comes from and do the proofs suggest how a random cluster of the kind you want looks like". Well, this I know very well, as I was one of the authors of this study. The proof does tell you that a typical such cluster is a concatenation of "irreducible pieces". The problem is that I have no idea how to sample the latter ;) . –  Yvan Velenik Oct 4 '11 at 7:07
    
@Gil Kalai: "I see very little hope that this sampling is related to the distribution claimed to be sampled". Well, it does look quite serious, and the guy was able to recover numerically with very high precision all kinds of predictions from SLE (in the 2d case) for very rare events. I still have to really see how it works, however... –  Yvan Velenik Oct 4 '11 at 7:09

2 Answers 2

Here is the algorithm as I remember it. There is a name and a reference attach to it, I will update my answer when I find them.

The algorithm is not limited by $N$ (does no require storing the grid). Each edge of an infinite lattice is either open, closed or unknown. Initially all edges are unknown. The idea is to grow a connected cluster iteratively, trying (generating the random number for) all yet unknown edges in cluster's neighborhood.

You will need two data structures: list CLUSTER for open edges that form a connected cluster, list KNOWN for all the edges that are either open or closed but not unknown.

  1. Start with both CLUSTER and KNOWN populated by one open edge.
  2. Construct the list NEIGHBOURS consisting of all the edges connected to the edges in CLUSTER.
  3. If there are no unknown edges in NEIGHBOURS then stop.
  4. For each unknown edge in NEIGHBOURS: a) throw a random number and determine whether it is open or closed; b) add the edge to KNOWN; c) if the edge is closed, add it to CLUSTER.
  5. Go back to step 2.

The algorithm terminates with probability if you are below the percolation threshold. By repeating it a sufficient number of times, you get an unbiased distribution of connected clusters. Depending on what you are particularly interested in, you may discard all 'small clusters' or build in a break once you cluster linear size exceeds $N$.

share|improve this answer
    
Yes, this is the natural way to grow a typical subcritical cluster. But what I'm after is an extremely atypical such cluster, one which connects two points at a distance much farther than the correlation length. With such an algorithm, I'd need to repeat the growth an exponential number of times in $N$ in order for the event to occur... –  Yvan Velenik Oct 2 '11 at 8:11
    
Indeed, a local algorithm like this is not efficient for your purposes. Hard to imagene how a global (target size) information can be incorporated effieciently but I hope you'll succeed. Sorry this one didn't help. –  Slaviks Oct 2 '11 at 8:46

The naive algorithm - sampling conditioned on the rare event in question (that vertices (0,0) and (N,0) are connected) is rather inefficient. The only hope I see for an efficient algorithm comes from duality results connecting subcritical percolation and supercritical percolation. There are various such results (that apply in greater generality - to nonplanar percolation, to random graphs etc.). I don't know if there are results of this kind for this precise question: namely of the law for the cluster containing (0,0) and (N,0) in subcritical percolation conditioned on them being connected is the same (or approximately the same) for subcritical percolation with parameter p and supercritical percolation (say of probability 1-p).

share|improve this answer
    
I'm not sure I understand your last sentence, since the probablity of connecting the two points in the supercritical case is of course of order $1$ (bounded below by the probability that both belong to the infinite component). On the other hand, I agree that if the $2$ points are not connected in a subcritical configuration, then there cannot be a dual circuit separating one from the other in the corresponding supercritical configuration. But I don't see how the latter event would be easier to simulate (it's really just a reformulation of the former). Am I mistakent? –  Yvan Velenik Oct 2 '11 at 8:20
    
Dear Yvan, I DONT refer here to planar duality. In fact duality between the behavior of events in the subcritical and supercritical probabilities exists for various models e.g. the Erdos Renyi model of random graph. For example, we may wonder if the distribution of clusters containing (0,0) and (N,0) in subcritical percolation with edge probability p is related to the distribution of the cluster containing (0,0) and (N,0) conditioned on the existence of such cluster and it not being infinite. (Such a relation is a bit wild speculation but I see no other hope for an efficient algorithm.) –  Gil Kalai Oct 2 '11 at 10:40
    
OK, I'll have to think more about what you're suggesting ;) . On the other hand, I don't think that there is no hope for an alternative efficient algorithm, see the edits in my question. –  Yvan Velenik Oct 2 '11 at 16:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.