Sampling typical clusters between distant points in subcritical percolation

Question

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.

Answer 1

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$.

Answer 2

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).