# Is an infinite scramble really "random"?



## unixpickle (Jul 3, 2014)

If you scramble a Rubik's 3x3x3 with 20 moves (htm), you are less likely to reach some configurations than others. For example, there are usually many more ways to reach a 6 move configuration than a 20 move one using exactly 20 moves.

I want to know if the probabilities "even out" after an infinite number of turns. Is there a uniform probability that any given configuration will be reached after doing an infinite number of turns? My intuition makes me believe that the probabilities are never uniform, but I do not know how to prove it.

*EDIT:* I am defining "random" in a very specific way. I consider a method of scrambling "random" if there is a 1/(4.3*10^19) probability that it will produce any given position from a solved state. Furthermore, by "infinite", I am talking about limits. I want to know the steady-state probabilities of the cube if you scramble it in half-turn metric.


----------



## BillyRain (Jul 3, 2014)

You can't have an 'infinite' scramble because the cube would never stop scrambling


----------



## unixpickle (Jul 3, 2014)

BillyRain said:


> You can't have an 'infinite' scramble because the cube would never stop scrambling



Then, in your mind, replace "infinite" with "really long." I am really asking about the probability distribution that you _approach_ as you continue to scramble the cube.


----------



## 10461394944000 (Jul 3, 2014)

maybe you could use a discrete markov process with 43252003274489856000 states where the transition=do a random move and try and find the equilibrium probabilities. if ist 1/43252003274489856000 then yay

that would probably be hard though


----------



## Kirjava (Jul 3, 2014)

I'm inclined to say that probabilities will not be uniform. 

I'd posit that rolling an uneven die an infinite number of times wouldn't give the same results as an even die. The results would only converge to being more accurate to the probabilities as quantity is increased.

I don't actually know though. Hopefully someone who can math will answer.


----------



## uberCuber (Jul 3, 2014)

My first thought is that the fact that some cases are symmetrical and others are not would make it have to be non-uniform, not sure though


----------



## unixpickle (Jul 3, 2014)

10461394944000 said:


> maybe you could use a discrete markov process with 43252003274489856000 states where the transition=do a random move and try and find the equilibrium probabilities. if ist 1/43252003274489856000 then yay
> 
> that would probably be hard though



This is how I would *like* to prove it, but I don't think a 4.3*10^19 x 4.3*10^19 matrix is reasonable...


----------



## whauk (Jul 3, 2014)

Yes! Assuming I interpret your question right.
So I will formulate the problem in Markov-chain-theory:
We have a starting distribution of states, that is 0 for every state except for the solved state which gets a 1. (This means essentially we have the probability 1, that the cube is solved after scrambling with 0 turns). Now we have a transition matrix (some array of numbers) which has entries of 1/18 exactly when the "row-state" and the "line-state" are reachable after one move and 0 else. (This means, when being in a state the propability of going to a state, that is reachable in one move, the propability for going to this state is 1/18 and 0 else (as you cannot go to a state that is not exactly one-move-apart)). Your question is: Does our initial distribution converge (in distribution) to a uniform distribution over all states?

Now the ergodic theorem states: "If some power of the transition matrix has entries that are all strictly greater than 0, then there is the same limit (as defined above) for every starting position, that is an eigenvector of the transition matrix with eigenvalue 1".
The condition reformulated in normal language says: "Every state is reachable from every state in some number of moves". This is clearly true for that number being 20.
The conclusion says: "If we find a distribution of states that remains constant after applying one move, our initial distribution will converge to this".
The first thing we check is (of course) the uniform distribution over all states. ("Every position has the same propability in the end"). Let A be the number of cube states, then every position gets an assigned propability of 1/A in the uniform distribution. When applying one move this state X will give 1/(18A) to every neighbour-state, but will likewise receive 1/(18A) from its 18 neighbour-states. This clearly sums up to 1/A for our state X. As this works for every state X, we found a distribution that remains invariant under "applying one move", and the ergodic theorem implies, that our initial distribution converges to this (the uniform distribution).

Note that we can even change the propabilities for choosing moves (e.g. we can make 'R'-moves 10-times as likely) and the result is still the same, as long as we ensure that every state is still reachable of course (with a fixed number of turns).

EDIT: Oh i got ninja'd ALOT  while writing this post. I just wanted to add, that it doesn't matter that states are symmetrical in looking at them "from the outside". The key in this is, that the cube group itself is symmetrical. (So every state has 18 'entries' and 18 'exits', which makes every state in equal measure symmetrical as viewed from "inside"). Maybe it helps if you think about only the U-layer with moves U, U', U2. The state after "U2" has much more symmetry but to get there from any non-U2-state has propability 1/3 exactly as the U-state has propability 1/3 from coming after any non-U-state.


----------



## unixpickle (Jul 3, 2014)

whauk said:


> The first thing we check is (of course) the uniform distribution over all states. ("Every position has the same propability in the end"). Let A be the number of cube states, then every position gets an assigned propability of 1/A in the uniform distribution.



Certainly you have proved something, but I am not sure it is what I was asking. What I get from your proof is that if I _start off_ with a random position and I perform a scramble on it, I will have a 1/A probability of landing on any given position. This would seem apparent for _any_ group. I still do not see how you proved that a random scramble performed on a _solved_ cube will generate a state with probability 1/A.


----------



## elrog (Jul 3, 2014)

I was in the middle of creating the thread "Gods Second Number?" while you posted this. It took me a while to create because I stopped to eat halfway through.



whauk said:


> Yes! Assuming I interpret your question right.
> 
> "Every state is reachable from every state in some number of moves". This is clearly true for that number being 20.


To be honest, I could not follow most of your post. I am not saying it is how you wrote it, it is just the terminology.

When you say "Yes!", are you saying yes that the OP was correct in his assumption, or yes that the probabilities even out. My intuition also leads me to believe they don't even out.

I am fairly certain that the second part of the above quote is incorrect. I do not think every position is reachable in exactly 20 moves.

Edit:
After reading whauk's edit, I was prepared to argue against it as it seemed to simple. I still don't understand how using just U, U', and U2 can be a good simulation of the whole cube, but I have arrived at the same conclusion in a different way.

If you did and infinite number of moves with the end result only affecting the last layer, you would still be more likely to get a case with 2 adjacent edges oriented correctly and the other two misoriented than you would to get a case with all four edges correctly oriented. There is also more states that have this orientation pattern. If you take the probability of getting any orientation case and divide it among how many states it has to cover, every individual state still has an equal chance to come up.

This logic should apply to the cube as whole.


----------



## unixpickle (Jul 3, 2014)

I suppose the Markov analysis argument is correct if you scramble the cube using moves and their inverses. However, I do not think that the same argument holds if you scramble the cube using some other basis, like only R, U, L, D, F, and B moves (but no inverses or squares).


----------



## 10461394944000 (Jul 3, 2014)

elrog said:


> I do not think every position is reachable in exactly 20 moves.



yes

that is what gods number is


----------



## uberCuber (Jul 3, 2014)

10461394944000 said:


> yes
> 
> that is what gods number is



Gods number just means that any scramble can be solved in <= 20 moves though. Is it actually true that any position can be reached in exactly 20 moves?


----------



## 10461394944000 (Jul 3, 2014)

uberCuber said:


> Gods number just means that any scramble can be solved in <= 20 moves though. Is it actually true that any position can be reached in exactly 20 moves?



o I didnt notice the "exactly" part, never mind


----------



## whauk (Jul 3, 2014)

I assmue you are familiar with the mathematical concept of limits?
I proofed that, if you start with a solved cube (but it works with any different position too) and perform N random turns you will reach every state with the same propability in the limit for N to infinity. Or sloppily formulated: "After an infinite number of random turns you reach each state with the same propability.
Or let again \( A \) be the number of cube states and \( P_N(X) \) the propabilty of being in state \( X \) after \( N \) turns. (with \( X \) being an arbitrary cube state).
Then
\( lim_{N \to \infty}P_N(X)=\frac{1}{A} \).


elrog said:


> I am fairly certain that the second part of the above quote is incorrect. I do not think every position is reachable in exactly 20 moves.


If a position is reachable in exactly 19 moves and the scramble leading there ends with an say R', you can replace it with R2 R to make it exactly 20. Similiarly for a position being reachable in exactly 18 moves you can use this method to make it 19 moves long and then make it 20 moves long (with the same method).


unixpickle said:


> I suppose the Markov analysis argument is correct if you scramble the cube using moves and their inverses. However, I do not think that the same argument holds if you scramble the cube using some other basis, like only R, U, L, D, F, and B moves (but no inverses or squares).


Then you have the problem that only positions without parity are reachable after an even number of turns, and likewise only positions with parity are reachable after an uneven number of turns, and we arise at the question again whether infinity is even or odd. This seems to be the only exception from my "Note"-part in the original proof.


----------



## elrog (Jul 3, 2014)

I have edited my post. Also, I am think the number in which every state can be reached in exactly this number of moves is 22, but it could very well be between 21 and 24.

Replacing R' with R2 R to make it 20 moves doesn't really prove anything because you just did 2 moves on the same face in a row and they should cancel.


----------



## whauk (Jul 3, 2014)

elrog said:


> If you did and infinite number of moves with the end result only affecting the last layer, you would still be more likely to get a case with 2 adjacent edges oriented correctly and the other two misoriented than you would to get a case with all four edges correctly oriented. There is also more states that have this orientation pattern. If you take the probability of getting any orientation case and divide it among how many states it has to cover, every individual state still has an equal chance to come up.



I talk about states whereas you collect many states in an "orientation pattern". I don't see any connection here.


elrog said:


> Replacing R' with R2 R to make it 20 moves doesn't really prove anything because you just did 2 moves on the same face in a row and they should cancel.


When we talked about making "random moves" I assumed we choose them randomly without knowing what the last one was. After applying more moves than the number of cube states you clearly have some trivial identities in there (as some state has to have been traversed twice (is that even grammar?)). Do you wish to remove them as well? It gets really hard to apply "infinitely many moves" then...


----------



## elrog (Jul 3, 2014)

I am still confused. you were talking about an orientation pattern with your example of only doing U, U', and/or U2 to the last layer?

I also don't see where it was stated that the moves were random moves, but it was implied (otherwise you could do an infinite amount of turns and cycle between just a few states). Would it not also be implied that you don't repeat the same move twice?

Also, you will only begin to traverse states more than once after performing a number of moves greater than the number of states if you are following the devils algorithm. I fail to see how this applies here though. How did this come from excluding turning the same face twice in a row to excluding multiple cube states?


----------



## Lucas Garron (Jul 3, 2014)

Moritz has said most of the important things. The key words are "Markov" and "ergodic".

If you search old posts, you'll see me advocating "Markov Random State Scrambles": define a random position on a puzzle using the distribution of states you would get if you kept doing moves. There's no need to avoid "backtracking", to compute canonical sequences, or in any way hack things so that the probability evens out. The theory gets you to a steady state.
To avoid periodicity (e.g. when you're using QTM), use the average:

Let the probability distribution \( D_n \) at time \( n = 0 \) be 100% on the solved state, and suppose your set of generators is \( G \).
For a distribution \( D \) and puzzle move \( g \)$, define \( D \circ g \) as the distribution where the probability mass at state \( S \) is moved to \( S \circ g \).

The distribution after n random moves is:
\( 
D_n = {1 \over |G|} \sum_{g \in G} D_n \circ g
\)

Then take the limiting Markov Random State distribution as:

\( 
\underset{n \to \infty}{\lim}~mean(D_0, D_1, ..., D_n)
\)

Representation theory lets you find limiting distributions by simply raising a matrix to a power.

The distribution of Square-1 states in the official scramble program is based on this. There are two "natural" ways to define a Square-1 move, which give you different distributions. The one that I think more sense turns out to be the same as if you assembled the cube by slotting pieces randomly (and starting over if it doesn't work).

This line of inquiry also gets you to a fun question: What is the limiting distribution for the 15 puzzle?



unixpickle said:


> I want to know if the probabilities "even out" after an infinite number of turns. Is there a uniform probability that any given configuration will be reached after doing an infinite number of turns? My intuition makes me believe that the probabilities are never uniform, but I do not know how to prove it.


Your answer depends on what exactly you're asking.

Even if you're in HTM, any *finite* number of moves will not get you an exactly even distribution.

In the limit, you will get an even distribution, in a (mathematically) fairly well-understood way.


----------



## Villyer (Jul 5, 2014)

Lucas Garron said:


> Even if you're in HTM, any *finite* number of moves will not get you an exactly even distribution.



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?


----------



## Dane man (Jul 8, 2014)

Villyer said:


> 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 (Jul 8, 2014)

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 (Jul 8, 2014)

rokicki said:


> 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
> ...


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.


----------

