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).
Estimating the time until we obtain five-in-a-row?
algorithms;combinatorics;probability theory;approximation