Randomly colour in the walls of an $n \times n$ grid. How many 1 by 1 squares have all four walls coloured?

26 Views Asked by At

Let's suppose you take an $n \times n$ grid of squares.

Each of these squares has four sides, in total giving a graph with $2n(n+1)$ edges.

Now, suppose you colour each of these edges with probability $p$, and subsequently colour the faces of all the $1 \times 1$ squares which have all four walls coloured in.

Let $X$ denote the number of coloured squares.

Question Is there a closed expression for $\mathbb E(X)$, or an asymptotic expression for this as $n \to \infty$?

Thanks.

(Alternative: Perhaps one can identify the top and the bottom sides, so that the graph of edges lies on the torus.)

1

There are 1 best solutions below

1
On BEST ANSWER

Assuming the edges are colored independently, the chance that any particular square is colored is $p^4$. So by linearity of expectation, the expected number of colored squares, $E(X)$, is $n^2p^4$.