Consider a random walk on the 2-d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i-1, j), (i+1, j), (i, j-1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. These four points will form one of the five free tetrominoes ("free" means considering rotations and mirror images to be the same).  For each tetromino find the probability that it will be the one formed in this way.

Source: IBM Ponder This, December 2008

Solution

In order of increasing probability,

P(I) = 2/21,
P(T) = 3/21,
P(O) = 4/21,
P(S) = 4/21, and
P(L) = 8/21

Consider the possible "animals" that are formed on the way to becoming tetrominoes.  Initially, there is a single-celled animal, and then no matter which direction the walk moves, a two-celled animal is created, and you're standing in one of the two cells.  From there, the walk stands a 25% chance of staying the same, if it happens to move into the other cell.  Or the walk stands a 50% chance of becoming an L triomino, because there are two directions that will cause that to happen.  Or the walk stands a 25% chance of becoming an I triomino, which happens only if he continues in the same direction for one more step.  Each blue arrow represents a 25% probability of the walk transitioning to another state.  In each case, the "X" marks the spot where the walk finds itself, which is necessary to distinguish among possible states of the walk as it progresses.  The final states are the tetrominoes, which are colored red.

In order to calculate the probability of each final state, we model the transitions as a superposition of the probabilities of the states, using an iterative process.  Initially, the probability 1 is assigned to the single-celled animal, and 0 is assigned to all the other states.  At each iteration, one quarter of the probability value of each state is "poured" out of that state, following a blue arrow, and into the next state indicated by the arrow.  For example, at each iteration, the "I" triomino with the walker situated at the end receives a quarter of the probability value previously held by the domino plus half of the probability value previously held by the "I" triomino with the walker situated in the middle.

The final states, colored red, inherit not only the probability values assigned to them by the blue arrows, but also keep their previous probability values, because the walker stops walking when he reaches a final state.  In this way, with each iteration, the probability values "drain out" of the smaller animals, and into the tetrominoes.  After twenty iterations, all but a billionth of the probability value will have drained into the final states.  (Think about it: it would be a highly unlikely fox-trot that would keep the animal so small!)  At this point, we simply observed the probability values of the five final states, and marked them in green.

Here is the Excel spreadsheet that shows the result, with all probability values scaled by the denominator, 21:

	A	B	C	D	E	F	G	H	I	J	K
1
2	21	0	0	0	0	0	0	0	0	0	0
3	0	=A2+B2/4	=B2/2+D2/2	=C2/4	=B2/4+F2/2	=E2/4	=D2/2+F2/2+G2	=E2/4+H2	=C2/4+E2/2+I2	=C2/4+J2	=C2/4+K2
4	0	5.25	10.5	0	5.25	0	0	0	0	0	0
5	0	1.3125	2.625	2.625	1.3125	1.3125	0	1.3125	5.25	2.625	2.625
6	0	0.32813	1.96875	0.65625	0.98438	0.32813	1.96875	1.64063	6.5625	3.28125	3.28125
7	0	0.08203	0.49219	0.49219	0.24609	0.24609	2.46094	1.88672	7.54688	3.77344	3.77344
...	...	...	...	...	...	...	...	...	...	...	...
39		4.44692E-21	2.33146E-15	2.33146E-15	1.16573E-15	1.16573E-15	3	2	8	4	4
40		1.11173E-21	1.16573E-15	5.82865E-16	5.82865E-16	2.91432E-16	3	2	8	4	4

More about this puzzle

Joe Riel emailed me to offer an extension of this puzzle to more (or fewer) than just 2 dimensions.

In two dimensions, the tetrominoes are called I, L, O, S, and T for the shapes , , , , and , respectively.  When three or more dimensions are considered, two additional shapes are added: Let u, v, and w be three orthogonal unit vectors.  Then the Y-shape corresponds to connecting all their tails together, while the 2-shape corresponds to connecting them head to tail.  So the Y-shape is like the T-shape, except the three neighbors of the central cell go off in three different dimensions.  Similarly, the 2-shape is like the S-shape, except the two ends go off in two different dimensions, each different from the dimension defined by the two central cells.

The relevant probabilities are

P(I) = n/D,

P(T) = 3(n-1)/D,

P(Y) = 2(n-1)(n-2)/D,

P(O) = 2n(n-1)/D,

P(S) = 2n(n-1)/D,

P(L) = 4n(n-1)/D,

P(2) = 4n(n-1)(n-2)/D,

with D = (2n²-1)(2n-1).

The formulae are valid for n > 0, and are listed in order of increasing probability if n>3.  The I shape is one-dimensional; the T, O, S, and L shapes are two-dimensional and look like their names; and the Y and 2 shapes are three dimensional.  All seven of these 1-, 2-, and 3-dimensional animals live in n-dimensional space.

Sanity check: If a shape requires more than n dimensions, then the formula correctly gives the probability of forming that shape as zero. For n=1 dimension, the formulae give P(I)=1; for n=2 dimensions, the formulae give the numbers listed at the top of this page; moreover, I verified that for all n>0, P(I)+P(T)+P(Y)+P(O)+P(S)+P(L)+P(2)=1.

Internet references

IBM Ponder This puzzle: December, 2008

Related pages in this website

Polyominoes enumerates and classifies polyominoes by their bilateral and rotational symmetries, and the size of the smallest rectangle that encloses them.

Tetris enumerates the ways to tile an n-by-n square by one-sided n-polyominoes

The webmaster and author of this Math Help site is Graeme McRae.