Sizes of connected components from a random choice in a grid

Question

This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares.

The result is a kind of maze in the 45° rotated grid of $\sqrt2 \times \sqrt2$ squares (which I'll now consider as new unit cells $-$ more precisely, the grid cells would be in fact $\frac{\sqrt2}2 \times \frac{\sqrt2}2 $, as the width of the labyrinth paths is $\frac{\sqrt2}2 $). I was wondering about the sizes of the connected components of such a labyrinth, and so I took Joseph O'Rourke's sample illustration and colored everything bigger than $1 \times 1$ and $1 \times 2$, which yields the following outcome:

For the two light blue regions and the big pink one between them, I have cheated a bit in coloring, as all three have tiny "leaks" into the infinite (yellow) part outside. In a strict sense, those three big regions would have to be yellow, but I think it makes sense to consider the infinite part as essentially linked to boundary effects only.
Asking about the average area of a connected region for big $n$ may thus be an ill-defined question, and even if we only consider the "completely interior" components (i. e. here all red, green, dark blue and white ones), I guess that such a question is way too hard to be feasible. But the following should be rather easy, as it only concerns local neighborhoods:

• What is the average proportion of components consisting of a $1 \times 1$ cell (not among all components, rather as a fraction of $n^2$, neglecting boundary effects) ?
• Same question for $1 \times 2$ components.

Of course, the probability to obtain such a unit component inside a given $2 \times 2$ subsquare of the original grid is simply $\frac1{16}$, but we cannot conclude from this that there are a total of $\frac{n^2}{32}$ (or $\frac{n^2}{16}$?) of them in average, as the $2 \times 2$ subsquares of the original grid can overlap. It may just need a simple inclusion-exclusion approach, but I don't see how, especially for the $1 \times 2$ components.

Answer 1

There are many interesting questions here, and one can probably answer some asymptotically, e.g. the tail behavior of the size of the connected component assuming it is finite (i.e., probability that the diameter is larger than $L$ for $L$ large, conditioned on being finite), or the question of percolation i.e is there a positive probability that the cluster of the origin is infinite (the cluster contains by coupling the percolation cluster of $p=1/2$ bond percolation on the 2D lattice, which is finite a.s., so I do not see a simple domination argument).

However the specific question you asked is indeed I believe easier. Here is an attempt.

Edit: Note that the question "is a vertex the center of a component of size 1" has a simple answer - it is $p_1=(1/2)^4$ (since it is determined by the neighboring squares, i.e. by 4 independent diagonals). Now apply the ergodic theorem to conclude that the asymptotic fraction of such squares is $p_1$. The reason this does not answer your question is that you asked for the asymptotic number of components, but it does give a lower bound on the fraction you asked about.

To get the answer to your question, repeat the computation for all 2x1 components, 3x1, 3x2, etc that contain the origin. That is, for a shape $Q$, compute $p_Q=P(C(0)\sim Q)$ where $C(0)$ is the shape containing $0$ and $\sim$ is up to translation of the shape. Then the events in the definition of $p_Q$ are disjoint, and $\sum p_Q\leq 1$. Now the fraction you ask about is $p_1/\sum_Q(p_Q/|Q|)$, where $|Q|$ is the number of vertices contained in the interior of $Q$.

(Former version, which looked at a somewhat different notion of component and answered a different notion of component, had: Note that the question "is the square A having (0,0) and (1,1) as vertices a component" has a simple answer - it is $p_1=(1/2)^{6}$ (since it is determined by the neighboring squares, and for a given orientation of the diagonal in $A$, only 6 of these neighbors are relevant).