Average Number of Fill Commands Needed to Turn a Billion Pixel Screen White

[Bartholomew]

You know how the fill tool in Paint works. If you have a really large computer screen (a billion pixels, say) and you fill each pixel in the screen randomly either black or white (equal probability either one), what is the average number of times you would have to use the fill command for turning black pixels white to then turn the entire screen white?

I just thought this up a little while ago and I have no idea how to do it except empirically. Is this a solved problem?

 

[noelhustler]

It is an interesting problem.
I'm not sure there's an elegant way to solve it.

The mean number of pixels changed on each fill is related to the distribution of black and white pixels in the image and this distribution changes with each fill. This is also ignoring distribution locality (because a fill in general changes the distribution more significantly in its locality) which I imagine would be another factor.

Assuming a 3x3 pixel kernel and filling based on adjacency, another problem is that each progressive kernel overlaps the parent kernel and other sibling kernels which means that the probability distribution of finding n new unfilled pixels (accounting for sibling overlap) is very irregular, and that is without even taking into account parent overlap.

If anybody has any ideas on this one, I'd like to hear them. Perhaps I'm missing a very simple way of approaching this.

 

[Bartholomew]

The problem is essentially the ratio of the number of "clumps" to the number of pixels. A clump is a single-color area so that every pixel in it is connected to every other pixel in it by a series of north, south, east, or west moves while not leaving the color. Also, for a clump to be a clump and not just a part of a clump, it must not be possible to include any additional pixels and still have all the pixels connected in that way.

One fill of black to white will delete one black clump.

The problem is easy in 1 dimension; the size of the clumps there has an exponential distribution, since a clump in 1 dimension is just a run of the same color.

I think if you could find the probability that any two randomly selected pixels are in the same (2-dimensional) clump, you could indirectly get the size of a clump. This might be easier to find or it might not; I don't know how to do it. Somehow you'd count the possible paths from one pixel to another and multiply each path by the probability of it being taken, and add all those together.

A possibly related problem which I came up with is, if you can use fills of BOTH black-to-white and white-to-black, how many fills would it take? If you try an experiment in paint using the spray gun to randomly fill one area until it's about half-and-half black and white, and then alternate between black-and-white and white-and-black, only a few clicks will clear everything.

 

[noelhustler]

The area of math dealing with this kind of problem would be percolation theory.

I wrote a program to run the problem experimentally and came up with a fairly consistent number of clumps. There were rougly 0.066A clumps where A is the total number of pixels.

I also came across s-Clusters and I found roughly the same value (0.065770) for the average number of clumps.

 

[Bartholomew]

Well, that's the answer then. I don't understand what that site on s-clusters means, though, by "number of s-clusters for s = 0, 1, ..." Those values seem to add up to more than the number of pixels. For n = 2 you have a 2x2 grid, with 4 pixels, but the total # of clumps it seems to indicate is 16. Even looking at all possible arrangements, there are only 10 possible groups of size 1 in such a grid, and it indicates 13. What is it counting?

 

[Bartholomew]

By the way, if you don't mind my asking, how did you find that page?