Probability of a black path on a random chess board - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:50:32Z http://mathoverflow.net/feeds/question/73055 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73055/probability-of-a-black-path-on-a-random-chess-board Probability of a black path on a random chess board alext87 2011-08-17T12:45:35Z 2011-08-18T23:57:30Z <p>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.)</p> <p>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.</p> <ol> <li><p>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.</p></li> <li><p>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)</p></li> </ol> http://mathoverflow.net/questions/73055/probability-of-a-black-path-on-a-random-chess-board/73108#73108 Answer by Brendan McKay for Probability of a black path on a random chess board Brendan McKay 2011-08-17T23:47:26Z 2011-08-18T23:57:30Z <p>James correctly identified percolation theory as the place where something like this is studied seriously. But let's do an elementary calculation.</p> <p>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.</p> <p>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}$).</p> http://mathoverflow.net/questions/73055/probability-of-a-black-path-on-a-random-chess-board/73114#73114 Answer by Tom LaGatta for Probability of a black path on a random chess board Tom LaGatta 2011-08-18T02:22:27Z 2011-08-18T02:22:27Z <p>James quickly gave the right answer in the comments, since $p_c \approx .5927$ for <b>site percolation</b> on the square lattice.</p> <p>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$.</p> <p>For a nice proof of the RSW theorem (with illustrative pictures!), see pages 33-44 of <a href="http://cims.nyu.edu/~nolin/AdvancedTopics/2&amp;3-Percolation.pdf" rel="nofollow">Pierre Nolin's lecture notes</a>. (After deriving RSW, Pierre uses this formula to prove Kesten's theorem: $p_c = 1/2$ for <b>bond percolation</b> on the square lattice)</p> <p>Another place to look is Section 1.3 of <a href="http://arxiv.org/pdf/0710.0856v3" rel="nofollow">Wendelin Werner's lecture notes on percolation</a>. Werner uses this to prove the Cardy-Smirnov formula, and then that site percolation on triangular lattice converges to $\operatorname{SLE}(6)$.</p> <p>Cardy's formula is just one of the many elegant results in mathematical conformal field theory. Define <code>$$f(x) = \mathbb P( \mbox{crossing starting from the point x on side 1 to side 2} )$$</code> for site percolation on the unit triangle with spacing $1/n$. Cardy's formula is that $$f(x) = x.$$ (<a href="http://webcache.googleusercontent.com/search?q=cache:PHaGfQpz--AJ:https://www.ipam.ucla.edu/publications/ann2010/ann2010_9484.ppt+gruzberg+random+complex+enounters&amp;cd=1&amp;hl=en&amp;ct=clnk&amp;gl=us&amp;source=www.google.com" rel="nofollow">Peter Jones</a> has described Cardy's formula as "the most difficult theorem about the identity function.")</p>