What kind of distribution is this? (Number of stones until 2 are adjacent in a game of Go)

Question

I've plotted the histogram of the number of stones required so that 2 are adjacent when randomly placed 1 by 1 on a goban (think of a 19x19 chessboard and I place pieces 1 by 1 until 2 are adjacent, not counting diagonals), after 10 million trials. I obtained what I consider a very strange looking distribution because it first very slightly decreases, then increases and then decreases. I wouldn't have expected the slight decrease from 2 stones to 3 stones. This strange behavior doesn't occur when I consider smaller boards, and it appears for larger boards too (like 21x21). I don't know yet the critical board size so that there's a decrease in occurrences between 2 and 3 stones placed. I'm wondering what's the type of distribution and whether it changes when the board size changes and if so, if there's a general way to obtain the type of distribution for an nxn sized board.

Edit: I've just been told (on IRC) not to use a histogram because my data is discrete and not continuous. I should use a barplot instead. By doing so, the strange behavior disappears and stopping at stone 3 is about twice as likely as stopping at stone 2. If someone knows which distribution it is, I'm all ears.

Answer 1

As I wrote in the comments,

I suspect that this distribution doesn't have a name, because it represents the outcome of a non-independent random process. But the description of the problem is binomial-flavored, so it's probably related to the binomial and Poisson distributions. In general I think these kinds of questions are misguided. If you're trying to model this outcome and want to know what kind of distribution to use, that's a more answerable question.

By "non-independent" here, I mean that the probability of success (two adjacent stones) changes at every step of the simulation, because the board arrangement changes at every step. I imagine the combinatorics involved here would make exact computations intractable.

User whuber adds the following insight (emphasis mine):

This distribution is unlikely to be named, parameterized, or studied as such because it's messy: the board is not homogeneous--it contains three different kinds of locations (central, edge, and corner cells). Thus obtaining an exact numerical answer is of little interest. There are standard methods for obtaining exact asymptotic answers (as the size of the board increases).

Answer 2

To simplify the issue: let the board be one-dimensional of size $1 \times n$.

Equivalent problem

For each $k$-th step number we can ask the following equivalent question:

• In how many ways can we distribute the $k$ stones such that only 2 or 3 are touching together (more or bigger groups are not a valid end-states). These are the possible end states.
• Then you have to consider in addition the number of ways to place the stones on the board such that one of the two touching or the middle of the three was the last stone placed on the board.

Gaps

The distribution question is equal to finding sufficient non-zero gaps between the stones. With $k$ stones, where 2 touch each other (for which there are $k-1$ ways, e.g the stones that touch are the 1st and the 2nd until the k-1-th and the k-th), there need to be $k-2$ gaps in between them and there are between $k-2$ and $n-k$ squares to use for this (the process should be stopped before $2k\geq n+2$). This is not a definite number because the outside stones may not need to touch the sides.

Let there be $l$ squares to be distribute among $k-2$ non zero gaps. The number of ways to do this is

$$f(l,k-2) = \dbinom{l-1}{k-3} $$

^{(see https://math.stackexchange.com/questions/58753/unique-ways-to-keep-n-balls-into-k-boxes )}

Counting the ways to get to finish with adjacent pair in $k$ steps

For the $l$ squares to be distributed in between the stones there are $n-k-l$ squares on the sides which can be split in $n-k-l+1$ ways.

So the number of end situations/states with $k$ stones is:

$$ N_{2states}(k) = \begin{cases} n-1 & \qquad \text{for } k=2 \\ \sum_{l=k-2}^{l=n-k} (k-1) (n-k-l+1) \dbinom{l-1}{k-3} & \qquad \text{for } k>2 \end{cases}$$

$$ N_{3states}(k) = \begin{cases} n-2 & \qquad \text{for } k=3 \\ \sum_{l=k-3}^{l=n-k} (k-2) (n-k-l+1) \dbinom{l-1}{k-4} & \qquad \text{for } k>3 \end{cases}$$

The number ways to end in these states is (such that one of the two adjacent stones or the middle of the three was in the last step):

$$N_{endings}(k) = N_{2states}(k) \cdot 2 (k-1)! + N_{3states}(k) \cdot (k-2)!$$

So the probability to end in $k$ steps is

$$P(k) = \frac{N_{endings}(k)}{n!/(n-k)!}$$

If you would wish to stick a name to this distribution than you could call it a sum of negative binomial distributions (ie. how long it takes before a success/failure), but with varying probabilities each step (success becomes more likely with more stones)

Answer 3

Your second graph looks log-normal to me. See sigma=1, mu=0 here: https://en.wikipedia.org/wiki/Log-normal_distribution.

Can you perform a regression of your data to log normal and report the results?