Particle clusters in a random lattice

[sha1000]

TL;DR

I have a probability/combinatorics question about random particles on a grid.

Hello,

Consider a square lattice with total number of sites $N_{\text{tot}}=L^2$.
I place $N_p$ indistinguishable particles uniformly at random on distinct sites
(sampling without replacement).

I am interested in compact fully occupied clusters. For example, in 2D a cluster
of size $s=2$ is a completely filled $2\times2$ square (4 neighboring occupied sites).
More generally, a cluster of size $s$ is a fully occupied $s\times s$ block.

My questions are:

1) What is the expected (average) number of such fully occupied $s\times s$ clusters
as a function of $N_{\text{tot}}$, $N_p$, and $s$?

2) Similarly in 3D, what is the expected number of fully occupied $s\times s\times s$
cubes?

What I tried:

For a $10\times10$ lattice (so $N_{\text{tot}}=100$), consider $s=2$.
There are $(L-s+1)^2=81$ possible positions of a $2\times2$ square.

If $N_p=4$, the total number of ways to choose occupied sites is

$$
\binom{100}{4}.
$$

A specific $2\times2$ square is fully occupied only if all 4 chosen sites fall inside it,
so I estimated the probability as

$$
P \approx \frac{81}{\binom{100}{4}}.
$$

For larger $N_p$ I am not sure how to write the correct general formula,
especially since occupancies are not independent when $N_p$ is fixed.

Any help with the correct expected value, or references to known results, would be
greatly appreciated.

Thank you.

 

[haruspex]

TL;DR: I have a probability/combinatorics question about random particles on a grid.

Hello,

Consider a square lattice with total number of sites $N_{\text{tot}}=L^2$.
I place $N_p$ indistinguishable particles uniformly at random on distinct sites
(sampling without replacement).

I am interested in compact fully occupied clusters. For example, in 2D a cluster
of size $s=2$ is a completely filled $2\times2$ square (4 neighboring occupied sites).
More generally, a cluster of size $s$ is a fully occupied $s\times s$ block.

My questions are:

1) What is the expected (average) number of such fully occupied $s\times s$ clusters
as a function of $N_{\text{tot}}$, $N_p$, and $s$?

2) Similarly in 3D, what is the expected number of fully occupied $s\times s\times s$
cubes?

What I tried:

For a $10\times10$ lattice (so $N_{\text{tot}}=100$), consider $s=2$.
There are $(L-s+1)^2=81$ possible positions of a $2\times2$ square.

If $N_p=4$, the total number of ways to choose occupied sites is

$$
\binom{100}{4}.
$$

A specific $2\times2$ square is fully occupied only if all 4 chosen sites fall inside it,
so I estimated the probability as

$$
P \approx \frac{81}{\binom{100}{4}}.
$$

Ok, but you wrote that you wanted the average number of clusters.
But I am unsure how you are defining that number. With 6 particles in a 2x3 block, is that one 2x2 or two?

For larger $N_p$ I am not sure how to write the correct general formula,
especially since occupancies are not independent when $N_p$ is fixed.

Any help with the correct expected value, or references to known results, would be
greatly appreciated.

Thank you.

I don't see any hope of an exact general solution, but maybe some bounds.
Simplify it a bit to start with. Try s=2, $N_p=5$.

 

[sha1000]

Ok, but you wrote that you wanted the average number of clusters.


I don't see any hope of an exact general solution, but maybe some bounds.
Simplify it a bit to start with. Try s=2, $N_p=5$.

Yes, I am interested in the expected (average) number of such clusters, but I first
tried to understand the probability of forming them

The best approximate expression I obtained (with GPT’s help) is

$$
E_d(k) \approx (L-k+1)^d\,p^{k^d},
$$

where $k$ is the linear size of the cluster (a $k\times k$ block in 2D or
$k\times k\times k$ in 3D), $d$ is the dimension, and
$p = N_p/N_{\text{tot}}$. Here $N_{\text{tot}}=L^d$.
This was presented as a large-$L$ approximation.

However, something feels incorrect to me.

My concern is that two fully occupied
$k\times k$ blocks cannot overlap, and the expression above seems not to account
for this exclusion.

Also, since I am placing exactly $N_p$ particles without replacement, the occupancy
events are not independent. For example, on a $10\times10$ grid with $N_p=4$,
the probability that a particular $2\times2$ square is fully occupied is

$$
\frac{1}{\binom{100}{4}}.
$$

But if I take $N_p=8$, then 2 such squares may appear.

$$
\frac{1}{\binom{100}{8}}\times\frac{1}{\binom{96}{8}},
$$

or is this reasoning wrong? I am not sure if I am describing the problem in undersdanble way.
This is just probabilities. I am not sure how to get to the average nubmer of clusters even if I get the probabilities right.

Thank you in advance.

 

[haruspex]

if I take $N_p=8$, then 2 such squares may appear.

$$
\frac{1}{\binom{100}{8}}\times\frac{1}{\binom{96}{8}},
$$

Looks wrong. You first have to decide how many ways you can pick two non overlapping 2x2 squares, then ask for the probability of choosing exactly the eight points corresponding to one of those pairs.