Tiempo medio de llenado de un campo de tetris

Question

Tengo un campo de tetris, infinitamente amplio (irrelevante) y N bloques de altura. Ahora empiezan a caer bloques al azar y no los muevo.

Dado que el campo es N bloques de altura, los bloques no se mueven, los bloques caen un bloque por segundo y los bloques son los predeterminados (siempre "aparecen" con la misma orientación), ¿cuánto tiempo tarda de media antes de que el juego termine?

Answer 1

Hay $7$ diferentes tipos de bloques. La altura de la pila generalmente aumentará en $2$ en cada paso, pero sólo por $1$ en los siguientes casos: Un bloque verde precedido por cualquier bloque; un bloque morado precedido por un bloque rojo; y un bloque azul precedido por un bloque amarillo o un bloque gris. Trataré los eventos de ciertos pares que se suceden como independientes; no lo son, pero no hay diferencia para la altura media después del tiempo $t$ (por linealidad de la expectativa) y sólo una pequeña diferencia para el tiempo medio $t$ para la altura $N$ .

Así que tenemos $49$ pares diferentes que se supone que ocurren con probabilidades iguales e independientes de $1/49$ para $1\cdot7+1\cdot1+1\cdot2=10$ de estos pares el segundo bloque aumenta la altura en $1$ y para $49-10=39$ de ellos por $2$ . Por lo tanto, la altura media después del tiempo $t$ será $\frac{10+2\cdot39}{49}t=\frac{88}{49}t$ . Una buena estimación del tiempo medio para alcanzar la altura $N$ es por lo tanto $\frac{49}{88}N$ . Pero podemos ser un poco más precisos que eso.

El tiempo medio $t_N$ para alcanzar la altura $N$ se satisface:

$$t_N=\frac{10}{49}t_{N-1}+\frac{39}{49}t_{N-2}+1\;,$$ ya que existe una probabilidad de $\frac{10}{49}$ que el siguiente paso tendrá altura $N-1$ izquierda y una probabilidad de $\frac{39}{49}$ que tendrá altura $N-2$ a la izquierda, y en cualquiera de los casos el paso actual toma el tiempo $1$ .

Podemos resolver esta relación de recurrencia lineal inhomogénea añadiendo una solución específica de la relación inhomogénea a la solución general de la relación homogénea e imponiendo después condiciones iniciales. Podemos adivinar una solución específica para la relación no homogénea a partir de nuestra estimación anterior: Es simplemente $t_N=\frac{49}{88}N$ . Para la solución general de la ecuación homogénea, tenemos que resolver la ecuación característica

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

con soluciones

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

Entonces la solución general de la relación no homogénea es

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

Las condiciones iniciales son $t_0=0$ (si no queda altura, se acaba el juego) y $t_1=10/49$ (si sólo queda una fila, el juego se acaba, a menos que el siguiente bloque sólo aumente la altura en $1$ , con probabilidad $10/49$ ). Sustituyendo esto en la solución general se obtiene

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

Así, los términos de corrección proporcionales a $c_1$ y $c_2$ son bastante pequeños al principio y mueren rápidamente, por lo que cuando la altura alcanza $N$ el resultado se aproxima bien a la estimación inicial $t_N=\frac{49}{88}N$ . La altura en la imagen parece ser $N=20$ , por lo que esto llevaría a un tiempo medio $t_N=\frac{245}{22}\approx11.1$ hasta que el juego termine.

Answer 2

Para un límite inferior, considera que la altura media de estos bloques (suponiendo que, como has dicho, no se genere una versión rotada) es (6 x 2 + 1 x 1)/7 = 13/7 = 1,857..., la respuesta es N/(13/7) = 7N/13, por ejemplo, para N=26 son 14 bloques. Sin embargo, esto no es exacto, ya que hay que tener en cuenta las posibilidades de que, por ejemplo, un bloque morado caiga sobre uno rojo, lo que daría una altura total de sólo 3, y así sucesivamente.

Por suerte, sólo hay que tener en cuenta todas las combinaciones de dos bloques secuenciales, ya que sin rotaciones sólo los bloques azules y morados que siguen a los blancos y amarillos o a los rojos, respectivamente, pueden dar lugar a una línea fusionada y no es posible que ninguna combinación de tres bloques se fusione más. Son 3 de 7² combinaciones de dos bloques, por lo que la altura media de todas las combinaciones de dos bloques debe corregirse de 13/7 a (13/7 x 7² - las 3 líneas contadas de más) / 7², = 88/49 ≈ 1,796. Así que ahora el resultado correcto es 49N/88, para N=26 que son 14,477 bloques.