Probability Thread

[Deleted member 52530]

Probability of a 3 move solution from an official 7x7 scramble? It's in a reg or something

 

[alexiscubing]

Believe it or not, my first ever solve in my life had a LL skip

My first 2 times finishing the cube had LL skips (not knowing LL and only knowing how to do F2L boosted this significantly)

 

[xyzzy]

Probability of a 3 move solution from an official 7x7 scramble? It's in a reg or something

Oh boy, this is a fun question.

Let's say our official scrambles are random-state. How many 3-move scrambles are there? There are 54 choices for the first move and 51 choices for the second move (always), and the number of choices for the third move depends on the first two moves but it's always between 48 and 51. So there are at least 54×51×48 = 132192 and at most 54×51×51 = 140454 3-movers. Divide this by the total number of possible 7^3 states (about 2×10^160), and you get an answer of about 7×10^−156.

But that's assuming that our official scrambles are random-state, which they are not! It is known (to me, at least) that random-move big cube scrambles require way more moves than what's currently used in TNoodle (60/80/100 moves for 5/6/7 respectively) to reach an approximately uniform distribution. One could naïvely estimate the probability of a 7^3 WCA scramble sequence not using three-layer moves at all as (2/3)^100 ~ 2.5×10^−18 (the true probability is actually somewhat lower because adjacent moves are not independent), and in this case the scramble will be functionally identical to just a 5^3 scramble. Now, if we assume that those hundred moves do reach an approximately uniform distribution on a 5^3, the probability of getting a 3-mover is now at least (2/3)^100 × (36×33×30/(2.6×10^90)) ~ 3.4×10^−104. This is fifty-two orders of magnitude greater than the probability with a true random-state scramble.

---

edit The above has some minor mistakes and simplifications (which don't affect the qualitative conclusion that the scrambles being random-move rather than random-state changes the result of the calculation by many orders of magnitude), so here's the real working.

For odd-order cubes, the number of 3-move states is the same as the number of canonical 3-move sequences, since the shortest "nontrivially" equivalent sequences are at least four moves long (U2 D2 L2 R2 = L2 R2 U2 D2). (Side note: On even-order cubes, the shortest nontrivially equivalent sequences are three moves long (U2 R2 U2 = R2 U2 R2 on 222).)

The number of canonical 3-move sequences is 28836 for 555 and 100764 for 777. This immediately gives:
\( P(\text{random-state 777 scramble can be solved in 3 moves})=\frac{100764}{1.95006\cdot10^{160}}=5.16724\cdot10^{-156} \)

TNoodle's random-move scramble generation looks very complicated, but most of that complexity seems to exist to deal with weird puzzles like megaminx (… except it no longer supports 12-gen mega scrambles anyway) and the core algorithm can be described simply as:
1. Pick a random move uniformly among the possible moves that doesn't cancel with the current scramble sequence. (Note: this checks for cancellations that can be obtained by rearranging commuting moves at the end, like L R L = L2 R, but not more complicated ones like L2 R2 U2 D2 L = U2 D2 R2 L'.)
2. Append that move to the scramble sequence and repeat until it is of the desired length.

In the case of the n×n×n cubes, this is fairly easy to implement directly, with a lot less complexity than the fully general version in TNoodle. See e.g. csTimer's or qqTimer's source code. But we don't care about that; we just want to count scramble sequences. If we assume every generated scramble sequence is equally likely (an assumption that turns out to be false, but still fairly close to the truth), then we can divide the number of 100-move 555 scramble sequences by the number of 100-move 777 scramble sequences to get the probability of a 777 scramble sequence not using any 3Uw*, 3Dw*, 3Lw*, 3Rw*, 3Fw* or 3Bw* moves. This works out to be
\( P(\text{scramble does not use 3*w* moves})\approx\frac{5.21753\cdot10^{150}}{7.74251\cdot10^{169}}=6.73881\cdot10^{-20}, \)
a bit more than an order of magnitude smaller than the fully naïve estimate of \( (2/3)^{100}\approx2.45965\cdot10^{-18} \) in the first section.

To get a proper lower bound, observe that after the first move (which always has an exactly 2/3 probability of not being 3*w*), the probability of a move not being 3*w*, conditioned on knowing the earlier moves and also on that the earlier moves are all not 3*w*, must be 11/17, 10/16, 9/15, or 8/14 (depending on how many moves along the same axis have been made), with the last one being the smallest. This gives a lower bound of
\( P(\text{scramble does not use 3*w* moves})>(2/3)\cdot(8/14)^{99}=5.79618\cdot10^{-25}. \)

Now, assuming that the scramble does not use 3*w* moves and that 100 moves is enough to scramble whatever can be scrambled almost uniformly, we have:
\( P(\text{scramble can be solved in 3 moves})>P(\text{no 3*w* moves and can be solved in 3 moves})\\
=P(\text{no 3*w* moves})P(\text{can be solved in 3 moves}|\text{no 3*w* moves})\\
\gtrsim(5.79618\cdot10^{-25})\cdot\frac{28836}{2.58264\cdot10^{90}}\\
=6.47163\cdot10^{-111} \)

This somewhat more rigorous lower bound is "only" 45 orders of magnitude smaller than what we would expect from random-state scrambles. There's still one handwaving step in the derivation where we assume that 100 moves is enough to scramble a 555, but heuristically, we expect that the deviation of this assumption from the truth is in our favour, i.e. it would actually increase the probability of getting a 3-mover.

Code to calculate the number of canonical sequences / possible scramble sequences:

def count_scramble_sequences(size, length):
    nmoves_per_axis = size-1
    last = [1] + [0]*nmoves_per_axis
    for i in range(length):
        same_axis = [0] + [last[j-1] * (nmoves_per_axis-(j-1)) for j in range(1, nmoves_per_axis+1)]
        diff_axis = [0] + [sum(last) * (2*nmoves_per_axis)] + [0] * (nmoves_per_axis-1)
        last = [same_axis[j]+diff_axis[j] for j in range(nmoves_per_axis+1)]
    return sum(last) * 3**length

def count_canonical_sequences(size, length):
    nmoves_per_axis = size-1
    last = [1] + [0]*nmoves_per_axis
    for i in range(length):
        same_axis = [sum(last[:j]) for j in range(nmoves_per_axis+1)]
        diff_axis = [0] + [2*sum(last)] * nmoves_per_axis
        last = [same_axis[j]+diff_axis[j] for j in range(nmoves_per_axis+1)]
    return sum(last) * 3**length

 

[1cubealot]

Wow that is low

 

[1cubealot]

My first 2 times finishing the cube had LL skips (not knowing LL and only knowing how to do F2L boosted this significantly)

I hav never gotten an LL skip before

 

[Username: Username:]

I hav never gotten an LL skip before

Since a LL is sooooooooooooooo rare, I have never gotten it. I have like 3000 solves this month and not even a single one.

Woah. Tysm but oof the ^ is kinda hard to understand, but tysm

^ means to bring up to X power.

 

[Deleted member 52530]

Oh boy, this is a fun question.

Let's say our official scrambles are random-state. How many 3-move scrambles are there? There are 54 choices for the first move and 51 choices for the second move (always), and the number of choices for the third move depends on the first two moves but it's always between 48 and 51. So there are at least 54×51×48 = 132192 and at most 54×51×51 = 140454 3-movers. Divide this by the total number of possible 7^3 states (about 2×10^160), and you get an answer of about 7×10^−156.

But that's assuming that our official scrambles are random-state, which they are not! It is known (to me, at least) that random-move big cube scrambles require way more moves than what's currently used in TNoodle (60/80/100 moves for 5/6/7 respectively) to reach an approximately uniform distribution. One could naïvely estimate the probability of a 7^3 WCA scramble sequence not using three-layer moves at all as (2/3)^100 ~ 2.5×10^−18 (the true probability is actually somewhat lower because adjacent moves are not independent), and in this case the scramble will be functionally identical to just a 5^3 scramble. Now, if we assume that those hundred moves do reach an approximately uniform distribution on a 5^3, the probability of getting a 3-mover is now at least (2/3)^100 × (36×33×30/(2.6×10^90)) ~ 3.4×10^−104. This is fifty-two orders of magnitude greater than the probability with a true random-state scramble.

Woah. Tysm but oof the ^ is kinda hard to understand, but tysm

 

[xyzzy]

Woah. Tysm but oof the ^ is kinda hard to understand, but tysm

7×10^−156 = 0.0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 000007
3.4×10^−104 = 0.0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 00034

Scientific notation makes it so that you're not literally staring at a long string of zeros when dealing with very small or very big numbers.

 

[1cubealot]

7×10^−156 = 0.0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 000007
3.4×10^−104 = 0.0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 00034

Scientific notation makes it so that you're not literally staring at a long string of zeros when dealing with very small or very big numbers.

0.0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 00034 =
0.0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 034%

 

[2018AMSB02]

Probability of cubeshape skip in square-1? I’ve seen it happen a few times so it shouldnt be too low

 

[brododragon]

Oh boy, this is a fun question.

Let's say our official scrambles are random-state. How many 3-move scrambles are there? There are 54 choices for the first move and 51 choices for the second move (always), and the number of choices for the third move depends on the first two moves but it's always between 48 and 51. So there are at least 54×51×48 = 132192 and at most 54×51×51 = 140454 3-movers. Divide this by the total number of possible 7^3 states (about 2×10^160), and you get an answer of about 7×10^−156.

But that's assuming that our official scrambles are random-state, which they are not! It is known (to me, at least) that random-move big cube scrambles require way more moves than what's currently used in TNoodle (60/80/100 moves for 5/6/7 respectively) to reach an approximately uniform distribution. One could naïvely estimate the probability of a 7^3 WCA scramble sequence not using three-layer moves at all as (2/3)^100 ~ 2.5×10^−18 (the true probability is actually somewhat lower because adjacent moves are not independent), and in this case the scramble will be functionally identical to just a 5^3 scramble. Now, if we assume that those hundred moves do reach an approximately uniform distribution on a 5^3, the probability of getting a 3-mover is now at least (2/3)^100 × (36×33×30/(2.6×10^90)) ~ 3.4×10^−104. This is fifty-two orders of magnitude greater than the probability with a true random-state scramble.

Here's an expansion to that question: What event is most likely to generate a scramble that's the minimum amount of moves for said event? Here's the regulation:

• 4b3) Specification for a scramble program: An official scramble sequence must produce a random state from all states that require at least 2 moves to solve (equal probability for each state). The following additions/exceptions apply:
  • 4b3a) For blindfolded events, the scramble sequence must orient the puzzle randomly (equal probability for each orientation).
  • 4b3b) 2x2x2 Cube: The (random) state must require at least 4 moves to solve.
  • 4b3c) Skewb: The (random) state must require at least 7 moves to solve.
  • 4b3d) Square-1: The (random) state must require at least 11 moves to solve.
  • 4b3e) 5x5x5 Cube, 6x6x6 Cube, 7x7x7 Cube, and Megaminx: sufficiently many random moves (instead of random state), at least 2 moves to solve.
  • 4b3f) Pyraminx: The (random) state must require at least 6 moves to solve.

 

[xyzzy]

Here's an expansion to that question: What event is most likely to generate a scramble that's the minimum amount of moves for said event? Here's the regulation:

>>> 1847 / (3674160-1-9-54-321) # 222
0.0005027526182196787
>>> 315198 / (3149280-1-8-48-288-1728-10248-59304) # skewb
0.10241498803472124
>>> (38893230+3091458)/(435891456000-1-64-1153-17050-235144-3091458) # upper bound for squan
9.631987413274141e-05
>>> (38893230)/(435891456000-1-64-1153-17050-235144) # lower bound for squan
8.922692123419956e-05
>>> pyra_notips = [1,8,48,288,1728,9896,51808,220111,480467,166276,2457,32,0,0,0,0]
>>> pyra_tips = [pyra_notips[i]+2*4*pyra_notips[i-1]+4*6*pyra_notips[i-2]+8*4*pyra_notips[i-3]+16*pyra_notips[i-4] for i in range(16)]
>>> pyra_tips[6]/sum(pyra_tips[6:]) # pyraminx
0.002414913105050851

The values for squan are only lower/upper bounds because the exact distribution is not known for the WCA metric. (Wouldn't be hard per se to just calculate the exact value without determining the full distribution, but it's not relevant to your question.) The answer is clearly skewb, with about 10% of skewb scrambles being 7-movers.

All raw values from Jaap's Puzzle Page.

 

[Cuberstache]

about 10% of skewb scrambles being 7-movers.

Wow, incredible! I guess most 7-movers just aren't obvious to humans.

 

[potatojuiceultra]

My first 2 times finishing the cube had LL skips (not knowing LL and only knowing how to do F2L boosted this significantly)

I was able to intuitively figure out f2l but the only last layer algorithm I would come up with was a sune. So my first solve either had a full LL skip or a sune or anti-sune with a PLL skip.
If I didn't get either of those I would just rescramble the cube.

 

[nuclearaven]

chance of a LL skip with EO and CP done (so a 2GLL skip)? my initial thought was that its just 1/6th of a ZBLL skip but im not sure.

 

[xyzzy]

chance of a LL skip with EO and CP done (so a 2GLL skip)? my initial thought was that its just 1/6th of a ZBLL skip but im not sure.

That is correct.

You can also calculate it directly as 1/3^3 (CO skip) × 1/(4!/2) (EP skip) = 1/324.

 

[2018AMSB02]

What is the probability of having one edge paired with the center on any face on clock? 2 paired up? 3?

 

[Cody_Caston]

What’s the probability of getting a skewb scramble with all corners solved

 

[Kit Clement]

What is the probability of having one edge paired with the center on any face on clock? 2 paired up? 3?

All 14 clock wheels are independent, so it's as simple as a binomial calculation. Assume the centers on each face are fixed, then you have 8 chances to get any pairs. It's easiest to go about this by first doing the chance of nothing pairing up at all to get the probability of at least one edge paired:

1 - (11/12)^8 = 50.14%

Having at least 2 or 3 matching on the same face gets more complicated, as we'd need to calculate the probability of getting it on one face, then use that probability to find whether it could happen on at least one of the faces. For just one face, we have 4 potential clocks to match a fixed center.

(4 choose 4)(1/12)^4(11/12)^0 + (4 choose 3)(1/12)^3(11/12)^1 + (4 choose 2)(1/12)^2(11/12)^2 = 0.03718

Now, since each face's edges/centers are determined independently, we can take the same approach of calculating the probability of neither face having this outcome, and then take the opposite probability:

1 - (1 - [above answer])^2 = 7.3%

We can do the same for 3 by taking the same approach but eliminating the case above for exactly 2 matching on one face.

(4 choose 4)(1/12)^4(11/12)^0 + (4 choose 3)(1/12)^3(11/12)^1 = 0.00217

1 - (1 - [above answer])^2 = 0.43%

 

[xyzzy]

What’s the probability of getting a skewb scramble with all corners solved

(Assuming true random-state and no scramble filter; this probably changes the probability by a few percent if you're using WCA-legal scrambles, which do have a scramble filter.)

Fix one tetrad of corners as a reference (e.g. the ones that are fixed to the core). Call this the first tetrad, and call the other tetrad the second tetrad.

P(first tetrad is oriented) = 1/3^4

P(second tetrad is permuted | first tetrad is oriented) = 1/4
(orientation of the first tetrad is related to the Klein 4-group coset of the second tetrad's permutation, so if the first tetrad is oriented, the permutation of the second tetrad must also be in the Klein 4-group)

P(second tetrad is oriented | first tetrad is oriented and second tetrad is permuted) = 1/3^3
(orientation of the first three corners can be freely chosen; the orientation of the fourth corner is determined by the rest)

P(all corners are solved) = 1/3^4 × 1/4 × 1/3^3 = 1/8748