3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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}$ $\endgroup$
    – Will Sawin
    Commented Jun 18, 2012 at 19:49
  • $\begingroup$ @Will Sawin, that's a great observation, but is this about as tight as what one can hope for without a lot of work? $\endgroup$
    – Roger S.
    Commented Jun 18, 2012 at 19:59
  • $\begingroup$ 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$. $\endgroup$
    – Will Sawin
    Commented Jun 18, 2012 at 20:34
  • 1
    $\begingroup$ Regarding your update: the answer is no as is evident from Will's comment. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jun 19, 2012 at 4:18

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .