Simulating the Ladybug Clock Puzzle(austinhenley.com)
austinhenley.com
Simulating the Ladybug Clock Puzzle
https://austinhenley.com/blog/ladybugclock.html
19 comments
I agree with this reasoning. I think this is more than intuition, it's pretty much a formal proof.
It's based on natural language in contrast to formal language, thus it is at best a social proof [1].
[1] https://mathweb.ucsd.edu/%7Esbuss/ResearchWeb/handbookI/Chap...
[1] https://mathweb.ucsd.edu/%7Esbuss/ResearchWeb/handbookI/Chap...
I had to read this a few times to get it, but I now that do it I like it.
OK, I give up for now for 12. Let's try 4. I hope I can do 4 at least.
The clock has only the numbers 0, 3, 6, 9 (I replaced 12 with 0 to save a character.)
[spoiler alert] Initially the state is [0]--- After the first move it goes to 3 or 9.
Case 3) Let's assume it first move to 3, so the state is now 0[3]--
There is a 50% chance that it goes to 6 and we get 03[6]- so the answer is 9
There is a 50% chance that it goes to 0 again, and we have [0]3--.
- Now there is a 50% chance that it goes to 9 and we get 03-[9] and the answer is 6.
- Now there is a 50% chance that it goes to 3 back and we get 0[3]--.
So starting from 0[3]--, there is a 50% of "9", 25% of "6", and 25% of back to 0[3]--. Using standard series trick, we can split the 25% loop in the final answers "9" and "6", in the same proportion of 50% vs 25%.
So the net result is that starting from 0[3]--, there is a 66.6...% of "9", 33.3...% of "6".
Case 9) Let's assume it first move to 9, so the state is now 0--[9] yada yada there is a 66.6...% of "3", 33.3...% of "6".
---
In total: (66.6%+0%)*50% = 33.3...% for 3 and the same for 9, and (33.3..%+33.3...%)*50%=33% for 6. So all endings are equiprobable. I still can believe my eyes, and I'm afraid there is an "obvious" solution that I'm missing.
The clock has only the numbers 0, 3, 6, 9 (I replaced 12 with 0 to save a character.)
[spoiler alert] Initially the state is [0]--- After the first move it goes to 3 or 9.
Case 3) Let's assume it first move to 3, so the state is now 0[3]--
There is a 50% chance that it goes to 6 and we get 03[6]- so the answer is 9
There is a 50% chance that it goes to 0 again, and we have [0]3--.
- Now there is a 50% chance that it goes to 9 and we get 03-[9] and the answer is 6.
- Now there is a 50% chance that it goes to 3 back and we get 0[3]--.
So starting from 0[3]--, there is a 50% of "9", 25% of "6", and 25% of back to 0[3]--. Using standard series trick, we can split the 25% loop in the final answers "9" and "6", in the same proportion of 50% vs 25%.
So the net result is that starting from 0[3]--, there is a 66.6...% of "9", 33.3...% of "6".
Case 9) Let's assume it first move to 9, so the state is now 0--[9] yada yada there is a 66.6...% of "3", 33.3...% of "6".
---
In total: (66.6%+0%)*50% = 33.3...% for 3 and the same for 9, and (33.3..%+33.3...%)*50%=33% for 6. So all endings are equiprobable. I still can believe my eyes, and I'm afraid there is an "obvious" solution that I'm missing.
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.
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.
Regarding that last question, the other day we were playing the Frozen-branded edition of Snakes&Ladders with my family:
https://www.straight2you.co.uk/products/disney-frozen-2-6-in...
Basically you throw the included coloured die and move your pawn to the next field that is of the colour the die indicates OR, and here's where it becomes a hellish nightmare, the previous such field if there's no way to advance.
You have to roll yellow and NOT purple if you're anywhere at the last five positions.
The probability of finishing this game is of course not 1, but it's sufficiently far from 1 that my preschooler was at her wit's end moving back and forth, so we had to finish early.
https://www.straight2you.co.uk/products/disney-frozen-2-6-in...
Basically you throw the included coloured die and move your pawn to the next field that is of the colour the die indicates OR, and here's where it becomes a hellish nightmare, the previous such field if there's no way to advance.
You have to roll yellow and NOT purple if you're anywhere at the last five positions.
The probability of finishing this game is of course not 1, but it's sufficiently far from 1 that my preschooler was at her wit's end moving back and forth, so we had to finish early.
> 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:
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%
Damn good. Does it matter that you're (presumably) using a psuedo random number? I mean you seem to nail the probabilities regardless.
Perhaps our pseudorandom algorithms are better at flipping a coin (this case) versus having to choose a random value over a range greater than 2 (or "1" if you like).
Perhaps our pseudorandom algorithms are better at flipping a coin (this case) versus having to choose a random value over a range greater than 2 (or "1" if you like).
It should not be a problem, pseudorandom numbers are used in simulations, like monte-carlo, all the time.
Nim uses xoroshiro[0] algorithm for std/random module and it produces good quality statistically random bits until 5TB of output. And lower 4 bits have a little bias, but it should not matter as we only use upper 64 out of available 128 bits.
Also, I just now realise that xoroshiro-128+ is really cheap, so perhaps my batching optimisation was unnecessary here.
[0] - https://en.wikipedia.org/wiki/Xorshift#xoroshiro
Nim uses xoroshiro[0] algorithm for std/random module and it produces good quality statistically random bits until 5TB of output. And lower 4 bits have a little bias, but it should not matter as we only use upper 64 out of available 128 bits.
Also, I just now realise that xoroshiro-128+ is really cheap, so perhaps my batching optimisation was unnecessary here.
[0] - https://en.wikipedia.org/wiki/Xorshift#xoroshiro
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.
[deleted]
At first it might seem that 6 is furthest to starting point and therefore it's quite likely it will be the last one reached. However whole process is chaotic enough, that once ladybug finally arrives to 4 and/or 8, the starting position has very little impact on overall outcome.
Well the starting position has no impact on the outcome. Each number other than the starting number has exactly 1/11 chance of being the last remaining number.
Shouldn't the code say:
position = (position + direction + 1) % 12;
The +12 is to keep the number positive. The direction contains the movement so a +1 wouldn't make sense.
The +12 there is so that % works correctly (ie the number never becomes negative)
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.
I still can't find an obvious solution. I think the solution posted by kmm in the top comment is correct, but I still don't think it's obvious. Can you post your solution?
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.