Expected number of clusters on chessboard

Question

N distinct squares are selected uniformly at random on an MxM chessboard, what is the expected number of clusters? A cluster is a collection of squares which are connected sideways, not cornerwise.

Answer 1

As @Henry mentioned, a simulation will give you insight into the nature of this function. At small N, we expect the function to be roughly linear. As N gets large, percolation theory gives the result that there will be a single large cluster, though it doesn't preclude the possibility of smaller, unconnected clusters. Plotted below is a simulation with 5000 trials for a standard 8x8 chessboard for each possible N value. The mean is a solid line while one standard deviation is shown as a shaded curve.

The code to produce the image is shown below for reproducibility:

import random
import numpy as np
from scipy.ndimage.measurements import label
M = 8
A = np.zeros([M,M],dtype=bool)
indices = list(np.ndindex(A.shape))

trials = 5000
N_test,C_mean,C_std = range(M**2), [], []

for n in N_test:
    cx = []
    for _ in xrange(trials):
        A[:,:] = False
        A[ zip(*random.sample(indices, n)) ] = True
        clusters = label(A)[-1]
        cx.append(clusters)
    cx = np.array(cx)
    C_mean.append(cx.mean())
    C_std.append(cx.std())
C_mean = np.array(C_mean)

import pylab as plt
import seaborn as sns
plt.plot(N_test, C_mean)
plt.fill_between(N_test, C_mean-C_std, C_mean+C_std,alpha=.2)
plt.title("Average number of clusters on {M}x{M} chessboard".format(M=M))
plt.xlabel("squares choosen")
plt.ylabel("clusters")
plt.axis('tight')
plt.show()