qqwref
Legend
- Joined
- Dec 18, 2007
- Messages
- 7,834
- Location
- a <script> tag near you
- WCA ID
- 2006GOTT01
- YouTube
- Visit Channel
4416/43946585901564160587264 ~= 1.005 * 10^-19
Random 20 move scramble
- Thread starter IQubic
- Start date
IQubic
Regular
How in the world did you manege to get that number?!?!?!?
cubernya
Premium Member
Number of scrambles that lead to superflip divided by the number of 20 move scrambles
cuBerBruce
Veteran
I note that it assumes that the 20-move scrambles would each have the same chance of occurring.
If the typical way scrambles are generated allows commuting moves in either order, then the numbers are somewhat different.
The total number of 20-move scrambles then is then 211768161058569529589760. (At least that's what I get.) The number of 20-move superflip maneuvers allowing commuting moves in either order I believe is: 48*((92-24)*(2^3) + 24*(2^2)) = 30720. That gives about 1 chance in 6.89 quintillion.
But that's not really the correct number because the possible scrambles do not have equal probabilities of occurring. What you really must do is add up the probabilities for each of the 30720 superflip scrambles. (Symmetry considerations can simplify this calculation quite a bit.)
qqwref
Legend
- Joined
- Dec 18, 2007
- Messages
- 7,834
- Location
- a <script> tag near you
- WCA ID
- 2006GOTT01
- YouTube
- Visit Channel
I spent a little time thinking about scrambling probabilities and came to the conclusion that we can figure out the probabilities for an N-move sequence or its equivalent (e.g. LR or RL are both acceptable) being generated by a normal random-move scrambler is:
1/6 * 1/5^(N-1) * 5/4^(number of adjacent same-axis move pairs not at the very end of the sequence) * 2^(number of adjacent same-axis move pairs).
So if we consider R U R' L U L' R, its probability of its being generated from a 7-move scrambler is 1/6 * 1/5^(6) * 5/4^(1) * 2^(2) = 1/18750. Note that that number allows both ...R L'... and ...L' R...
If we want to know the exact probability of one of a given list of N-move sequences being generated, we can just sum the probability of each one (which only really requires knowing how many same-axis move pairs are in each one, and whether any of those are at the very end of the sequence). It won't be as easy as just dividing two numbers, but fortunately we don't have to actually work out the number of sequences of that length.
1/6 * 1/5^(N-1) * 5/4^(number of adjacent same-axis move pairs not at the very end of the sequence) * 2^(number of adjacent same-axis move pairs).
So if we consider R U R' L U L' R, its probability of its being generated from a 7-move scrambler is 1/6 * 1/5^(6) * 5/4^(1) * 2^(2) = 1/18750. Note that that number allows both ...R L'... and ...L' R...
If we want to know the exact probability of one of a given list of N-move sequences being generated, we can just sum the probability of each one (which only really requires knowing how many same-axis move pairs are in each one, and whether any of those are at the very end of the sequence). It won't be as easy as just dividing two numbers, but fortunately we don't have to actually work out the number of sequences of that length.
IQubic
Regular
Can someone give me the source code of a scrambler, so I can work out the chances of getting the superflip?
peterbone
Regular
What are you thinking of doing? Generating random scrambles and counting how many superflips you get? I don't think that will work even for a super-computer. Maybe you have something else in mind?
cuBerBruce
Veteran
OK, I believe I have the actual probability for the supewrflip position being generated by a 20-move scramblebeing for a typical scramble program that generates commuting moves in either order, but avoids trivial redundancies.
The 92 cases Herbert listed can be partitioned into three sets:
1) those that start and end with commuting moves
2) those that end with a pair of commuting moves
3) all others
For these categories, the following table gives:
1) the number of cases (out of the total of 92)
2) a miultipler (how many variations you can generate by swapping adjacent commuting moves)
3) a symmetry multiplier (48 in each case)
4) the probability of a scramble matching the maneuver (not including multiplier effects)
Multiplying out the values in the three categories, and summing, this yields a value of 376 / 2660205384063720703125. This is about 1 in 7.075*(10^18).
Of course, this assumes the scramble generator uses a random number generator (PRNG plus scaling logic) with ideal characteristics.
The 92 cases Herbert listed can be partitioned into three sets:
1) those that start and end with commuting moves
2) those that end with a pair of commuting moves
3) all others
For these categories, the following table gives:
1) the number of cases (out of the total of 92)
2) a miultipler (how many variations you can generate by swapping adjacent commuting moves)
3) a symmetry multiplier (48 in each case)
4) the probability of a scramble matching the maneuver (not including multiplier effects)
Code:
Category cases mult. sym. mult. probability
1 24 4 48 (1/18)*(1/15)^17*(1/12)^2
2 12 8 48 (1/18)*(1/15)^17*(1/12)^2
3 56 8 48 (1/18)*(1/15)^16*(1/12)^3Of course, this assumes the scramble generator uses a random number generator (PRNG plus scaling logic) with ideal characteristics.
Carrot
Veteran
Code:
,/("FRUDLB"@{#&(=':x),2_&':5=+':x}{25?6}/2#2),'25?" ","'2",'" "IQubic
Regular
I will have Guy, the guy guy get me a programming/mathematics guy. We will tackle the problem together.
