Is an infinite scramble really "random"?

[Dane man]

So there is no number N where applying exactly N random moves to the cube will result in each case having the exact same distribution? How does that proof go?

Well, it actually kinda makes sense. Think about this.

Let's say you have a coin (only two states), and every "turn" is to flip the coin from head to tails or tails to heads. If you had an infinite number of "turns", then mathematically (taking it to a representative limit), yes, you have a perfect distribution among the states, but the fact remains that any finite number of "turns" will result in only 1 state, depending on whether that number is even or odd. Therefore, any finite number results in uneven distribution.

Now the cube has more than one state (43 quintillion-ish), but the fact still remains that it conforms to a pattern of movement. Because of this, there are some states, that from the solved state, can be reached in 6 moves, but can't be reached in 7 or 8, and then can be reachable in 9. Not only that, but there are also less 6 move combinations that produce that state than 9 move combinations. This is a very uneven distribution among the lower levels of turning, and we can safely assume that adding this uneven distribution on top of itself for any given "finite" period would only result in yet another uneven distribution, and it could also occur that some patterns that we do not yet have the computer power to analyze might begin to show (for example, the Rubik's cube equivalent of the penny's even or odd).

So, for example, say we chose 923,892 moves and decided to find the distribution of the states. Even if all possible states could be reached using that many moves, some states would have more combinations of length 923,892 that reach it than others. State 1 could have 5,003,283 different ways to be reached with 913,892 moves, while state 2 could only have 768,301. If you continue to increase the number of moves the distribution will continue to remain uneven, and therefore, for any "finite" selection of the number of moves, you will have an uneven distribution, even though theoretically with limits, the distribution evens out.

Not exactly a proof, and I doubt we'll have a solid one for a while (perhaps years from now with much faster computers), but that's the general idea, and both mathematical and statistical experience supports it.

Make sense?


"Now", says Captain Statistics, "What about the least common multiple?". Well, let's think about it. Say we take all of the states, and find, for each one of them, the number of moves that can reach it in exactly 250 different ways (assuming that such can be found). This means that if one state can be reached exactly 250 different ways in 24 moves, then that state's move count is 24. Say we find another state that can be reached exactly 250 different ways with 35 moves. Then that state's move count will be 35.

One could say in theory, "Now, having done that with all states, we should find the least common multiple of all of the move counts of those states! That number is the move count that will give us an even distribution!"

But wait, there are three problems with that. First, we don't even know if it's possible to find such a value as the move count with a common number of possibilities for every one of the 43 quintillion states. Two, we don't know if using a multiple of a move count will result in a mathematically even addition of possible move combinations (example, doubling: 24 moves to 48 moves = 250 combinations to 500 combinations), which is seriously doubtful given the data we already have. And three, even if using multiples gave and even addition of combinations, each state will be multiplied by a different number than others (3 to 15 is 5, and 5 to 15 is 3, the state with move count 3 will have it's combinations multiplied by 5, and the state with move count 5 will be mulitplied by 3. The first state will have more combinations at that move count than the second state). So even if it were possible to look at all of the states and their individual distributions, any form of trying to even out one number or distribution (for example, trying to find a least common multiple) will make another number or distribution uneven, therefore breaking conformity to the goal.


So, in many intuitive and theoretical ways, we see that the possibility of finding an even distribution among any finite number, however big, is extremely unlikely if not impossible. And while theoretically, an infinite number or limit reaches an even distribution, it is because the number infinity is not defined. If it were, you'd be hard pressed to say that it gives an even distribution to possible cube states.

That's my "proof". While I don't have any mathematical proof (we don't yet have a good group representation of the cube to even attempt that), this is the simplified theory behind it. Anyone else have ideas?

 

[rokicki]

There's a much simpler proof.

If we just use "random sequences", in the half-turn metric, the number of
sequences of length n is 18^n which is never a multiple of the number of
positions (which has a factors of 5, 7, and 11).

If we use "canonical sequences", it is fairly easy to show that the number
of odd-parity canonical sequences and even-parity canonical sequences
of a given length always differ. Indeed, the absolute difference increases
rather dramatically, although the relative difference decreases.

This alone shows that there is no length (or even finite range of lengths)
that generates an even distribution of positions.

 

[Dane man]

There's a much simpler proof.

If we just use "random sequences", in the half-turn metric, the number of
sequences of length n is 18^n which is never a multiple of the number of
positions (which has a factors of 5, 7, and 11).

If we use "canonical sequences", it is fairly easy to show that the number
of odd-parity canonical sequences and even-parity canonical sequences
of a given length always differ. Indeed, the absolute difference increases
rather dramatically, although the relative difference decreases.

This alone shows that there is no length (or even finite range of lengths)
that generates an even distribution of positions.

Well, simpler to state, but harder to be understood by those who it isn't explained to. Nonetheless, what you're talking about here is one of the points I was referring to in my post. I just wanted to make an easy to understand explanation of the possible "proofs" instead of a slightly jargon dense group theory based post.


EDIT: Just a note. While it is 18^n for any "random" sequence, it actually changes if you are using what I assume you're calling "canonical sequences". You might think it'd naturally be 18*15^(n-1), but you forget that if the second move is opposite the first, then you can use neither of those faces for the next move and have to multiply the next step as 12. Resulting in 18*15*12 for a three step sequence where the second move is opposite the first. Whenever there's a move opposite another, the next move will be one of only 4 sides, not five, thus multiplying by 12 instead of 15.

Doesn't change much about the fate of the distribution, though it is something to add to what you've said.