Consider higher (NxNxN) Rubik's cube group, with specific set of generators described below. What is important - that there are huge COMMUTING subsets of generators.
Question: Consider a random walk making "K"-steps on Cayley graph of the N-Rubik's group. What is known about the expected distance from start to K-th position for such a group ? (For "K" quite smaller than diameter of the group).
Sub-question 1: At least what pattern should we expect - is it growing like sqrt(number of moves) - like standard $R^d$ case and many commutative groups, or it is more linear like - what happens for free-group and might be expected for randomly chosen elements of any big non-commutive group ?
Sub-question 2: If it is linear, then is it something like (1-1/13)*(number of moves) for 3x3x3 case, where 13 comes from growth rate of Cubik's group - see Derek's Holt answer MO322877. Or in the other words how the "growth-rate" is related to the random walk properties ?
Details. Structure of the group. Generators.
First take a look on that wonderful video for 3x3x3 case: https://www.reddit.com/media?url=https%3A%2F%2Fpreview.redd.it%2Fimq4s00bgx1a1.gif%3Fformat%3Dmp4%26s%3Dabea9b805f838832ba835c36eeefd2e73fd2eae1 . You can see co-centric circles - and their moves are clearly commutative.
Commutative generators of the group are rotations of the parallel "sheets" - those parallel to one of the faces. See attached picture - we have 4 generators for 4 parallel "sheets", each such generator has order 4. For NxNxN respectively there are N such generators, again each of order 4.
Cubes have 6 faces - so we there are 6 families of generators above, but, of course, we need only 3 - because those for parallel faces - will duplicate each other.
So we arrived:
Group: have 3*N generators, denoted by $F_0,F_1,...,F_{N-1}, R_0,R_1,...,R_{N-1}, D_0,D_1, ... , D_{N-1}$ - 3 subfamilies, each generator of order 4. Generators within each subfamily commute among themselves.
Remark: explicit permutation describing examples for small N can be found e.g. here: https://www.kaggle.com/code/alexandervc/santa23-eda?scriptVersionId=158030054&cellId=26
PS
Why bother?
Since DeepMind showed that AI methods can tackle effectively complicated combinatorial problems - like GO-game, one may be curious what are the other tasks can be tackled by AI methods. The diameter for N-Rubik cube group seems still to be unknown. And that open problem seems which might be tackled by AI methods (to some extent), moreover it can be seen like "toy-model". There are many ways how to approach - one I described here, and one of the issues is related to random walks on such groups - understanding its properties would be helpful for AI approaches. Moreover now (January 2024) there is on-going challenge on the Kaggle platform where participants competing "to estimate diameter" (well, not precisely, but somehow related - see here and here). Imho it would be great to exchange the experience between Mathoverflow community and Kaggle community.
