Probability Thread

[stwert]

Edit: I think my question fits better in a separate thread. It's not exactly probability.

 

[kubesolver]

If you had all the stickers necessary to sticker a blank cube, but placed them randomly, what are the odds that it'll be solvable in the standard color scheme?

What are the odds that it'll be solvable in any color scheme?

Are center, edge and corner stickers distinguishable?

 

[Cubing Forever]

If you had all the stickers necessary to sticker a blank cube, but placed them randomly, what are the odds that it'll be solvable in the standard color scheme?

What are the odds that it'll be solvable in any color scheme?

1 in 12 if the centers are in the correct order. If the centers are in the wrong order, probably 1 in 72.

 

[kubesolver]

1 in 12 if the centers are in the correct order. If the centers are in the wrong order, probably 1 in 72.

I think you misunderstood the question. It's about random stickering and not random assembly. My guess is more like one in a 1 000 000 000.

 

[xyzzy]

If you had all the stickers necessary to sticker a blank cube, but placed them randomly, what are the odds that it'll be solvable in the standard color scheme?

What are the odds that it'll be solvable in any color scheme?

kubesolver brought up the observation that standard speedcube stickers have distinguishable centres/edges/corners, so this question has two reasonable answers: one where all 54 stickers are the exact same shape, and one where you use only corner stickers on the corners, etc.

It's helpful to imagine that the 54 stickers are all distinctly labelled, even the ones with the same colour.

1. All stickers are the same shape

The colour scheme can be uniquely defined exactly when every centre gets a different colour.
\( \displaystyle P(\text{centres get different colours})=\frac{9^6}{\binom{54}{6}}\approx0.0206 \)

There are 6!=720 ways to arrange the colours on the centre pieces, of which 24 are a rotation of the standard colour scheme, so there's a 24/720 chance of the colour scheme being the standard one.
\( \displaystyle P(\text{centres get standard colour scheme})=P(\text{standard colour scheme}|\text{centres get different colours})P(\text{centres get different colours})\\
=\frac1{30}P(\text{centres get different colours})\approx6.86\cdot10^{-4} \)

Once the colour scheme has been defined, we can compute the conditional probability of getting solvable corners and edges. There are \( \tfrac12\cdot2^{11}\cdot12!\cdot3^7\cdot8! \) legal cube states once the centres are fixed, and for each of those, we can freely permute the eight remaining white stickers among themselves, etc., so there's an 8! term for each colour.
\( \displaystyle P(\text{solvable}|\text{centres get different colours})=\frac{\tfrac12\cdot2^{11}\cdot12!\cdot3^7\cdot8!\cdot8!^6}{48!}\\
\approx1.497\cdot10^{-14} \)
This conditional probability calculation remains the same even if we restrict to any one (or any nonempty subset) of the 30 possible colour schemes.

Putting these together:
\( \displaystyle P(\text{solvable})=P(\text{any colour scheme})P(\text{solvable}|\text{centres get different colours})\\
=\frac{\tfrac12\cdot2^{11}\cdot12!\cdot3^7\cdot8!\cdot9!^6}{54!/6!}\\
\approx3.08\cdot10^{-16}\\
P(\text{solvable into standard colour scheme})=P(\text{standard colour scheme})P(\text{solvable}|\text{centres get different colours})\\
=\frac{\tfrac12\cdot2^{11}\cdot12!\cdot3^7\cdot8!\cdot9!^6}{54!/6!}\cdot\frac{24}{6!}\\
\approx1.027\cdot10^{-17} \)

(Actually, now that I've worked it out, it wasn't really necessary to treat the centres specially at all. Whatever.)

2. The stickers differ by orbit

Same logic.

\( \displaystyle P(\text{solvable into any colour scheme})=\frac{\tfrac12\cdot2^{11}\cdot12!\cdot3^7\cdot8!\cdot4!^6\cdot4!^6}{24!24!}\\
\approx4.10\cdot10^{-12}\\
P(\text{solvable into standard colour scheme})=\frac{\tfrac12\cdot2^{11}\cdot12!\cdot3^7\cdot8!\cdot4!^6\cdot4!^6\cdot24}{6!24!24!}\\
\approx1.368\cdot10^{-13} \)

These numbers are approximately 13000 times larger than in the earlier case, which makes sense: if the stickers can only go on the same piece type, there're (intuitively speaking) less ways to mess up.

 

[IsThatA4x4]

How could you best find the number of algs required in a step e.g. if you had invented OLL, PLL, LSE, 6CO, etc. for the first time how would you figure out how many algs would be needed?

 

[ruffleduck]

Math, or HARCS.

 

[xyzzy]

Consider these questions:

1. What type(s) of pieces are you solving in this step?
2. How many pieces of each type are you solving?
3. For each type, are you fully solving the pieces, or only solving them partially (e.g. orientation only)?
4. Are there constraints between the piece types? Constraints within a piece type?
5. What do you consider to be "equivalent" cases?

Spoiler: Example with CMLL

CMLL is a step in the Roux method where, after finishing the first two blocks, you solve the four remaining corner pieces.

1. What type(s) of pieces are you solving in this step?
Only one type: the U-layer corners.

2. How many pieces of each type are you solving?
Four.

3. For each type, are you fully solving the pieces, or only solving them partially?
Fully solving.

4. Are there constraints between the piece types? Constraints within a piece type?
Corner orientation must add up to 0 mod 3.

5. What do you consider to be "equivalent" cases?
If two cases are the same up to recolouring (e.g. if you did the same setup on a cube starting in a different orientation), we consider them to be equivalent. We also consider the cases to be equivalent after applying any number of U moves. (To wit: we don't care about AUFs before/after the alg.)

The four corner pieces have 4! = 24 permutations and 3^4/3 = 27 orientations, so there are 24×27 = 648 cube states to consider.

What the "don't care about AUF" equivalence relation really means is that, if cube state \( X \) and cube state \( Y \) satisfy \( X=U^aYU^b \) for some \( a,b\in\{0,1,2,3\} \), then we consider them to be equivalent up to AUF. This can be seen as a (right) group action of \( (\mathbb Z/4)^2 \) on the set of states, acting by \( (a,b):X\mapsto U^{-b}XU^a \). At this point, you can use this thing called Burnside's lemma to count the number of equivalence classes – the number of states that are distinct up to AUF.

"okay but if I knew group theory I wouldn't be asking this question in the first place"

So here's another trick you can use: consider the permutation and orientation separately. You can do permutation first, or orientation first, and they're both very valid approaches.

Spoiler: permutation first

As you should know, up to AUF, the corner permutation can only be three things: (i) solved, (ii) adjacent swap, or (iii) diagonal swap.

In cases (i) and (iii), no matter what AUF you're at, doing any solved-CP alg (e.g. Sune) or any diag-CP alg (e.g. Y perm) (respectively) will always solve CP (up to AUF). In these cases, you can work out all 3^4/3=27 ways to orient the corners and see which of them are equivalents pretty easily – the eight equivalence classes are CO skip (aka "O"), 3 clockwise (aka "antisune"), 3 anticlockwise (aka "sune"), T, U, L, H, and pi. This gives 8 CMLL cases for (i) and (iii) each.

In case (ii), the adjacent swap is uniquely determined (e.g. if it's a URF-UBR swap, you can't do a ULB-UFL swap alg to solve CP), so you can AUF the case to have the corner swap on the right side. Now, all 27 corner orientations will lead to different cases: you can't convert one to another via AUFs, because then the corner permutation would change. So there are 27 cases within (ii).

Putting the numbers together, we have 8+27+8 = 43 CMLL cases. One of them is the solved case, where you don't need an alg, so there are 42 algs needed here.

Spoiler: orientation first

There are eight possible corner orientations up to AUF:
O, A, S, T, U, L, H, pi.
(Corner orientation is only affected by AUF on one side: the four cube states X, U X, U2 X, U' X will always have exactly the same corner orientation, while the four states U, X U, X U2, X U' might have different corner orientations (that are equivalent up to AUF anyway).)

In all of these other than O and H, the corner orientation has no nontrivial rotational symmetry. Once you know the CO, the corner permutation must be one of 4! = 24 permutations. These all have equivalence classes of size 4: X, U X, U2 X, U' X have different permutations, but they're equivalent up to AUF. Thus there are six equivalence classes each for A, S, T, U, L and pi.

O has 90° rotational symmetry: no matter how you AUF it, it's still the same. As in the permutation-first case, there are three CMLL cases here: solved, O-adjacent (solve with a J perm), and O-diag (solve with a Y perm).

H has 180° rotational symmetry: if you do a U2 AUF, the corner orientation remains unchanged. There are four CMLL cases here: H CP skip, H front swap, H right swap, and H diag swap. (H back swap is equivalent to H front swap, and H left swap is equivalent to H right swap.)

This gives 6×6 + 3 + 4 = 43 cases, one of which is solved, so there are 42 algs needed.

CMLL is just a type of CLL, and the calculations above will apply to any type of CLL. That's why COLL, 2×2×2 CLL, Waterman CLL, etc. also have 43 cases (42 algs).

(okay wow typing that out was a lot more effort than I expected; I was going to do two or three examples but maybe not)

If you have something in particular you want to see, I can work that out in detail. If not… condensing a few hours of combinatorics classes into a single forum post is maybe not the best use of my time. Or your time, for that matter. You'll learn some basic combinatorics in school in a couple of years (usually taught together with probability); pay attention in your maths classes.

edit: See also this other post I made (which says mostly the same things, but with less detail). tl;dr: Be systematic, so as to ensure you don't miss out on anything.

 

[ottozing]

Probably a very annoying stat to generate correctly, but one that I'm very interested in since it has interesting implications for CN CFOP solvers

How likely is it to get a 3x3 scramble where at least 1 edge is already lined up with its center? (so 0-1 HTM from solved on 2 colors, or 0-2 QTM from solved)

How likely is it to get a 3x3 scramble where at least 1 edge is already lined up with its opposite center? (so 2 HTM from solved on 2 colors, or 3-4 QTM from solved)

The reason I'm curious about this is that as a CN CFOP solver, the way you typically filter is by looking for one of these 2 types of edges since they stand out the most & tend to give crosses under 7 moves (though the opposite edge is a lot less reliable). I'd be curious to know how often CN CFOP solvers are given a scramble where you're forced to semi-brute force-check a bunch of crosses before you find something nice (nice being 6 or under because 7 move crosses in theory should only happen 0.03% of the time according to cubezone's cross study)

 

[2018AMSB02]

Probably a very annoying stat to generate correctly, but one that I'm very interested in since it has interesting implications for CN CFOP solvers

How likely is it to get a 3x3 scramble where at least 1 edge is already lined up with its center? (so 0-1 HTM from solved on 2 colors, or 0-2 QTM from solved)

How likely is it to get a 3x3 scramble where at least 1 edge is already lined up with its opposite center? (so 2 HTM from solved on 2 colors, or 3-4 QTM from solved)

The reason I'm curious about this is that as a CN CFOP solver, the way you typically filter is by looking for one of these 2 types of edges since they stand out the most & tend to give crosses under 7 moves (though the opposite edge is a lot less reliable). I'd be curious to know how often CN CFOP solvers are given a scramble where you're forced to semi-brute force-check a bunch of crosses before you find something nice (nice being 6 or under because 7 move crosses in theory should only happen 0.03% of the time according to cubezone's cross study)

I believe I could figure this out.

There are 12 positions and 2 orientations of each edge, meaning that there is a 4/24 or 1/6 chance of any edge being lined up with its center. Because there are 12 edges, just do the calculator function binomial dsitribution and use this: 1-binompdf(12,1/6,0), which gives your your answer to the first question of an 88.78% chance. I think this is right, but maybe someone better at his will have to correct me.

For lined up with opposite center, as long as you aren't looking for the probability of it being lined up with opposite center OR it's own center, then I believe it should be the same.

 

[qwr]

I believe I could figure this out.

There are 12 positions and 2 orientations of each edge, meaning that there is a 4/24 or 1/6 chance of any edge being lined up with its center. Because there are 12 edges, just do the calculator function binomial dsitribution and use this: 1-binompdf(12,1/6,0), which gives your your answer to the first question of an 88.78% chance. I think this is right, but maybe someone better at his will have to correct me.

For lined up with opposite center, as long as you aren't looking for the probability of it being lined up with opposite center OR it's own center, then I believe it should be the same.

idk if this is correct because the edges aren't independent of each other.
also this should go in the probability requests not the wca stats, unless we are asking specifically about solves that occurred in wca, but I see no reason not to calculate the exact number

 

[tsmosher]

If I have DBM, DFM, DRS, and all of the U layer edges (7 edges total) oriented and permuted randomly-- with the other edges all being solved-- what would be the lowest case count required to make EOdM (one step solving EO, DFM, and DBM simultaneously) entirely algorithmic?

Let's assume we can influence the good edge (since we know that 1 of these 7 edges will be a good edge) to be in a known location.

Also, let's assume we don't care about DRF, DRB, or any U corners.

We do, however, want to preserve the solved edges (including the FRE and BRE belt edges).

How does this case count change if we are instead on LS with 7 edges remaining (replacing DRS above with FRE)? (Wanting to preserve dL and dbR, i.e. Roux FB and SS. And with our good edge in a known location. And not caring about DFR or U corners.)

And how does the case count change if we attempt EOdM just after SB in a Roux solve (with DBM, DFM, and U layer edges unsolved-- wanting to preserve FB and SB but not U corners)? e.g., ZBRoux

Thanks for anyone who helps answer this.

 

[Jeff Dunham]

I'm interested in learning Winter Variation, and was curious as to what the probability of attaining a winter variation (no specific case, just getting a case) in any given solve is.
I suppose this is equivalent to asking "knowing Winter Variation, what is the probability of an 'OLL Skip'" (yes I know that often it is just a cancellation into OLL but the premise is there.)

 

[Garf]

I'm interested in learning Winter Variation, and was curious as to what the probability of attaining a winter variation in any given solve is.
I suppose this is equivalent to asking "knowing Winter Variation, what is the probability of an 'OLL Skip'" (yes I know that often it is just a cancellation into OLL but the premise is there.)

Winter variation only works when you have a f2l pair stuck together and all the edges are oriented up to the point of last layer. I would suggest trying to figure out the probability of just that, then whatever WV case you want.

 

[Jaym-er]

I'm in the process of generating a 2x2 alg set where you build half the base as a bar of one colour, and half the base with a bar of the opposite colour (example a solid bar of white and solid bar of yellow on the bottom).

Could someone tell me the chance of getting a scramble that starts with this solved and compare to chance of a CLL or EG-1. I'm also wondering how to figure out the average number of moves to solve this base from any scramble (would this be done by sampling or is there convenient math?).

 

[Burrito]

Do the bars have to be solve completely or just oriented like Ortega?

 

[DuckubingCuber347]

Correct me if I am wrong but this method already exists:

NMCLL - Speedsolving.com Wiki

Algs would be the same as CLL.

 

[Jaym-er]

Do the bars have to be solve completely or just oriented like Ortega?

Bars have to be solved completely.

Correct me if I am wrong but this method already exists:

NMCLL - Speedsolving.com Wiki

Algs would be the same as CLL.

Similar but instead of using CLL and up to 3 AUFs, the opposite faces are solved with a direct alg. This makes for only 1 AUF, and algs will be better than the CLL alg

 

[Cubing Forever]

Similar but instead of using CLL and up to 3 AUFs, the opposite faces are solved with a direct alg. This makes for only 1 AUF, and algs will be better than the CLL alg

that would be a lot of algs

 

[Jaym-er]

that would be a lot of algs

True. Roughly 175. I ended up generating over 1 Billion solutions when generating algs. Currently sorting through them to find the best one (I have a program that helps with this though).