Las probabilidades de tener$2 \times 2$ píxeles del mismo color en diferentes planos

Question

Estoy tratando de entender a los cálculos de probabilidad de obtener patrones básicos sobre aleatoria de píxeles generadores. Hay alguna información de fondo para mis preguntas, así que gracias de antemano por la lectura.

A continuación es el fondo de mis preguntas:

Supongamos que tenemos aleatoria de píxeles generador con una plaza de pantalla que ha $10 \times 10$ resolución (100 píxeles en total, cada píxel puede tener 3 colores)

Con el fin de calcular la probabilidad de tener al menos un $2 \times 2$ mismo color bloque cuadrado en la pantalla, estoy aplicando la siguiente cálculo basado en el complemento de la probabilidad:

$1-(26/27)^{81}=95\%$ aproximadamente. (Hay 81 diferentes $2 \times 2$ bloques en $10 \times 10$ cuadrícula. Las probabilidades de tener que existen al menos dos colores diferentes en $2 \times 2$ bloque cuadrado es $26/27$)

Me dijeron que todo el equipo de modelación/simulación calcular la probabilidad de tener al menos un $2 \times 2$ mismo color block como aproximadamente el 93%, un poco menos de lo que he calculado con mi enfoque básico.

En esta $10 \times 10$ plaza de la pantalla, mientras que el centro de pixeles que pueden ser parte de las 4 diferentes bloques cuadrados de la esquina, los píxeles de cada uno de ellos puede ser sólo una parte de 1 bloque cuadrado y los píxeles de los bordes puede ser parte de 2 plazas diferentes. Yo pensé que esta es la razón por la que terminé con mayor probabilidad.

Sin embargo, se me informó que me comportaba cada una de las $2 \times 2$ bloques cuadrados de forma independiente, por lo tanto, no presté atención a la intersección de $2 \times 2$ multicolor bloques que crean $2 \times 2$ mismo color de bloques cuadrados. Por lo tanto, en lugar de las posiciones de los píxeles que me indican arriba, el hecho de que me comportaba cada una de las $2 \times 2$ independientemente hizo dar la probabilidad incorrecta.

Mis Preguntas

También me dijeron que por alguien que si mi $10 \times 10$ red fue el avión de un toro (en forma de rosquilla) o de la botella de Klein (banda de Mobius) primera columna sería el siguiente paso a la décima parte de la columna y la primera fila sería el siguiente paso a la décima fila que permite a todos los $2 \times 2$ pixeles que pueden ser parte de 4 plazas, por lo tanto mi básicas de cálculo de trabajo.

-Es esta lógica es la correcta? Hay un error en mis cálculos relacionados con la forma de la pantalla o es relativa a la independencia de los eventos? Porque no importa que forma la pantalla es $2 \times 2$ bloques cuadrados será siempre de intersección porque son dependientes.

-¿Hay una fórmula matemática que nos permite calcular esta probabilidad en diferentes planos? Son simulaciones por ordenador ajustable basada en diferentes planos?

Answer 1

Es debido a la dependencia de los acontecimientos.

Imagine que en lugar de una $10\times 10$ plano tiene un $2 \times 2$ plano ... pero es toroidal. Entonces eso significa que usted tiene $4$ posible $2 \times 2$ azulejos como "parte" de este plano, y por tanto si los colorantes de estos $4$ azulejos eran independientes, tendría un $1-(\frac{26}{27})^4$ de probabilidad de tener al menos una ficha con el mismo $4$ colores.

Sin embargo, es evidente que estos son no independientes de los eventos, y la probabilidad es sólo $1-\frac{26}{27}$, que por supuesto es un poco menor: si una pieza no tiene todos el mismo color, entonces, obviamente, los demás no pueden tener los mismos colores.

Algo similar sucede con los grandes planos, toroidal o no. Esto no es tan evidente como en este ejemplo, pero el concepto básico sigue siendo el mismo: si una pieza no tiene $4$ cuadrados del mismo color, entonces la probabilidad de la baldosa, que se superpone a la mitad con lo tendrá un poco menos de probabilidad de tener todos los $4$ cuadrados del mismo color en comparación con el basic $\frac{26}{27}$ porque la razón de la primera baldosa no tiene todas las $4$ del mismo color podría ser debido a que la compartió dos plazas no son del mismo color.

Por lo tanto, la probabilidad de que la segunda baldosa no tener $4$ cuadrados del mismo color es un poco más alto, si la primera baldosa no tiene $4$ cuadrados del mismo color en comparación a $1-\frac{26}{27}$. Y por lo tanto, la probabilidad de tener al menos un azulejo en todo el avión con $n$ azulejos será un poco menor que $1-(\frac{26}{27})^n$... y, de hecho, la simulación por ordenador se encontró un valor menor que su valor calculado, ya que su fórmula suponga la independencia.

Por último, yo no sé cuál es la fórmula real sería ... y tal vez por eso las personas han recurrido a las simulaciones por ordenador: es demasiado desagradable de una fórmula!

Answer 2

Primero: el avión vs toro cosa. Estoy asumiendo que usted realmente se preocupan por, digamos, de la $1000 \times 1000$ caso. En ese caso, usted tiene alrededor de un millón de 2x2 plazas, pero sólo 4000 de ellos están a lo largo de los bordes, así que pretender que las cosas envoltura presenta casi ningún error. Por el contrario, si se busca, por ejemplo, en una pantalla de 2x2, en el "plano" de ejemplo, no sería sólo una plaza, pero en el torus ejemplo no estaría de $4$ -- la diferencia sería enorme. En $10 \times 10$, está llegando al límite entre estos dos dominios: estás en la adición de alrededor de 20 plazas para la $81$ ya tiene: esa es una muy alteración sustancial. Por el momento estamos hablando de $100 x 100$, estás agregando $200$ plazas $9801$ ya tienes, la introducción en la mayoría de un $2\%$ de error. Pero como digo, en $10 \times 10$, me pegan con el "plano", el modelo se ha $81$ plazas.

Segundo: usted puede mirar en el 81 plazas de forma independiente? No. Para el caso de dos plazas de la superposición de dos píxeles, por ejemplo,

ABC
ABC

donde la primera plaza se compone de a y B de píxeles y, a continuación, otro es el de la B y la C píxeles, a continuación, si el primer cuadrado es "todo blanco", sólo se necesita para las dos Cs a ser blanco para hacer un segundo "todo blanco" de la plaza; si usted elige los dos C píxeles uniformemente al azar, lo que va a suceder $1/9$ del tiempo.

Así: su cálculo es erróneo, debido a la fallida independencia de la asunción.

Pero volvamos un momento y preguntar cómo imperfecto que es:

Supongamos que tenemos un cuadrado en la parte superior izquierda y uno en la parte inferior derecha. La probabilidad de ser blanco no es el producto de las probabilidades de cada ser todo en blanco (es decir, no son independientes), pero son casi independientes. Usted probablemente podría hacer un muy precisa el cálculo suponiendo independencia de si las dos plazas que había al menos una fila o columna entre ellos (aunque tengo que decir que esto es totalmente una conjetura, que no admita ningún esfuerzo real para comprobarlo por mi parte).

Una última cosa: el real cálculo exacto que usted quiere hacer es algo que me gustaría dude en para hacer frente porque...es un dolor en el cuello con el borde especial-casos, etc. Si se va a abordar, me gustaría utilizar un método que puede sorprender: yo iba a escribir exactamente el programa que escribió (que genera aleatorios uniformes $10 \times 10$ patrones de pixeles), y contar el número de all mismo plazas. Me gustaría ejecutar un par de miles de veces, y el promedio de los resultados. La Ley de los Grandes Números me dice que este resultado sería una sorprendentemente buena estimación de la probabilidad.

Me fui por delante y escribió algunos (feo) de código en Matlab:

function [y, yt] = squares(n, k)
% Generate n k x k squares containing one of 3 pixel; look for any 2x2 square
% in which all pixels have the same color; if you find one, count "1" for
% this example; if not, count "0". Produce the average count (i.e, the
% number of 1s, divided by n). 

count = 0;
countt = 0; % additional "t" indicates "torus case"
for i = 1:n
    s = randi([1,3], k);
    st = s([1:end, 1], :); % copy first row to end
    st = st(:, [1:end, 1]); % copy first col to end

    t1 = s(1:(k-1), 1:(k-1));  % each pixel that's the upper left corner of a potential square
    t2 = s(1:(k-1), 2:k); % pixels to the right of those
    t3 = s(2:k, 2:k); % pixels to the right-and-down of those
    t4 = s(2:k, 1:(k-1)); % pixels just below the main pixel
    a = (t1 == t2) & (t3 == t4) & (t1 == t3);
    count = count + any(a(:)); % if any entry of "a" is a "1", there's a monochrom square

    k = k + 1;
    t1 = st(1:(k-1), 1:(k-1));  % each pixel that's the upper left corner of a potential square
    t2 = st(1:(k-1), 2:k); % pixels to the right of those
    t3 = st(2:k, 2:k); % pixels to the right-and-down of those
    t4 = st(2:k, 1:(k-1)); % pixels just below the main pixel
    at = (t1 == t2) & (t3 == t4) & (t1 == t3);
    countt = countt + any(at(:)); % if any entry of "a" is a "1", there's a monochrom square
    k = k - 1;
end
y = count/n; 
yt = countt/n; 
squares(100000, 10)

ans =

    0.9331

Varias carreras producidas valores similares (0.9334, 0.9335, ,...).

Cuando me encontré con él en el modo en que los informes del toro resultados así, tengo esto:

>> [y,yt] = squares(10000, 10)

y =

    0.9334


yt =

    0.9629

En otras palabras: $93.3\%$ probabilidad de un monocromo de la plaza con un $10 \times 10$ grid, sino $96.3\%$ oportunidad con un $10\times 10$ cuadrícula que está en un toro.