Average size of connected components in grid

[mXSCNT]

Start with an infinite 2d grid of cells, with each cell randomly colored black or white (50% chance). Now take the graph G whose nodes are the cells, and with an edge (A, B) if A and B are adjacent in the grid, and the same color.

What is the average size of a connected component of G? Is it finite, or infinite?Specifically, let's say you have an nxn grid. G(n) is the graph whose nodes are the cells with an edge (A, B) if A and B are adjacent in the grid and the same color. Let f(n) be the expected number of connected components in G(n), so that \frac{n^2}{f(n)} is the expected average size of connected components in the grid. Find \lim_{n \rightarrow \infty} \frac{n^2}{f(n)}

 

[Stephen Tashi]

If we consider a row in the grid, it has a certain number of "runs" in it. My intuition is that there are no more connected components in the whole grid than there are total runs in its rows. Does the expected total number of runs in the rows provide any useful upper bound for the expected number of connected components?

 

[mfb]

Just for clarification: "Adjacent" means "same column, row differs by 1 OR same row, column differs by 1"? So each cell has 4 adjacent cells.

My intuition is that there are no more connected components in the whole grid than there are total runs in its rows.

If that is true and I understand it correctly, the number of connected components grows just linearly with n, and the fraction components/tile goes to zero.

It is easy to find an upper bound for the average size (=lower limit for the components per tile): Consider non-overlapping 3x3 subgrids. Each subgrid has a probability of 1/16 to have an isolated cell in the middle. With a better pattern, you can get a "cross" every 6 tiles. Therefore, the maximal average size (as defined in post 1) is at most 16*6=96.

 

[mXSCNT]

Just for clarification: "Adjacent" means "same column, row differs by 1 OR same row, column differs by 1"? So each cell has 4 adjacent cells.

Yeah

If that is true and I understand it correctly, the number of connected components grows just linearly with n, and the fraction components/tile goes to zero.

It is easy to find an upper bound for the average size (=lower limit for the components per tile): Consider non-overlapping 3x3 subgrids. Each subgrid has a probability of 1/16 to have an isolated cell in the middle. With a better pattern, you can get a "cross" every 6 tiles. Therefore, the maximal average size (as defined in post 1) is at most 16*6=96.

Cool! I should have thought of that.

I ran a simulation and got around 7.6 for average component size (random grids of 3000 x 3000). For grids of 300x300 it was 7.5-7.6 so it does seem to be roughly constant.