MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an $N$ by $M$ grid (a Go board for example), where for every square in the grid, I place a white stone with probability $p$ and a black stone with probability $(1-p)$. We call two white stones (or two black stones) 'connected' if there exists a path between them, consisting of stones of their same color, that hops along von Neumann neighborhood of each cell along the way (North, South, East, West nearest-neighbors). Diagonal hops are prohibited.

What is the probability that all white stones in the $N$ by $M$ grid are 'connected' in this fashion? If all white stones are 'connected', what is the probability that each white stone has two or more white neighbors?

Update - The percolation threshold, $p_c$, of a graph or lattice (hat tip to Igor Rivin) is the minimum connectivity before which one begins to see connected components spanning from one side of a graph or a lattice to the other. Is there some similar threshold for which one expects a single connected component?

share|cite|improve this question
One can easily bound the answer to the first question between two exponentials. If every stone is white, then every white stone is connected. Then divide the board into 3 x 3 cells. If any of those cells has a white stone surrounded by black stones, then not every white stone is connected. So it's between $p^{NM}$ and $(1-p(1-p)^4)^{NM/9}$ – Will Sawin Jun 18 '12 at 19:49
@Will Sawin, that's a great observation, but is this about as tight as what one can hope for without a lot of work? – Roger S. Jun 18 '12 at 19:59
Depends. You can strengthen the lower bound with a tree that covers about half the squares and is connected to every square it doesn't cover, so if those are all white then the white stones are connected. This gets up to $p^{NM/2}$. Also if everything is black then that works just as well, so $p^{NM/2}+(1-p)^{NM}$. There are certainly other not-too-difficult tricks that can tighten this further. In particular there are currently big gulfs for $p$ near $1$. – Will Sawin Jun 18 '12 at 20:34
Regarding your update: the answer is no as is evident from Will's comment. – Ori Gurel-Gurevich Jun 19 '12 at 4:18
up vote 6 down vote accepted

The magic word is "percolation". This is a huge subject, but Grimmett's book of the same title should be a very good start.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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