A percolation problem - MathOverflow

A percolation problem

2011-12-01T12:01:19Z

Let's consider the 2-dimensional integer lattice $\mathbb{Z}^2$ for simplicity. In "ordinary" bond percolation, there is a parameter $p \in [0,1]$, and each edge is on with probability $p$. Consider now the following model : all edges are present, but each is to be given an orientation either away from or toward the origin (this is well-defined in $\mathbb{Z}^2$). Hence, each edge is oriented away from $(0,0)$ with probability $p$, and toward $(0,0)$ with probability $1-p$. The basic question is whether we percolate when $p > 1/2$, i.e.: if $p > 1/2$, is there a non-zero probability of there being an oriented path from $(0,0)$ to infinity ? The intuition behind this is that a biased 2-D random walk is known to be transient. I have seen other models of "oriented percolation" but not this one, so my question is really whether there are any results on this model ? By the way, it is known we don't percolate at $p = 1/2$. Here the model coincides with one that appears for example in several of Grimmett's books, where the bias is in a certain direction (north and east), rather than away from $(0,0)$. There it is also apparently open whether one percolates for $p > 1/2$.

Answer by jc for A percolation problem

2011-12-02T22:08:51Z

I don't have anything rigorous to say, but let me share some images that may be useful or interesting to you. The Mathematica code to generate them is here. It's sparsely commented, so feel free to ask in the comments for clarification.

Below, the "out-component" is the set of vertices which are reachable by a directed path from the origin.

Here are a few example out-components at various $p$ in your model for a 161 by 161 grid:

I'm quite fond of this animated GIF file which shows the "averaged" out-component of the vertex at the origin in a 41 by 41 square grid as $p$ is tuned from 0 to 1 (in steps of 0.02). The intensity of a pixel corresponds to the frequency that that vertex was reachable from the origin in a set of 1000 pseudorandom configurations.

I'm not sure what to make of this pattern -- in particular, are they an artifact of the square boundary conditions, as they might cut off longer paths that would have made the dark regions parallel to the $x$ and $y$ axes reachable?

From the same data, here's the probability of percolation (existence of a directed path from the origin to the boundary of that 41 by 41 square grid) as a function of $p$:

And here's the mean fraction of the full grid that is reachable from the origin as a function of $p$:

Perhaps someone with more computer time can run do this with larger system sizes (my run took somewhere around an hour). I might do this for the last two graphs I showed, just to see how the transition sharpens for larger system sizes.

Edit. The last plot doesn't quite tell the full story about the distribution of out-component sizes.

Here's a plot showing the standard deviation of the out-component sizes:

Here's a sequence of plots showing histograms (from 1000 pseudorandomly generated configurations) of the fraction of total vertices reachable from the origin in a 41 by 41 grid at various $p$:

The distribution is bimodal sufficiently near $p=0.5$!

Here's a density plot of the fraction of vertices in the out-component as a function of $p$:

Answer by Nathanael Berestycki for A percolation problem

2011-12-02T22:56:40Z

This is a nice model. Call an edge increasing if it is oriented in the direction going away from the origin, and dercreasing otherwise. Of course increasing edges form a usual bond percolation model. For $p<1/2$ we know, by duality, that there exists a closed dual contour. So no increasing edge can cross that contour and hence the origin does not percolate. So $p_c \ge 1/2$ in this model, in the sense that for all $p<1/2$ there is $a.s.$ no infinite cluster.

For $p>1/2$ I agree it seems intuitively likely that the origin does percolate. For instance, is it known whether there always exist northeast paths in supercritical bond percolation in $\mathbb{Z}^2$?

At any rate, a first step would be to prove that the critical probability is $<1$, I think. (By the way, it is not immediately obvious that $p_c$ is well-defined, as there isn't any obvious monotonicity).

Answer by Peter Hegarty for A percolation problem

2011-12-03T11:25:33Z

To Nathanael : I'll put my comment on your comment as an answer, because it's too long for it to be acepted as a comment.

I disagree with a couple of things you say. First, I don't think it's true that the increasing edges form a usual bond percolation. For example, suppose each of the three edges (0,0) -> (1,0), (1,0) -> (1,1) and (0.1) -> (1,1) is increasing. Then in ordinary bond percolation, there would be a path from (0,0) to (0,1), but not in my model. Secondly, I don't see why the question is equivalent to asking for the existence of a monotone path, since I only require that a path follow the designated orientations. The path can twist and turn however it likes as long as it eventually heads off to infinity.

However, it is certainly true that it suffices to have a monotone path. If we simply threw away all the decreasing edges, then this would be equivalent to looking for a montone path in an ordinary bond percolation. This is what is ususally referred to in the literature as "oriented percolation", and it is known that the critical value for this process is strictly less than one. The best upper bound I know of is about 0.6735, and is proven in

P. Balister, B. Bollobas and A. Stacey, Imrpoved upper bounds for the critical probability in oriented percolation, RSA 5 (1994), 573-589.

Hence, in my model we will certainly also percolate above this value of p. You are correct to point out, however, that even monotonicity is not obvious for my model, so what happens between p = 1/2 and p = 0.6735 is not clear. I do not have a proof of monotonicity. For the proof that one doesn't percolate at p = 1/2, I suggest you look at Lemma 2.1 in

S. Linusson, A note on correlations in randomly oriented graphs, arXiv:0905.2881

Grimmett has results on his "north-east bias" model in

G.R. Grimmett, Infinite paths in randomly oriented lattices, RSA 18 (2001), no.3, 257-266.

However, he utilises a symmetry in his model which allows him to play around with the dual lattice in a way which I don't see how to transfer to my model.

Answer by Vincent Beffara for A percolation problem

2011-12-05T17:28:41Z

Not sure if that is what Linusson does, but it is not difficult to see that the cluster distribution at the origin at $p=1/2$ is exactly the same as for ordinary percolation at $p=1/2$ (in fact, that holds in any graph, in particular in $\mathbb Z^3$ there is percolation wpp at $p=1/2$; there is no use of duality).

Here is a coupling argument. Start with standard percolation, and explore the cluster of the origin by looking at every edge you need one by one. On the directed side of the coupling, if the edge is open, put it in the orientation that allows you to proceed, and if it is closed, put it in the reverse orientation. That builds an orientation on a random set of bonds, which you can complete into a configuration in the whole plane.

In particular, the average size of the cluster at $p=1/2$ is infinite. Maybe there is even Russo-Seymour-Welsh and so on, anyway it looks very critical. And there is "too much symmetry" in that for every $x$ in the plane, the cluster of $x$ has the same distribution in both models.

But indeed without monotonicity it is difficult to see how to proceed ...