That’s easily corrected (e.g: flip a coin first to determine whether to do 10k or 10k+1 random rotations), but this shows it is easy to make slip ups solving such a seemingly trivial problem.

Rotating top side left one is the same as rotating bottom 2 sides right.

But, more generally limiting rotations to 90 degrees slows things down as 90 or 180 degree rotations can be directly computed with the same overhead.

My analogy is to Markov chain Monte Carlo. It is well known that MCMC on a discrete space will converge to the desired distribution (we’ll get to that in a second) if the chain is irreducible and aperiodic.

Irreducible means any state can eventually transition to any other state using the permutations allowed. This is easy to validate if we just use the various face rotations. Aperiodic essentially means that there is no fixed “loop” from one state back to itself that occurs with probability one. (The even parity issue that @someone raised comes in here. An absolute fix in the lack of full understanding of all possible such issues is to allow null moves with some low probability.). For a simple state space like this, the main thing is to make the permutations chosen in such a way that all states are reachable.

OK, iterated permutations converge in distribution, but to what? All the states in the target distribution here have equal probability, so (in MCMC terms) the posterior is totally flat:

  P(s) / P(s’) = 1

What is reversible? It means that, if you are at state s, you are just as likely to go to s’ as if you are at s’ and going to s. [1] The easy way to ensure this is to make “clockwise twist of left face” chosen with the same probability as “counterclockwise twist of left face”.

This is the obvious strategy anyway, which is why reversible samplers are popular.

So in sum, the recommended algorithm is to start from any legal state and perform “N” permutations randomly chosen from clockwise/counterclockwise (50/50 chance) rotations of a randomly chosen face. To accomplish the null moves, just subtract a small random number from N.

On a discrete state space, you will get exponentially fast convergence to the desired distribution. The space is strongly connected, because you can get from any state to any other state with at most 40 moves.

I don’t see the problem here.

[1] https://en.m.wikipedia.org/wiki/Metropolis–Hastings_algorith..., A(x, x’) = 1.

The World Cube Association requires "equal probability for each state" by scramble programs used for their events.

You're right that a large number of rotations will result in something indistinguishable from random by an individual, but that is not sufficient according to WCA regulations as it's not uniformly random.

If I can hand you multiple sets of 10^10 cubes and you can’t tell which method was used that’s what I mean from indistinguishable not simply humans can’t tell.

Sum 20 coin flips mod 3 and you can find the bias in the output. It’s hard with a small sample set, but you could do it. Sum 10k coin flips and it’s a different situation.

Eventually you fall through the noise floor for any reasonable sample size.