5
$\begingroup$

Question: How the maximal height grows for random Tetris like blocks falling down ? Numeric simulation (see below) shows leading term is linear with some constant depending on shapes of blocks allowed. Can the constant be calculated ? Can the subleading term like $h(T) = a T + b T^p + ...$ be found ( similar to "sticky disks" = "ballistic deposition" model where $p=1/3$) ?

Background: Considerable research interest attracted models like "Ballistic Deposition" where blocks randomly fall down and glue to neighbors. See MO Tetris-like falling sticky disks, youtube video from 36 second for illustration, Borodin's lectures, I. Corwin Notices 2016 Kardar-Parisi-Zhang Universality etc...


Numeric simulation 1. (Horizontal blocks) Consider horizontal blocks of fixed length $n$ falling down into the "box" (playing field in Tetris) of horizontal size $L$. The model has only two parameters (n,L) and n<=L. One uniformly generates random position (horizontal position x = 1... (L-n+1)) of the block and it falls down straight vertically. The heap of blocks grows - like in Tetris and we are interested in maximal height. In contrast to Tetris to simplify things let us forget about burning out the fully packed raws.

We are interested in height growth depending on number $T$ of fallen blocks: $$ h(T) = a T + ... $$ where constant $a$ depends on $(n,L)$. It is clear that for $n>L/2$, $a(n,L)=1$. Numeric estimation for $a(n,L)$ are given in table 1 below. It seems plausible that for $k=1$, $a(1,L) = 1/L$; and $a(n,L) = 2n/L + ...$.

It would be interesting to find subleading terms $h(T)$, however from numeric simulation it seems there is no reasonable term.

Numeric simulation 2. Young diagrams Consider Young diagrams for some fixed $n$ falling down into the "box" (playing field in Tetris) of horizontal size $L$. Let us use English notation for diagrams. The model has only two parameters (n,L) and n<=L. One uniformly generates random position of the block in horizontal direction and it falls down straight vertically (horizontal position is UNchanged).

Again we are interested how the height grows : $$ h(T) = a T + ... $$ where constant $a$ depends on $(n,L)$. Numeric similation results given in the table 2 below.


Table 1: Constant $a(n,L)$ for falling horizonal blocks of size $n$ and $L$ is horizontal size of "playing field".

Simulation number T= 200000

       n\L   10.0000   20.0000   50.0000   80.0000  100.0000
    1.0000    0.1014    0.0508    0.0207    0.0129    0.0106
    2.0000    0.3808    0.1975    0.0803    0.0508    0.0408
    3.0000    0.6100    0.3276    0.1349    0.0843    0.0679
    4.0000    0.7999    0.4486    0.1875    0.1188    0.0952
    5.0000    0.9510    0.5651    0.2404    0.1521    0.1227
   10.0000    1.0000    0.9847    0.4923    0.3167    0.2562
   25.0000    1.0000    1.0000    0.9972    0.7424    0.6181
   40.0000    1.0000    1.0000    1.0000    0.9989    0.8956
   50.0000    1.0000    1.0000    1.0000    1.0000    0.9993

Table 2: Constant $a(n,L)$ for falling Young diagrams (English notation), $n$ is Young diagrams's $n$ and $L$ is horizontal size of "playing field".

Simulation number T= 500000

    n\L   10.0000   20.0000   50.0000   80.0000  100.0000
 1.0000    0.1005    0.0508    0.0203    0.0130    0.0104
 2.0000    0.3643    0.1876    0.0763    0.0478    0.0381
 3.0000    0.6663    0.3491    0.1427    0.0895    0.0719
 4.0000    0.8899    0.4728    0.1942    0.1226    0.0977
 5.0000    1.3263    0.7220    0.2998    0.1891    0.1512
 6.0000    1.6307    0.9046    0.3772    0.2387    0.1913
 7.0000    2.0022    1.1360    0.4767    0.3015    0.2420
 8.0000    2.3123    1.3349    0.5675    0.3591    0.2872

There are several other questions on Tetirs here and on MSE: MO Is there winning strategy in Tetris ? What if Young diagrams are falling?, MSE The Mathematics of Tetris, MSE Mathematics of Tetris 2.0, MSE An impossible sequence of Tetris pieces, but they seems to discuss different sides of the game.

It would be natural to ask what will happen with the height growth if Tetris rule: burning out the fully packed raws is introduced... It might be next question ...

$\endgroup$
  • $\begingroup$ The post you cited, Tetris-like falling sticky disks, also sees linear growth. The connection to KPZ universality may be especially relevant. $\endgroup$ – Joseph O'Rourke Aug 31 '17 at 18:20
  • 1
    $\begingroup$ @JosephO'Rourke Yes, agree. I justed wanted to say that in "sticky disks" they see MORE - they see subleading term $T^{1/3}$ - but unforturatenly I do not see ... The reason is not clear for met - may be I am just doing tooo small number of similations ? or may be models without gluing are too simple to show KPZ like behaviour ? (I am afraid the second option is true). $\endgroup$ – Alexander Chervov Aug 31 '17 at 18:25
5
$\begingroup$

This model is known as "Random Walk in Heap Monoids", see Chapter 5 of Vincent Jugé's PhD thesis and the references therein. The law of large numbers, as usually, follows from Kingman's subadditive theorem. A calculation of the rate of growth amounts to finding the limit distribution on infinite heaps. However, I am not sure to what extent it can be made explicit (cf. Abbes-Mairesse). As for the sublinear term, I would still expect the central limit theorem to hold.

$\endgroup$
  • $\begingroup$ Thank you very much ! However it is not clear for me the relation of those monoids with Tetris like ... $\endgroup$ – Alexander Chervov Sep 8 '17 at 19:05
  • 1
    $\begingroup$ OK - so let me be more formal. You have a finite set $S$ (the bottom of tetris cylinder) and a finite collection of functions ("tetris pieces") $f:S\to\mathbb Z_+$. I presume that the pieces fall vertically, so that the horizontal translates of the same shape correspond to different functions above. The monoid operation consists in letting the pieces drop one by one until they reach the lowest possible position. Usually the "heap people" consider just 0,1 valued functions (pieces of height one linked horizontally) as pieces, but this assumption is not really necessary. $\endgroup$ – R W Sep 8 '17 at 20:26
  • $\begingroup$ @R W Thank you ! But still it is not quite clear why such interpretation is useful is there any result like those on famous "sticky disks" ? Or may be cancelation propert in Tetris can be related to product of elements equal to identity? $\endgroup$ – Alexander Chervov Sep 10 '17 at 19:04
  • $\begingroup$ Oops - my bad - are you talking about the "real tetris" so that if a row is filled then it disappears? This feature is indeed missing in the heap theory. However, I still believe that the heap technique should be applicable here - with some modifications though. $\endgroup$ – R W Sep 10 '17 at 21:38
  • $\begingroup$ No, no, you made no mistake -- my question, was about NON real Tetris - without cancellation, just it came to mind that monoid language can treat cancelation - just imposing some products to be identity ... $\endgroup$ – Alexander Chervov Sep 11 '17 at 19:42

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.