Simulating the Ladybug Clock Puzzle

The probability of landing on each number is the same—this is the theoretical stationary distribution, which can only be approximated and never perfectly reached within a finite number of steps. If we focus on completing the traversal within a finite sequence, the probability of being at 1 or 11 is the highest, while it's lowest at 6. In other words, the average number of steps to reach 6 is higher than for other numbers; it takes about 10 something steps to hit 6 than it does to hit 1, which is more than a full lap! The world of infinity is really strange, isn't it? Human intuition is always much closer to the finite.

I think I have some sort of intuition why all the probabilities are the same.

Imagine you're standing on a randomly chosen vertex on the ring which is not right next to the starting position. At some point, the ladybug will be guaranteed to appear either to the left of you or to the right of you for the first time, and this cannot happen as the second-to-last step, because then the ladybug would have had to have visited both of your neighbors. At this point, for your vertex to be the one last visited, the ladybug would have to turn around and loop all the way around the circle to your other neighbor. But this means the previous trajectory of the ladybug and which vertices were visited before is irrelevant, as the ladybug will have to pass by them anyway. By symmetry, this situation is completely equivalent to being at the very start of the process on one of the vertices neighboring the starting position. Hence any randomly chosen vertex not next to the starting position has to have the same probability of being visited last as those two vertices. Hence all vertices have to have to same probability of being visited last.

Bruteforce thinking works in this case, given that there's only ~12*2^12 total states and transition matrix is very sparse, 1/11 is quick to calculate.

But not all of these states are valid, visited set is just defined by 2 markers on the circle (and the start position), so now state count is much smaller.

Ladybug needs to be on 7 or 5 while having a nice (7,5) visited state to reach 6, movements inside (7, 5) don't really matter, so state count gets to 12*11/2=66. Quite small and enough to do by hand.

edit: been thinking a bit on finding a short proof, as 1/11 (or 1/(N-1) in general case) sounds like there could be a nice short proof, but it only made me realize how these constructive proofs are so clean and any attempts to formalize this gets me into graph theory vibes where I just feel like proof is making nonsymbolic leaps in reasoning that I just can't feel are true.

It's a nice puzzle because at first it seems like you would need to do some complex probability calculations but by just looking at it for a while you can come up with the 1 basic insight that instantly makes the solution obvious.

> After 5000 runs, they were all 8.4-9.7%

This sample size is really small. I ran 100 million simulations in Nim[0] (takes around a minute). And distribution converges toward 9.09% on all positions equally:

    Average turns: 65.99609065001634
    Final position distribution:
     4: 9.095%
    11: 9.093%
     7: 9.091%
     3: 9.091%
    10: 9.090%
     9: 9.090%
     1: 9.090%
     8: 9.090%
     2: 9.090%
     6: 9.090%
     5: 9.089%
     0: 0.000%

Shouldn't the code say:

    position = (position + direction + 1) % 12;