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

Supongamos que tenemos un generador de píxeles aleatorios 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 .

Aquí está mi lógica para tal cálculo:

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

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

3) Hay 81 grupos diferentes 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 , según la probabilidad del complemento.

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

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) solo pueden estar en un bloque cuadrado de 2X2 cada uno

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

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

Como traté todos los píxeles por igual, no reflejé 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 esto matemáticamente posible de demostrar a través de cálculos?

¡Muchas gracias!

No puedo responder a su pregunta, pero modelar esto da una probabilidad de aproximadamente 93.3 %
¡Gran pregunta! Solo una nota: 4 / 3 4 = 4 / 81 ≠ 1 / 27 .
@unit, gracias por su atención. Debería ser 3/81, ha sido editado.
@Daniel Mathias Todos los cálculos de modelado indican aproximadamente un 93 % de probabilidad. Estoy tratando de explicar por qué mi enfoque básico anterior termina con una probabilidad del 95%, que es un poco más alto que el resultado correcto. Creo que multiplicar la probabilidad de cada bloque cuadrado de 2X2 81 veces solo da la probabilidad de una secuencia. No tiene en cuenta la posición de los bloques cuadrados de 2X2 en la cuadrícula. La probabilidad de que cada píxel cambie según su posición (esquinas, líneas exteriores e interior de las líneas exteriores). ¿Puedes explicar?
Su aproximación es alta porque los bloques 2X2 superpuestos no son independientes. Un bloque central de 2X2 comparte dos píxeles con cada uno de los cuatro bloques superpuestos. Si ese bloque no es de un color sólido, al menos dos de sus vecinos tampoco son de un color sólido.
@Daniel Mathias Gracias, pero un último punto que quiero verificar. Si esta cuadrícula de 10X10 fuera el plano de una tira de Moebius o un simple toroide, la décima columna estaría al lado de la primera columna y la décima fila estaría al lado de la primera fila. (Por ejemplo, el píxel en la esquina superior izquierda, la esquina superior derecha, la esquina inferior izquierda y la esquina inferior derecha formarían un bloque de 2X2). trabajaría. ¿Es eso cierto? ¿La razón está puramente relacionada con la independencia independientemente de cualquier tipo de forma?
@DanielMathias, ¿El modelo que utilizó tiene en cuenta la forma de la cuadrícula al calcular las probabilidades de los píxeles? Tengo curiosidad por saber si es posible aplicar la misma fórmula en una cuadrícula de 10X10, que es el plano de una forma de dona (toroide). Por lo tanto, cada píxel al final de la fila será vecino de los del principio. Lo mismo se aplica a las columnas también. ¿Es posible ajustar el modelado y ejecutarlo de nuevo de esta manera? Si es posible, me gustaría ver qué tan cerca está el resultado de mi cálculo básico. Gracias de nuevo
Modelado 10 × 10 como toro da una probabilidad de ≈ 96.28 % , que es menor que 1 − ( 26 / 27 ) 100 ≈ 97.7 %

Respuestas (1)

Tiendo a creer que no existe una fórmula simple para eso, pero puede usar ideas de la llamada "programación dinámica con perfil" para calcularlo.

Dejar X ser el número de colorantes 'malos' (sin un solo color) 2 ∗ 2 cuadrícula). Claramente la respuesta es

1 − X 3 100

A continuación, deja F ( norte , metro a s k ) (dónde norte ∈ { 0 . . 9 } y metro a s k ∈ { 1 , 2 , 3 } 10 , { 1 , 2 , 3 } se refiere a los colores) sea el número de formas de pintar primero norte + 1 filas de modo que:
1) No haya filas de un solo color. 2 ∗ 2 cuadrado
2) El color de la última fila está determinado por metro a s k

Claramente

X = ∑ metro a s k ∈ { 1 , 2 , 3 } 10 F ( 9 , metro a s k )

Usamos la fórmula recurrente para calcular F ( 9 , metro a s k )

De este modo,

F ( norte , metro a s k ) = ∑ metro a s k ′ ∈ { 1 , 2 , 3 } 10 F ( norte − 1 , metro a s k ′ ) ∗ pag mi r metro i t t mi d ( metro a s k ′ , metro a s k )
dónde
pag mi r metro i t t mi d ( metro a s k 1 , metro a s k 2 ) = { 1 , si  metro a s k 2  pintado junto a  metro a s k 1  no produce un cuadrado de 2*2 de un solo color 0 , de lo contrario

y

F ( 0 , metro a s k ) = 1
para cualquier metro a s k

La fórmula anterior simplemente refleja el hecho de que cualquier coloración de la primera norte filas es la combinación adecuada de coloración de la primera norte − 1 filas y la última, y ​​todo lo que necesita para asegurarse de que el color de la última fila (definido por metro a s k ) junto con el color de la fila anterior (definido por metro a s k ′ ) no forman un cuadrado de un solo color.

Si solo necesita una fórmula, entonces el trabajo está hecho. Si realmente necesita obtener un número, tendrá que esperar un par de horas (o incluso días) para que su computadora lo haga. 10 ∗ 3 2 ∗ 10 ≈ 3 ∗ 10 10 operaciones calculando todos estos valores. Tomará un tiempo, pero no es imposible, ya que la toma de fuerza bruta completa 3 100 ≈ 5 ∗ 10 47 que es casi para siempre.

Upd:

por estas fórmulas, el número exacto de colorantes sin un solo color 2 ∗ 2 el cuadrado es

34588239301492881803538634375825365877151370240
Por lo tanto, la probabilidad es
3 100 − 34588239301492881803538634375825365877151370240 3 100 = 0.9328875670549894

Gracias por tus conocimientos. No soy tan conocedor de programación. ¿La fórmula con máscaras que proporcionó es una fórmula matemática o una fórmula de programación? Tengo curiosidad por saber si hay alguna manera de hacer un razonamiento paso a paso para obtener un porcentaje con cálculos de probabilidad simples como lo demostré en los detalles de mi pregunta.
Es una fórmula matemática, sin embargo, la única forma de evaluarla realmente es usar una computadora, ya que se debe calcular una gran cantidad de valores. Como dije antes, apuesto a que no hay forma de calcularlo con precisión usando solo un razonamiento de probabilidad simple. Por cierto, acabo de ejecutar el programa para calcularlo, espero que mañana entregue la respuesta :)
¡gracias! Supongo que debería darnos una probabilidad del 93,3%. Esta probabilidad ha sido confirmada hasta ahora por dos personas (una respuesta está en los comentarios) que utilizaron modelos informáticos.
Actualicé la respuesta. El modelaje no mentía :)
Se agradece su enfoque con fórmula matemática :) De hecho, me pregunto por qué mi enfoque básico anterior termina con un 95% de probabilidad, que es un poco más alto que el resultado correcto. Creo que multiplicar la probabilidad de cada bloque cuadrado de 2X2 81 veces solo da la probabilidad de una secuencia. No tiene en cuenta la posición de los bloques cuadrados de 2X2 en la cuadrícula. La probabilidad de que cada píxel cambie según su posición (esquinas, líneas exteriores e interior de las líneas exteriores) ¿Qué opinas?
Bueno, estos casos límite (píxeles de esquina y borde) no son el único problema con nuestro enfoque. Para obtener la probabilidad de que todos los 2*2 cuadrados tengan al menos 2 colores, simplemente multiplicó las probabilidades de cada uno de esos cuadrados y obtuvo (26/27)^81. Sin embargo, esta regla de multiplicación solo funciona para eventos independientes y no es el caso para dos cuadrados que tienen intersección. Creo que no hay forma de corregir este enfoque y obtener la respuesta precisa, pero puede inventar algunas heurísticas para acercarlo más a la correcta.
Gracias de nuevo. Si esta cuadrícula de 10X10 fuera el plano de una tira de Moebius o un simple toroide, la décima columna estaría al lado de la primera columna y la décima fila estaría al lado de la primera fila. (Por ejemplo, el píxel en la esquina superior izquierda, la esquina superior derecha, la esquina inferior izquierda y la esquina inferior derecha formarían un bloque de 2X2). trabajaría. ¿Es eso cierto? ¿La razón está puramente relacionada con la independencia independientemente de cualquier tipo de forma?
Permítame preguntarle un punto más. ¿La fórmula que utilizó tiene en cuenta la forma de la cuadrícula al calcular las probabilidades de los píxeles? Tengo curiosidad por saber si es posible aplicar la misma fórmula en una cuadrícula de 10X10, que es el plano de una forma de dona (toroide). Por lo tanto, cada píxel al final de la fila será vecino de los del principio. Lo mismo se aplica a las columnas también. ¿Es posible ajustar la fórmula y volver a ejecutarla de esta manera? Si es posible, me gustaría ver qué tan cerca está el resultado de mi cálculo básico. ¡Gracias de nuevo!
¿Cómo calcular la probabilidad de tener al menos un bloque cuadrado de 2X2 del mismo color en un generador de píxeles aleatorios?
RespuestasAquíPolítica de privacidad1y, 0v