How to compute the expected value of the number of domains of a given size?

70 Views Asked by At

Given a regular lattice (i.e., a finite set of identical squares - or triangles, or hexagons - stacked next to each other as a large rectangle - or some other shape), each border between cells is randomly removed (with given probability), so now we have domains of different sizes.

What is the expected number of domains of size 1, 2, 3 &c?

PS1. E.g., the simplest non-trivial case is probably this: the lattice is 4 triangles forming a double triangle:

4 triangles

Suppose each of $DE$, $EF$ and $DF$ is removed with probability $p$ (say, $p=\frac13$). What is the expected number of domains of size 1, 2, 3 and 4? (each smaller triangle, e.g., $ADF$ has size 1).

This is solved trivially by brute force, so I am NOT interested in solving it. I am only bringing is as an illustration.

Here is the answer ($r$ is the number of removed borders, $d$ is the domain size):

$$ \begin{array}{|c|c|}\hline & r=0 & r=1 & r=2 & r=3 & \mathbb{E} \\\hline P(r) & (1-p)^3 & 3(1-p)^2p & 3(1-p)p^2 & p^3 & \\\hline d=1 & 4 & 2 & 1 & 0 & 2(1-p)^2(2+p) \\\hline d=2 & 0 & 1 & 0 & 0 & 3(1-p)^2p \\\hline d=3 & 0 & 0 & 1 & 0 & 3(1-p)p^2 \\\hline d=4 & 0 & 0 & 0 & 1 & p^3 \\\hline \end{array} $$

Another simple example is a $2\times2$ square where there are 4 possible internal borders to remove:

$$ \begin{array}{|c|c|}\hline & r=0 & r=1 & r=2(1) & r=2(2) & r=3 & r=4 & \mathbb{E} \\\hline P(r) & (1-p)^4 & 4(1-p)^3p & 3(1-p)^2p^2 & 3(1-p)^2p^2 & 4(1-p)p^3 & p^4 \\\hline d=1 & 4 & 2 & 1 & 0 & 0 & 0 & (1-p)^2(4-p^2) \\\hline d=2 & 0 & 1 & 0 & 2 & 0 & 0 & 2(1-p)^2p(2+p) \\\hline d=3 & 0 & 0 & 1 & 0 & 0 & 0 & 3(1-p)^2p^2 \\\hline d=4 & 0 & 0 & 0 & 0 & 1 & 1 & p^3(4-3p) \\\hline \end{array} $$

PS2. I am interested in methodology rather than in a specific solution for any particular limited case.