6
$\begingroup$

Consider the following random process. We have a $10\times 10$ grid. At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker in that grid cell. As soon as we have five contiguous markers in a line (in a row, column, or diagonal), we stop.

I'm given a grid containing some markers in some positions, and I'd like to estimate how long until the process stops if we start from that configuration (i.e., the number of additional time steps until five-in-a-line occurs). I would be happy with any reasonable metric for that: e.g., the expected time until it stops, or the value $t$ such that there's a probability $0.5$ that the process will stop in $\le t$ time steps. I'd be happy with an estimate of any such metric.

Is there any efficient algorithm to estimate this metric, given a configuration where some markers have already been placed? I'm hoping for something faster than random simulation (repeatedly simulating the process and computing an estimate based upon the resulting empirical distribution).

$\endgroup$
  • $\begingroup$ Random simulation would be pretty fast, how fast an algorithm are you hoping for? $\endgroup$ – Yuval Filmus Oct 2 '13 at 7:07
  • 1
    $\begingroup$ When doing random simulation, are you keeping counters for the number of ones per row, column and diagonal? That could speed things up. $\endgroup$ – Yuval Filmus Oct 2 '13 at 7:08
  • $\begingroup$ @YuvalFilmus, that's a good suggestion, I'll try that. How fast? The faster, the better. As far your comment that beating random simulation is going to be tough to beat: fair enough. I realize that beating random simulation might be awfully unlikely.... $\endgroup$ – D.W. Oct 2 '13 at 7:26
  • $\begingroup$ Percolation theory seems to be a relevant field here. The phenomena are quite well understood, I wouldn't be surprised if you find a paper about this somewhere. $\endgroup$ – adrianN Oct 2 '13 at 11:13
  • 1
    $\begingroup$ Here's an idea for something I think is doable and will give approximately the right answer. (1) Figure out how to compute for any specific diagonal, row, or column the probability that adding $k$ markers will give you five in a row. (2) Do this for all the rows, columns, and diagonals of your grid and assume they are all independent processes. $\endgroup$ – Peter Shor Oct 3 '13 at 20:03
2
$\begingroup$

Just for fun, I coded this up in Mathematica. I started with a $10 \times 10$ matrix initialized to all zeros. I then considered two processes throwing darts in the cells: (1) a cell is chosen uniformly and independently at random from the set of all cells, and (2) a cell is chosen uniformly and independently at random from the set of all empty cells. When a dart hits a cell, the value of that cell is set to $1$. A five-in-a-row can appear on a row, column, the diagonal, or on the antidiagonal.

For both processes, I ran $N = 20000$ simulations. Rounded up to the nearest integer, for process (1) we need $65$ dart throws on average to obtain a five-in-a-row. For process (2), the same number was $47$.

This is not exactly what you were asking for, but maybe you can at least compare the numbers you get with mine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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