playing with colored pixels

today, vaguely inspired by the four color map theorem, I played around with generating images with pixels of N different colors, where each pixel's color must not match any of its 4 orthogonal neighbors.

for N = 2, the only way to do this is with a checkerboard pattern:

for N > 2, though, the possibilities are far more numerous. the way I first thought to generate these images randomly was to simply draw pixels from left to right, top to bottom, picking a random color for each pixel as long as it doesn't match the color of any neighboring pixels (only needing to check the ones on top and to the left, since the pixels on bottom and to the right aren't drawn yet). for N = 3, where the 3 colors are represented as red, green, and blue, this produces an image that looks like this:

this certainly does produce an image where no two orthogonally neighboring pixels have the same color. however, there is something you may notice: there is a strong tendency for it to produce these long diagonal lines which go down and to the right. furthermore, this bias is dependent on the drawing direction: if you draw the pixels from right to left instead of left to right, the diagonal lines will go the other direction:

after thinking about this for a little while, I eventually realized what causes this to happen.

what causes this to happen

consider a 2x2 image generated using this procedure. pick a color for the top left pixel, for instance red.

then pick the colors for the pixels to its right and bottom. these pixels can each only be one of the two colors that isn't the color we started with, in this case either green or blue. there is an equal probability of it being either one. thus the four possible equiprobable cases are:

in fact, for any size image, all of the pixels on the top and left edges will be generated in this same equiprobable manner that only looks at one neighboring pixel at a time. these edges are like their own little one-dimensional sequences independent from everything else (aside from the fact that they share the same starting value, ie. the top left corner).

anyway, back to our 2x2 image. now we pick the color for the final bottom-right pixel. the colors we can choose for this new pixel are now dependent on not one, but two neighboring pixels.

half of the time, these two pixels will be different colors: one of them will be green and the other will be blue, which means the new pixel must be red. the other half of the time, the two pixels will be the same color: if both pixels are green, the new pixel will either be blue or red. if both pixels are blue, the new pixel will either be green or red.

as you can see, the color of our new pixel is much more likely to be red than any other color. 3/4 or 75% likely, to be exact. green and blue each only have a 1/8 or 12.5% probability of being chosen.

here is an important thing to note, which may shine a bit of light on the discrepancy: no matter what colors the two neighboring pixels are, it must always be possible for the new pixel to be red, because the only way for this to be impossible would be if any of those two pixels were red, but this cannot be the case because the top left pixel is red to begin with.

so, with any image generated using this procedure, for any pixel that isn't in the top or left edge (and whose color therefore determined by two neighboring pixels instead of one), it is more likely than not that the pixel immediately above and to the left of it will have the same color. this is what produces the noticeable diagonal lines.

generalization

now let's generalize this to higher numbers of distinct colors (higher values of N). starting with any arbitrary color for the top-left pixel of our 2x2 image (the "starting pixel"), the top right and bottom left pixels (the "neighboring pixels") can each only be one of N-1 colors (any color except that of the starting pixel). this creates (N-1)² possible equiprobable cases.

in N-1 of those cases, ie. (N-1)/(N-1)² = 1/(N-1) = (N-1)⁻¹ of the time, the neighboring pixels will be the same color. in these cases, there are N-1 possible choices for the bottom-right pixel (the "new pixel"), since we can chose any color except for the one that the neighboring pixels happen to share. one of these possible choices must always be the starting color, as proven earlier. so the probability that this happens is (N-1)⁻¹. so our probability thus far that the new pixel will be the same color as the starting pixel is (N-1)⁻¹ (the probability of two identical neighboring pixels) multiplied by (N-1)⁻¹, ie. (N-1)⁻².

the other 1-(N-1)⁻¹ of the time, the neighboring pixels will be different colors. in these cases, there are N-2 possible choices for the new pixel, since we can chose any color except either of the two neighboring colors. again, one of these possible choices must always be the starting color, and this time the probability of this happening is now 1/(N-2). multiply this by the probability of differing neighbor colors: 1-(N-1)⁻¹ × (N-2)⁻¹.

adding this to our other probability from earlier, we get a formula for determining the probability (let's call it P) of the new pixel being the same color as the starting pixel, for any number of colors N >= 3:

P = (N-1)⁻² + (1-(N-1)⁻¹) × (N-2)⁻¹

I guess this formula also works for N = 2, if you're okay with 0 × (1/0) being 0 and not undefined, but your calculator probably isn't.

the probability for each color that isn't the starting pixel's color becoming the new pixel's color is just (1-P)/(N-1). here's a table of all of these values for N from 3 to 10 (to 3 digits of precision):

so as N gets larger, the general diagonal-line-ness of the image should gradually lessen, although there will always be a bias in favor of it, even if it's a really really really tiny and imperceptible one. for instance, here's an image generated for N = 5, where you may notice that there's a bit less diagonal-line-ness... although, maybe that's an intuitive thing to expect... because... there's more possible colors...

also, looking at the table you may notice some... patterns. and then realize that a much simpler formula for P could be:

P = N/(N-1)²

except this formula isn't exactly the same because there's less weird division by zero stuff, so now you can input N = 2 and get... 2? which I guess means that the probability is doubly certain?

I don't know how math works in case you couldn't tell.

so now what?

now that I've explained all that, perhaps you're thinking that I am now going to present some sort of solution to all of this, so that you can generate Pure and Unbiased images where no two pixels have the same color. well, I don't actually have one. because I am not a smart person. I just thought this would be a fun thing to write a blog post about.