Probability of survival on an infinite go board On an infinitely sized go board, a black stone is placed on a certain position. For each other position, it has an equal probability of being black, white, or empty, each being $1/3$. What is the probability that the first black stone survives?
In one dimension, the probability is
$$P=1-\left(\sum_{n=1}^\infty \frac{1}{3^n}\right)^2 = \frac{3}{4}$$
What about the two-dimensional case?
Here a go board is a square grid in which each position is denoted by an integer pair $(x,y)$. Each position can be empty, occupied by a black stone, or a white stone. Position $(x,y)$ is adjacent to positions $(x-1,y)$, $(x,y-1)$, $(x+1,y)$, $(x,y+1)$. A stone is alive or living if and only if


*

*It is adjacent to an empty position, or

*It is adjacent to an living stone of the same color



Edit: thanks to @joriki's comment, I think $1-(1/2)^4=15/16\simeq 0.9375$ establishes a lower limit for the probability. And $1-(1/3)^4=80/81\simeq 0.98765$ would be a first-order upper limit. Based on a 30 million game Monte-Carlo simulation, the probability should be $0.98470\pm0.00004$.
 A: Here's a rephrasing of the question for those who are unfamiliar with Go:
The vertices of an infinite square grid are labeled with $b$ ("black stone"), $w$ ("white stone"), or $e$ ("empty"). The vertex at $(0,0)$ is always labeled with $b$; the other vertices are randomly and independently labeled with $b$, $w$, or $e$, with equal probability.
Define the "black group" $B$ as the largest connected set of vertices which includes $(0,0)$ and where every vertex is labeled with $b$. ($B$ is finite with probability $1$.) What is the probability that $B$ is adjacent to at least one vertex which is labeled with $e$ (meaning that $B$ "survives")?
This probability can be written out as a pseudo-formula like so:
$$1 - \sum_{B} \text{(probability of $B$ occurring)}\text{(probability, given $B$, that $B$ does not survive)}.$$
The summation runs over all possible (finite) black groups $B$. Note that a "possible black group" is simply a "pointed fixed polyomino": in other words, a fixed polyomino where one particular point has been distinguished as $0,0$.
Now, let's define $N(B)$ has the number of vertices ("black stones") in $B$, and define $F(B)$ as the number of vertices which are not in $B$ but which are adjacent to $B$ (the number of "frontier vertices" of $B$).
The probability of any particular black group $B$ occurring is just the probability that $N(B) - 1$ vertices have randomly been labeled with $b$ and $F(B)$ vertices have randomly been labeled with $w$ or $e$. In other words:
$$P(\text{$B$ occurs}) = \left (\frac13 \right)^{(N(B) - 1)} \left (\frac23 \right)^{F(B)}.$$
Meanwhile, given a particular black group $B$, the probability that $B$ does not survive is simply the probability that $F(B)$ vertices have randomly been labeled with $w$, or
$$\left (\frac12 \right)^{F(B)}.$$
Substituting, we find that the overall probability of survival is
$$1 - \sum_{B} \left (\frac13 \right)^{(N(B) - 1)} \left (\frac23 \right)^{F(B)} \left (\frac12 \right)^{F(B)}\\
= \sum_{B} \left (\frac13 \right)^{(N(B) - 1)} \left (\frac13 \right)^{F(B)}\\
= \sum_{B} \left (\frac13 \right)^{(N(B) + F(B) - 1)}.$$
Recall that the sum ranges over all pointed fixed polyominoes $B$. It may be hard to find information about pointed fixed polyominoes, so let's rewrite the summation to instead range over all fixed polyominoes $P$. Each fixed polyomino $P$ appears as a pointed fixed polyomino $N(P)$ times, so we get
$$1 - \sum_{P} N(P) \left (\frac13 \right)^{(N(P) + F(P) - 1)}.$$
The value of this sum is almost certainly not known. But by enumerating all of the polyominoes up to, say, size 10, it should be possible to get very good upper and lower bounds.
