I ran a 22 segment worm starting with alternating 1's and 0's, a few dozen times. It took a low of 45 steps and a high of 1124 steps. Given it takes over 4 million steps using my deterministic strategy, that seems better.
This puzzle has revealed so many nice symmetries, I thought I'd share another one. If you have b black balls and w white balls in an urn, the expected number of monochromatic balls you will pick out of the urn before you pick a ball of the other color is the same as the expected number of balls remaining after you have exhausted one color.
One really interesting aspect of this problem is that by removing the balls, you even out the odds of pulling one color or another as the numbers get big.
For example, I ran a simulation 1,000 times where I flipped a fair coin 1,000,000 times and noted abs( H - T ). The average value was 783. But if we put 500,000 black balls and 500,000 white balls in the urn, the average number of balls left after exhausting one color is very close to 2!
I'm not totally convinced by this argument. I obviously believe it. But don't see the logical argument why the number of black balls left scales linearly with the starting number of black balls, given a fixed number of white balls.
For instance. It's obvious that if w = 10 and b = 1, then on average, there will be 1/11 black balls left. But let's look at w = 10 and b = 2. I would use this formula:
1/12 * 1/11 * 2 * 2 + 1/12 * 10/11 * 2 * 1 which does equal the expected result of 2/11. The first term is chances a particular black ball is in last position * chances the other black ball is in second-to-last position * 2 ways for that happen * 2 black balls left. The second term is chances a particular black ball is in last position * chances the second black ball is not in second-to-last position * 2 ways for that to happen * 1 black ball remaining.
But the statement "If there are originally b black balls, this expectation becomes b/(w+1)" does not convince me of this fact.
Maybe I'm missing a simple identity, but I haven't been "aha'ed" just yet.
"aha" still eludes me. I ran a simple Python simulation as well. But I thought I'd share my friend's elegant recursive approach to this problem. The nice thing was he got exact answers, which helps when looking for patterns.