# expectation value of connected areas

• May 6th 2007, 12:06 AM
cornail
expectation value of connected areas
Hi!

The problem is the following:
We have an N-by-N square matrix of zeros. We turn M random elements of the matrix into 1-s. I need a closed formula for the expectation value of the number of connected 1-areas in the matrix (it is especially important, how it depends on M).
An element is connected to another, when it is in its 8-neighborhood in the matrix. (If it is easier to calculate for a 4-neighborhood, then we can go with that one...). So eg.

0 0 0
0 1 0
0 0 1

These two 1-s are connected in an 8-neigborhood-way.
In the following example, there are 2 connected areas:

0 0 0 1 1 0
0 0 0 0 1 0
0 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0

I weren't able to solve this problem myself. Do you think there is a chance to obtain an analytic formula for this? I have already run simulations in MATLAB, here is the result:
http://server6.pictiger.com/img/5041...8c7ba29.th.png
http://server6.pictiger.com/img/50412/other/expectation-value-of-connected-areas.php][IMG]http://images6.pictiger.com/thumbs/29/e4054ec690b745ccc2e6999648c7ba29.th.png