# Is 20 turns enough for a scramble?



## peterbone (Nov 16, 2012)

I wrote some code to analyse this. I tested scrambles from 0 turns to 50 and counted the average number of joined corner-edge pairs after the scramble. I tested each scramble number 100,000 times to get an accurate average.

The results are shown in the graph below. The average number of corner-edge pairs converges to 1 for a fully random scramble because there are 24 possible corner edge pairs and each one has a 1 in 24 chance of being joined (12 edge positions * 2 possible edge orientation for each).

The average number of corner-edge pairs for a 20 move scramble is 1.92 - almost double the value for a fully random scramble. Admittedly, by scramble algorithm doesn't avoid cancellations, so the actual value would be slightly less.

The more corner-edge pairs you have, the easier it will be to perform an x-cross or block build and get a quick solve.







Sorry if this has been done before and is already well known. Obviously increasing the number of turns for a scramble would be annoying, but increasing it to only 30 brings the value down to 1.23 - much closer to a fully random scramble. I wonder who chose 20 in the first place and what did they base it on?

So, what are people's thoughts on this?
Also, has anyone derived formula for calculating the above data mathematically?

Peter


----------



## AndersB (Nov 16, 2012)

> I wonder who chose 20 in the first place and what did they base it on?


20 is based on God's number.


----------



## stannic (Nov 16, 2012)

AndersB said:


> 20 is based on God's number.



I think he knows it.

@Peter: Interesting analysis. I do not know, though, how the scrambles are selected "officially". Maybe they are using something like Cube Explorer to generate truly random positions and then find generators for them? In this case, all positions can be picked with equal probability.

- Bulat


----------



## peterbone (Nov 16, 2012)

AndersB said:


> 20 is based on God's number.


I agree that it should be at least God's number since this is the minimum required to reach any state. However, only an infinite move scramble would ensure a fully random solve (probability of corner-edge pair = 1). There has to be a compromise between practicality and randomness. Maybe 20 is it, but to me it looks too far from random.



stannic said:


> I think he knows it.
> 
> @Peter: Interesting analysis. I do not know, though, how the scrambles are selected "officially". Maybe they are using something like Cube Explorer to generate truly random positions and then find generators for them? In this case, all positions can be picked with equal probability.
> 
> - Bulat



OK, I hadn't considered that. If that is the method they use for generating scrambles in competitions then obviously the scrambles are fully random but still only 20 moves long, which is ideal.


----------



## stannic (Nov 16, 2012)

Found this thread:
http://www.speedsolving.com/forum/showthread.php?12969-WCA-Scramble-Algorithm


----------



## Kirjava (Nov 16, 2012)

Competition scrambles are suboptimal random state, and checking ce pairs solved is a poor method of testing scramble randomness.


----------



## qqwref (Nov 16, 2012)

peterbone said:


> Admittedly, by scramble algorithm doesn't avoid cancellations, so the actual value would be slightly less.


Okay, so that definitely needs to be fixed to get useful results. I think that move cancellation is definitely contributing to the high number of c/e pairs you found.

And 25 moves (not 20) was the standard before we implemented random-state scrambles, which are now used in competitions as well as good scrambling programs.


----------



## Zarxrax (Nov 16, 2012)

There is a difference between a truly random scramble and a scramble that meets the arbitrary measure of randomness that you have proposed.
Having corner edge pairs that match up might make a solve easier. But they have nothing to do with the random state of the cube. You could have a fully solved cube that is still a random state.


----------



## qqwref (Nov 16, 2012)

Zarxrax said:


> Having corner edge pairs that match up might make a solve easier. But they have nothing to do with the random state of the cube. You could have a fully solved cube that is still a random state.


Uh what? He's measuring averages. If we know that doing X random moves gives you more corner-edge pairs on average than a random-state scramble, that means that X random moves is noticeably easier than a random-state scramble.


----------



## CarlBrannen (Nov 16, 2012)

I would like to know what a " suboptimal random state" is, or failing that, an "optimal random state" might be enough.

And I'd also like to see the graph when the moves are prevented from cancelling each other. In addition to stuff like L L'.
And there's one more addition to the random scramble I'd like to see and that is to avoid consecutive moves like LR. The reason for avoiding this is because LRLR doesn't do anything.

So given that the most recent move was U, the next move can be: F, B, R, L, or these with ' or 2. So there are a total of 12 possible next moves.

With this restriction, I wonder what the shortest identity is? Sexy move 6 times would be length 24, (i.e. RLRL RLRL RLRL RLRL RLRL RLRL) but I bet there's one of length around 9.


----------



## qqwref (Nov 16, 2012)

"Suboptimal random state" = generate random cube position, generate a short but not necessarily optimal scramble for that position.
"Optimal random state" = generate random cube position, generate an optimal scramble for that position.

And there's no reason to exclude stuff like LR, just exclude stuff like LRL. I don't know why people are acting like the problem of randomly generating non-canceling moves hasn't been solved, because it has, for many years. Jaap's scrambler did it for all cube sizes in 2006, and I wouldn't be at all surprised if someone had written a proper scrambler several years before that.


----------



## Stefan (Nov 16, 2012)

CarlBrannen said:


> I would like to know what a " suboptimal random state" is



It's a quote taken out of context. The "suboptimal" (I still prefer "near-optimal") referred to the scramble, not the state.



CarlBrannen said:


> And there's one more addition to the random scramble I'd like to see and that is to avoid consecutive moves like LR. The reason for avoiding this is because LRLR doesn't do anything.



LRLR is bad, but LR is good and shouldn't be avoided.


----------



## Stefan (Nov 16, 2012)

peterbone said:


> The average number of corner-edge pairs converges to 1 for a fully random scramble because there are 24 possible corner edge pairs and each one has a 1 in 24 chance of being joined



I'm wondering whether that's true. The 24 possible pairs aren't fully independent (for example it's impossible to have exactly 23 pairs), so I have doubts whether we can just add the 24 values of 1/24. Thoughts?


----------



## qqwref (Nov 16, 2012)

We could generate a whole bunch of random scrambles and check how many c/e pairs they have. I would think the expected value would be near 1, although it may not be exact.


----------



## CarlBrannen (Nov 17, 2012)

Stefan said:


> I'm wondering whether that's true. The 24 possible pairs aren't fully independent (for example it's impossible to have exactly 23 pairs), so I have doubts whether we can just add the 24 values of 1/24. Thoughts?



Nice observation!

Maybe here's a way of getting around it...

Unassemble a cube. Pick a corner and an edge at random. Now assemble the rest of the cube randomly. Is the expected number of edge matches equal to 21/24? (I'm guessing that the number will depend on whether or not the corner and edge happen to match, but that the expected number of matches will be 21/24.) Now you can get a random cube position by inserting the two missing pieces in only one of the six possible ways. And I think it's possible to figure out the expected number of matches.

But to do the problem, maybe you have to sum over all possible relative choices of the separate cube and edge and it might be hard to do.


----------



## Stefan (Nov 17, 2012)

qqwref said:


> I would think the expected value would be near 1, although it may not be exact.



The thing is, it might be exact and I just don't understand why, so maybe some theory master can help me out 

Consider the 2x2x1 and its corner-corner pairs. It has six states, one with four pairs, one with zero pairs, four with one pair. So an average of 8/6=4/3 pairs. On the other hand, there are four possible pairs, each with 1/3 chance. Which also leads to 4/3.


----------



## peterbone (Nov 17, 2012)

Stefan, yes, I did wonder why it was exactly 1 despite the non-independence between pairs. It does seem to be exactly 1 from my results though. I also tested a 1000 move scramble 100000 times and it came to 1 to three decimal places. It's no wonder that colour neutral solvers have an advantage when there's a 50/50 chance that they'll get a corner-edge pair that they can make full use of.

qqwref, I may re-run my program with cancellations then. Do you just have to check cancellations between consecutive pairs of turns or is it more complex than that?


----------



## qqwref (Nov 17, 2012)

peterbone said:


> Do you just have to check cancellations between consecutive pairs of turns or is it more complex than that?


The rule is, you can't use the same face twice in a row, and if you use one face and then the opposite face you can't immediately use the first face again. So you don't need to check for cancellations, just avoid anything of the form FF or RLR.


----------



## Stefan (Nov 17, 2012)

Stefan said:


> The thing is, it might be exact and I just don't understand why, so maybe some theory master can help me out



Oh well, just needed some non-busy time to think.

It's exactly 1.

The obvious way to determine the average number of connected pairs is to look at each state, count the connected pairs, sum it all up, and divide by the number of states. Like so:


```
counter = 0
for each possible state:
    for each possible pair:
        if the pair is connected in that state:
            increase counter by 1
print counter / numberOfAllStates
```

When looking at some state, the pairs indeed aren't independent. If the first 23 pairs are all connected, then the last one must be connected as well. For other constellations of the first 23 pairs, the last one must *not* be connected.

But here's the thing: The set of possible states and the set of possible pairs are fixed, they don't depend on each other. So I can switch the loops without changing the result:


```
counter = 0
[COLOR="#FF0000"]for each possible pair:
    for each possible state:[/COLOR]
        if the pair is connected in that state:
            increase counter by 1
print counter / numberOfAllStates
```

Here it is clear that the pairs don't influence each other, because we're looking at them one after the other without context, not inside the context of a specific state. In terms of the 2x2x1 I looked at earlier: The original perspective, counting pairs for each state, gives 4+0+1+1+1+1, which is complicated. The other perspective, counting states for each pair, gives 2+2+2+2, which is much nicer. For each of the 4 pairs, 2 out of the 6 states have that pair connected. So the average is 4*(2/6) (or (4*2)/6, reflecting the above program more closely). And for the 3x3x3, we can indeed say 24*(1/24). Considering all possible states, the average number of connected pairs is exactly 1.


----------



## Stefan (Nov 17, 2012)

peterbone said:


> It's no wonder that colour neutral solvers have an advantage when there's a *50/50 chance that they'll get a corner-edge pair* that they can make full use of.



With the average being 1, I doubt that's a 50/50 chance. How did you get this?


----------



## Stefan (Nov 18, 2012)

What I got *without* move filtering (matches Peter's numbers well):


```
1 moves: 20.000000000000007 pairs on average
2 moves: 16.888888888888903 pairs on average
3 moves: 14.370370370370374 pairs on average
4 moves: 12.29812528577962 pairs on average
5 moves: 10.576233297769651 pairs on average
6 moves: 9.136050850423668 pairs on average
7 moves: 7.92573399493077 pairs on average
8 moves: 6.904854843647676 pairs on average
9 moves: 6.041227344586831 pairs on average
10 moves: 5.308858475646257 pairs on average
11 moves: 4.686536492662642 pairs on average
12 moves: 4.156812212843681 pairs on average
13 moves: 3.705239489372838 pairs on average
14 moves: 3.3197953774706974 pairs on average
15 moves: 2.9904295422670812 pairs on average
16 moves: 2.7087091889176316 pairs on average
17 moves: 2.467536074264948 pairs on average
18 moves: 2.2609188151305557 pairs on average
19 moves: 2.0837881969834253 pairs on average
20 moves: 1.931846309234786 pairs on average
21 moves: 1.8014425582929698 pairs on average
22 moves: 1.6894712255567823 pairs on average
23 moves: 1.5932864303193184 pairs on average
24 moves: 1.5106312502854236 pairs on average
25 moves: 1.4395784289107039 pairs on average
26 moves: 1.3784806172383361 pairs on average
27 moves: 1.3259284993933003 pairs on average
28 moves: 1.2807154647613732 pairs on average
29 moves: 1.241807737409917 pairs on average
30 moves: 1.2083190700951247 pairs on average
31 moves: 1.1794892678029565 pairs on average
32 moves: 1.1546659328422635 pairs on average
33 moves: 1.1332889265925283 pairs on average
34 moves: 1.114877127100683 pairs on average
35 moves: 1.09901713066894 pairs on average
36 moves: 1.085353602366492 pairs on average
37 moves: 1.0735810273715032 pairs on average
38 moves: 1.063436654050622 pairs on average
39 moves: 1.0546944521761028 pairs on average
40 moves: 1.047159936836175 pairs on average
41 moves: 1.0406657313537269 pairs on average
42 moves: 1.0350677616524733 pairs on average
43 moves: 1.0302419906169527 pairs on average
44 moves: 1.0260816145876175 pairs on average
45 moves: 1.022494655629079 pairs on average
46 moves: 1.0194018929490034 pairs on average
47 moves: 1.0167350851091004 pairs on average
48 moves: 1.0144354416917114 pairs on average
49 moves: 1.0124523090602258 pairs on average
50 moves: 1.0107420399411995 pairs on average
55 moves: 1.0051346328438848 pairs on average
60 moves: 1.0024563708863639 pairs on average
65 moves: 1.0011759974926608 pairs on average
70 moves: 1.000563409474172 pairs on average
75 moves: 1.0002701041874538 pairs on average
80 moves: 1.0001295734494384 pairs on average
85 moves: 1.0000621968974277 pairs on average
90 moves: 1.0000298731677388 pairs on average
95 moves: 1.0000143564271673 pairs on average
100 moves: 1.0000069033068955 pairs on average
110 moves: 1.0000015987848982 pairs on average
120 moves: 1.0000003710475829 pairs on average
130 moves: 1.000000086283419 pairs on average
140 moves: 1.0000000201018482 pairs on average
150 moves: 1.000000004691477 pairs on average
160 moves: 1.00000000109674 pairs on average
170 moves: 1.0000000002567888 pairs on average
180 moves: 1.0000000000602123 pairs on average
190 moves: 1.000000000014138 pairs on average
200 moves: 1.0000000000033247 pairs on average
210 moves: 1.0000000000007832 pairs on average
220 moves: 1.0000000000001847 pairs on average
230 moves: 1.0000000000000435 pairs on average
240 moves: 1.0000000000000104 pairs on average
250 moves: 1.0000000000000029 pairs on average
260 moves: 1.0000000000000007 pairs on average
270 moves: 1.0 pairs on average
```

What I got *with* move filtering:


```
1 moves: 20.0 pairs on average
2 moves: 15.999999999999986 pairs on average
3 moves: 12.711111111111117 pairs on average
4 moves: 10.22656790123456 pairs on average
5 moves: 8.303328395061738 pairs on average
6 moves: 6.804680164609056 pairs on average
7 moves: 5.628323526291721 pairs on average
8 moves: 4.699535228898027 pairs on average
9 moves: 3.9630543026652423 pairs on average
10 moves: 3.3769874396501924 pairs on average
11 moves: 2.9093291985021805 pairs on average
12 moves: 2.535327085388386 pairs on average
13 moves: 2.2356883333425555 pairs on average
14 moves: 1.995273983769414 pairs on average
15 moves: 1.8021428670596737 pairs on average
16 moves: 1.6468373957446398 pairs on average
17 moves: 1.5218421035614655 pairs on average
18 moves: 1.4211684943309422 pairs on average
19 moves: 1.340033973499339 pairs on average
20 moves: 1.2746118044612573 pairs on average
21 moves: 1.2218352266266255 pairs on average
22 moves: 1.1792432554414272 pairs on average
23 moves: 1.1448588022887909 pairs on average
24 moves: 1.1170920123672308 pairs on average
25 moves: 1.0946633829914663 pairs on average
26 moves: 1.076542466546658 pairs on average
27 moves: 1.0618988988390403 pairs on average
28 moves: 1.0500632065445195 pairs on average
29 moves: 1.040495394702222 pairs on average
30 moves: 1.0327597382430938 pairs on average
31 moves: 1.026504530593815 pairs on average
32 moves: 1.0214457997076636 pairs on average
33 moves: 1.0173542040200738 pairs on average
34 moves: 1.0140444802705006 pairs on average
35 moves: 1.0113669413290651 pairs on average
36 moves: 1.0092006223456444 pairs on average
37 moves: 1.0074477532681272 pairs on average
38 moves: 1.0060292993690163 pairs on average
39 moves: 1.0048813622370707 pairs on average
40 moves: 1.003952274364989 pairs on average
41 moves: 1.003200253064764 pairs on average
42 moves: 1.0025915056033143 pairs on average
43 moves: 1.0020986984650637 pairs on average
44 moves: 1.0016997205433873 pairs on average
45 moves: 1.001376683656276 pairs on average
46 moves: 1.001115114725811 pairs on average
47 moves: 1.0009033027772896 pairs on average
48 moves: 1.000731771019272 pairs on average
49 moves: 1.0005928499949084 pairs on average
50 moves: 1.0004803324159215 pairs on average
55 moves: 1.0001678533222043 pairs on average
60 moves: 1.0000587445211244 pairs on average
65 moves: 1.0000205886180502 pairs on average
70 moves: 1.000007225769992 pairs on average
75 moves: 1.0000025392980354 pairs on average
80 moves: 1.0000008934943463 pairs on average
85 moves: 1.0000003147711476 pairs on average
90 moves: 1.0000001110196375 pairs on average
95 moves: 1.0000000391997934 pairs on average
100 moves: 1.0000000138555758 pairs on average
110 moves: 1.000000001736167 pairs on average
120 moves: 1.0000000002183402 pairs on average
130 moves: 1.0000000000275493 pairs on average
140 moves: 1.0000000000034872 pairs on average
150 moves: 1.0000000000004419 pairs on average
160 moves: 1.0000000000000562 pairs on average
170 moves: 1.0000000000000062 pairs on average
180 moves: 0.9999999999999993 pairs on average
190 moves: 1.0000000000000004 pairs on average
200 moves: 0.9999999999999996 pairs on average
210 moves: 1.0000000000000007 pairs on average
220 moves: 1.0 pairs on average
```

As usual, I analyzed *all* possible scrambles, not just a few million or so. Thus the only source of error should be the rounding of double values, which I believe (=hope) is negligible. I'll upload the code after cleaning it.



peterbone said:


> The average number of corner-edge pairs for a 20 move scramble is 1.92 - almost double the value for a fully random scramble. Admittedly, by scramble algorithm doesn't avoid cancellations, so the actual value would be slightly less.



Unless I made a mistake, it's not just slightly but considerably less. Not 1.92, but 1.27. And looking at the correct length (25 moves), it's even just 1.09.


----------



## Stefan (Nov 18, 2012)

Stefan said:


> Thus the only source of error should be the rounding of double values, which I believe (=hope) is negligible.



Seems to be. Just tried it again with 100 digits precision and it matches my double values very well:


```
1 moves: 19.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995 pairs on average
2 moves: 15.99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999624 pairs on average
3 moves: 12.711111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111106190 pairs on average
4 moves: 10.2265679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345678970838 pairs on average
5 moves: 8.30332839506172839506172839506172839506172839506172839506172839506172839506172839506172839506172839167936 pairs on average
6 moves: 6.804680164609053497942386831275720164609053497942386831275720164609053497942386831275720164609053495196772 pairs on average
7 moves: 5.628323526291723822588020118884316415180612711476909007773205304069501600365797896662094192958390487095360 pairs on average
8 moves: 4.69953522889803383630544124371284865112025605852766346593507087334247828074988568815729309556470050116530 pairs on average
9 moves: 3.96305430266524411929075852258293959254178732916730173245948280241833053904384494233602601229487374738149 pairs on average
10 moves: 3.37698743965018882622906399769682805805348100729902284543345357245677318836898169317007908686006536822192 pairs on average
11 moves: 2.90932919850217954580094497789971040999847584209724127419600670629477213839353757049230300259106843366542 pairs on average
12 moves: 2.5353270853883860673150923620872307556248012479278038389962385288301053174294042047941351909242982748970 pairs on average
13 moves: 2.2356883333425544911539255219927204211442725219419151577189816618088053675447196082600577172881530271508 pairs on average
14 moves: 1.9952739837694146864844827553764199600708263005677017768670463889688601368731430205798950400891161947037 pairs on average
15 moves: 1.8021428670596728416122565990566389481791191482389564584954101382077394466352036430370619866725737361677 pairs on average
16 moves: 1.6468373957446397744441440731339327796883762644778448978727090502433390919601053933933783249135282563309 pairs on average
17 moves: 1.5218421035614641092617360255306476576152377939928726898075852668700751136577084853145183036512041566446 pairs on average
18 moves: 1.4211684943309407420063547542525558063605665419517861379809471047361152858386898582434033322383215509996 pairs on average
19 moves: 1.3400339734993379630877203984600480607691005899965880913094058550596343567845392572065714022333668225589 pairs on average
20 moves: 1.2746118044612564045185848064140172227413839459814653449804738873500541394672827664746685322801522992015 pairs on average
21 moves: 1.2218352266266248267576531141727643247726766076772599014121454613753925265041549859413480457023148950104 pairs on average
22 moves: 1.1792432554414266881838255226061764433392303939267533991955841863045230736332208596710677119060820554203 pairs on average
23 moves: 1.1448588022887907528221556034472058713501337759538919249797513532180274484540058773938685115906193530948 pairs on average
24 moves: 1.1170920123672306015022824531017205652955235110142771724913809299026209946995037429425890486348236168022 pairs on average
25 moves: 1.0946633829914655058923868480125012259316966185158030349461469692894890465885590022859239949811902522863 pairs on average
26 moves: 1.0765424665466584593071148878140620694906220593550484374630764594686733578586062431870100053099552143930 pairs on average
27 moves: 1.0618988988390407502523151259039834424511001821848539783461181601717467960587264996912911991309998686594 pairs on average
28 moves: 1.0500632065445191363435335046279738768320478248267803269349651680769450614642559101451229204018085667978 pairs on average
29 moves: 1.0404953947022212114925353859679374694314424695852534420774632826867462060336923998509904158791239638544 pairs on average
30 moves: 1.0327597382430936157187252556805222293892281456325129401106419810808939898036718976272968306448185550611 pairs on average
31 moves: 1.0265045305938140443809988756683317679282606620345263660947481408548386786091902875560407743695745803500 pairs on average
32 moves: 1.0214457997076632713441171885042226113445156569064192183022125534782489678048423512459624032289755820623 pairs on average
33 moves: 1.0173542040200727393376515476029085907313952786588731511606968180759619774813562220835901839748830916508 pairs on average
34 moves: 1.0140444802705005817892314408748769813418535967245470250293826587679722941014466353145591411922776356328 pairs on average
35 moves: 1.0113669413290647812140764886853668385353383250822015724477685710631490324941907607638667860900576222924 pairs on average
36 moves: 1.0092006223456449289524048293808990835448884361480054928077725278649682399118158090945328404644172688410 pairs on average
37 moves: 1.0074477532681276744239457806679474595107547701876296502828609127775924449695623165642515263277746289994 pairs on average
38 moves: 1.0060292993690149343739544757870934989468451602307147590920903069892477331933945104499302993528852861715 pairs on average
39 moves: 1.0048813622370723491626316799996704540440762634778634274285672417624911679006732118897272403516214306594 pairs on average
40 moves: 1.0039522743649882666503353500877865212634160172492608384872489410327889713977433784043311349485087138172 pairs on average
41 moves: 1.0032002530647643574536382011439925791708599463726576451046003651251407230903032469827886897955203038255 pairs on average
42 moves: 1.0025915056033151958530878769182425590277153825498431880865396435141732942199386858516174015858132832475 pairs on average
43 moves: 1.0020986984650638553783833101681876910042894162336811978329191083966338163189866325227537716523012055697 pairs on average
44 moves: 1.0016997205433871066383053023033100317176672848237952519636995417046056168805876093693493024106040732513 pairs on average
45 moves: 1.0013766836562758646426353177436279863267809178093826818706440528359568021611583595591774586677013076874 pairs on average
46 moves: 1.0011151147258117445037506820291176860434183999109221396315467206724639662916111151223486990232916561439 pairs on average
47 moves: 1.0009033027772901350416053332868787618023299375647457451724122026428680680023218406608614129170681260630 pairs on average
48 moves: 1.0007317710192709635098263061373199676202050023938879085159446276451772004376576900187654392218123940285 pairs on average
49 moves: 1.0005928499949082663223247118472480378574042273189465861120059848512911800419338745418322509340683217935 pairs on average
50 moves: 1.0004803324159208779666673556372297348647603857828751127029220206189737208279157438025705182960282518070 pairs on average
55 moves: 1.0001678533222041353087866431555059570405048472235017247500444343104778357607460540473553178190609165570 pairs on average
60 moves: 1.0000587445211237867960776076872040233763266768582936625499598275108923634378072263017281533877956818358 pairs on average
65 moves: 1.0000205886180487136519581947784172349330336818395968780829920034457912563889510842957548530465406821229 pairs on average
70 moves: 1.0000072257699915606173997671978329242678084543202707395337582562368497904966554224135885543874319029180 pairs on average
75 moves: 1.0000025392980348396499148982564109742660285829214428031559130550413839094718376090803960238609917623653 pairs on average
80 moves: 1.0000008934943459609716866511485095148526755837899286529626410766786827383091104998973896481909369130371 pairs on average
85 moves: 1.0000003147711466073540233628876106962010019377397608901333927279420491081708165903177831553532035003276 pairs on average
90 moves: 1.0000001110196382100888115330001567387166289330251547060265760926299331872050117038964651476324392803134 pairs on average
95 moves: 1.0000000391997921196599652529249585591816584092914241851921779754650113976177376921499080367739357726198 pairs on average
100 moves: 1.0000000138555762403340530380944409898139151092244303591384410643126149331946541682548913093305726808595 pairs on average
110 moves: 1.0000000017361651820093745213124649784798697216261744957242587467932404792947591268760630274720405634757 pairs on average
120 moves: 1.0000000002183403348514127416822098311378743942438575091669171400304889732423762460765494221370126248490 pairs on average
130 moves: 1.0000000000275485765893069229708922804289656477518086177899981567060023576513000437329635016877093333916 pairs on average
140 moves: 1.0000000000034861325922153189804137398832076132860794057343673143958371666657212130553247500561500349251 pairs on average
150 moves: 1.0000000000004423205113030880553380389052504288376909006103796997761212869151123174963054922759719190491 pairs on average
160 moves: 1.0000000000000562547246931767699984366520995032712121070265070388430849562263236516832814112078030501682 pairs on average
170 moves: 1.0000000000000071696995743055054543018662122281428246033955227372562377859254170108469453275745663521072 pairs on average
180 moves: 1.0000000000000009155132113768945150328101149909694263991415168823355758501225503640266165923602954582642 pairs on average
190 moves: 1.0000000000000001171012035244021298351928654975196045725063780842273189644990574809598513576298762864468 pairs on average
200 moves: 1.0000000000000000150007008118011567828002228195782765909038683928088852319004300924825824319569520478187 pairs on average
210 moves: 1.0000000000000000019241715482675810904765250450608037077002783079010343866647426418155603011535265841044 pairs on average
220 moves: 1.0000000000000000002471122000197261359472010287987766669890786131238115668637498597001239817825689227466 pairs on average
230 moves: 1.0000000000000000000317691549088672540804160274624291966450551320046207871656284640283708437131647432460 pairs on average
240 moves: 1.0000000000000000000040881542800324728406243453952124862997934910332853197639396021360530412748728464136 pairs on average
250 moves: 1.0000000000000000000005265184850530931880609386926513488411576035499018304252905985584123437365708412025 pairs on average
260 moves: 1.0000000000000000000000678616246729233175449909547280469604428211858178515806652653737441350605233498787 pairs on average
270 moves: 1.0000000000000000000000087523194330793411524334851060250168491105638955818001041571665733128856972216374 pairs on average
280 moves: 1.0000000000000000000000011294793768452522171259016869774540307606016536717801127465397179206499910208136 pairs on average
290 moves: 1.0000000000000000000000001458348080191221707108230757333828163029255397414859573421991223933569443195360 pairs on average
300 moves: 1.0000000000000000000000000188385072757828447584762199789903225564650549585596915473804186749854313177911 pairs on average
310 moves: 1.0000000000000000000000000024345105353446200815398945309306818204390494752729320852712282855937741649464 pairs on average
320 moves: 1.0000000000000000000000000003147289441251601605289707390912820352573936162884827679126856718690064043213 pairs on average
330 moves: 1.0000000000000000000000000000407008773609587953874796559951539621728709526534224248682682431146359092311 pairs on average
340 moves: 1.0000000000000000000000000000052649845690315353803052147048751680656922153385789394934238756084546489720 pairs on average
350 moves: 1.0000000000000000000000000000006812438986537164371288200357377708879196724504453972324807463518758311210 pairs on average
360 moves: 1.0000000000000000000000000000000881673630212249543646732827896252287144754357163795407839451556334637814 pairs on average
370 moves: 1.0000000000000000000000000000000114130490481979406744172941332537850081089498125287613272346446317952066 pairs on average
380 moves: 1.0000000000000000000000000000000014776591262004574449176736151514709443462244262931658499772606196474824 pairs on average
390 moves: 1.0000000000000000000000000000000001913448683220302077682348622619800775399643499823626933111186281037618 pairs on average
400 moves: 1.0000000000000000000000000000000000247811567127624450385635447144553879697636553277117243878696858707362 pairs on average
410 moves: 1.0000000000000000000000000000000000032098268483709621149923875291062515782613878415511402235948446430529 pairs on average
420 moves: 1.0000000000000000000000000000000000004158060119521817510299860811823935713094699020711957849200788708070 pairs on average
430 moves: 1.0000000000000000000000000000000000000538695796655870422677008831256223616078004451592691658760603200284 pairs on average
440 moves: 1.0000000000000000000000000000000000000069796752634255757388345972075638608533366292470890108260912227922 pairs on average
450 moves: 1.0000000000000000000000000000000000000009044016369036016399263005909174363302439040950366282301480986645 pairs on average
460 moves: 1.0000000000000000000000000000000000000001171974384648151193877697265828828620212236639853544925552302498 pairs on average
470 moves: 1.0000000000000000000000000000000000000000151880545520444233361370562420071269573412852866456418298493102 pairs on average
480 moves: 1.0000000000000000000000000000000000000000019683865862787854392326913325325273638995411484986583160129505 pairs on average
490 moves: 1.0000000000000000000000000000000000000000002551174544180748173419742309570501337609274269006318652561355 pairs on average
500 moves: 1.0000000000000000000000000000000000000000000330665651081078411802185089688806954076654537669648418897131 pairs on average
510 moves: 1.0000000000000000000000000000000000000000000042860279851702686514284148092751725171596871983247627877329 pairs on average
520 moves: 1.0000000000000000000000000000000000000000000005555664855535070888562223842293437515146237023755744164345 pairs on average
530 moves: 1.0000000000000000000000000000000000000000000000720162517419520027723893479997855661779303343264047049294 pairs on average
540 moves: 1.0000000000000000000000000000000000000000000000093354860211346107719899169246108805214587417137248615566 pairs on average
550 moves: 1.0000000000000000000000000000000000000000000000012101911415270861775111509675622656083299398038373649906 pairs on average
560 moves: 1.0000000000000000000000000000000000000000000000001568846466650288347439740048762513048604276717911968249 pairs on average
570 moves: 1.0000000000000000000000000000000000000000000000000203383308258474077997499609988806697383831977219542276 pairs on average
580 moves: 1.0000000000000000000000000000000000000000000000000026366812314318214255877748383501746898604642866677168 pairs on average
590 moves: 1.0000000000000000000000000000000000000000000000000003418271678758317177133666881367196180851301752883954 pairs on average
600 moves: 1.0000000000000000000000000000000000000000000000000000443160881888805625489910153330358803497955415314997 pairs on average
610 moves: 1.0000000000000000000000000000000000000000000000000000057454162273801904576699959404981651280250303546763 pairs on average
620 moves: 1.0000000000000000000000000000000000000000000000000000007448798585211349252236250522780756518453119019056 pairs on average
630 moves: 1.0000000000000000000000000000000000000000000000000000000965728624373560959541109790894669793473398082379 pairs on average
640 moves: 1.0000000000000000000000000000000000000000000000000000000125206725004992580193667084942853428621036186800 pairs on average
650 moves: 1.0000000000000000000000000000000000000000000000000000000016233175277148639062064136215849700982000422740 pairs on average
660 moves: 1.0000000000000000000000000000000000000000000000000000000002104661258309961141545942710834277152799388588 pairs on average
670 moves: 1.0000000000000000000000000000000000000000000000000000000000272874856106250246635085747672700883377398940 pairs on average
680 moves: 1.0000000000000000000000000000000000000000000000000000000000035379128409832372843795629563135638825921728 pairs on average
690 moves: 1.0000000000000000000000000000000000000000000000000000000000004587042682096679021069498257884464958746440 pairs on average
700 moves: 1.0000000000000000000000000000000000000000000000000000000000000594730550161306059402012868889007877332032 pairs on average
710 moves: 1.0000000000000000000000000000000000000000000000000000000000000077109755858698855448368329042439557759472 pairs on average
720 moves: 1.0000000000000000000000000000000000000000000000000000000000000009997694052985177546786385021663141713148 pairs on average
730 moves: 1.0000000000000000000000000000000000000000000000000000000000000001296258543284204193880133976113831393064 pairs on average
740 moves: 1.0000000000000000000000000000000000000000000000000000000000000000168067815129093330405869465976762724708 pairs on average
750 moves: 1.0000000000000000000000000000000000000000000000000000000000000000021791066413845643837383875715172601224 pairs on average
760 moves: 1.0000000000000000000000000000000000000000000000000000000000000000002825356861163031676681365439067772436 pairs on average
770 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000366327001790462594617478627191707900 pairs on average
780 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000047496899505396954171612802681861032 pairs on average
790 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000006158319532051793935760340645045900 pairs on average
800 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000798472083115226937438154423986060 pairs on average
810 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000103527982579764513278803300724860 pairs on average
820 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000013423204528456337438859873841612 pairs on average
830 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000001740423973160907639798174768084 pairs on average
840 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000225659829233306684388710207600 pairs on average
850 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000029258614974317729133831425608 pairs on average
860 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000003793617574669683480387312696 pairs on average
870 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000491873673547676759154415904 pairs on average
880 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000063775493292372395343774044 pairs on average
890 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000008269024301357811359004304 pairs on average
900 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000001072148351839735933610172 pairs on average
910 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000139013074797642657017212 pairs on average
920 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000018024223037068103798008 pairs on average
930 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000002336993891329336941308 pairs on average
940 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000303011219386763387924 pairs on average
950 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000039288001407334154344 pairs on average
960 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000005094027078721180180 pairs on average
970 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000660484510901730860 pairs on average
980 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000085637522116410772 pairs on average
990 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000011103646007691272 pairs on average
1000 moves: 1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000001439683992364984 pairs on average
```


----------



## qqwref (Nov 18, 2012)

1.09 is actually respectably close to 1.0 - it'd be kinda hard to tell the difference, although maybe after enough scrambles you could. Nice calculations by the way. How did you keep track of so many positions - did you track every possibility for every c/e pair or something?


----------



## Stefan (Nov 18, 2012)

qqwref said:


> How did you keep track of so many positions - did you track every possibility for every c/e pair or something?



Remember the earlier post where I explained why the overall average of connected pairs is exactly 1, why we can take the 1/24 of one pair and just multiply it by 24. For scrambles I did the same. Instead of counting connected pairs for each scramble, I count scrambles (or rather probabilities) for each possible pair, and I'm just following one pair (corner URF and edge UR) and multiply by 24.

This is then done with dynamic programming on an array _probability[state]_. A state is a triple of the locations of the URF corner, the UR edge, and which moves are allowed. I start with "URF UR UDLRFB", the states reached from that are:

UFL UF DLRFB
ULB UL DLRFB
UBR UB DLRFB
URF UR DLRFB
URF UR ULRFB
URF UR UDRFB
BRU BR UDLFB
DRB DR UDLFB
FRD FR UDLFB
URF UR UDLFB
RDF UR UDLRB
DLF UR UDLRB
LUF UR UDLRB
URF UR UDLRB
URF UR UDLRF

There are 5185 states (1+24*24*9). I initialize the probability for the start state with 1 and all other states with 0. Then I go through the scramble lengths, each iteration computing the probabilities for the new scramble length based on those of the previous one. And add up the probabilities of the states where the pair is connected and print that multiplied by 24.


----------



## CarlBrannen (Nov 18, 2012)

Stefan said:


> The thing is, it might be exact and I just don't understand why, so maybe some theory master can help me out
> 
> Consider the 2x2x1 and its corner-corner pairs. It has six states, one with four pairs, one with zero pairs, four with one pair. So an average of 8/6=4/3 pairs. On the other hand, there are four possible pairs, each with 1/3 chance. Which also leads to 4/3.



Which raises the question of what the 2x2x2 statistics are. The number of distinct positions (keeping one corner fixed) is 1(7x3)(6x3)(5x3)(4x3)(3x3)(2x3) = 7! 3^6 = 3674160 which should be doable by computer.


----------



## Stefan (Nov 18, 2012)

CarlBrannen said:


> Which raises the question of what the 2x2x2 statistics are. The number of distinct positions (keeping one corner fixed) is 1(7x3)(6x3)(5x3)(4x3)(3x3)(2x3) = 7! 3^6 = 3674160 which should be doable by computer.



I think the average number of connected pairs is 4/7 (but I only did that in my head, not with a computer).


----------



## CarlBrannen (Nov 18, 2012)

Stefan said:


> Remember the earlier post where I explained why the overall average of connected pairs is exactly 1, why we can take the 1/24 of one pair and just multiply it by 24. For scrambles I did the same. Instead of counting connected pairs for each scramble, I count scrambles (or rather probabilities) for each possible pair, and I'm just following one pair (corner URF and edge UR) and multiply by 24.



I'm quite stupid but I'm at least half convinced this is right. Nice programming.


----------



## jaap (Nov 18, 2012)

Stefan said:


> It's exactly 1.



This follows directly from the Linearity of expectation - expected values are linear (i.e. can be added together) regardless of whether the events are independent or not. There are 24 possible c-e pairs. Each individually has 1/24 probability. Therefore the expected number of, say, red-white + red-white-blue matching pairs is 1/24, and the same for any other pair. By linearity, the total expected number of pairs is 24 * 1/24 = 1, regardless of them not being independent of each other.


----------



## Stefan (Nov 19, 2012)

Here's my program now, in case someone's interested (I find it quite neat, I loooove Python). I think it's fairly readable, but ask if something's unclear. Peter, I'd still appreciate numbers from your experiment with moves filtered, to compare with mine.


```
#--- Explore the states to build the successors/paired lists
queue = [("URF", "UR", frozenset("UDLRFB"))]
state2int = {queue[0]: 0}
successors, paired = [], []
for fromState in queue:
    successors.append([])
    paired.append(fromState[0][:2] == fromState[1])
    for layer in "U:RFLB D:RBLF L:FDBU R:FUBD F:URDL B:ULDR".split():
        layerName, layerRim = layer.split(":")
        trans = str.maketrans(layerRim, layerRim[1:] + layerRim[0])
        corner, edge, allowed = fromState
        if layerName in allowed:
            allowed = (allowed | set(layerRim)) - set(layerName)
            for angle in "123":
                if layerName in corner: corner = corner.translate(trans)
                if layerName in edge: edge = edge.translate(trans)
                toState = (corner, edge, allowed)
                if toState not in state2int:
                    queue.append(toState)
                    state2int[toState] = len(state2int)
                successors[state2int[fromState]].append(state2int[toState])

#--- Scramble and compute/show the expected value E[number of pairs]
S = len(state2int)
E = [24] + [0] * (S - 1)
for moves in range(101):
    print("{} moves: {} pairs".format(moves, sum(E[s] for s in range(S) if paired[s])))
    E, oldE = [0] * S, E
    for state in range(S):
        for succ in successors[state]:
            E[succ] += oldE[state] / len(successors[state])
```

Prints this:

```
0 moves: 24 pairs
1 moves: 20.0 pairs
2 moves: 15.999999999999986 pairs
3 moves: 12.711111111111089 pairs
4 moves: 10.226567901234567 pairs
5 moves: 8.303328395061712 pairs
6 moves: 6.804680164609054 pairs
7 moves: 5.628323526291727 pairs
8 moves: 4.699535228898036 pairs
9 moves: 3.963054302665246 pairs
10 moves: 3.3769874396501933 pairs
11 moves: 2.9093291985021787 pairs
12 moves: 2.5353270853883854 pairs
13 moves: 2.2356883333425532 pairs
14 moves: 1.9952739837694142 pairs
15 moves: 1.802142867059673 pairs
16 moves: 1.646837395744639 pairs
17 moves: 1.521842103561465 pairs
18 moves: 1.4211684943309422 pairs
19 moves: 1.3400339734993372 pairs
20 moves: 1.274611804461256 pairs
21 moves: 1.2218352266266252 pairs
22 moves: 1.1792432554414272 pairs
23 moves: 1.1448588022887913 pairs
24 moves: 1.1170920123672308 pairs
25 moves: 1.0946633829914665 pairs
26 moves: 1.0765424665466583 pairs
27 moves: 1.06189889883904 pairs
28 moves: 1.0500632065445186 pairs
29 moves: 1.040495394702222 pairs
30 moves: 1.0327597382430938 pairs
31 moves: 1.0265045305938139 pairs
32 moves: 1.0214457997076631 pairs
33 moves: 1.0173542040200727 pairs
34 moves: 1.0140444802704995 pairs
35 moves: 1.0113669413290651 pairs
36 moves: 1.009200622345645 pairs
37 moves: 1.0074477532681276 pairs
38 moves: 1.0060292993690145 pairs
39 moves: 1.004881362237073 pairs
40 moves: 1.0039522743649876 pairs
41 moves: 1.0032002530647643 pairs
42 moves: 1.002591505603315 pairs
43 moves: 1.002098698465064 pairs
44 moves: 1.0016997205433866 pairs
45 moves: 1.0013766836562756 pairs
46 moves: 1.0011151147258115 pairs
47 moves: 1.0009033027772911 pairs
48 moves: 1.0007317710192711 pairs
49 moves: 1.0005928499949093 pairs
50 moves: 1.0004803324159208 pairs
51 moves: 1.0003891940190355 pairs
52 moves: 1.0003153677939114 pairs
53 moves: 1.00025556136083 pairs
54 moves: 1.0002071092379479 pairs
55 moves: 1.0001678533222045 pairs
56 moves: 1.0001360461875253 pairs
57 moves: 1.000110272837987 pairs
58 moves: 1.0000893873888608 pairs
59 moves: 1.0000724618236863 pairs
60 moves: 1.0000587445211235 pairs
61 moves: 1.0000476266864236 pairs
62 moves: 1.000038615178964 pairs
63 moves: 1.0000313105156033 pairs
64 moves: 1.0000253890626767 pairs
65 moves: 1.0000205886180482 pairs
66 moves: 1.0000166967370576 pairs
67 moves: 1.0000135412795312 pairs
68 moves: 1.0000109827547647 pairs
69 moves: 1.000008908122103 pairs
70 moves: 1.000007225769991 pairs
71 moves: 1.0000058614492324 pairs
72 moves: 1.0000047549788775 pairs
73 moves: 1.0000038575777905 pairs
74 moves: 1.0000031297029426 pairs
75 moves: 1.0000025392980345 pairs
76 moves: 1.000002060374553 pairs
77 moves: 1.0000016718620122 pairs
78 moves: 1.000001356676323 pairs
79 moves: 1.0000011009648018 pairs
80 moves: 1.0000008934943467 pairs
81 moves: 1.00000072515556 pairs
82 moves: 1.0000005885608414 pairs
83 moves: 1.0000004777186213 pairs
84 moves: 1.0000003877692942 pairs
85 moves: 1.0000003147711463 pairs
86 moves: 1.000000255526817 pairs
87 moves: 1.0000002074425967 pairs
88 moves: 1.0000001684143525 pairs
89 moves: 1.0000001367350277 pairs
90 moves: 1.0000001110196386 pairs
91 moves: 1.0000000901444497 pairs
92 moves: 1.0000000731976524 pairs
93 moves: 1.0000000594393592 pairs
94 moves: 1.0000000482691576 pairs
95 moves: 1.0000000391997919 pairs
96 moves: 1.0000000318358238 pairs
97 moves: 1.0000000258563062 pairs
98 moves: 1.0000000210007525 pairs
99 moves: 1.0000000170577183 pairs
100 moves: 1.0000000138555767 pairs
```

Removing the _"allowed = (allowed | set(layerRim)) - set(layerName)"_ line disables move filtering and results in this:

```
0 moves: 24 pairs
1 moves: 19.999999999999996 pairs
2 moves: 16.888888888888882 pairs
3 moves: 14.370370370370374 pairs
4 moves: 12.298125285779602 pairs
5 moves: 10.57623329776965 pairs
6 moves: 9.136050850423661 pairs
7 moves: 7.925733994930761 pairs
8 moves: 6.904854843647673 pairs
9 moves: 6.041227344586827 pairs
10 moves: 5.308858475646254 pairs
11 moves: 4.686536492662635 pairs
12 moves: 4.156812212843678 pairs
13 moves: 3.705239489372832 pairs
14 moves: 3.319795377470694 pairs
15 moves: 2.9904295422670786 pairs
16 moves: 2.7087091889176294 pairs
17 moves: 2.467536074264946 pairs
18 moves: 2.2609188151305544 pairs
19 moves: 2.0837881969834235 pairs
20 moves: 1.9318463092347848 pairs
21 moves: 1.8014425582929685 pairs
22 moves: 1.6894712255567808 pairs
23 moves: 1.5932864303193175 pairs
24 moves: 1.5106312502854224 pairs
25 moves: 1.439578428910703 pairs
26 moves: 1.3784806172383355 pairs
27 moves: 1.3259284993932996 pairs
28 moves: 1.2807154647613728 pairs
29 moves: 1.2418077374099166 pairs
30 moves: 1.2083190700951238 pairs
31 moves: 1.1794892678029558 pairs
32 moves: 1.154665932842263 pairs
33 moves: 1.1332889265925272 pairs
34 moves: 1.114877127100682 pairs
35 moves: 1.0990171306689396 pairs
36 moves: 1.0853536023664911 pairs
37 moves: 1.0735810273715025 pairs
38 moves: 1.0634366540506215 pairs
39 moves: 1.0546944521761015 pairs
40 moves: 1.0471599368361744 pairs
41 moves: 1.0406657313537258 pairs
42 moves: 1.035067761652473 pairs
43 moves: 1.0302419906169522 pairs
44 moves: 1.026081614587617 pairs
45 moves: 1.0224946556290786 pairs
46 moves: 1.019401892949003 pairs
47 moves: 1.0167350851091006 pairs
48 moves: 1.0144354416917107 pairs
49 moves: 1.0124523090602255 pairs
50 moves: 1.0107420399411993 pairs
51 moves: 1.0092670208963919 pairs
52 moves: 1.0079948354580446 pairs
53 moves: 1.0068975438662808 pairs
54 moves: 1.0059510630543673 pairs
55 moves: 1.0051346328438844 pairs
56 moves: 1.0044303562952952 pairs
57 moves: 1.0038228038588493 pairs
58 moves: 1.0032986724276793 pairs
59 moves: 1.0028464916445867 pairs
60 moves: 1.0024563708863636 pairs
61 moves: 1.0021197812700566 pairs
62 moves: 1.0018293678161994 pairs
63 moves: 1.001578787583214 pairs
64 moves: 1.001362570170902 pairs
65 moves: 1.0011759974926604 pairs
66 moves: 1.0010150001475198 pairs
67 moves: 1.0008760680941222 pairs
68 moves: 1.0007561736479715 pairs
69 moves: 1.0006527050979146 pairs
70 moves: 1.0005634094741716 pairs
71 moves: 1.0004863432036464 pairs
72 moves: 1.0004198295633921 pairs
73 moves: 1.0003624219938607 pairs
74 moves: 1.000312872463426 pairs
75 moves: 1.0002701041874533 pairs
76 moves: 1.0002331881015198 pairs
77 moves: 1.0002013225713249 pairs
78 moves: 1.000173815893301 pairs
79 moves: 1.0001500712015075 pairs
80 moves: 1.000129573449438 pairs
81 moves: 1.0001118781810727 pairs
82 moves: 1.0000966018449262 pairs
83 moves: 1.00008341343876 pairs
84 moves: 1.0000720273019157 pairs
85 moves: 1.000062196897427 pairs
86 moves: 1.0000537094478203 pairs
87 moves: 1.0000463813072438 pairs
88 moves: 1.0000400539687295 pairs
89 moves: 1.0000345906193109 pairs
90 moves: 1.0000298731677386 pairs
91 moves: 1.000025799679875 pairs
92 moves: 1.0000222821657918 pairs
93 moves: 1.0000192446702774 pairs
94 moves: 1.0000166216251094 pairs
95 moves: 1.0000143564271669 pairs
96 moves: 1.0000124002113928 pairs
97 moves: 1.0000107107918745 pairs
98 moves: 1.0000092517479875 pairs
99 moves: 1.000007991635702 pairs
100 moves: 1.0000069033068952 pairs
```


----------



## CarlBrannen (Nov 19, 2012)

Nice proof jaap.


----------



## peterbone (Nov 19, 2012)

Thanks Stefan for your proof and far superior code, which looks very elegant even though I've not had time to understand it in detail. My results for the filtered scrambles look like this, which seems to agree fairly well with yours - although consistently slightly lower for some reason. My scramble code rejects moves of the form RR and also of the form RLR as qqref described. Does your code reject the RLR form?

```
1,20
2,16
3,12.71536
4,10.17626
5,8.20778
6,6.69461
7,5.51389
8,4.60366
9,3.85761
10,3.28588
11,2.83156
12,2.46748
13,2.18027
14,1.94697
15,1.75957
16,1.61144
17,1.50358
18,1.40242
19,1.32295
20,1.26504
21,1.20993
22,1.16699
23,1.13864
24,1.11946
25,1.0943
26,1.0779
27,1.062
28,1.04514
29,1.03541
30,1.03571
31,1.02502
32,1.0183
33,1.00819
34,1.01508
35,1.01237
36,1.01218
37,1.00504
38,1.00698
39,1.0112
40,1.00184
41,1.0028
42,0.99707
43,1.00695
44,1.00226
45,1.00032
46,0.99846
47,0.99726
48,1.00554
49,1.00282
50,0.99507
```

Regarding me saying that the filtered results would be only slightly less; I had no idea that the actual scramble restrictions were so strict.

You're also right about the 50/50 statement I made about the chance of getting a corner-edge pair. I had assumed that since the average number was one, then there would be equal chance of getting above or below one - but clearly this is just wrong. The actual value seems to be around 63% chance irrespective of using filtered or unfiltered scrambles. I guess this is because we're talking about infinite scrambles and so whether they're filtered or not makes no difference.


----------



## Stefan (Nov 19, 2012)

peterbone said:


> although consistently slightly lower for some reason. My scramble code rejects moves of the form RR and also of the form RLR as qqref described. Does your code reject the RLR form?



I wouldn't call that consistently:

```
20.000000   =  20.000000
16.000000    > 16.000000
12.715360    > 12.711111
10.176260  <   10.226568
 8.207780  <    8.303328
 6.694610  <    6.804680
 5.513890  <    5.628324
 4.603660  <    4.699535
 3.857610  <    3.963054
 3.285880  <    3.376987
 2.831560  <    2.909329
 2.467480  <    2.535327
 2.180270  <    2.235688
 1.946970  <    1.995274
 1.759570  <    1.802143
 1.611440  <    1.646837
 1.503580  <    1.521842
 1.402420  <    1.421168
 1.322950  <    1.340034
 1.265040  <    1.274612
 1.209930  <    1.221835
 1.166990  <    1.179243
 1.138640  <    1.144859
 1.119460    >  1.117092
 1.094300  <    1.094663
 1.077900    >  1.076542
 1.062000    >  1.061899
 1.045140  <    1.050063
 1.035410  <    1.040495
 1.035710    >  1.032760
 1.025020  <    1.026505
 1.018300  <    1.021446
 1.008190  <    1.017354
 1.015080    >  1.014044
 1.012370    >  1.011367
 1.012180    >  1.009201
 1.005040  <    1.007448
 1.006980    >  1.006029
 1.011200    >  1.004881
 1.001840  <    1.003952
 1.002800  <    1.003200
 0.997070  <    1.002592
 1.006950    >  1.002099
 1.002260    >  1.001700
 1.000320  <    1.001377
 0.998460  <    1.001115
 0.997260  <    1.000903
 1.005540    >  1.000732
 1.002820    >  1.000593
 0.995070  <    1.000480
```

The long bias from 4 to 23 moves is suspicious, though, yes. I do filter both RR and RLR (implemented as "after each turn, forbid the latest layer and allow all its adjacent layers"). Do you build the scrambles of length L+1 from scratch or do get them by extending the scrambles of length L?


----------



## peterbone (Nov 20, 2012)

Stefan said:


> I wouldn't call that consistently:
> 
> The long bias from 4 to 23 moves is suspicious, though, yes. I do filter both RR and RLR (implemented as "after each turn, forbid the latest layer and allow all its adjacent layers"). Do you build the scrambles of length L+1 from scratch or do get them by extending the scrambles of length L?


Since both our sets of numbers start at the same values and end at the same values, it's only the values in the middle which have a significant bias. The values at the start and end are therefore subject to the precision of my results, which I think is the only reason we don't see all my values being lower.
I generate all scrambles new each time. In fact, I don't store any scrambles. It generates the scramble as it's turning the cube. Perhaps the way I'm doing the filtering by limiting the possible turns based on the previous ones gives my scrambles a slightly different probability distribution to your state method, which perhaps is more uniform?
Here's my scramble code. I'm sure there's a much better way of doing this (I did it quickly and had to do it in a way that integrates into my Delphi Rubix simulator program).

```
prev_axis := AxisNone;
      prev_layer := 255;
      prev_prev_axis := AxisNone2;
      prev_prev_layer := 254;
      for i := 1 to num_turn do begin
        repeat
          r := Random(3);
          Axis := AxisX;
          if r = 1 then Axis := AxisY else if r = 2 then Axis := AxisZ;
          layer := Random(2) * 2;
        until not (((Axis = prev_axis) and (layer = prev_layer)) or
                   ((Axis = prev_prev_axis) and (layer = prev_prev_layer) and (Axis = prev_axis)));

        r := Random(2);
        if r = 0 then clockwise := True else clockwise := False;
        r := Random(2);
        if r = 0 then t180 := True else t180 := False;
        TurnLayer(Axis, layer, clockwise, False, t180);

        prev_prev_axis := prev_axis;
        prev_prev_layer := prev_layer;
        prev_axis := Axis;
        prev_layer := layer;
      end;
```
Random(n) generates an integer random number between 0 and n-1
TurnLayer performs the layer rotation on the cube. The False input doesn't apply to 3x3x3.


----------



## speedcuber50 (Dec 1, 2012)

The whole problem (at least the one that I've encountered) is that 20 moves isn't always 20 moves!

Suppose we scramble (10 moves, but shows principle): RUD2LR'L2RD2U'D
That's the same as: RUD2L'D'U'-only 6 moves!

So, are the scramblers remembering not to end up doing a scramble that'll cancel down?


----------



## Kirjava (Dec 1, 2012)

speedcuber50 said:


> The whole problem (at least the one that I've encountered) is that 20 moves isn't always 20 moves!
> 
> Suppose we scramble (10 moves, but shows principle): RUD2LR'L2RD2U'D
> That's the same as: RUD2L'D'U'-only 6 moves!
> ...



Lol. Try actually reading the thread.


----------



## MaeLSTRoM (Dec 1, 2012)

speedcuber50 said:


> The whole problem (at least the one that I've encountered) is that 20 moves isn't always 20 moves!
> 
> Suppose we scramble (10 moves, but shows principle): RUD2LR'L2RD2U'D
> That's the same as: RUD2L'D'U'-only 6 moves!
> ...



Well, the L R' L2 R Wouldn't occur, since only 2 consecutive moves on 1 axis are made at a time, maximum.


----------



## ThomasJE (Dec 9, 2012)

speedcuber50 said:


> The whole problem (at least the one that I've encountered) is that 20 moves isn't always 20 moves!
> 
> Suppose we scramble (10 moves, but shows principle): RUD2LR'L2RD2U'D
> That's the same as: RUD2L'D'U'-only 6 moves!
> ...



That would never happen, as the WCA scrambler is optimal. So that 10 mover would never come up; only the 6 mover. Also, what MaeLSTRoM said.


----------



## Oneriwien (Apr 10, 2013)

*How many moves does it take to fully scramble a cube?*

Like how many turns do you have to make before it is completely scrambled, and making more moves won't scramble it any more? Is there a formula for finding it on different cubes? Like the 3x3, megaminx, pyraminx


----------



## Ollie (Apr 10, 2013)

Define completely scrambled?

You can say it's 20 since some of the 'hardest' scrambles will need the full 20 moves to solve optimally (referring to God's number.) But it obviously depends on what moves you do, since you can scramble a cube fairly well with 10 moves - U L R' D F R2 B D R F


----------



## Oneriwien (Apr 10, 2013)

Because I sometimes have "OCD" when scrambling cubes. Like "GAHHH what if i haven't scrambled it enough, then it'll be too easy!" especially on the v cube 7 since it takes more to scramble


----------



## ben1996123 (Apr 10, 2013)

use computer generated scrambles then


----------



## peterbone (Apr 10, 2013)

If you're scrambling by hand then you can never reach a completely random scramble. 20 is probably enough though. If you use a computer generated scrambler that uses random state selection (not all scramblers use this) then 20 is always enough for a completely random scramble.


----------



## kinch2002 (Apr 10, 2013)

ThomasJE said:


> That would never happen, as the WCA scrambler is optimal.


I'm afraid that's not true


----------



## TMOY (Apr 10, 2013)

Ollie said:


> Define completely scrambled?
> 
> You can say it's 20 since some of the 'hardest' scrambles will need the full 20 moves to solve optimally (referring to God's number.) But it obviously depends on what moves you do, since you can scramble a cube fairly well with 10 moves - U L R' D F R2 B D R F



Yep. God's number is irrelevant here, since there are way more possible scrambles than what you will be able to solve in your entire life, you don't need to be able to reach all of them. IMHO a good scrambling must fulfill the following two conditions:
- same proportion of lucky solves as a completely random scrambling;
- you don't geat repeatedly the same scrambles.

10 moves is probably not enough, but IMHO 20 moves is. When I handscramble though, I usually prefer to play safe and perform something like 30-40 moves or so (at least with a good cube, with a crappy storebought I tend to stop earlier).


----------



## Renslay (Apr 10, 2013)

And always make sure to "break your habit", i.e., don't repeat movements / algorithms / sequences without thinking.


----------



## mark49152 (Apr 10, 2013)

Renslay said:


> And always make sure to "break your habit", i.e., don't repeat movements / algorithms / sequences without thinking.


This is hard and is the reason hand scrambling is less reliable. I try to use all 6 faces; include cw and ccw turns; include double turns; turn opposite faces consecutively; rotate every few moves in case I am favouring faces or patterns; don't look at the cube while scrambling; and use about 30+ moves. I try to emulate computer scrambles, so plenty of practice with those helps.


----------



## jayefbe (Apr 10, 2013)

mark49152 said:


> This is hard and is the reason hand scrambling is less reliable. I try to use all 6 faces; include cw and ccw turns; include double turns; turn opposite faces consecutively; rotate every few moves in case I am favouring faces or patterns; don't look at the cube while scrambling; and use about 30+ moves. I try to emulate computer scrambles, so plenty of practice with those helps.



I agree, and do many of the same things whenever I do scramble by hand. I try to avoid hand scrambling whenever possible because it can be so difficult to avoid these repetitive movements. Plus, I want know that a good solve is not simply due to poor scrambling. I personally wouldn't call a hand scrambled solve a pb, and I always take someone else's hand scrambled times with a grain of salt.


----------



## cannon4747 (Apr 10, 2013)

When I use a scramble generator, I have it at a set number of moves for each puzzle and take whatever it gives me. Hand scrambling, I scramble it for a while, then close my eyes and randomly turn it for a few seconds. I accept whatever scramble I have when I open my eyes. Make sure to throw in a few random cube rotations and to do it for longer amounts of time with bigger cubes.


----------



## TMOY (Apr 10, 2013)

Renslay said:


> And always make sure to "break your habit", i.e., don't repeat movements / algorithms / sequences without thinking.



That's the main reason why I use more moves than needed. More moves = less chances to always do the same thing.


----------

