This week the question is: Can You Paint by Number?
I’m completing a paint-by-number painting, although this one is a little different from any that I’ve seen before. It’s an infinitely long strip of canvas that is 1 cm wide. It’s broken up into adjacent 1 cm-by-1 cm squares, each of which is numbered zero or one, each with a 50 percent chance. The squares are all numbered independently of each other. Every square with a zero I color red, while every square with a one I color blue.
Once I’m done painting, there will be many “clusters” of contiguous red and blue squares. For example, consider the finite strip of canvas below. It contains 10 total squares and seven clusters, which means the average size of a cluster here is approximately 1.43 squares.
Once I’m done painting, what will be the average size of each red or blue cluster?
Before we get to that though, woohoo!
Congratulations to the (randomly selected) winner from last week: 🎻 Lise Andreasen 🎻 from Valby, Copenhagen, Denmark.
Læs mere: #ThisWeeksFiddler, 20240405Highlight to reveal solution:
Imagine going through the strip. I can ask: Is this square the beginning of a new cluster? If my color is not the same as the color of the preceding square, the answer is yes. Good! Let’s look at this cluster.
What is the color of the next square? If it’s not the same as mine, my cluster is over, it’s 1 square long. This happens with a probability of 50%.
Otherwise we’re still going. Let’s look at the possible square 3. If it’s not the color same as me, my cluster is over, it’s 2 squares long. This happens with a total probability of 25%. (50% chance square 2 was right, 50% chance square 3 was wrong, 50% * 50% = 25%).
Otherwise we’re still going. Let’s look at the possible square 4. If it’s not the same color as me, my cluster is over, it’s 3 squares long. This happens with a total probability of 12.5%.
And so on.
Cluster size | Probability |
1 | 50% |
2 | 25% |
3 | 12.5% |
To compute the average cluster size, we do this:
1 * 50% + 2 * 25% + 3 * 12.5% …
This could also be written as:
1 * 1/21 + 2 * 1/22 + 3 * 1/23 …
Or:
Sum of n / 2n, 1 <= n, going to infinity.
According to a reliable source, the sum is 2.
Just to make sure, I wrote a program to simulate the situation. Same result.