It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = 0, 1, \ldots, 20$. (Some of the entries of the table are approximations, but they're good enough for the purposes of this question.)
In particular, the median number of moves needed is 18, and in fact about 70 percent of all positions require eighteen moves.
This seems a bit counterintuitive to me — I'd expect the median to be around half the maximum number of moves needed. Consider for example generating $S_n$, the symmetric group on $n$ elements, from the adjacent transpositions $(k, k+1)$ for $k = 1, 2, \ldots, n-1$. The number of such transpositions needed to get from the identity permutation to any permutation $\sigma$ using adjacent transpositions is the number of inversions of that permutation — that is, the number of pairs $(i,j)$ such that $i < j$ and $\sigma(i) > \sigma(j)$. The maximum number of inversions of a permutation in $S_n$ is ${n \choose 2}$. The mean is ${1 \over 2} {n \choose 2}$; this is also the median if it's a whole number; and the distribution is symmetric around ${1 \over 2} {n \choose 2}$. Another similar case is $(Z/2Z)^n$ generated by the generators of the factors — the diameter is $n$, the typical distance between elements is $n/2$.
My question: which of these situations is, in some sense, "more typical"? More formally, what's known about the relationship between the diameter of the Cayley graph of a group and the typical distance between two vertices? And is there a third case, where the median or mean distance between two random elements is less than half the diameter? Here I'm looking for something like the distribution of Erdos numbers as given by Grossman — the maximum Erdos number is 15 but the median is only 5 — although of course there is the complication here that the collaboration graph is very far from being vertex-transitive.
Best Answer
Your facts about $S_n$ are actually all facts about Coxeter groups with the generating set given by simple reflections: the distribution is symmetric around the mean, which is half the diameter. It even has a unique local maximum (assuming you allow the floor and roof of the mean to be "one maximum" even if they're different). In the Weyl group case, you can think of this as Hard Lefschetz for the flag variety.
I think perhaps the lesson here is that Coxeter groups are not a good representative of "groups in general."