5
$\begingroup$

Let's assume we have random pixel generator which has 10X10 resolution (100 pixels in total) and each pixels can have 3 different colors. I'm trying to calculate probability of having at least one 2X2 same color square block on that screen.

Here is my logic for such calculation:

1) Odds of all pixels having same color in 2X2 square block is 1/27 (3/3^4)

2) Odds of there is at least two different colors in 2X2 square block is 26/27 (1-1/27), which is complement probability of (1)

3) There are 81 different group of 2X2 square blocks on 10X10 grid.

4) Probability of that one 2X2 square block at least having two different colors is (26/27)^81, based on complement probability.

5) Therefore probability of at least one 2X2 square block having same color is
1-(26/27)^81=95% approximately.

However,

-4 pixels on 10X10 grid which are located at the corners (top left,top right,bottom left & bottom right) can be only in one 2X2 square block each

-All pixels located in outermost parts except these 4, can be in two different 2X2 square blocks each

-All remaining pixels inside outermost lines can be in four different 2X2 square blocks each.

As I treated all pixels equally I didn't reflect the condition above in my calculation. How can I reflect the condition above in my calculation and have the correct probability? Is this mathematically possible to demonstrate via calculations?

Thanks a lot!

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I cannot answer your question, but modeling this gives a probability of approximately $93.3\%$ $\endgroup$ – Daniel Mathias Mar 10 '19 at 13:58
  • $\begingroup$ Great question! Just a note: $4/3^4 = 4/81 \ne 1/27$. $\endgroup$ – Unit Mar 10 '19 at 14:09
  • $\begingroup$ @unit, thanks for your attention. It should be 3/81, has been edited. $\endgroup$ – franckbart Mar 10 '19 at 14:21
  • $\begingroup$ @Daniel Mathias All modelling calculations indicate approximately 93% probability. I'm trying to elaborate why my basic approach above ends up with 95% probability which is a little high than correct result. I think multiplying probability of each 2X2 square blocks 81 times just gives probability of a sequence. It doesn't take into account position of 2X2 square blocks in the grid. Probability of each pixel changes based on where they are positioned (corners, outermost lines and inside of outermost lines). Can you explain? $\endgroup$ – franckbart Mar 12 '19 at 10:11
  • 1
    $\begingroup$ Your approximation is high because overlapping 2X2 blocks are not independent. A central 2X2 block shares two pixels with each of four overlapping blocks. If that block is not a solid color, then at least two of its neighbors are also not a solid color. $\endgroup$ – Daniel Mathias Mar 12 '19 at 12:36
1
$\begingroup$

I tend to believe that there is no simple formula for that, but you can use ideas from so-called "dynamic programming with profile" to calculate it.

Let $x$ be the number of 'bad' colorings (with no single-colored $2*2$ squares). Clearly the answer is $$1-\frac{x}{3^{100}}$$
Next, let $f(n, mask)$ (where $n \in \{0 .. 9\}$ and $mask \in \{1, 2, 3\} ^ {10}$, $\{1, 2, 3\}$ refers to colors) be the number of ways to paint first $n+1$ rows so that:
1) There is no single-colored $2*2$ square
2) The last row coloring is determined by $mask$

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

We use recurrent formula in order to calculate $f(9, mask)$

Thus, $$f(n, mask) = \sum_{mask' \in \{1, 2, 3\} ^ {10}}{f(n - 1, mask') * permitted(mask', mask)}$$ where $$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}$$

and $$f(0, mask) = 1$$ for any $mask$

The formula above simply reflects the fact that any coloring of the first $n$ rows is proper combination of coloring of first $n - 1$ rows and the last one, and all you need to ensure that the coloring of the last row (defined by $mask$) together with the coloring of previous row (defined by $mask'$) don't form a single-colored square.

If you just need a formula then the job is done. If you actually need to get a number you will have to wait a couple of hours (or even days) waiting your computer to do $10 * 3 ^ {2 *10} \approx 3 * 10^{10}$ operations calculating all these values. It will take a time, but it is not impossible as full brute-force taking $3^{100} \approx 5 * 10 ^ {47}$ which is almost forever.

Upd:

By these formulas the exact number of colorings with no single-colored $2*2$ square is $$34588239301492881803538634375825365877151370240$$ Thus, the probability is $$\frac{3^{100} - 34588239301492881803538634375825365877151370240}{3^{100}} = 0.9328875670549894$$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks for your insights. I am not that knowledgeable about programming. Is the formula with masks you've provided a mathematical formula or programming formula? I am curious if there is any way to make a step by step reasoning for getting a percentage with simple probability calculations as I demonstrated in the details of my question. $\endgroup$ – franckbart Mar 10 '19 at 17:05
  • $\begingroup$ It is a mathematical formula, however, the only way to actually evaluate it to use a computer as a huge amount of values are to be calculated. As I said before, I bet there is no way to precisely calculate it using only simple probability reasoning. Btw, I've just run the program to calculate it, hope tomorrow it will give away the answer :) $\endgroup$ – Vladislav Mar 10 '19 at 17:13
  • $\begingroup$ thanks! I assume it should give us the probability as 93,3%. This probability has been so far confirmed by two people (one answer is in the comments) who used computer modelling. $\endgroup$ – franckbart Mar 10 '19 at 17:28
  • 1
    $\begingroup$ I updated the answer. The modelling didn't lie :) $\endgroup$ – Vladislav Mar 11 '19 at 7:57
  • 1
    $\begingroup$ Well, these boundary cases (corner and edge pixels) are not the only problem with our approach. To obtain the probability all 2*2 squares have at least 2 colors you simply multiplied probabilities for every single such square and got (26/27)^81. However, this multiplication rule works only for independent events, and it is not the case for any two squares that have intersection. I think there is not way to fix this approach and get the accurate answer, but you can invent some heuristics to make it closer to the right one. $\endgroup$ – Vladislav Mar 12 '19 at 12:38

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.