Take a $2n$ by $2n$ chess board (oriented so the grid lines are vertical and horizontal). Usually there are $2n^2$ squares coloured black and $2n^2$ squares coloured white so that a black square is only adjacent to white squares. (Here, two squares are adjacent if they have a common edge.)

Suppose instead we start with a blank $2n$ by $2n$ chess board. We pick $2n^2$ squares at random and assign them black. The other half of the squares are assigned white.

  1. What is the probability the resulting chessboard has a monotonic black path? (Here, a monotonic black path is one which starts in the South-West corner and finishes in the North-East corner, and consists entirely of black squares adjacent along their North or East edge.

  2. What is the probability that the resulting chessboard has a black path from the South-West corner to the North-East corner? (Here, a black path is a sequence of adjacent black squares)

  • 18
    $\begingroup$ In both cases, it decays exponentially in $n$, since $1/2$ is below the critical point for directed site percolation on the 2D lattice (case 1) and also for undirected site percolation on the 2D lattice (case 2). The keyword to look for is "percolation"; it's a massively active research area in probability / statistical physics / combinatorics. For good references, see for example the answers to this question: mathoverflow.net/questions/35756 (or you could start form the Wikipedia articles) $\endgroup$ Aug 17 '11 at 13:38
  • 1
    $\begingroup$ @James, perhaps you'd consider making your comment an answer? $\endgroup$ Aug 17 '11 at 23:29
  • $\begingroup$ This is an interesting connection to percolation. Thank you! Unfortunately, MathOverFlow does not allow me to accept a comment as an answer. $\endgroup$
    – alext87
    Aug 18 '11 at 8:02

James correctly identified percolation theory as the place where something like this is studied seriously. But let's do an elementary calculation.

Each possible path consists of $4n-1$ squares and is uniquely specified by saying which $2n-1$ of the $4n-2$ squares other than the first is vertically above the square before. Thus, there are exactly $$\binom{4n-2}{2n-1}$$ possible paths. Each path appears in a random board with probability $2^{-4n+1}$. Therefore, the expected number of paths is $$2^{-4n+1}\binom{4n-2}{2n-1} \sim \frac{1}{\sqrt{8\pi n}},$$ where the last expression comes from Stirling's formula.

Since the expected number of paths goes to 0, the probability that there is at least one path goes to 0 at least as fast. A quick simulation shows that James is correct that the probability goes to 0 exponentially fast (maybe slightly faster than $2^{-n}$).


James quickly gave the right answer in the comments, since $p_c \approx .5927$ for site percolation on the square lattice.

These crossing questions often have elementary answers, but neither the proofs nor the applications are trivial. For example, in critical percolation, the Russo-Seymour-Welsh theorem states that there is a uniform lower bound in the crossing probability. i.e., there is a uniform constant $c$ such that $\mathbb P_n(\mbox{there is a black crossing}) \ge c$, independently of $n$.

For a nice proof of the RSW theorem (with illustrative pictures!), see pages 33-44 of Pierre Nolin's lecture notes. (After deriving RSW, Pierre uses this formula to prove Kesten's theorem: $p_c = 1/2$ for bond percolation on the square lattice)

Another place to look is Section 1.3 of Wendelin Werner's lecture notes on percolation. Werner uses this to prove the Cardy-Smirnov formula, and then that site percolation on triangular lattice converges to $\operatorname{SLE}(6)$.

Cardy's formula is just one of the many elegant results in mathematical conformal field theory. Define $$f(x) = \mathbb P( \mbox{crossing starting from the point $x$ on side $1$ to side $2$} )$$ for site percolation on the unit triangle with spacing $1/n$. Cardy's formula is that $$f(x) = x.$$ (Peter Jones has described Cardy's formula as "the most difficult theorem about the identity function.")

  • $\begingroup$ Thanks for more information. That's great. I'm confused, by my lack of knowledge on percolation, and by the uniform lower bound on the probability of a black cross. I'm not sure how your answer fits together with Brendan McKay's answer... $\endgroup$
    – alext87
    Aug 18 '11 at 8:13
  • 1
    $\begingroup$ The uniform lower bound and in fact most of the nice results described in Tom LaGatta's answer apply only at criticality, that is, when $p=p_c$. Your question is about subcritical percolation, where $p<p_c$. The sources linked in this answer focus mainly on critical percolation, good sources on percolation in general are Grimmett's book or Bollobás and Riordan's book. $\endgroup$
    – j.c.
    Aug 19 '11 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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