¿Cómo calcular la probabilidad de tener al menos un bloque cuadrado de 2X2 del mismo color en un generador de píxeles aleatorio?

Question

Supongamos que tenemos un generador de píxeles aleatorio que tiene una resolución de 10X10 (100 píxeles en total) y cada píxel puede tener 3 colores diferentes. Estoy tratando de calcular la probabilidad de tener al menos un bloque cuadrado de 2X2 del mismo color en esa pantalla .

Esta es mi lógica para dicho cálculo:

1) La probabilidad de que todos los píxeles tengan el mismo color en un bloque cuadrado de 2X2 es 1/27 (3/3^4)

2) La probabilidad de que haya al menos dos colores diferentes en un bloque cuadrado de 2X2 es 26/27 (1-1/27), que es la probabilidad de complemento de (1)

3) Hay 81 diferentes grupos de bloques cuadrados de 2X2 en una cuadrícula de 10X10.

4) La probabilidad de que un bloque cuadrado de 2X2 tenga al menos dos colores diferentes es (26/27)^81 , basado en la probabilidad de complemento.

5) Por lo tanto, la probabilidad de que al menos un bloque cuadrado 2X2 tenga el mismo color es
1-(26/27)^81=95% approximately.

Sin embargo,

-4 píxeles en una cuadrícula de 10X10 que se encuentran en las esquinas (arriba a la izquierda,arriba a la derecha, abajo a la izquierda y abajo a la derecha) pueden ser sólo en un bloque cuadrado de 2X2 cada uno

-Todos los píxeles situados en las partes más externas, excepto estos 4, pueden ser en dos bloques cuadrados diferentes de 2X2 cada uno

-Todos los píxeles restantes dentro de las líneas exteriores pueden ser en cuatro bloques cuadrados diferentes de 2X2 cada uno.

Como he tratado todos los píxeles por igual, no he reflejado la condición anterior en mi cálculo. ¿Cómo puedo reflejar la condición anterior en mi cálculo y tener la probabilidad correcta? ¿Es posible demostrarlo matemáticamente mediante cálculos?

¡Muchas gracias!

Answer 1

Tiendo a creer que no hay una fórmula sencilla para ello, pero se pueden utilizar ideas de la llamada "programación dinámica con perfil" para calcularlo.

Dejemos que $x$ sea el número de coloraciones "malas" (sin ningún color único $2*2$ cuadrados). Claramente la respuesta es $$1-\frac{x}{3^{100}}$$
A continuación, dejemos que $f(n, mask)$ (donde $n \in \{0 .. 9\}$ y $mask \in \{1, 2, 3\} ^ {10}$ , $\{1, 2, 3\}$ se refiere a los colores) sea el número de formas de pintar primero $n+1$ filas para que:
1) No hay ningún color único $2*2$ cuadrado
2) La coloración de la última fila está determinada por $mask$

Claramente $$x = \sum_{mask \in \{1, 2, 3\} ^ {10}}{f(9, mask)}$$

Utilizamos la fórmula recurrente para calcular $f(9, mask)$

Así, $$f(n, mask) = \sum_{mask' \in \{1, 2, 3\} ^ {10}}{f(n - 1, mask') * permitted(mask', mask)}$$ donde $$permitted(mask1, mask2) = \begin{cases} 1, & \text{if $mask2$ painted next to $mask1$ doesn't produce single-colored 2*2 square} \\ 0, & \text{otherwise} \end{cases}$$

y $$f(0, mask) = 1$$ para cualquier $mask$

La fórmula anterior simplemente refleja el hecho de que cualquier coloración del primer $n$ filas es la combinación adecuada de la coloración de la primera $n - 1$ filas y la última, y todo lo que necesita para asegurarse de que la coloración de la última fila (definida por $mask$ ) junto con la coloración de la fila anterior (definida por $mask'$ ) no forman un cuadrado de un solo color.

Si sólo necesitas una fórmula, el trabajo está hecho. Si realmente necesita obtener un número tendrá que esperar un par de horas (o incluso días) esperando que su ordenador haga $10 * 3 ^ {2 *10} \approx 3 * 10^{10}$ operaciones de cálculo de todos estos valores. Tomará un tiempo, pero no es imposible como la toma de fuerza bruta completa $3^{100} \approx 5 * 10 ^ {47}$ que es casi eterna.

Actualización:

Mediante estas fórmulas el número exacto de coloraciones sin un solo color $2*2$ cuadrado es $$34588239301492881803538634375825365877151370240$$ Por lo tanto, la probabilidad es $$\frac{3^{100} - 34588239301492881803538634375825365877151370240}{3^{100}} = 0.9328875670549894$$