6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to MSE. This is a great first question, and you've posed it really nicely, explaining how you were thinking about it, and laying out your exact points of confusion. For future questions, you should probably learn to use MathJax, which is how we make our equations look nice. Here's a quick tutorial: math.meta.stackexchange.com/questions/5020/…. You don't need to read all of it -- you'll get 90% of the value from the first few paragraphs. $\endgroup$ – John Hughes Mar 16 '19 at 12:25
  • $\begingroup$ @YuiTo Cheng, why did you edit my probability calculation? It should be 1-(26/27)^81=95% I cannot change it to original calculation with my edit due to the format you used. $\endgroup$ – franckbart Mar 16 '19 at 15:24
  • $\begingroup$ @franckbart It's not me, it's Jneven...See John Hughes's advice on how to use mathjax formatting. $\endgroup$ – YuiTo Cheng Mar 16 '19 at 15:25
  • $\begingroup$ @franckbart Fixed. $\endgroup$ – YuiTo Cheng Mar 16 '19 at 15:28
  • $\begingroup$ @YuiTo Cheng, thanks but can we change as 95%,there is only 95 appearing. $\endgroup$ – franckbart Mar 16 '19 at 15:29
2
$\begingroup$

It's due to the dependence of events.

Imagine that instead of a $10\times 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-(\frac{26}{27})^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-\frac{26}{27}$, 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 $\frac{26}{27}$ 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-\frac{26}{27}$. And therefore, the probability of having at least one tile in the whole plane with $n$ tiles will be a little lower than $1-(\frac{26}{27})^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!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for your simplified demonstration. I can understand trying to come up with a formula is complicated. Do you think it is even hard to apply simulations considering toroidal plane,something unachievable? Is simulating on flat plane convenient compared to toroidal? $\endgroup$ – franckbart Mar 16 '19 at 13:02
  • $\begingroup$ @franckbart Simulating toroidal is not any significantly harder than non-toroidal ... the change in code is minimal. And the math for toroidal is probably even a little easier than non-toroidal ... but still nasty. And, for large $n$, both become undoable ... but intuitively I think a mathematical approximation should be feasible ... though I'm not expert enough to know how to do that. $\endgroup$ – Bram28 Mar 16 '19 at 13:48
  • $\begingroup$ Thanks. indeed my question here is outcome of a question I previously raised. I'm not such math literate but there is a mathematical formula provided related with masks/dynamic programming profile for the calculation on flat screen. It is on the link. Probability result could only be achieved after computer calculation.Do you think the formula there adjustable based on screen shape/ plane geometry?math.stackexchange.com/questions/3142232/… $\endgroup$ – franckbart Mar 16 '19 at 15:33
2
$\begingroup$

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 $10\times 10$ grid that's on a torus.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ your detailed explanation is appreciated. I have two remarks.In the beginning how do you conclude we have more squares in torus shape? Doesn't number of pixels stay same when wrapped? Because at 10X10 you almost come up with squares more than total pixel number. Thanks for demonstration on matlab, I don't know coding indeed. 93% probability was given to me based on calculation at brute force. I think you only used a linear calculation considering flat screen. Do you think it is even hard to code on toroidal plane? $\endgroup$ – franckbart Mar 16 '19 at 12:57
  • $\begingroup$ John, indeed my question here is outcome of a question I previously raised. I'm not such math literate but there is a mathematical formula provided related with masks/dynamic programming profile for the calculation on flat screen. It is on the link. Probability result could only be achieved after computer calculation.Is that formula adjustable based on screen shape/ plane geometry? math.stackexchange.com/questions/3142232/… $\endgroup$ – franckbart Mar 16 '19 at 13:14
  • $\begingroup$ A 2x2 square can be labelled by its upper left corner. In the NxN flat-screen case, any pixel except those in the last row or column can be such a label, so there are $(N-1)\times (N-1)$ of these 2x2 squares. In the toroidal case, even pixels in the last column or row can label a 2x2 square: the pixels of that square come from the last column plus the first column, for example. So there are $N \times N$ of them. As for re-coding for the toroidal case, that's pretty easy: you take your $N \times N$ array of colors, and copy the first row to make a new row at the bottom, and copy the first ... $\endgroup$ – John Hughes Mar 16 '19 at 15:54
  • $\begingroup$ column to make a new coiumn at the right; then you do the same computation as before, but on this enlarged matrix. $\endgroup$ – John Hughes Mar 16 '19 at 15:55
  • 1
    $\begingroup$ If we do your calculation on the toroidal version, you have to compute $1 - (26/27)^{100}$, because there are now 100 possible 2x2 blocks; that gives $0.977$, i.e., about $1\%$ higher than the observed value in my program. As to your first question, Bram28's answer shows that the computation -- taking dependence into account -- will give a lower number than the all-independent assumption, just as you observed (and now see in the toroidal case as well). $\endgroup$ – John Hughes Mar 16 '19 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.