What's the Monkey number of the Rubik's cube?
NEW (Christmas 2019). Two ways to support Mathologer
Mathologer Patreon: / mathologer
Mathologer PayPal: paypal.me/mathologer
(see the Patreon page for details)
The "Monkey number" is the average number of twists it takes to solve a Rubik's cube starting from a randomly chosen scrambled position and by making random twists. It's pretty obvious that this number will be gigantic but nobody knows the exact value of this number nor even how gigantic a number we are talking about.
So what are the Monkey numbers for the 3x3x3 or the 2x2x2? How do you create a mathematically certified random scramble of a Rubik's cube? And how would a virtual Monkey solver fare in an actual speedcubing competition? Accompany me the Mathologer, my friend Erich Tomanek and our pet monkey as we explore these and other confounding Rubik's cube puzzles.
Check out Erich's infinite monkey lab website: www.infinitemonkeylab.com
This fairly accessible article by Peter Doyle contains the maths necessary to calculate the Monkey number in terms of the transition matrix of the markov chain associated with the Rubik's cube : arxiv.org/abs/0909.2636 (see in particular Proposition 3).
That the mean recurrence (or return) time is equal to the number of configurations of a Rubik's cube is a corollary of some basic results in the theory of stochastic processes. I came across this insight for the first time in an answer by TonyK to the following question on stackexchange: math.stackexchange.com/questi...
Here are the World Cubing Association rules on scrambling twisty puzzles for competitions:
www.worldcubeassociation.org/...
Here is a link to a video which shows the scrambling program tnoodle in action: github.com/thewca/tnoodle/pul...
Notes on implementing the 2x2x2 experiments: As with counting configurations of the 2x2x2, we fixed one corner cubie and twisted the three faces not containing this corner. In this video I only report on the most interesting aspects of Erich and my playing around with this circle of problem. We tried lots of other things. Happy to discuss in the comments :)
Many thanks to Jeremy Fleischman and Lucas Garron for their help with understanding how the World Cubing Association creates scrambles of twisty puzzles for cubing competitions. Thank you to Erich for programming all those virtual cubing monkeys. And, as usual, thank you to Marty for nitpicking early drafts of the script and to Danil for his Russian support.
Enjoy!
Fun fact: the early versions of tNoodle were primarily coded at Thai Noodle 2 near UC Berkeley, which is where it gets its name.
fun fact indeed :)
"To be or not to be that is the gznutnik." - one million years in.
It is a nice gnzutnik to consider, though. Worth the wait.
To be or not to be that is the covefe
Gznutnik is now a word.
Bcdhjgvnhgvfdtbnifωωχηηφφηξилрстлдоопсва🤣
It was actually, "To be or not to be, that is the gzornmplat;" and it was Bob Newhart on his 2nd album, _The Button-Down Mind Strikes Back_ (1960), in a track titled, "An Infinite Number of Monkeys." Fred
I’ve got something quite different for you today. Usually when I start making a video I know “all the answers” before I even start writing up the script. Not so today. This video is about a circle of more or less open problems that I personally find very interesting, that I don’t know all the answers to and that are not very well known. My main mission today is to get you interested in these problems by reporting on some neat partial results that my friend Erich and I came across while playing around with these problems last month and hopefully even inspire some of you to do some original research. So a KZhead video to inspire research :) What do you think of this idea? Progress update on the problems (20 June 2018) I posed at the end of this video: Two of you, David Stolp and Mark Miller really went for it with my 2x2x2 challenge at the end and succeeded in calculating very good approximations of the Monkey numbers of the Pocket cube. Here is what they did, in their own words. Also, if you are interested in joining the quest for other Monkey numbers, Mark has put together a Slack organisation (link at the end or ask me for his e-mail address). David Stolp: Average twists to solve (half-turn metric): 4410504.275 Average twists to solve (quarter-turn metric): 4647940.184 Let X be a random variable representing how many twists it takes the monkey to get from a solved state back to a solved state. The answer we seek is (E(X^2)/E(X)-1)/2. E means expected value. As noted in the video, picking a random configuration is equivalent to picking a random time in the monkey's history, thus asking how long it takes to solve a random start state is equivalent to asking when the next solved state is after a random point in time. To compute E(X^2), I used a computer simulation. Initially there were way too many states. The state graph has many symmetries, so many states can be combined together. Doing this resulted in a graph with just 77802 states. I simulated the first 2000 twists. After 2000 twists, the probability density function of X is indistinguishable from a geometric distribution, so I used that as an optimization to get the final result. Mark MIller: Rather than statistical estimates from repeatedly selecting moves [which I have gathered was the strategy employed by Erich Tomanek], these are calculations from the matrix representing transition probabilities in the random walk, which was solved numerically with the SciPy sparse linear algebra module. It's exact... up to some decimal precision. :) QTM - 4,647,941.44707 HTM - 4,410,505.47686 Pretty close to the empirical numbers, indeed! The second part is a request of you. In response to the request for serious research, I put together a Slack organization [mathologersmonkeycube.slack.com] for people who are willing and interested to discuss the problem of the 3x3x3 cube. The invite link to the slack group is join.slack.com/t/mathologersmonkeycube/shared_invite/enQtMzgwODc1NjAwMzg3LWJjOGEwYWJlYTYwZjZkZmM4NDg5YWNkOWIzNzhiYTE3NzU1NDI4NGUwZjI3ODBlNTJjMWZjNmUyYjViZmM5YjI
Mathologer I have got a different proof for 1+2+3+4+5+6... =-1/12 . If U want to see it reply me
There is also something called the slice turn metric which counts turns of the middle slices separately :)
Mathologer I study in grade 9 and I have absolutely no idea what U just said however I will look forward to it
There is also something called the slice turn metric which does count turns of the center slices :)
You should look at the library of Babel, it’s like the monkey thing your friend does
Great video! I loved the way you walked through your explorations.
Yesterday I've rewatched almost all of your videos and was wondering when you were going to upload next. What a surprise! :D The way you present them is unique, and the cameraman just makes it all 100 times better Also wow you sure do love rubik's cubes
:)
Yes indeed. Shame about Infinite Series.
:( agreed
tbh I didn't notice; now I'm sad
@@abstractapproach634 I stopped watching after the Kelsey left. I watched because it contained higher quality math, but annoyingly, it was framed in a juvenile setting and I think that alienated both younger and older audience members alike.
I'm so glad you included the bit at the end about the quarter turn metric. Having a single antipode is so much more satisfying. Also, I'm glad I watched to the end before I commented.
The quarter-turn metric is the way to go as far as I am concerned :)
Your videos are fantastic and I'm looking forward for more :D
Well, I just finished my teaching at uni for a while so I finally got a bit more time for making videos :)
I'm glad someone has publicly come out and said that decision to end Infinite Series was shit. It really was. It was one of the best maths youtube channels around. and I don't buy into the change of hosts being innately bad. I actually loved all 3 of them. People just don't like change.
Stupendous!
I had an unsolved cube in my room for a few years now, I solved it during this video, well, I followed instructions on how to solve one during this video
I was sure that the mean time from equilibrium should be equivalent to mean recurrence time the until 13:10. Then you pointed out that the monkey can benefit from undoing his moves up to that point only in the mean recurrence time scenario. Interesting.
Yes -- the mean recurrence time is lower because for the first few moves after the solved position, there's guaranteed to be a short solution and the monkey might stumble across that. But from a random position, there's unlikely to be a short solution available.
Very nice video!!
A really nice video again :) I approve as a speedcuber and student of Mathematics.
That's great. I actually sometimes find it a bit frustrating that a lot of mathematicians just hate everything about twisty puzzles and that on the other hand the vast majority of speedcubers just don't see the point of treating twisty puzzles as actual puzzles to be sorted out and not just an exercise in pattern recognition :)
Mathologer Actually, at the moment I'm taking a course in abstract algebra and I really enjoy learning about Group theory concepts and applying them to a cube.
I feel like a more interesting version of the second problem would be to see how many random moves it takes on average to solve a specific cube configuration. I'm guessing that there's some symmetry in the graph of configurations that makes it so that this number is only dependent on how many moves away that configuration is from a solved cube, which would immediately let you solve problem #2 by computing a weighted average, while also containing a solution to problem #3. What's more, I feel like that problem might be easier, or at least easier to approximate. Given a configuration c, let l_c be the minimum amount of moves needed to solve it, and let s(c) be the (random) result of performing a random move on c. Evidently, if l_c=0, l_s(c)=1, and l_c=20=>l_s(c)=19 However, if l l=c=1, there's a 1/12 chance l_s(c)=0, and a 11/12 chance l_s(c)=2. Similarly for l_c=19 For 2>=l_c
1x1x1 cube puzzle solution: 24.75 I did this with the PRISM Model Checker using a markov chain. Here's the module: dtmc module m s : [0..65] init 0; [] s=0 -> 1/24:(s'=61)+1/24:(s'=62)+1/24:(s'=64)+1/24:(s'=65)+1/24:(s'=16)+1/24:(s'=12)+1/24:(s'=13)+1/24:(s'=15)+1/24:(s'=26)+1/24:(s'=21)+1/24:(s'=23)+1/24:(s'=24)+1/24:(s'=31)+1/24:(s'=32)+1/24:(s'=34)+1/24:(s'=35)+1/24:(s'=46)+1/24:(s'=42)+1/24:(s'=43)+1/24:(s'=45)+1/24:(s'=56)+1/24:(s'=51)+1/24:(s'=53)+1/24:(s'=54); [turn] s=61 -> 1/6:(s'=62) + 1/6:(s'=65) + 1/6:(s'=46) + 1/6:(s'=13) + 1/6:(s'=21) + 1/6:(s'=51); [turn] s=62 -> 1/6:(s'=61) + 1/6:(s'=64) + 1/6:(s'=56) + 1/6:(s'=23) + 1/6:(s'=12) + 1/6:(s'=42); [turn] s=64 -> 1/6:(s'=62) + 1/6:(s'=65) + 1/6:(s'=16) + 1/6:(s'=43) + 1/6:(s'=24) + 1/6:(s'=54); [turn] s=65 -> 1/6:(s'=61) + 1/6:(s'=64) + 1/6:(s'=26) + 1/6:(s'=53) + 1/6:(s'=15) + 1/6:(s'=45); [turn] s=16 -> 1/6:(s'=12) + 1/6:(s'=15) + 1/6:(s'=31) + 1/6:(s'=64) + 1/6:(s'=26) + 1/6:(s'=56); [turn] s=12 -> 1/6:(s'=16) + 1/6:(s'=13) + 1/6:(s'=51) + 1/6:(s'=24) + 1/6:(s'=62) + 1/6:(s'=32); [turn] s=13 -> 1/6:(s'=12) + 1/6:(s'=15) + 1/6:(s'=61) + 1/6:(s'=34) + 1/6:(s'=23) + 1/6:(s'=53); [turn] s=15 -> 1/6:(s'=16) + 1/6:(s'=13) + 1/6:(s'=21) + 1/6:(s'=54) + 1/6:(s'=65) + 1/6:(s'=35); [turn] s=26 -> 1/6:(s'=21) + 1/6:(s'=24) + 1/6:(s'=32) + 1/6:(s'=65) + 1/6:(s'=16) + 1/6:(s'=46); [turn] s=21 -> 1/6:(s'=26) + 1/6:(s'=23) + 1/6:(s'=42) + 1/6:(s'=15) + 1/6:(s'=61) + 1/6:(s'=31); [turn] s=23 -> 1/6:(s'=21) + 1/6:(s'=24) + 1/6:(s'=62) + 1/6:(s'=35) + 1/6:(s'=13) + 1/6:(s'=43); [turn] s=24 -> 1/6:(s'=26) + 1/6:(s'=23) + 1/6:(s'=12) + 1/6:(s'=45) + 1/6:(s'=64) + 1/6:(s'=34); [turn] s=31 -> 1/6:(s'=32) + 1/6:(s'=35) + 1/6:(s'=43) + 1/6:(s'=16) + 1/6:(s'=21) + 1/6:(s'=51); [turn] s=32 -> 1/6:(s'=31) + 1/6:(s'=34) + 1/6:(s'=53) + 1/6:(s'=26) + 1/6:(s'=12) + 1/6:(s'=42); [turn] s=34 -> 1/6:(s'=32) + 1/6:(s'=35) + 1/6:(s'=13) + 1/6:(s'=46) + 1/6:(s'=24) + 1/6:(s'=54); [turn] s=35 -> 1/6:(s'=31) + 1/6:(s'=34) + 1/6:(s'=23) + 1/6:(s'=56) + 1/6:(s'=15) + 1/6:(s'=45); [turn] s=46 -> 1/6:(s'=42) + 1/6:(s'=45) + 1/6:(s'=34) + 1/6:(s'=61) + 1/6:(s'=26) + 1/6:(s'=56); [turn] s=42 -> 1/6:(s'=46) + 1/6:(s'=43) + 1/6:(s'=54) + 1/6:(s'=21) + 1/6:(s'=62) + 1/6:(s'=32); [turn] s=43 -> 1/6:(s'=42) + 1/6:(s'=45) + 1/6:(s'=64) + 1/6:(s'=31) + 1/6:(s'=23) + 1/6:(s'=53); [turn] s=45 -> 1/6:(s'=46) + 1/6:(s'=43) + 1/6:(s'=24) + 1/6:(s'=51) + 1/6:(s'=65) + 1/6:(s'=35); [turn] s=56 -> 1/6:(s'=51) + 1/6:(s'=54) + 1/6:(s'=35) + 1/6:(s'=62) + 1/6:(s'=16) + 1/6:(s'=46); [turn] s=51 -> 1/6:(s'=56) + 1/6:(s'=53) + 1/6:(s'=45) + 1/6:(s'=12) + 1/6:(s'=61) + 1/6:(s'=31); [turn] s=53 -> 1/6:(s'=51) + 1/6:(s'=54) + 1/6:(s'=65) + 1/6:(s'=32) + 1/6:(s'=13) + 1/6:(s'=43); [turn] s=54 -> 1/6:(s'=56) + 1/6:(s'=53) + 1/6:(s'=15) + 1/6:(s'=42) + 1/6:(s'=64) + 1/6:(s'=34); endmodule rewards [turn] true : 1; endrewards and the property is: R=? [ F s=65 ] A state is characterized by two numbers. The first is its front side, the second its top side. Opposite sides are 1-4 and 2-5 and 3-6. Each line represent an action called "turn" with six equally likely outcomes. The first line specifies the initial state from which you go to any state with a equal probability. The reward specifies 1 reward for each turn action (i.e. for every action except the first one). The property asks for the reward accumulated specifies a reachability reward, i.e. what reward will be accumulated on average ("R=?") when my goal is hit ("F", stands for finally) where the goal is to be in state 65. State 65 is my declared solved state but any other valid state works here too. Run that through PRISM using the exact engine you get 99/4 or 24.75. With the 2x2x2 this method may work as well. You just need some good encoding for the cube state and maybe a super computer (PRISM starts to struggle when numbers become 6 digits usually, for the 2x2x2 we'd need 7 digits even).
I once held a seminar lecture about random walks on an integer lattice, and one of the results was that the expected recurrence time was infinite (for the symmetric case). Makes sense, since in this case the number of possible states is infiinite.
This whole circle of idea is definitely worth another video, Polya's theorem especially is something I'd really like to do at some point :)
Only in 3-or-greater dimensions, though.
This argument only applies to finite state spaces. In one or two dimensions, the expected recurrence time is finite; it's only infinite for three or more dimensions.
10:11 "Okay, so the God of speedcubing is Feliks Zemdegs." why is this so true
But _is_ it true? Or is it just the best thing a monkey has typed since the invention of the typewriter?
Deep Blue, great reference!
Hey can you do a video about using math to get out of the inside of a Rubik’s cube? I got sucked into another giant Rubik’s cube again and was thinking about your maths when trying to figure out how I get out.
Hey Mathologer, are you possibly having any merch with these shirts? I'd love to buy the: "Math. Nothing 2b^2 of!". It's like my greatest mission yet as a math student. Love your videos!
I always get chills when someone says my first name in a KZhead video
In speedcubing we say "turns" for what you mean "twist". "Twist" means phisicall corner rotation whitout turning the cube.
I was catching up on some old ones I hadnt seen. like this one. i recently watched a video by Lazslo Babai from 6 years or so on the graph isomorphism problem. he links the string isomorphism problem to that. he describes the string isomorphism problem by means of the Rubik Cube. randomly stick stickers onto 2 cubes, can you find an algorithm to determine whether or not one can be "moved" to be the other.
So i dont unterstand why the average from random to solved to should be more than the number of States. Both the random and the solved state are more or less imdistiguishble so the number should also be the number of possible States. The Simulation might have a bug or using non random numbers....
Average twists to solve (half-turn metric): 4410504.275 Average twists to solve (quarter-turn metric): 4647940.184 Let X be a random variable representing how many twists it takes the monkey to get from a solved state back to a solved state. The answer we seek is (E(X^2)/E(X)-1)/2. E means expected value. As noted in the video, picking a random configuration is equivalent to picking a random time in the monkey's history, thus asking how long it takes to solve a random start state is equivalent to asking when the next solved state is after a random point in time. To compute E(X^2), I used a computer simulation. Initially there were way too many states. The state graph has many symmetries, so many states can be combined together. Doing this resulted in a graph with just 77802 states. I simulated the first 2000 twists. After 2000 twists, the probability density function of X is indistinguishable from a geometric distribution, so I used that as an optimization to get the final result.
For half-turns only, I get E(X) = 24, E(X^2) = 1600.8 (exact), monkey number = 32.85 (exact). For the bandaged case, with quarter-twists only, I get E(X) = 29160, E(X^2) = 2769802402 (not exact), monkey number = 47492.68. For bandaged with half-twists allowed, I get E(X^2) = 2572392092 (not exact) and monkey number = 44107.73
I just quoted your initial post and that by Mark Miller in my comment pinned at the top of this comment section. Mark also put together a Slack organization [mathologersmonkeycube.slack.com] for people who are willing and interested to discuss the problem of the 3x3x3 cube (if you are interested in getting in touch with him directly please send me an e-mail and I'll forward his address to you) join.slack.com/t/mathologersmonkeycube/shared_invite/enQtMzgwODc1NjAwMzg3LWJjOGEwYWJlYTYwZjZkZmM4NDg5YWNkOWIzNzhiYTE3NzU1NDI4NGUwZjI3ODBlNTJjMWZjNmUyYjViZmM5YjI
Finally found someone that understand the cube and know there's WCA
I don't know why, but for some reason the words "devil's algorithm" kept coming to mind.
It's on my list :)
'Our three monkey problems' makes me think of the three body problem, but with monkeys...
My thoughts on the 3x3x3 God's number: Rather than solving every possible configuration, one might make a matrix of every possible configuration, and then track how to get there from a good state. One would start with one twist and then add that to a tree structure. Then add every possible single twist and add those configurations to the tree. One could then track how many steps (from solved) are required to get all the possible configurations. Still requires a super computer however.. My time to solve the 3x3x3 is about the minutes. I adapted those steps to 2x2x2 but I'm not all familiar with that yet.
I'm curious if you and Erich explored the shape of the distribution for the recurrence time (rather than just the mean)? I suspect it is fat-tailed vs. a normal distribution because of scenarios like the 2-move solve you pointed out. Understanding this distribution might be helpful with the "mean time from equilibrium" question.
"Understanding this distribution might be helpful with the "mean time from equilibrium" question." Yes, I was also pretty hopeful in this respect for a while and I still believe that there may be some insights to be gained in this respect. However, the first couple of things that came to my mind all did not really get me anywhere :)
The discussion on half-turn and quarter-turn metrics didn’t mention if turning a middle layer counts as a single step. I’m guessing it counts as one step, despite the prevailing move notations representing a center turn as two turns of the flanking layers.
Actually in both these metrics slice moves are counted in terms of two turns of flanking layers. There is a third kind of metric called slice turn metric where any turn of any layer, by any angle, counts as one turn. God's number for this metric could be less than 20 (but at least 18 :) There are also anti-slices, imbalanced anti-slices, compound slices and anti-slices, compound imbalanced anti-slices and various metrics that incorporate these specialised turns.
Mathologer - My first thought was since it’s possible to turn the middle layer independently, it should count as a single move. But then I started thinking of n-layer cubes. In retrospect, I think a single move should be defined as fundamentally and generalizably as possible, which would be a quarter-turn slice move. I take that to mean the player chooses any slice plane, partitioning the pieces left and right, and then do a quarter turn of those two partitions in either direction. With that definition, turning a 3-cube’s middle layer a half turn would comprise four quarter-turn slice moves, two quarter turns in each side. Otherwise we’d have to count a synchronous turn of the first, third, and sevenths layers as a single move.
I think the average solving time is greater than average recurrence time because of short recurrence sequences like U U’ or U R R’ U’ I think if we consider several main cases, we may get a good approximation of the average solving time. But if you ask for the exact expression, I don’t see how.
This is exactly correct. For the first few moves after a solved position, you're guaranteed that a short solution exists, and there's a small but significant chance that you'll randomly follow one of those paths.
Very interesting and amusing, as allways👍. Question: what is the number scrambled configurations that actually require at least 20 movements? It seems to me that a fair competition scrambler should make sure that the starting configuration is one of these combinations
There are about 500 million such configurations (www.cube20.org/)
I remember bringing the scrambled to solved problem up about a year ago. The people I asked kept insisting the answer was 20, because that's what google told them.
It might seem counter-intuitive that solved to solved takes fewer moves on average than scrambled to solved. You might think "But it has to go through scrambled first so why isn't solved to solved twice as long?" The solution was hinted at in the video, but maybe a more blatant explanation is needed. Solved to solved includes the possibilities where you simply do one or two moves and then reverse them, so solutions that are much less than the average. It also includes many that are much larger, where you maybe come withing one of solving the cube, and then stray away from the solved state for a while. This is what brings the average to the total number of possible states. However, when you are going from "well scrambled" to solved, you are not allowing the starting configurations that would only take one or two moves to solve the cube, but maybe only ones that take at least 5 moves, making it much less likely to get a short solve. This means the larger numbers still occur but the smaller ones do not, so the average gets driven up.
I thought 58 seconds was a bit much for randomly solving a Pocket Cube, so I wrote a monkey in c++ that solves in ~0.2 seconds.
cool, is it graphical or do you give it some kind of data structure and it spits out moves?
It was a data model that permutated until it solved.
Please do some continued fractions videos, it's something nobody makes videos about :)
0:08 lol im a speedcuber and a hardcore mathologer fan.
What are the numbers for those 3x3x3 cubes with pictures on each of the six faces where the orientation of the center square of each face has to be correct?
I've been thinking about the pocket cube recently. If one restricts to turning only one axis, then the options can be represented one-dimensionally. Of course, it is a circular geometry (or 1D spherical). If we use two axes, then the geometry of configurations seems almost 2D spherical, but in this case it is noncommutative. I'm beyond my depth at that point, but I would love to learn more.
It's helpful to fix one corner of the 2x2x2 in space and just turn the three faces that do not contain this corner. Then you can build things up by just twisting one of the faces (your circular), then two and then the full 3. I'll actually do a video soon in which I'll talk about this sort of stuff :)
I look forward to the future video. I think drawing it out as a network is not too much trouble, but I've been trying to think about how to represent it in (some sort of) space, given the noncommutative structure. I also wanted to represent it geometrically, recognizing, as you said, that each position is equivalent to the others. That is, the structure of the whole network of configurations looks the same from any node. As a side note, if I've done my calculations correctly, restricting the 2x2x2 to only two rotational axes limits it to 28197 configurations but the god's number (htm) would be 12.
Is a quarter turn of the middle rank of the cube considered a single turn, or may one only twist a top-bottom-or-side away from the rest of the cube in a single move?
Do the half- and quarter-turn metrics here count turning the middle layer instead of some face? I expect that in both cases that isn't considered a valid move and you need to turn both parallel faces instead, but I'm not sure.
Yes, that's right :)
Yes, HTM and QTM deal slice moves as two outer layer moves. There is also STM (slice turn metric) which handles slice moves as a single move (besides that it acts like HTM).
In this model the centres are fixed and cannot be turned, so it takes two moves to perform a slice turn
I don't understand why the random to solved can be longer than solved to solved. Why is that possible?
jwrm22 You can solved the solved to solved with a shorter time because with luck you can solve it in only 2 turns or a little bit more (wich is not the case with the unsolved)
I thought the same (going from solved to solved should be the same as from solved to scrambled to solved), but not all possible ways from solved to solved go through a state of sufficient "scrambledness", and those that don't pull down the average (solved -> solved) by quite a lot, because they are very short, compared to the average.
The solved to solved don't necessarily need to go through a position that is particularly scrambled, so it's more likely to just finish the cube in 1-5 moves or something a decent amount of the time. This brings the average down quite a bit, while the amount of twists needed to scramble it don't make up for the decreased average.
Exactly. If you start with a solved cube, after the first move, the cube is only one move away from being solved. Every time the second randomly-chosen move is the inverse of the first move, your "solved-to-solved" figure gets a 2 averaged in.
I wonder if its possible to devise a metric for how scrambled a cube is.
Do your simulations show the percentage of states visited by those random walks from solved to solved? Or the expected number of twists to visit all states? That might explain intuitively why the "scrambled to solved" path is longer than "solved to solved"
I had a feeling when the average number of turns was equal to the number of configurations that the proof would involve the fact that all configurations are functionality the same.
sir Mathologer you are my ideal plss tell me how to make a Mathematics channel like you
When you say "on average" is that the mean moves required by all solutions or the time it takes for the average monkey to solve the puzzle (i.e. median)? Big difference here I suspect (skewed distribution?) and one where both are quite suitable summaries of the problem given.
Agree, we shouldn’t have to wait for monkeys or anyone to scramble/unscramble possible combinations of particles in any multiverse to continue to enjoy “PBS Infinite Series“. Not a forward-thinking decision on the part of PBS to cancel it. The hosts, all 3, were gifted presenters of fascinating, thought-provoking material normally obtuse for almost anyone without a higher mathematics background. The kind of show (like yours) that can inspire folks to pursue math and science careers as they realize mathematics is a rosetta-stone for deciphering creative processes at work in nature, and which also reveals ways for them to create the kind of better future we all hope to live in. Enjoyed this video. Look forward to other Boltzmann (via monkeys if you want) related topics you might choose to do. In an era where content decisions can correlate with lowest common denominator trends, glad you are continuing to make videos.
10:15 are you sure? We're in 2018 and Max Park is a beast xD
I prefer counting quarter-turns but I guess a half-turn can be done as quick as a quarter turn so execution time must be differentiated from counting cycles.
Hi, I really like your videos, but here in the case of the 3x3x3 there is something you forgot to consider. If you start with a solved 3x3x3 cube, and later got it with only two centers rotated (by a quarter for instance), then the cube is solved though the state is not the one you started with. Said otherwise, there is not only one combination for a 3x3x3 cube to get solved, as there is no orientation needed for the center of each color, and this is even more true (truer?) for greater cubes. However, what you told is perfectly true if you switch the color of the centers for an oriented pattern (like a sign with no symetry by 180° rotation, the letter A for instance, but not the letter Z). Photographs or pictures generally do the job as well. To check my words, get a 3x3x3 Rubik's cube and see how the logo is oriented on the whites, then shuffle it and give it to solve to somebody who doesn't know how it was oriented. There is only one chance on four the logo will be oriented the same when the cube is solved again... so now imagine you have a logo on each colors... I tried to evaluate by myself, it took me only a few minutes to identify about one hundred (well I stopped at 82) different combinations for which the 3x3x3 cube is solved with only colors. And as I told you this is even "worse" for bigger cubes (because the center part is then also bigger). Hope this helps.
Karl Deux what you say is an excellent insight however the way that the solved cube is measured isn't based on one of the centers, in which case you would be right, but rather on one of the corners, thus leaving only one possible solution assuming that corner is stationary
Time to crowdfund a supercomputer for Mathologer to solve this by brute forcing!
I stopped monkeying around with the Rubik's Cube about thirty years ago. Ducci Sequences and Pythagorean Triads are far more satisfying
You should give cubing another go. What really interests me when it comes to twisty puzzles is finding my own solutions in a systematic way. There is so much great maths to be found there. I talk about the main very simple key insight in this video kzhead.info/sun/YLKFZ5qtiIGmfGg/bejne.html
So what's the intuition behind it taking longer to solve a scrambled cube than to scramble, then solve? I assume that's due to "lucky" barely scrambled configurations? And how long are the necessary mixing times actually? My vague guess is, that something like twice the maximum number to solve (i.e. 40 or 52) would suffice? And finally, is there any substantial difference between the metrics? Like, if you want to be efficient with respect to one or the other, does the most efficient sequence of moves ever change? - I assume the answer is no, since if quarter turns are ever more efficient, the half-twist metric will just use those. But maybe there are instances where, I don't know, two half-twists (= four quarter twists) can accomplish a solution just as fast as three quarter twists (pretty sure this particular example won't work due to the quarter twists not both being even or both being odd, but something to that effect) which would then mean the most efficient half-twist path is longer (in terms of quarter twists) than the most efficient quarter twist path...
Monkey'ing a cube wouldn't be a straightforward task on a supercomputer, since the calculation has to be done in series, and supercomputers work in parallel. Though I think you could make a parallel algorithm to do the job. To monkey-solve a random cube: 1) Each node starts with a solved cube (the "node cube") and constantly applies random moves. Each time a move is made, record the state of the cube in a hash table, along with the *inverse* of the move made. (if we want a verifiable solution, store the data in two hash tables, so we can discard cube states later; if we don't care about the moves used to solve, we don't need to record them) Each node calculates this list until it receives the current cube (the "objective cube"). 2) When a node receives the objective cube, check if any recorded cube states from the node cube match. If a match exists, then the objective cube is solved. The solution is all the previous moves to objective cube (by other nodes), plus every inverse move in the list of moves added before and including the matching record in the hash table. 3) If there is no match, then take the node cube and apply its permutation to the objective cube. (i.e. apply every move this node has generated, all at once). Then pass the objective cube on to the next node, reset the node cube to a solved state, and start a new hash table for recording moves (delete the old states, but keep the list of moves if you want to look at it later) I assert that this algorithm will provide solutions with the same distribution as a simple monkey solver. This algorithm is also light on network resources and automatically adjusts to network lag and cluster size (nodes will just keep calculating while waiting). It seems like a perfect candidate for a distributed computing effort.....
Nice
Ok, complete wild guess on my part. 43.252B*4/3^(1/3)= 47.6 Billion moves. I also guestimate the 1 sided cube at 33.9 moves. using the same approach. For curiosity my formula is : #of configurations * ((n+1)/n)^(1/n) .
Too bad, that logic does not hold up. I assume you meant to say the expected number of moves to solve a random 1x1x1 is 33.9, but it is 24.75.
Hm. The proof for the mean recurrence time wouldn't even necessarily require that all of the states of something are similar. The only requirement really is that all states tend towards being equally probable as the number of steps goes to infinity.
It should be noted that monkeys, like humans, are notoriously non-random. Also, rather destructive. See "Notes Towards the Complete Works of Shakespeare" (2002) by Elmo, Gum, Heather, Holly, Mistletoe and Rowan.
Transmission Control The typewriters used in the experiment ended up rather unsanitary, if I remember correctly.
Did anyone else notice that at 3:25 when the twenty is hilighted, the cube that represents it is in a super flip configuration?
Well spotted :)
So I know \how\ to do the problem given at the end of the video, but it involves me making a 24 by 24 matrix, with each row and column corresponding to one of the states, with 0's everywhere unless you can transition from the row state to the column state, in which case you put an entry of 1, with the states in the same order for the rows and columns. Then, you divide each row by its sum, to change it into the probability matrix, which you then modify by setting each entry in the row and column of the solved position to 0, and call this matrix A. Then if a vector x has the probability of the matrix being at a certain state (each entry corresponding to the column), Ax has the probability of all of the twisting you can do to the matrix. This is a symmetric matrix, and since it has this "probability minus a little bit" feel, we hope that as n goes to infinity, A^n*x goes to 0. Note that what we care about for average solve time is slightly different- the percentage of cubes that achieve the solved state at step i+1 is it is |x_i|-|Ax_i|=|x_i|-|x_(i+1)|=f(i+1), so really what we want is the sum from i=1 to infinity of i*f(i) So, if there is some nice, closed form version of f(i), you can probably plug it into wolfram alpha. And thankfully for us, there is, because as already mentioned, A is real and symmetric, and as such has an eigenvalue decomposition and can be written as VDV', where D is a diagonal matrix and V is orthogonal.Then, f(i+1)=|x_i|-|VDV'x_i|=|VD^iV'x_0|-|VD^(i+1)V'x_0|, where we set x_0 to be the matrix with 1/24 at every position, i.e. an equal chance to be at every ruby position state, and you're done! … except that I don't know how to simplify down f(i). Lets try a different strategy: this time, we're going to change the matrix A so that the entry corresponding to the row and column of the solved position is 1. , i.e. once you are at the solved position, you stay there. Then, set f(i+1)=x_i+1,(solved position)-x_i,(solved position)=x_(i+1)*e_s-x_(i)*e_s=e_s*(x_(i+1)-x_i), where e_s is the standard basis column vector corresponding to the solved position, and * is inner product. Notice that the "direction of the subtraction" reversed. Then, we still want the sum from i=1 to infinity of i*f(i). We still need a closed form for f(i+1), and the approach starts off the same way, but is much more successful- f(i+1)=e_s*(x_(i+1)-x_i)=e_s'(VD^(i+1)V'x_0-VD^iV'x_0)=e_s'V(D-I)D^iV'x_0. Grouping usefully, this becomes: f(i+1)=(e_s'V(D-I)) D^i (V'x_0), using the same x_0 as before. f(i) then is not geometric, but its close- For some constants a_m, it can be written as a_1D_1^i+a_2D_2^i+…a_24D_24^i, which is definitely good enough to get a number for the sum from one to infinity of i*f(i), by separating each of the terms and summing them up separately. There are 2 flaws in this approach: The eigenvalue decomposition is not guaranteed (and in fact, probably wont) only contain say algebraic numbers in it, particularly if done iteratively (like every computer ever does it), but this would just need to be checked for this example, and the other flaw is I reallyyyy don't want to make the matrix Either way you cut it, this does not seem to be the correct way of doing this calculation. Anyone have any comments on this or better ways to do it?
Well, apparently this is basically the right thing to do, because I think the paper cited uses (much more elegant) versions of the same basic idea
Given a solved Rubik's Cube, what is the most number of scrambling moves that can be made before there is more than one solution to unscramble it with the same number of moves? I suspect it's more than 5 or 10 but how would you prove what it is.
feliks' 4.22 is the world record
Are there multiple ways of having a solved Rubik's Cube? for example if the centers could be rotated 90 180 or 270° it would also be in a different configuration, but still solved?
yes, if you have a picture cube where you can see the center rotation, the cube can be completely solved with the centers still being rotated (no one center can be turned 90° only 180° or 2 centers each 90°)
Yes, these states are all considered "solved" on a normal cube. You can get cubes where the centres do have an orientation; these are known as "supercubes". Here's what a 4x4 supercube looks like: i.imgur.com/h3UoxCA.jpg Some also have arrows on; solving the cube normally may leave the central arrow pointing in the wrong direction. Solving these normally is not much different to solving a regular cube, but it would certainly change the calculations in this video!
math amatics In real life yes, but in this experiment the centres of the cube are fixed, and therefore there is only one solution
Im not sure if you have accounted for this, a wile back I realized that the rubiks technically doesn't just have one solved state, their are actually thousands of them, possibly even tens of thousands of solved states in a regular rubiks cube, it might be a little hard to wrap ones head around it, but you can rotate the the middle prices on a regular rubiks cube, and I suspect if you tell a computer only to look for one of theses solved states it may entirely pass by so perfectly solved positions just because the center pieces weren't oriented currently, is this accounted for in theses calculations? if not you could be massively overstating the average amount of turns it takes to reach one of the thousands of different solved states
Starting from fully solved cube and twisting it once in any direction gives one random position, it can be solved with one twist backwards, that's the shortest random move, but if one turns it instead to the same direction again and then back again and then back to the original direction and so on then we are at a loop and no solution can be found, unless one changes the direction of turn just before the solution. So the number is the mean value between infinity-1 and 1 Problem solved... :) Randomness does not mean diversity, just one turn of the cube gives one possible random position the cube can be at. It's just as valid random position than one that has been twisted thousands of times. Twisting the cube in a loop one step forward and one step back is just as random as any other move.
Jyrki Koivisto but it's much less likely.
It's just as likely, that's the way randomness works. It has no prejudice for one move over the other. Just think about it, looping infinetely just before the solution is just as random as any other move. You could twist the cube in any other direction randomly and infinitely if you wish just loop it such that the solution will not be found and the solution will still be between infinite-1 and 1 The cube can be twisted infininetly and no solution will ever be found (if one is just about to solve the cube, then just don't. There's always a move to be done that doesn't solve the cube), that's the main point. And the move will still be as random as the others. But all it takes is one turn and the cube is solved. "number" that has no limit is very much larger than any "number" before it, so it doesn't matter how long one twists the cube, but still the solution will come just before infinity or else there is no solution.
Yes, but the probability of that infinite sequence of "wrong" moves is only infinitesimal, which is why the _average_ recurrence time is N (number of states of the system).
3:22 Or Jeff Goldblum's powerbook.
at 3:39, the subtitles should read stochastic instead of sophistic, no?
I think I'm missing something: The sketch of the proof tells us that we can consider any starting configuration of a cube, and the expectation will be the same: the number of permutations. But isn't that exactly what we're asking the monkey to do in problem 2?
"and the expectation will be the same". You have to be clear about what expectation we are talking about here. It is the expected number of steps it takes to get back to this configuration when you start at this configuration :)
Ok, then I get it.
Wouldn't there be multiple 'solved' configurations for the 2x2x2, since the solved cube can be in one of 24 orientations? This would bring the mean recurrence time down by a factor of 24.
Standard is, just like how the centers of a 3x3x3 are considered to never move, that a specific corner is considered to never move.
lmaoo 10:10 "the god of speedcubing"
Well, he certainly is :)
Cube is one move away from being solved... does wrong move
M Lienau happens to me all the time...
That's OK -- you're still only two moves away from being solved, so you have a decent chance of solving in two more moves.
i like it
@7:45 At this point I'm really interested in why my intuition is wrong. Intuitively, it _feels_ like starting with a solved cube, putting in 100 random twists to randomize it, then randomly solving, should give the answer to Problem 1 less the number of random twists at the start. But the answer to problem 2 is significantly larger than the answer to Problem 1. Mathematics is frequently counter-intutiive so that in and of itself is fine. I'm just wondering what the problem in the intuitive reasoning is.
I think your intuition breaks down by overestimating the likelihood you would successfully invert the sequence of 100 twists you made and what it means for those 100 twists to randomize the cube. If the 100 twists actually randomizes the cube (i.e. chooses one of the N configurations uniformly at random) then it doesnt matter if this was done with 100, 1000 or 100000 twists. The problem is still the same. Furthermore, in the video he mentioned that any configuration can be solved with 20 moves or fewer. So if we assume that we need 20 moves then the probability we correctly perform the sequence of 20 moves is (1/27)^20 or approximately 10^-20. Which is a very small number. The probability that you exactly invert your sequence of 100 moves is much worse.
@@a63bd8lkjbf98 Thanks for responding! :) "I think your intuition breaks down by overestimating the likelihood you would successfully invert the sequence of 100 twists you made and what it means for those 100 twists to randomize the cube." Hmm... Let me see if I'm understanding what you're saying. First, I'll restate the problem I'm having a little bit better: It takes an average of 3,674,160 twists to go from solved back to solved. Let's re-run that test, two instances in parallel. We give Monkey A a solved cube and get it to start twisting randomly. After Monkey A has done a couple of hundred twists, we stop it. We then copy the cube it currently has, and give the copy to Monkey B. Both monkeys then start randomly twisting their own cube at the same rate. My intuition tells me that both monkeys should arrive at the solved cube in the same number of random steps. However, Monkey A is doing mean recurrence time, and Monkey B is doing mean time from equilibrium. And the host is telling us that Monkey A takes 3,674,160 twists on average, and Monkey B takes 4,500,000 twists on average. Intuitively, that seems kind of bonkers. If I'm understanding you correctly, is the problem that Monkey A isn't _actually doing_ a mean recurrance time? In the example above, we're not truly doing mean recurrance, because any example where Monkey A accidentally solves the cube too early by randomly reversing its own sequences gets removed from the data set for Monkey B. Which means that all of the instances where a mean recurrance test finishes before the "couple of hundred" threshold are removed from the data set, and this inflates the count for Monkey B? Or am I completely lost here? Thanks again. Genuinely confused here. Appreciate the help.
I only understand about 2/3 of the math related terms you say, but that’s probably because I’m still taking calculus in high school
I just have a question, if I remember right the 43 quintillion also includes the impossible states, those that could never be archived by twisting a cube, so on the average from solve to solve are we taking them into consideration or not? Or I'm wrong and the 43 quintillion is only of accessible states?
The the 43 quintillion are only of accessible states. For the 3x3x3 to get the total number of all configurations, accessible and inaccessible you have to multiply this number by 12 :)
Mathologer Thanks, I guess the number of states is way bigger than I remembered.
For your math did you use quarter turn metric, half turn metric, or slice turn metric? It would have an effect on the results.
If you watch to the end I talk about half turn and quarter turn metric and what influence using one or the other has on these numbers. To start with all numbers are w.r.t. the half turn metric :)
Mathologer OK thanks, sorry about that.
The Monkey number? Well, I don't know, maybe it's the "Humans' intellectual superiority has gone far beyond far, transcending that of monkeys, to the point where monkeys can't count." So no Monkey number for you.
Where can I sign up for PBS Infinite Series to produce videos again? I loved their videos as much as I love yours!
Leave a comment on their last videos and also leave a couple of comments to this effect on some of the other PBS channels you like :)
There is a similar idea with monkeys instead of letters. In a finite amount of time (which can also be veeeery long, but much shorter than an infinite amount of time) you could try out all possible colour combinations of an image of a defined size like 1920x1080 with a defined colour depth like 24 Bits. The result would be ANY image you could possible imagine. That idea is quite mind blowing. There is a blog post about that idea: www.mathegedanken.de/bitmap-zeigt-alle-bilder
It was the best of times, it was the blurst of times.
Here’s an example of bad reasoning but I’m not sure why (I should probably wait until the end of the video and whatever proofs you go through; I stopped when I first got confused). It seems counterintuitive to me that the mean time from equilibrium should be so much larger than the mean recurrence time. Maybe I’m being led astray by the mean recurrence time being equal to the number of configurations. That seems to suggest to me that some significant fraction of the configurations occur during a given “recurrence trial”, ergo there’s a reasonable likelihood
ack didn’t get to finish before my clumsy fingers foiled me... anyway to continue - configurations occur during any “recurrence trial”, ergo there’s a reasonable likelihood that any given configuration will occur during some “recurrence trial” ergo the mean time from equilibrium should be shorter than the mean recurrence time.
I'm a bit confused by the result for the average number of moves to randomly descramble. Could someone tell me what is wrong with the following argument? Randomly descrambling a random configuration is like starting off at some extremely large (and random) N on the diagram at 15:00 and seeing how many moves it takes to visit the solved configuration. Since we are starting at a random N, the average number of moves to the next recurrence will be exactly half the recurrence time. (i.e. 1837080, not 4.5 million for 2x2x2) Is there some stipulation that the random starting position be at least some number of moves away from solved?
Wie rechnet man eigentlich die ganzen verschiedenen Möglichkeiten aus, wie ein würfel verdreht sein kann? Also wie zum Beispiel beim 2x2x2 die 3,674,160
I think I might have an idea to approach the 2x2x2 problem, but I need some clarification, as somewhere in the comments i saw you saying you have a 1/12 chance to come back after one move. I'm not quite sure how you get to 1/12. To stick with notation usually used, there is U, U', U^2, D, D', D^2, B, B', B^2, F, F', F^2, L, L', L^2, R, R' and R^2. Regardless of the first move, there are 2 that solve it. It in reverse and it's opposite one in the other layer. So where is this 1/12 coming from? What am i missing?
Use quarter turn metric
Even in quarter turn metric, there are 2 out of 12 that solve the cube. Suppose R is our first move, both R' and L solve it.
tbpotn good point. Are you sure the comment you saw didnt refer to the 3x3x3? Because there it would be 1/12
I guess that is possible!
This is too complicated for me, I mean, I can barely do a 1x1x1 cube :/
I've got just the 1x1x1 problem for you at the end :)
luclily 1x1x1 cubes come solved out of the box, so i always just throw the old one away and buy a new one. it's very clever.
Indeed, 1x1x1 is hard, I want 0.5x0.5x0.5 :) But btw, I wam wondering here if it's possible to every construct some formula to actually calculate any n*n*n cube just by putting "n" into a given formula/algorithm, whatever, knowing, that the algorithm itself should be more clever though than just the brute force method ...
It depends how the 1x1x1 cube is sitting in the box and which way its opened. There a 23 in 24 chance that it won't be solved unless its packaged to sit in the solved configuration with careful instruction on which way to open the box.
RCB Am I the only one who still calls him NerdBubbleGum?
I get it so. every combination if you were to randomly scramble the cube for as many combinations as there are. to the power of as many combinations as there are. there would be an equal number of chances for it to be any given combination including solved and completely scrambled. Something like that???
Consider my mind blown.
What were you talking about 20:05 how could they and why didn't you help us help you help us all, by helping us at sending complaints...
Andreas Aristokrates wow, I understood your train of thought, wow. Well said.
that train of though is almost worth a video on it's own :)
I feel it
If you're scrambling a pocket cube, (or a 4x4x4 but a 3x3x3 is OK), you can't just say "Do N random moves". You have to start by flipping a coin to decide whether you're going to do N or N+1.
No you don't, you just leave one corner fixed in space throughout and randomly turn the faces that don't contain this corner :)
I think I see what you mean. If (on the 2x2x2) I end up in the dreaded "odd number of swaps" scenario with exactly two corner pieces swapped (i.e. one swap), I can just decide that one of those two corners is actually in the right place, and all the other seven corners are wrong, which I can fix with 6 swaps (an even number). I need to get my 2x2x2 back from the kid I lent it to to try this :)
If by random move you mean a quarter turn, then you were right. Choosing a fixed N will always give you the same permutation parity, so only half the scrambled states can be reached. This is so whichever corner you consider fixed because a whole-cube rotation is an even permutation too. If your random moves include half turns, then the parity is not correlated to the number of moves, and for a large enough fixed value of N every cube state could be reached.
Jaap Scherphuis Yes exactly, and you're right that you won't run into this issue if you do a fixed number of random half turns. But I think for the 2x2x2 any position can be solved with either an even or odd number of quarter turns after all if you just change your mind about the orientation. There are no centre cubies to stop you doing this. This difference between the metrics only highlights the arbitrariness of shuffling with N random turns in either metric. I think we can design a much better small alphabet of moves which when chosen randomly a certain number of times will give us a much more uniformly distributed scramble. It would be fun to try and design these moves. Having said that the uniformity of the distribution is pretty much a red herring when it comes to how difficult the cube is going to be to solve. For any human solver about 26 random quarter turns will take as long to solve from as a anywhere else. But I do think 26 random quarter turns will on average be faster for God or a monkey to solve from than a uniformly selected random state of the cube.
Changing your mind about the cube orientation has no effect on parity. Cube rotations are even permutations - a cube rotation can be done with two quarter turn moves - so reorienting the cube or choosing a different corner as your fixed reference point keeps the parity the same regardless. Re different scramble sets: It is theoretically possible to solve the 3x3x3 cube using just 2 move sequences, without even reorienting the cube. Conversely, you can scramble to any state by randomly applying those two sequences. It will take a lot longer however, even if you count each of those sequences as one move. This is because you have fewer options to choose from at each step, only two in this case, so it takes more steps for the number of possible scramble sequences to exceed the number of possible scrambled states. And much longer still for the scrambled states reached in this way to be approximately equally probable.
ОБ ЭТОМ Я ДОДУМАЛАСЬ17ЛЕТ НАЗАД.И ДЕЛАЛА ГЕНЕРАЦИЮ ИЗ БУКВ.ЖАЛЬ,ЧТО ВЫГЛЯДИТ ТАК,БУДТО ОН ПРИДУМАЛ ЭТУ ЗАДАЧУ,А ДРУГИЕ-ТИПА НЕТ( спасибо за русский перевод!
Sir please make video how to solve 8 power eq.
what is 8 power eq.? my first thought was an eigth degree polynomial, some of which have solutions which can't be expressed exactly.
You mentioned that the recurrence time is the same whether you use the 1/4-turn or 1/2-turn metric. So what if we use a 26-quarter-turn metric? In this metric, one "turn" is any combination of 26 quarter-turns. Since God's Number is 26 (in the 1/4-turn metric), we can always solve the cube with just one of these big "turn"s. We just have to pick the right one. Thinking about recurrence time, the diagram you drew looks the same, so the reasoning should work the same. I can still do one "turn" and end up somewhere (e.g. superflip :) and then get lucky and get back from there with one "turn", since any state of the cube is within 26 1/4-turns of any other. So I think the recurrence time is the same in the 26-quarter-turn metric as in the 1/4-turn metric. But the number of turns needed to scramble the cube is surely just 1 in this 26-qt metric. It's just like rolling a die-- you only have to roll it once to "scramble" it. In the 26-qt metric our cube essentially becomes a 43 quintillion-sided die. So to answer the question: how many moves is enough to scramble a cube in the regular 1/4-turn metric? Well 26 random 1/4-turns is equivalent to a single random turn in 26-qt, so I reckon 26 1/4-turns (or 20 1/2-turns) should be enough to scramble the cube.
Good point. However, it's important to realise that we are not just interested in scrambling the cube. What we want is to make sure that after whatever procedure for randomising we settle on we are "equally likely" to end up at every possible configuration of the cube. In fact, it's fairly easy to see that no matter how many twists you use to scramble "equally likely" is never going to happen and so we first need to agree on what we mean by "equal enough". Have a look at the discussion of randomising a deck of cards by shuffling starting on page 9 of this document www.dartmouth.edu/~chance/teaching_aids/Mann.pdf
Mathologer There's clearly (at least one) flaw in the argument I gave anyway, although I think it might work like that if you stick strictly to the 26qt metric, in other words if you end up with a solved cube halfway through the 26 parts of a single "turn" you ignore it and keep going. The weird thing is how scrambled to solved is about a million more turns on the pocket cube than solved to solved. You wouldn't think it would take a million turns to scramble a pocket cube! The chance of backtracking back to solved whole trying to scramble doesn't feel like it should be so high. Of course there is a difference between scrambling for a monkey (or for God) and scrambling for a human solver. I'm still thinking about the original problem but a good way to scramble for God or a monkey might be to just put the cube in superflip (which is a God's move away from solved). There's no need to do anything else as the monkey won't have memorised a quick way back from superflip and God knows the fastest way back from anywhere anyway.
OK see what you mean about "equally likely". I was just thinking more in terms of how to make life difficult for the Monkey or God (in which case I think "scrambling" by putting the cube in Superflip would work pretty well-- I think that might take the Monkey longer on average to get back to solved from than a uniformly randomised starting state, and would take God the longest it's ever going to take Him, but would be terrible for human competitions). So then I was thinking how many random twists to get the Cube to a state where the Monkey will take at least as long to get back from as from a uniformly random state (which is what the "blowing apart" you said in the video they do for competitions gives you). But this is not the criterion for "shuffled" we're interested in. We want to know how many random 1/4 turns to emulate blown apart well enough. Thing is with cards you're usually going to play some other game (than trying to get back to an ordered deck with more shuffling) so the uniformity of the distribution is more of a priority. If you wrote down all 43 quintillion states and the God's move for each one, then picked one of those God's moves at random and did it, that would give you perfect uniform shuffling. So that would be one move from an "alphabet" of 43qn. A super-efficient and effective way of shuffling, apart from needing to work with such a big alphabet. Instead we're trying to do a close-to-uniform shuffle with N moves (we don't know how many) from an alphabet of 12 (the number of possible 1/4 turns). So here are some other questions: is there some compromise position between these two, where instead of picking from a choice of 12 moves at each step, or from a choice of 43qn, I pick at random from say 100 carefully designed sequences of moves, and end up with a better shuffle (i.e. closer to uniformity in fewer total 1/4-turns) than with the alphabet of 12? Is it just better to use longer and longer alphabets all the way up to 43qn if you can? How to design those sequences of moves? I think there's some magic a bit like this involved in crypto algorithms like DES where they use carefully designed sequences of shuffles that are supposed to make sure things get shuffled up well with the smallest number of iterations, but obviously there's also a memory constraint on the size of the "alphabet".
Mathologer So I think 26 random moves doesn't give you a very good distribution. 26 moves will only give you one route to the "maximal" positions (like superflip although I just read that superflip is only maximal in 1/2 turn metric, but there are similar positions that are maximal and only have one path to them in 1/4 turn metric) but it will give you many more different routes to intermediate positions that are closer to solved. So the positions closer to solved will be quite heavily weighted. It's a bit like setting a random ant the task of walking from the North Pole to the South Pole. If you work out it's N steps to get to the South Pole if he's very lucky and goes in a straight line (OK geodesic) , and he takes N random steps he's unlikely to even make it out of the Northern hemisphere. Of course there is more than one route to the South Pole but many fewer routes than there are ways of noodling around and ending up not far from where you started. To work out how many ant steps are enough to approximate picking a random point on the globe sounds like it might not be _too_ hard. But the paths between the cube states are more like a very complicated tube map with a lot of intersections and varying distances between stops on different lines. Seems like it might be very hard to work out the distribution of states you reach after N moves without completely brute forcing it.
If I used the proof method to get the scrambled->solved number as well, wouldnt i end up also getting # of configurations as my answer? What am i missing?
In the proof we are averaging over the lengths of intervals between dots that follow each other in columns (solved to solved), at the same time we use the fact that the contribution to this average of the irregular way things start out vanishes in the long run :)
When the computer "explodes"and rearranges all of the pieces, wouldn't it be possible for it to make a parity error?
Yes, that's why I said only 1/3 of the cubes you get this was are actually solvable by twisting. In the very early days of this channel I made a video about how you can recognise easily whether or not things will work out : kzhead.info/sun/qM-GnryvfWuvZ5s/bejne.html
Aren't the configurations dependent? To me it seems like this proof (14-15 min) is for the case when you can randomly go from one to another, like rolling a dice.
The configurations are certainly "dependent", but the main thing to realise is that once the monkey hits a configuration it basically starts the whole experiment again from this configuration but this time with respect to that new configuration. And so we can expect from that point on for the cube to return to this state in essentially the same way as for the solved configuration. And when we are averaging it does not matter that it took a while to get to the new state in the first place because we are averaging over arbitrarily large numbers :)
Was Mr. Polster ever a Pollster?
I don't know if it's because of the left out details, but the proof you gave in this video did not manage to convince me. After thinking about it some more I accepted that the result might be correct, but it still seems completely counter-intuitive.
2x2x2 Rubiks cube should be called the Twobiks Cube
I feel like I'm missing the obvious here but at 14:17 I don't exactly understand how the diagram can contain N dots. Can somebody explain that?