26
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This problem is fairly similar to my computer science masters thesis. Since I haven't finished writing the thesis and haven't yet submitted the paper, I am loath to put the argument here on MO. Still, I'm almost positive my argument will work in your situation and answer the question. If you like, we can talk via email. I'm a grad student at Wesleyan and my email address is dwhite03@<name of my school>.edu $\endgroup$ Dec 1, 2011 at 14:37
  • $\begingroup$ @Peter: what is the orientation "away from the origin" e.g. of the edge with end-points {(0,1),(1,1)} ? $\endgroup$ Dec 1, 2011 at 18:04
  • $\begingroup$ @Pietro: I think "east" is away from the origin for that edge, since traveling it from (0,1) takes you strictly further away from the origin in the graph metric. $\endgroup$ Dec 1, 2011 at 18:44
  • 3
    $\begingroup$ After thinking about the problem, I'm now fairly far away from "almost positive" that my proof will work in this situation. I'm been in contact with the OP via email and given him my argument, but while doing so I realized a number of serious obstructions to it working in this case. I say this because I don't want to hold others back from posting their ideas. $\endgroup$ Dec 1, 2011 at 18:52

4 Answers 4

12
$\begingroup$

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:

images of sampled out-components

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

percolation probability

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

fraction in out-component

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:

standard deviations

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

distribution of fractions

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$ -- lighter colors means higher probability density:

density plot

$\endgroup$
5
  • $\begingroup$ Thanks for the images. Your graphs seem to suggest that there is a critical value somewhere close to 0.5 alright. But one thing confused me in your first set of images : it looks like there is a much smaller white cluster at p = 0.49 than at p = 0.45. Is this really the case ? $\endgroup$ Dec 3, 2011 at 11:21
  • $\begingroup$ Yes, and quite interestingly, the distribution of the fraction of reachable vertices around those values of $p$ seems to be bimodal! I'll add a few plots in a bit. $\endgroup$
    – j.c.
    Dec 3, 2011 at 20:45
  • $\begingroup$ @JC: Forgive me, I'm not an expert on percolation. Is the bimodality significant ? i.e.: does it not occur in ordinary bond percolation ? What does P(p,n) look like for ordinary perc, where P(p,n) = probability that, at intensity p, the cluster of the origin has size n ? $\endgroup$ Dec 4, 2011 at 18:36
  • $\begingroup$ To be honest, I'm not sure about the significance of the bimodality. In ordinary percolation on an infinite square grid, the cluster size distribution decays exponentially for large $n$ at all $p$ except at $p=p_c$, where it decays as a power law, so in that sense there is no bimodality. However, for $p>p_c$, the origin may be contained in the infinite cluster, so in a finite system there actually would be bimodality. In any case, without doing a careful finite size scaling analysis, what my plots show is not clear. $\endgroup$
    – j.c.
    Dec 5, 2011 at 19:15
  • $\begingroup$ But anyways, this behavior is why a configuration at p=0.49 won't always have a much larger reachable cluster than p=0.45, for example. $\endgroup$
    – j.c.
    Dec 5, 2011 at 19:17
5
$\begingroup$

To Nathanael : I'll put my comment on your comment as an answer, because it's too long for it to be accepted 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 monotone path in an ordinary bond percolation. This is what is usually 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. Bollobás and A. Stacey, Improved 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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Come to think of it, the question can be rephrased in terms of standard percolation. It's fairly easy to check that the question is equivalent to asking for the existence of monotone paths (by which I mean, paths for which the x and y coordinates are monotone functions of time, e.g. that travel only in the North and East direction). I think the problem is clearer this way. Phrased this way, it is clear that the problem is monotone in $p$ so $p_c$ is well-defined, and moreover it is obvious that $p_c \ge 1/2$. $\endgroup$ Dec 3, 2011 at 8:35
  • $\begingroup$ @Peter: yes, I agree that my comment above is not correct: the model is not strictly equivalent to finding monotone paths. But the argument I outlined initially to show $p_c \ge 1/2$ is still valid, do you agree? ps. sorry to be answering here, but this is the only place I am allowed to put comments... $\endgroup$ Dec 3, 2011 at 11:29
  • $\begingroup$ @Nathanael: yes, I think your argument why we don't percolate below 1/2 is fine. Though I guess you agree something extra is needed to prove non-percolation at 1/2. Anyway, it's clear that the region of interest is (1/2,p_0), where p_0 is the critical value for oriented percolation. $\endgroup$ Dec 3, 2011 at 13:32
  • 3
    $\begingroup$ @Nathanel: wait, I'm not so sure about the below 1/2 argument. You can also get across a closed dual contour with a decreasing edge, depending on the shape of the contour - for example, if this contour contains three consecutive steps in the lower half-plane which are up, to the right and down, then you can get outside it via a decreasing edge if you come from the left. So I'm not even sure we have a proof of non-percolation below 1/2. The argument in Linusson seems to be very specific to 1/2. $\endgroup$ Dec 3, 2011 at 13:38
  • $\begingroup$ Yes, I agree ! Very interesting... $\endgroup$ Dec 5, 2011 at 8:23
2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ @Vincent: Yes, that is precisely how the argument goes in Linusson's paper for p = 1/2. $\endgroup$ Dec 5, 2011 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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