You can always cross an $n\times n$ grid with random diagonals, from one side of the grid to the opposite side of the grid. So the probability of this crossing is $1$.

Here random diagonals means you have an $n\times n$ grid and you draw at random one diagonal in each of the 1×1 unit squares of the grid. Then you can always find a connected path using these small diagonals that goes from one side of the grid to the opposite side, up to down or left to right.

(You can prove that by contradiction that makes repeated use of the Lemma of Sperner. In these two posts, you can find a related discussion and several different proof ideas https://math.stackexchange.com/a/3677664/782412 and https://mathoverflow.net/q/112067/156936.)

I have two questions about the crossing probability

(1) Can we use the symmetry to conclude that the probability of crossing from top to down is $1/2$ ? My thinking is that this follows directly from the symmetry, and from the fact that the unrestricted (up-down or left-right) probability is $1$.

I have seen such a symmetry argument in the post of user joriki here https://math.stackexchange.com/a/3641146/782412, but I wanted to ask for confirmation that the symmetry arguments is also valid for my problem.

(2) Bond percolation critical probability threshold $p_c$? Assuming the answer to my question is $1/2$, i.e. probability of crossing the grid top-down, this reminds me of an introductory article about percolation theory here https://en.wikipedia.org/wiki/Percolation_theory, following a comment from user joriki (thank you for that!).

In particular, I am refering to bond percolation, i.e. percolating from the top side down to the bottom side. The article says that for the infinite square lattice $\mathbb Z^2$ in two dimensions, the critical probability threshold $p_c$ for bond percolation is $1/2$.

My question, is crossing the grid along random diagonals in fact EQUIVALENT to bond percolation on a square grid? In this case, my crossing problem could be related to $p_c$ for the finite case of an $n \times n$ grid? Is the finite $n\times n$ case an established and known result? I am not sure, and maybe I am misunderstanding the concept of $p_c$. I would be grateful if someone could help me clarify and answer this.


1 Answer 1


To your first question: No, you cannot conclude that the probability of crossing from the top down is $\frac12$. In addition to the assumptions that you mention (symmetry and probability $1$ of some crossing), you’d need the assumption that the crossings in the two directions are mutually exclusive, that is, that exactly one of them exists. This is the case if the paths are dual to each other, as in the case of the bridge that you linked to, where there is either a horizontal path for the ant or a vertical path for the dual ant on the dual lattice. But that’s not the situation in the case of the diagonals, where horizontal and vertical paths can meet. For example, for even $n$, you can have both diagonals connected, from top left to bottom right and from bottom left to top right, such as in this example for $n=2$:


If $E_|$ and $E_-$ are the events that there’s a connection top-down and left-right, respectively, then $\mathsf P(E_|\cup E_-)=1$ and $\mathsf P(E_|)=P(E_-)$ and $\mathsf P(E_|\cap E_-)\gt0$, and thus $\mathsf P(E_|)\gt\frac12$.

To your second question: Yes, there’s a connection to bond percolation on the square lattice. If you turn the ant bridge by $\frac\pi4$, the lattice points and the dual lattice points (but not the points of intersection of the edges with the dual edges) together form a new square lattice (with a lattice constant smaller by a factor $\sqrt2$), with one edge and one dual edge forming crossing diagonals in each grid square. Since both the lattice and the dual lattice are at the bond percolation threshold at $p=\frac12$, it follows that if we choose one of each pair of diagonals with $p=\frac12$ (corresponding to choosing an edge or its dual with $p=\frac12$), both half-lattices are at the bond percolation threshold, that is, they are at the critical point, at which there is no infinite cluster. Since there are no connections between the two half-lattices, that means that there is no infinite cluster in the lattice. If you want to consider probabilities other than $\frac12$, the connection to the square lattice only holds if you checker the lattice and use $p$ for different directions of the diagonals on black and white squares, corresponding to the alternating pattern of edges and dual edges in the bridge turned by $\frac\pi4$.

  • $\begingroup$ joriki thanks a lot for a great answer. Very clear and super helpful! And your answer on (2) triggers a lot of interest. Is this your own research area, I wonder. Thanks again for your help! $\endgroup$
    – Claus
    May 16, 2020 at 18:20
  • $\begingroup$ joriki by the way I saw you are located in Berlin. Drop me a note when you visit Munich, where I am based. Your answers and comments help a lot, I owe you a beer. $\endgroup$
    – Claus
    May 16, 2020 at 18:27
  • 1
    $\begingroup$ @Claus: You're welcome :-) I actually have an old friend in Munich; it's quite possible that I'll come to visit again some day. No, this is not my research area; in fact I don't do mathematical research in a professional sense; I just do a lot of maths (and learn a lot) in the course of answering questions on this site :-) I happened to know about percolation theory from the time long ago when I studied physics and did simulations of statistical systems for quantum field theory. $\endgroup$
    – joriki
    May 16, 2020 at 18:56
  • 1
    $\begingroup$ I see! Keep doing this, it adds great value to this forum! And give me a signal regarding Munich, can use this post to connect. I will put it on “follow” such that I get a notification $\endgroup$
    – Claus
    May 17, 2020 at 4:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .