Expected number of same-colour regions in a tiled floor

Question

Suppose we have a rectangular floor, $a$ units long by $b$ units wide, which we need to tile with black and white unit square tiles. We flip a coin to decide whether the first tile will be black or white, and lay it down in the top left corner. The second and all subsequent tiles will also have a 50-50 chance of being black and white.

A 'region' is defined as a contiguous area of same-colour tiles, touching each other by their sides (just a corner is not enough). Thus, the maximum number of regions possible is $ab$ (checkerboard tiling), while the minimum number is 1 (the whole floor is either black or white).

What is the expected number of regions on the board, as a function of $a$ and $b$?

Answer 1

In the case of a checkerboard, the number of regions is simply $ab$.

When two adjacent squares are of the same colour, this reduces the number of regions by 1. There are $a$($b$-1) + $b$($a$-1) total possible connections between two adjacent squares. For any given pair of adjacent tiles, there is a 50% chance that they are the same colour. Consequently, the expected number of connections is simply $ab$ - ($a$+$b$)/2. We now subtract this from the total number of tiles. Thus, the expected number of regions is ($a$+$b$)/2 .

However, consider the case when a 2*2 square of 4 tiles are all the same colour. Here, there are 4 tiles and 4 same-color connections between adjacent tiles. However, the number of regions is not 4-4=0, but rather, it is 1. Consequently, for every same-colour square that appears, we need to add 1 to the count of regions. For any given 2*2 square, there is a 1/8 chance that all tiles are the same colour. There are ($a$-1)($b$-1) total squares, so an expected value of ($a$-1)($b$-1)/8 same-colour squares.

Putting the pieces together, the expected number of regions simplifies to: (($a$+3)($b$+3)/8) - 1.

Answer 2

At first I won't take the edges into account. Suppose the board wraps around, in a torus shape.

The expected number of 1-square regions is $ab/2^4$ because all four edges must be the opposite colour.

The expected number of vertical dominoes is $ab/2^7$, as the six edges and one internal match must be correct. So is the number of horizontal dominoes, so that gives $2ab/2^7$ 2-square regions.

For triominoes, there are eight edges and two internal lines. The L triomino has four orientations, and the I triomino has two, so you get $6ab/2^{10}$ three-square regions.

For tetrominoes, I get $18ab/2^{13}$. The square contributes $ab/2^{12}$, and the others various multiples of $ab/2^{13}$.

The total looks like $$ab\left[\frac1{16}+\frac2{128}+\frac6{1024}+\frac{18}{8192}+\cdots\right]$$

So it looks like only a small portion of the area - say, a quarter - is covered with small regions.

You get a rectangle from a torus by cutting along a horizontal line and a vertical line to make the edges. Some of these polynomials are cut into two pieces. That gives an extra $$(a+b)\left[\frac0{16}+\frac1{128}+\frac6{1024}+\frac{23}{8192}+\cdots\right]$$ Some polyominos, including the U-pentomino, are cut into three or more pieces. Also, the square tetromino and P-pentomino can be cut into four pieces if they end up at all four corners of the rectangle.