# Probability that a randomly filled Go board has a set of white stones connected through their von Neumann neighborhoods

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?

• 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}$ 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? 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$. Jun 18 '12 at 20:34
• Regarding your update: the answer is no as is evident from Will's comment. Jun 19 '12 at 4:18