Probability of a black path on a random chess board - MathOverflow

Probability of a black path on a random chess board

2011-08-17T12:45:35Z

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.

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

Answer by Brendan McKay for Probability of a black path on a random chess board

2011-08-17T23:47:26Z

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

Answer by Tom LaGatta for Probability of a black path on a random chess board

2011-08-18T02:22:27Z

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