Return to Question

In his 1988 book Group Representations in Probability and Statistics , Diaconis considers mixing times of the 15-puzzle. He states:

Here is a simplified version: Consider the blank as a $16$th block, and consider the puzzle on a "torus." ... It is not hard to show that it takes order $n^3$ steps to randomize a single square (on an $n\times n$ grid). I presume that order $n^3\log n$ steps suffice to randomize everything. For a $4\times 4$, this gives about $90$ "moves" to randomize. I presume this simplified version converges to uniform faster than the original 15 puzzle. Similar questions can be asked for other puzzles such as Rubic's cube. (page 90, § G(4). Emphasis added).

Quanta magazine describes how recently Chu and Hough have solved Diaconis' version of the mixing time of the 15-puzzle by studying the eigenvalues of the corresponding transition (adjacency) matrix. Chu and Hough showed that, contrary to Diaconis's conjecture, an $(n^2-1)$-puzzle takes $n^4\log n$ random steps to have a uniform probability of being in one of the $\frac 12\cdot 16! \approx 10^{13}$ possible positions. I believe instead of only $90$ moves, it may take up to $4^4\log 4 \approx 355$ moves to sufficiently scramble the 15-puzzle.

Of course, both the the 140-year old 15-puzzle and the 40-year old Rubik's cube have had storied histories in mathematics and culture. It's natural to ask:

How much of the results of Chu and Hough carry over to address the mixing time of the $3\times 3$ Rubik's cube? Under, say, the half-turn metric, or if easier under the quarter-turn metric?

Given that Chu and Hough's solution of the 15-puzzle mixing time is longer than the intuition of Diaconis, perhaps the mixing time of the Rubik's cube under the half-turn metric (quarter-turn metric) is much longer than the diameter of $20$ ($26$).

In his 1988 book Group Representations in Probability and Statistics , Diaconis considers mixing times of the 15-puzzle. He states:

Here is a simplified version: Consider the blank as a $16$th block, and consider the puzzle on a "torus." ... It is not hard to show that it takes order $n^3$ steps to randomize a single square (on an $n\times n$ grid). I presume that order $n^3\log n$ steps suffice to randomize everything. For a $4\times 4$, this gives about $90$ "moves" to randomize. ... Similar questions can be asked for other puzzles such as Rubic's cube. (page 90, § G(4). Emphasis added).

Quanta magazine describes how recently Chu and Hough have solved Diaconis' version of the mixing time of the 15-puzzle by studying the eigenvalues of the corresponding transition (adjacency) matrix. Chu and Hough showed that, contrary to Diaconis's conjecture, an $(n^2-1)$-puzzle takes $n^4\log n$ random steps to have a uniform probability of being in one of the $\frac{n!}{2}$ positions. I believe instead of only $90$ moves, it may take up to $4^4\log 4 \approx 355$ moves to sufficiently scramble the 15-puzzle.

Of course, both the the 140-year old 15-puzzle and the 40-year old Rubik's cube have had storied histories in mathematics and culture. It's natural to ask:

How much of the results of Chu and Hough carry over to address the mixing time of the $3\times 3$ Rubik's cube? Under, say, the half-turn metric, or if easier under the quarter-turn metric?

Given that Chu and Hough's solution of the 15-puzzle mixing time is longer than the intuition of Diaconis, perhaps the mixing time of the Rubik's cube under the half-turn metric (quarter-turn metric) is much longer than the diameter of $20$ ($26$).

In his book Group Representations in Probability and Statistics from 1988, Diaconis considers mixing times of the 15-puzzle. That is, he asks how long it would take to scramble a 15-puzzle by randomly walking along the Cayley graph of the groupoid, from starting at the solved position. Diaconis conjectured that, in general, an $(n^2-1)$-puzzle will take $n^3\log n$ steps to be fully scrambled. For the original 15-puzzle, he estimated that it would take about $90$ random steps to sufficiently randomize everything. See page 90, § G(4) of Diaconis's book.

Quanta magazine describes how recently Chu and Hough have solved the question of the mixing time of the 15-puzzle by studying the eigenvalues of the corresponding transition (adjacency) matrix. Chu and Hough showed that, contrary to Diaconis's conjecture, an $(n^2-1)$-puzzle takes $n^4\log n$ random steps to have a uniform probability of being in one of the $\frac 12\cdot 16! \approx 10^{13}$ possible positions. I believe instead of only $90$ moves, it may take up to $4^4\log 4 \approx 355$ moves to sufficiently scramble the 15-puzzle.

Chu and Hough, and Diaconis before them, simplify the problem and consider the 15-puzzle on the torus - that is, they consider the 15-puzzle wherein the sides "wrap around" each other.

Nonetheless, in the same section as above Diaconis poses a similar question about the mixing time other puzzles, specifically inquiring of the Rubik's cube. Of course, both the the 15-puzzle and the Rubik's cube have had storied histories among many mathematicians and those interested in puzzles, so it's natural to ask:

How much of the results of Chu and Hough carry over to address the mixing time of the $3\times 3$ Rubik's cube? Under, say, the half-turn metric, or if easier under the quarter-turn metric?

Given that Chu and Hough's solution of the 15-puzzle mixing time is longer than the intuition of Diaconis, perhaps the mixing time of the Rubik's cube under the half-turn metric (quarter-turn metric) is much longer than the diameter of $20$ ($24$).

In his 1988 book Group Representations in Probability and Statistics , Diaconis considers mixing times of the 15-puzzle. He states:

Here is a simplified version: Consider the blank as a $16$th block, and consider the puzzle on a "torus." ... It is not hard to show that it takes order $n^3$ steps to randomize a single square (on an $n\times n$ grid). I presume that order $n^3\log n$ steps suffice to randomize everything. For a $4\times 4$, this gives about $90$ "moves" to randomize. I presume this simplified version converges to uniform faster than the original 15 puzzle. Similar questions can be asked for other puzzles such as Rubic's cube. (page 90, § G(4). Emphasis added).

Quanta magazine describes how recently Chu and Hough have solved Diaconis' version of the mixing time of the 15-puzzle by studying the eigenvalues of the corresponding transition (adjacency) matrix. Chu and Hough showed that, contrary to Diaconis's conjecture, an $(n^2-1)$-puzzle takes $n^4\log n$ random steps to have a uniform probability of being in one of the $\frac 12\cdot 16! \approx 10^{13}$ possible positions. I believe instead of only $90$ moves, it may take up to $4^4\log 4 \approx 355$ moves to sufficiently scramble the 15-puzzle.

Of course, both the the 140-year old 15-puzzle and the 40-year old Rubik's cube have had storied histories in mathematics and culture. It's natural to ask:

How much of the results of Chu and Hough carry over to address the mixing time of the $3\times 3$ Rubik's cube? Under, say, the half-turn metric, or if easier under the quarter-turn metric?

Given that Chu and Hough's solution of the 15-puzzle mixing time is longer than the intuition of Diaconis, perhaps the mixing time of the Rubik's cube under the half-turn metric (quarter-turn metric) is much longer than the diameter of $20$ ($26$).

In the late '80's, in his book Group Representations in Probability and Statistics Diaconis considered mixing times of the 15-puzzle. That is, he asked how long it would take to scramble a 15-puzzle by randomly walking along the Cayley graph of the groupoid, while starting at the solved position. Diaconis conjectured that, in general, an $n\times n$-puzzle will take $n^3\log n$ steps to be fully scrambled. For the original 15-puzzle, he estimated that it would take about $90$ random steps to sufficiently randomize everything.

Quanta magazine notes that recently Chu and Hough have solved the question of the mixing time of the 15-puzzle by studying the eigenvalues of the corresponding transition (adjacency) matrix. Chu and Hough showed that, contrary to Diaconis's conjecture, an $n\times n$-puzzle takes $n^4\log n$ random steps to have a uniform probability of being in one of the $\frac 12\cdot 16! \approx 10^{13}$ positions. I believe instead of only $90$ moves, it may take up to $4^4\log 4 \approx 355$ moves to sufficiently scramble the 15-puzzle.

Chu and Hough, and Diaconis before them, simplify the problem and consider the 15-puzzle on the torus - that is, they consider the 15-puzzle wherein the sides "wrap around" each other.

Nonetheless, in the same book as above Diaconis poses a similar question about the mixing time specifically for the Rubik's cube. Of course, both the the 15-puzzle and the Rubik's cube have had a storied history among many mathematicians and those interested in puzzles, so it's natural to ask:

How much of the results of Chu and Hough carry over to address the mixing time of the $3\times 3\times 3$ Rubik's cube? Under, say, the half-turn metric, or if easier under the quarter-turn metric?

Given that Chu and Hough's solution of the 15-puzzle mixing time is longer than the intuition of Diaconis, perhaps the mixing time of the Rubik's cube, under the half-turn metric, is much longer than the diameter of $20$.

In his book Group Representations in Probability and Statistics from 1988, Diaconis considers mixing times of the 15-puzzle. That is, he asks how long it would take to scramble a 15-puzzle by randomly walking along the Cayley graph of the groupoid, from starting at the solved position. Diaconis conjectured that, in general, an $(n^2-1)$-puzzle will take $n^3\log n$ steps to be fully scrambled. For the original 15-puzzle, he estimated that it would take about $90$ random steps to sufficiently randomize everything. See page 90, § G(4) of Diaconis's book.

Quanta magazine describes how recently Chu and Hough have solved the question of the mixing time of the 15-puzzle by studying the eigenvalues of the corresponding transition (adjacency) matrix. Chu and Hough showed that, contrary to Diaconis's conjecture, an $(n^2-1)$-puzzle takes $n^4\log n$ random steps to have a uniform probability of being in one of the $\frac 12\cdot 16! \approx 10^{13}$ possible positions. I believe instead of only $90$ moves, it may take up to $4^4\log 4 \approx 355$ moves to sufficiently scramble the 15-puzzle.

Chu and Hough, and Diaconis before them, simplify the problem and consider the 15-puzzle on the torus - that is, they consider the 15-puzzle wherein the sides "wrap around" each other.

Nonetheless, in the same section as above Diaconis poses a similar question about the mixing time other puzzles, specifically inquiring of the Rubik's cube. Of course, both the the 15-puzzle and the Rubik's cube have had storied histories among many mathematicians and those interested in puzzles, so it's natural to ask:

How much of the results of Chu and Hough carry over to address the mixing time of the $3\times 3$ Rubik's cube? Under, say, the half-turn metric, or if easier under the quarter-turn metric?

Given that Chu and Hough's solution of the 15-puzzle mixing time is longer than the intuition of Diaconis, perhaps the mixing time of the Rubik's cube under the half-turn metric (quarter-turn metric) is much longer than the diameter of $20$ ($24$).