Número esperado de racimos en tablero de ajedrez

Question

Plazas distintas de N se seleccionan uniformemente al azar en un tablero de ajedrez de MxM, ¿cuál es el número esperado de racimos? Un cluster es una colección de cuadrados conectados lateralmente, no perpendicular.

Answer 1

Como @Henry se ha mencionado, una simulación le dará una idea de la naturaleza de esta función. En la pequeña N, se espera que la función a ser aproximadamente lineal. Como N se hace grande, la teoría de la percolación da el resultado de que habrá un único gran grupo, aunque no excluye la posibilidad de que los más pequeños, desvinculados de grupos. Trazada por debajo es una simulación con 5000 ensayos para un estándar de tablero de ajedrez de 8x8 para cada posible valor de N. La media es una línea sólida, mientras que una desviación estándar se muestra como una sombra de la curva.

El código para producir la imagen que se muestra a continuación para la reproducibilidad:

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()