Fdtxjr

I'm trying to understand probability calculations of getting basic patterns on random pixel generators. There is some background information for my questions, so thanks in advance for reading.

Below is the background for my questions:

Let's say we have random pixel generator with a square screen which has $10 times 10$ resolution (100 pixels in total, each pixel can have 3 colors)

In order to calculate the probability of having at least one $2 times 2$ same color square block on that screen, I'm applying the following calculation based on complement probability:

$1-(26/27)^81=95%$ approximately.
(There are 81 different $2 times 2$ blocks on $10 times 10$ grid. Odds of having there are at least two different colors in $2 times 2$ square block is $26/27$)

I was told that all computer modeling/simulations calculate the probability of having at least one $2 times 2$ same color block as approximately 93%, a little less than what I calculated with my basic approach.

On this $10 times 10$ square screen while center pixels can be part of 4 different square blocks, corner pixels each can be only part of 1 square block and pixels on the edges can be part of 2 different squares. I thought this is the reason why I ended up with higher probability.

However, I was informed that I behaved each $2 times 2$ square blocks independently, therefore, I disregarded intersection of $2 times 2$ multicolor blocks that create $2 times 2$ same color square blocks. Therefore rather than positions of the pixel I indicate above, the fact that I behaved each $2 times 2$ independently did give incorrect probability.

My Questions

I was also told by someone else that if my $10 times 10$ grid was the plane of a torus (doughnut shape) or Klein bottle (Mobius strip) first column would be next to the tenth column & first row would be next to the tenth row which allows all $2 times 2$ pixels can be part of 4 squares, therefore my basic calculation would work.

-Is this logic correct? Is there a flaw in my calculation related to the shape of the screen or is it related to independence of events? Because no matter which shape the screen is $2 times 2$ square blocks will be always intersecting because they are dependent.

-Is there a mathematical formula that allows us to calculate this probability on different planes? Are computer simulations adjustable based on different planes?

It's due to the dependence of events.

Imagine that instead of a $10times 10$ plane you have a $2 times 2$ plane ... but it is toroidal. Then that means that you have $4$ possible $2 times 2$ tiles as 'part' of this plane, and so if the colorings of these $4$ tiles were all independent, you would have a $1-(frac2627)^4$ probability of having at least one tile with the same $4$ colors.

However, obviously these are not independent events, and the actual probability is just $1-frac2627$, which is of course a little lower: if one tile does not have all the same color, then obviously the others can no longer have the same colors either.

Something similar happens with larger planes, toroidal or not. It's not as obvious as with this example, but the basic concept remains the same: if one tile does not have $4$ squares of the same color, then the probability of the tile that overlaps half with it will have a slightly lower probability of having all $4$ squares of the same color as compared to the basic $frac2627$ because the reason the first tile does not have all $4$ of the same color could be because the shared two squares are not the same color.

Hence, the probability of the second tile not having $4$ squares of the same color is a little higher if the first tile does not have $4$ squares of the same color as compared to $1-frac2627$. And therefore, the probability of having at least one tile in the whole plane with $n$ tiles will be a little lower than $1-(frac2627)^n$... and indeed the computer simulation found a lower value than your computed value, since your formula did assume independence.

Finally, I don't know what the actual formula would be ... and maybe this is why people have resorted to computer simulations: it's just too nasty of a formula!

First up: the plane vs. torus thing. I'm assuming you actually care about, say, the $1000 times 1000$ case. In that case, you have about a million 2x2 squares, but only 4000 of them are along the edges, so pretending things wrap introduces almost no error. By contrast, if you were looking at, say, a 2x2 screen, in the "flat" example there'd be only one square, but in the torus example there'd be $4$ -- the difference would be huge. At $10 times 10$, you're nearing the edge between these two domains: you're adding about 20 squares to the $81$ you already have -- that's a pretty substantial alteration. By the time you're talking $100 x 100$, you're adding $200$ squares to the $9801$ you've already got, introducing at most a $2%$ error. But as I say, at $10 times 10$, I'd stick with the "flat" model were you have $81$ squares.

Second: can you look at the 81 squares independently? No. For if two squares overlap on two pixels, e.g.

ABC
ABC

where the first square consists of the A and B pixels, and then other is the B and C pixels, then if the first square is "all white", you only need for the two Cs to be white to make a second "all white" square; if you choose those two C pixels uniformly randomly, that'll happen $1/9$ of the time.

So: your calculation is flawed because of the failed independence assumption.

But let's step back a moment and ask how flawed it is:

Suppose we have a square at the top left and one at the bottom right. The probability of both being all-white is not the product of the probabilities of each being all-white (i.e., they're not independent), but they are very nearly independent. You could probably do a pretty accurate computation assuming independence if the two squares had at least one row or column between them (although I say this as a completely wild guess, unsupported by any actual effort to verify it on my part).

One last thing: the actual exact computation you want to do is something that I'd hesitate to tackle because...it's a pain in the neck with the special edge-cases, etc. If I were going to tackle it, I'd use a method that might surprise you: I'd write exactly the program you wrote (one that generates uniform random $10 times 10$ pixel patterns), and count the number of all-same squares. I'd run it a few thousand times, and average the results. The Law of Large Numbers tells me that this result would be a surprisingly good estimate of the true probability.

I went ahead and wrote some (ugly) code in 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

Multiple runs produced similar values (0.9334, 0.9335, ,...).

When I ran it in the mode that reports the torus results as well, I got this:

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

y =

 0.9334


yt =

 0.9629

In other words: $93.3%$ chance of a monochrome square with a $10 times 10$ grid, but $96.3%$ chance with a $10times 10$ grid that's on a torus.