# Average time for a tetris field to fill

I have a tetris field, infinitely wide (irrelevant) and N blocks high. Now random blocks start falling down, and I do not move them. For example:

Given that the field is N blocks high, the blocks aren't moved, the blocks fall one block per second and the blocks are the default blocks as seen in the picture (they always "spawn" with the same orientation), how long does it take on average before the game is over?

-
It seems like this problem would require many cases, finding the probability of the cases and calculating the expected time. –  Mark Apr 21 '11 at 12:27
Great to see questions like this! Thanks nightcracker! :) –  quantumelixir Apr 21 '11 at 13:11

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.

-
very rigorous (+1)! now you could go even further and consider that the blocks fall down from the top with a given velocity (say on line per second) and calculate the actual duration (considering that the last lines are faster filled due to the shorter falling way) –  Tobias Kienzler Apr 21 '11 at 12:37
Nice answer! Would you recommend any textbook that teaches probability at this level? –  Mark Apr 21 '11 at 12:42
@Mark: I'm sorry, I don't know any. –  joriki Apr 21 '11 at 12:47
Eehm, a pair of 2 squares increases height by 4 and a pair of a long one and a L increases height by 3. –  nightcracker Apr 21 '11 at 12:58
@nightcracker: My formulation may have been ambiguous. In talking about pairs $(A,B)$ of colours, I was analyzing by how much a block of colour $A$ increases the height when preceded by a block of colour $B$, not about the total height increase due to the pair. –  joriki Apr 21 '11 at 13:02

For a lower boundary, consider the average height of these blocks (assuming as you stated no rotated version is spawned) is (6 x 2 + 1 x 1)/7 = 13/7 = 1.857..., the answer is N/(13/7) = 7N/13, e.g. for N=26 its 14 blocks. This is not exact though, you'll have to include the chances of e.g. a purple block dropping on a red one, yielding a total height of only 3 and so on.

Luckily, only all combinations of two sequential blocks have to be considered, since without rotations only the blue and purple blocks following white&yellow or red blocks respectively can result in a merged line and it's not possible that any three block combination merges any further. That's 3 out of 7² two-block combinations, the average height of all two-block combinations has therefore to be corrected from 13/7 to (13/7 x 7² - the 3 lines counted too much) / 7², = 88/49 ≈ 1.796. So now the correct result is 49N/88, for N=26 that's 14.477 blocks.

-
That's incorrect -- more comprehensive answer to follow... –  joriki Apr 21 '11 at 12:09
Clearly if you have a white followed by a blue block you only gain 1 block of height with the blue block –  Alexander Thumm Apr 21 '11 at 12:10
@joriki: @Alexander thanks, I didn't consider these first... –  Tobias Kienzler Apr 21 '11 at 12:12
@Alexander, @joriki: corrected –  Tobias Kienzler Apr 21 '11 at 12:21