Average time for a tetris field to fill

There are $7$ different kinds of blocks. The height of the stack will generally increase by $2$ in each step, but only by $1$ in the following cases: A green block preceded by any block; a purple block preceded by a red block; and a blue block preceded by either a yellow or a gray block. I'll treat the events of certain pairs following each other as independent; they're not, but it doesn't make a difference for the average height after time $t$ (by linearity of expectation) and only a small difference for the average time $t$ for height $N$.

So we have $49$ different pairs that are assumed to occur with equal and independent probabilities of $1/49$; for $1\cdot7+1\cdot1+1\cdot2=10$ of these pairs the second block increases the height by $1$, and for $49-10=39$ of them by $2$. Thus the average height after time $t$ will be $\frac{10+2\cdot39}{49}t=\frac{88}{49}t$. A good estimate for the average time to reach height $N$ is therefore $\frac{49}{88}N$. But we can be a bit more precise than that.

The average time $t_N$ to reach height $N$ satisfies:

$$t_N=\frac{10}{49}t_{N-1}+\frac{39}{49}t_{N-2}+1\;,$$ since there is a probability of $\frac{10}{49}$ that the next step will have height $N-1$ left and a probability of $\frac{39}{49}$ that it will have height $N-2$ left, and in either case the current step takes time $1$.

We can solve this inhomogeneous linear recurrence relation by adding a specific solution of the inhomogeneous relation to the general solution for the homogeneous relation and then imposing initial conditions. We can guess a specific solution for the inhomogeneous relation from our earlier estimate: It is simply $t_N=\frac{49}{88}N$. For the general solution of the homogeneous equation, we have to solve the characteristic equation

$$\lambda^2-\frac{10}{49}\lambda-\frac{39}{49}=0\;,$$

with solutions

$$\lambda_{1,2}=\frac{5\pm\sqrt{1264}}{49}\;,$$ $$\lambda_1\approx 0.8276, \lambda_2\approx -0.6235\;.$$

Then the general solution of the inhomogeneous relation is

$$t_N=\frac{49}{88}N+c_1\lambda_1^N+c_2\lambda_2^N\;.$$

The initial conditions are $t_0=0$ (if there is no height left, the game is over) and $t_1=10/49$ (if there is only one row left, the game is over unless the next block only increases the height by $1$, with probability $10/49$). Substituting these into the general solution yields

$$c_2=-c_1=\frac{10-49^2/88}{\sqrt{1264}}\approx 0.2431\;.$$

Thus, the correction terms proportional to $c_1$ and $c_2$ are quite small to begin with and die off quickly, so by the time the height reaches $N$ the result is well approximated by the initial estimate $t_N=\frac{49}{88}N$. The height in the image seems to be $N=20$, so this would lead to an average time $t_N=\frac{245}{22}\approx11.1$ until the game is over.

Tags:

Probability