# Generalization: (The "number" of) smaller sized clusters in large random binary matrices follow a descending order. Why?

This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix?

In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of size $1$ clusters in a random matrix are always greater than the number of sizes $2$ clusters in large $N\times N$ matrices (for any $p\in (0,1)$). From my data files, it also seems that the number of sizes $2$ clusters will be greater than the number of size $3$ clusters for all $p\in (0,1)$. That is, at least for the first few natural numbers $n$, the number of clusters of size $n$ is greater than the number of clusters of size $n+1$. Around the site percolation threshold $p=0.407$ there seem to be some fluctuations, however, still, for the first few natural numbers, the cluster sizes continue showing the above trend.

So, my question basically is: Is it possible to generalize the above trend? If yes, up to which natural number $n$ can it be generalized, and why?

P.S:

This sounds a bit like some kind of graphic Benford's law.

I'm not sure if Benford's law is somehow applicable in this situation. However, I'd be interested to hear if someone has any idea regarding this.

I don't see that it has anything to do with Benford's law. That has to do with the frequency of $k$ as the leading digit for lists of a certain sort, like the heights of 100 mountains measured in feet, or inches or meters (in base $10$ one expects $k$ to occur $\log(k+1)-\log(k)$ where the logs are base $10$ so $2$ appears only about $55\%$ as often as $1.$

Note that the result you claim will fail for $p=1$ and also, for an $N \times N$ board, if $p \gt 1-\frac{1}{N^2}.$ Then over $90\%$ of the time there are $0,1$ or $2$ white cells so for sure there is a single huge black cluster. There is, for a $1000 \times 1000$ board some critical probability $p_1$ above which your phenomenon fails. Your calculations support $0.99 \lt p_1.$ I found that pretty surprising! I'm saying $p_1 \lt 0.999999.$ If forced to guess, I would predict $p_1 \sim 1-\frac1{4N}=0.99975$ . If you want to experiment, then I would increase the number of runs to $10000$ but only fill in the cells on the edge and one in. Try $p=0.999$ then, if the phenomenon holds, $0.9995$ and then $0.9999.$ There is a probability of $pq^3$ at the four corners and of $pq^5$ at any one of the $3992$ other edge cells to be a single cell black cluster.

It is clear that in the one dimensional situation the phenomenon you describe occurs for an appointment nfinite strip (see my revised proof.)

Actually for a very long $2 \times N$ rectangle size $2$ will on average beat size $1$ for $p \gt 0.5.$ So the previous result does not immediately explain the two dimensional case. I'd predict that in the infinite 2D case any of not $0$ or $1$ suffices in a certain sense.

An analysis for size $3$ should be possible.

• "Note that the result you claim will fail for $p>1-\frac{1}{N^2}$"? Could you please explain the proof for that?
– user125648
Jul 28, 2018 at 14:56
• Does that "the result you claim will fail for $p>1-1/N^2$" also hold for $N\times N$ matrices?
– user125648
Jul 28, 2018 at 15:12
• That's what the answer is claiming. Think about why the clusters don't behave as you predicted when $p$ is so close to $1$. Jul 29, 2018 at 10:08
• Just to give some motivation to the comment of mine the OP refers to : the distribution of leading digits in Benford's law is scale-invariant, and it seems the OP observed some similar phenomenon in the problem he's considering. Jul 29, 2018 at 19:47
• That makes sense Jul 30, 2018 at 8:22