Is 20 turns enough for a scramble?

[Stefan]

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.

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]

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]

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]

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]

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]

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]

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]

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]

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]

Nice proof jaap.

 

[peterbone]

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]

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]

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]

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]

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?

Lol. Try actually reading the thread.

 

[MaeLSTRoM]

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?

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

 

[ThomasJE]

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?

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]

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]

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]

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