After playing a little with a Rubik cube I thought of the following problem :
Suppose we start with a solved Rubik cube (a general one , with $n^3$ cubes) . Then we choose one of the moves , each having a probability of $\frac{1}{6n}$ of being chosen , and apply it on our cube . We continue doing so ( choosing a new move randomly and then applying it and so on…) , until we reach the solved position again . What is the expected number of moves needed to solve the cube in this way ?
I thought about it and I think the answer should be $\infty$ (at least for $n \geq 3$) because there are a lot of random sequences of moves that will take a long time to solve the cube but I don't have a rigorous way to prove it.
For $n=2$ I'm not that sure if the answer should be finite or infinite (but I still tend to think it's infinite).
Thank you for your time to help me!
Best Answer
As you can see by reading the answers to this question involving a knight tour on a chessboard, we can determine the expected return time for any irreducible Markov chain by finding the unique stationary distribution; if the mass of the distribution at a given state is $p$, then the expected return time to that state is $\frac{1}{p}$. (Intuitively, if we process the Markov chain for a long time, we expect to be at the given state with probability $p$, so the average distance between returns to the state is $\frac{1}{p}$.)
In the case of a random walk on a graph $G$, the unique stationary distribution is given by making the mass at each vertex proportional to its degree. When the graph is regular (as is the case here), each vertex will have the same mass, namely $\frac{1}{|G|}$. So the expected return time for each vertex will be exactly $|G|$.
Thus the expected number of turns required to get back to the starting state of any type of Rubik's cube is equal to the number of positions of the cube.