Average swaps needed for a random bubble sort algorithm
Suppose we have $n$ elements in a random permutation (each permutation has equal probability initially). While the elements are not fully sorted, we swap two adjacent elements at random (e.g. the permutation $(1, 3, 2)$ can go to $(1, 2, 3)$ or $(3, 1, 2)$ with equal probability $0.5$). How many times does it take on average to fully sort the $n$ elements?
For the case $n=2$, there is a $0.5$ chance that the elements are already sorted, in which case $0$ swaps are needed, and a $0.5$ chance that the two elements are swapped, in which case a single swap is needed to bring the elements back into order, in which case you need $1$ swap, so you need on average $0.5$ swaps.
For the case $n=3$, I used a Markov chain to represent the possible permutations, and (sparing the details) I found that on average $5\frac{5}{6}$ swaps would be needed to get the $3$ elements in order.
For $n\geq4$ it is too difficult to manually construct Markov chains representing the permutations, but I noticed:
- The inversion number always changes by exactly $1$
- From any given state, there are $n-1$ possible states you can transition to
Any ideas for getting a closed form on the expected number of swaps?
Let $S(n)$ be the symmetric group of the set $\{1,2,\dots, n\}$.
It acts on "words" of length $n$ with the letters $1,2,\dots$ taken each exactly once by permuting corresponding places. A permutation will be identified with its action / its result on the "first word" $12\dots n$. There are $n!$ such words, each is an anagram of the first word.
This answer computes explicitly and exactly for small values of $\bf n$ the mean time to reach the permutation $e=()=12\dots n$, which is the neutral element written in alternative notations, when performing a random walk starting from a random element in $S(n)$ / from an anagram. The steps of the random walk correspond to switching two adjacent places in the word.
For very small values, the structure is described, and computations are done easily by hand. However for bigger values, there is no chance. So a computer aided answer is given for those cases, so that we have exact answers from the linear systems extracted from the Markovian structure. My choice of a computer algebra system is sage, since open source and object oriented.
Here are some general conventions first, we try to use standard terminology. The group $S(n)$ is a Weyl group of type $A_{n-1}$, its simple reflections are $$ s_j = s(j) = (j, j+1)\ ,\qquad 1\le j< n\ . $$ (There are $(n-1)$ such reflections, this is also the index in the type.) Depending on the context, the notation $s(j)$ may be better (instead of $s_j$), because the index $j$ is the main feature, so it is not a good idea to show it smaller. Each permutation has a writing as a product of minimal length of these generators taken in a specific order. (There may be one or more such writings.) In case a (non-commutative) "word" $w\in S(n)$ (with alphabet having letters among the simple reflection) is $$ w = s_is_j\dots s_k\ , $$ we will alternatively write it as $$ w = s(i,j,\dots,k)\ , $$ and even - in case of no possible confusion - as $s(ij\dots k)$. In case we use this notation, minimal product representations should be used. (So $s(11)$ is not what we want to write.)
Note the (braid) relations $s(121)=s(212)$, $s(232)=s(323)$, and so on.
Computations will be done in sage. Sage has its own convention(s) to write permutations and work with them. Since below we use code to write down examples, i will use also these conventions. For instance, consider the permutation $p$ that brings the ordered list $(1,2,3,4,5,6,7,8,9)$ into the list $(1,2,3,8,5,6,7,4,9)$. Then we will use for $p$ also this representation as word, $p=123856749$.
On it we can action by the simple reflections from the left. For instance:
sage: W = SymmetricGroup(9)
sage: p = Permutation([1,2,3,8,5,6,7,4,9])
sage: W(p)
(4,8)
sage: s1 = W.simple_reflections()[1]
sage: s2 = W.simple_reflections()[2]
sage: s3 = W.simple_reflections()[3]
sage: s3 * W(p)
(3,8,4)
sage: (s3 * W(p)).tuple()
(1, 2, 8, 3, 5, 6, 7, 4, 9)
sage: # so 1 -> 1, 2 -> 2, 3 -> 8, 4 -> 3, 5 -> 5, 6 -> 6, 7 -> 7, 8 -> 4, 9 -> 9
sage: (s2*(s3 * W(p))).tuple()
(1, 8, 2, 3, 5, 6, 7, 4, 9)
sage: ((s2*s3) * W(p)).tuple()
(1, 8, 2, 3, 5, 6, 7, 4, 9)
sage: s7 = W.simple_reflections()[7]
sage: (s7*W(p)).tuple()
(1, 2, 3, 8, 5, 6, 4, 7, 9)
So this is a left action on "places".
For this action, the composition is a composition of fuctions acting on places.
In order to make this convention work, note that $s_2s_3=(23)(34)$ is $(2,4,3)$.
There is an other convention, also the one i like, where the permutations are function, and their composition is a composition of functions. However, this is not what we want here. To have it explicitly:
sage: s2, s3, s2*s3
((2,3), (3,4), (2,4,3))
sage: s2(s3(4))
2
sage: (s2*s3)(4)
3
On $W=S(n)$ we have a (weak) Bruhat order. See also the Wiki page on the Bruhat order(s).
It is the order given by writing words $w\in W$ in terms of the simple reflection generators. For a simple reflection $s$ and a word $w$ the elements $w$ and $sw$ are in relation. If $w$ has a (i.e. at least one) minimal writing that starts with $s$, then we set $$ sw \prec w\ . $$ Else, prepending $s$ makes each writing "longer" and we define $$ w \prec sw\ . $$ Let $\le$ be the relation obtained by closing the relation $\prec$ to an order relation, the (weak left) Bruhat order we are working with. (We add transitivity, and reflexivity.)
With respect to this order, we have an oriented graph, the (oriented) Bruhat graph. Its vertices are the elements of $W=S(n)$, its edges are corresponding to the simple relations $sw\prec w$ or $w\prec sw$ (only one holds) from above. Its unoriented version is the graph we consider in the problem, so the Bruhat graph is this one below. Its edges have natural labels $s$, simple reflections, in order to move from one vertex to the other one one multiplies from the right with $s$. The "word length" either increases or decreases by one, $l(sw)=l(w)\pm 1$.
There are standard properties of this order. For instance, taking final subwords of a minimal word lead to Bruhat-smaller words.
Our problem is related to a random walk on this graph, each step having length one. The question asks for the expected time needed to entry the set $\{e\}$ consisting of the neutral element only.
Although simple, let us consider first the case $n=3$ in detail to illustrate the structural situation in other cases, where propositions are not so simple.
n = $\bf 3$
There are $6=3!$ elements in $S(3)$. We denote the two transpositions or simple reflections $(12)=213$ and $(23)=132$ by $s_1=s(1)$, and respectively $s_2=s(2)$. Each element can then be written in a minimal (length) fashion as a product of $s_1,s_2$. Explicitly: $$ \begin{aligned} () &= 123 = e = s()\ , \\ (12) &= 213 = s_1=s(1)\ , \\ (23) &= 132 = s_2=s(2)\ , \\ (132) &= 312 = (12)(23) = s_1s_2=s(1,2)=s(12)\ , \\ (123) &= 213 = (23)(12) = s_2s_1=s(2,1)=s(21)\ , \\ (13) &= 321 = s_1s_2s_1=s_2s_1s_2=s(1,2,1)=s(2,1,2)=s(121)=s(212)\ . \end{aligned} $$ (Some of the above lines have the meaning of an implicit notation.)
The corresponding Bruhat graph is:
s()
/ \
2/ \1
/ \
s(2) s(1)
| |
1| |2
| |
s(12) s(21)
\ /
2\ /1
\ /
s(121)
Let $N_w$ or $N(I)=N_w$ if $w=s(I)$, be the expected number of steps to go from the permutation $w$ to the neutral element $e$. Here, if $I$ is a multiindex choice of simple reflections, $I=(i,j,\dots,k)$ we denote by $s(I)=s_is_j\dots s_k$. Then we have the following system of equations to solve: $$ \left\{ \begin{aligned} N_e = N() &= 0\ ,\\ N(1) &= 1 + \frac 12N() + \frac 12 N(12)\ ,\\ N(2) &= 1 + \frac 12N() + \frac 12 N(21)\ ,\\ N(12) &= 1 + \frac 12N(1) + \frac 12 N(121)\ ,\\ N(21) &= 1 + \frac 12N(2) + \frac 12 N(121)\ ,\\ N(121) &= 1 + \frac 12N(12) + \frac 12 N(21)\ . \end{aligned} \right. $$ (In fact, we do not need to solve this system explicitly, we need only the value $\displaystyle \frac 1{3!}(\ N()+N(1)+N(2)+N(12)+N(21)+N(121)\ )$.)
var('x,x1,x2,x12,x21,x121');
solve( [x == 0, x1 == 1 + (x + x12)/2, x2 == 1 + (x + x21)/2,
x12 == 1 + (x1 + x121)/2, x21 == 1 + (x2 + x121)/2,
x121 == 1 + (x12 + x21)/2, ],
[x, x1, x2, x12, x21, x121] )
The solution is:
[[x == 0, x1 == 5, x2 == 5, x12 == 8, x21 == 8, x121 == 9]]
And we build the sum $0+(5+5)+(8+8)+9=35$, so the expected mean is $\displaystyle\frac {35}6\approx 5.8333\dots$ .
From the above we want to extract only the "cellular" structure, there are four cells, coincidently corresponding here to the four possible lengths of a word. The cells and the transitions between them are as follows:
s()
A |
1/2 | | 1
| V
s(1), s(2)
A |
1/2 | | 1/2
| V
s(12), s(21)
A |
1 | | 1/2
| V
s(121)
So we have to solve a simpler system, using $M_l$ for the cell with words of length $l$: $$ \left\{ \begin{aligned} N_0 &= 0\ ,\\ N_1 &= 1 + \frac 12 N_0 +\frac 12 N_2\ ,\\ N_2 &= 1 + \frac 12 N_1 +\frac 12 N_3\ ,\\ N_3 &= 1 + N_2\ . \end{aligned} \right. $$ Its solution is of course the "same" one, $N_0=0$, $N_1=5$, $N_2=8$, $N_3=9$, so counting each cell weighted corresponding to the number of its elements,
The next case is slightly more complicated.
n = $\bf 4$
There are $24=4!$ elements in $S(4)$. We have three simple reflections. The elements have the following representations (code and results):
sage: W = WeylGroup('A3')
sage: elements = list(W)
sage: elements.sort(key=lambda w: w.length())
sage: for w in elements:
....: print(' = '.join([''.join([str(j) for j in word]) for word in w.reduced_words()]))
....:
3
2
1
32
23
21
31 = 13
12
321
232 = 323
231 = 213
132 = 312
123
121 = 212
2321 = 3213 = 3231
2312 = 2132
1321 = 3212 = 3121
3123 = 1323 = 1232
1213 = 1231 = 2123
32132 = 21321 = 23121 = 23212 = 32312
12321 = 31231 = 13231 = 31213 = 13213 = 32123
12132 = 21323 = 23123 = 12312 = 21232
312312 = 213213 = 321232 = 312132 = 132132 = 323123 = 231213 = 212321 = 121321 = 321323 = 123212 = 123121 = 213231 = 231231 = 232123 = 132312
(The first empty line stays for the neutral element.) The "cells" are now harder to be isolated and shown. At the beginning there is no problem.
()
A|
1 || 1
|V
1, 2, 3
But now we have to separate
1_________ __2__ _________3
| \/ \/ |
2| 1/\3 1/\3 |2
V / \ / \ V
21 12 13=31 32 23
The entry $13=31$ is not "like the other" length two entries, since it has two possible beginnings. From here, we know that each of the entries $21$, $12$; $23$, $32$ is connected to two words of lenght three, while $13=31$ connects to only one such entry in the Bruhat graph.
In length $3$ we have a similar separation. We show only how the entries connect to lower and higher length levels.
1\ /2 2\ /3 |3 |1 1\ /3 |2
\ / \ / | | \ / |
\ / \ / | | \ / |
121 232 321 123 132 213
=212 =323 / \ / \ =312 =231
| | / \ / \ | / \
| | 1/ \2 2/ \3 | / \
|3 |1 |2 1/ \3
It is not easy to draw the graph. We have only a symmetry corresponding to $s_1\leftrightarrow s_3$ that we can use. Doing this, we still obtain some graph that can be traced back humanly. Each entry has now representatives shown in a single writing. Only some vertices are drawn.
____e____
/ \
/ \
/ \
1, 3___ 2
| \ |
| \ |
| \ |
21, 23 13 ____12, 32
| \ \ / |
| \ _____X |
| X \ |
| / \ \ |
121,/ 123, 213 132
323 321 | |
| / \ | |
| / \ | |
| / \ | |
1321, 1213, 2132
1323 2321 /
\ \ _____/
\ ____X
\ / \
12132, 12321
23212 /
\ /
\ /
121321
This leads to a system with $15$ unknowns to be solved. I will solve the system with all $24$ equations using code. But it is good to see that the solutions respect this and only this symmetry! The code is as follows:
def expected_steps(n):
W = WeylGroup(['A', n-1])
w_list = list(W)
w_list.sort(key=lambda w: w.length())
for w in w_list:
exec("var('x{}')".format(''.join([str(j) for j in w.reduced_word()])))
class WE(object):
"""Associate to each w in W an instance with some more needed structure.
WE is a short cut for Weyl element.
"""
def __init__(self, w):
self.w = w
self.varname = 'x' + (''.join([str(j) for j in w.reduced_word()]))
self.var = eval(self.varname)
vars = [WE(w).var for w in w_list]
eqs = [ WE(W.one()).var == 0 ] \
+ [ WE(w).var == 1 + 1/(n-1) * sum([WE(s*w).var for s in W.simple_reflections()])
for w in w_list if w != W.one()]
sol = solve(eqs, vars, solution_dict=True)[0]
return sol
Then sol = expected_steps(4) gives:
sage: sol
{x: 0,
x3: 625/28,
x2: 341/14,
x1: 625/28,
x32: 981/28,
x23: 981/28,
x21: 981/28,
x31: 405/14,
x12: 981/28,
x321: 1153/28,
x232: 1081/28,
x231: 274/7,
x312: 274/7,
x123: 1153/28,
x121: 1081/28,
x2321: 171/4,
x2312: 621/14,
x3121: 171/4,
x1232: 171/4,
x1231: 171/4,
x23121: 1273/28,
x12321: 629/14,
x12312: 1273/28,
x123121: 324/7}
So the expected number of steps needed to reach $e$ starting from a random element is:
sage: sum(sol.values())/factorial(4)
1019/28
The next case is more complicated, although the same code leads to a quick solution.
n = $\bf 5$
We get:
sage:
sage: sol = expected_steps(5)
sage: sol
{x: 0,
x3: 3860770457/31585785,
x2: 3860770457/31585785,
x4: 3656646373/31585785,
x1: 3656646373/31585785,
x32: 10793324539/63171570,
x34: 1486245371/9024510,
x23: 10793324539/63171570,
::::::::::::::::::::::::::::::
x1234312: 6637368586/31585785,
x23412312: 13606936667/63171570,
x23423121: 13500639197/63171570,
x23412321: 1355491084/6317157,
x12342312: 1355491084/6317157,
x12341231: 13500639197/63171570,
x34123121: 13500639197/63171570,
x12342321: 13419193339/63171570,
x12343121: 13419193339/63171570,
x12341232: 13500639197/63171570,
x234123121: 6825812773/31585785,
x123412312: 6825812773/31585785,
x123423121: 88342141/410205,
x123412321: 88342141/410205,
x1234123121: 15737160/72611}
sage:
I see no way to organize combinatorially the values obtained without a deep (group-theoretical) insight. For instance, the common denominator is:
sage: lcm([val.denominator() for val in sol.values() if val])
63171570
sage: ZZ(_).factor()
2 * 3 * 5 * 7 * 11 * 23 * 29 * 41
The mean expectation is:
sage: sum(sol.values())/120
73483980061/379029420
One observation we make is that the expected number of steps to go from $w$ to $e$ is the same as when we go from $w^{-1}$ to $e$.
n = $\bf 6$
The case is even more complicated from the combinatorial point of view. However the linear algebra exercise is still easy for the computer.
sage: sol = expected_steps(6)
sage: sum(sol.values()) / factorial(6)
1105216051055620235300660929/1023883272960409990968840
sage: _.n()
1079.43559607146
We can still hope to see some structure from the factorization of the denominator. But...
sage: QQ(sum(sol.values()) / factorial(6)).denominator()
1023883272960409990968840
sage: QQ(sum(sol.values()) / factorial(6)).denominator().factor()
2^3 * 3^3 * 5 * 7 * 11 * 13 * 19 * 23 * 29 * 41 * 61 * 67 * 71 * 1931 * 3253
There was an observation in case $n=5$, that the expected number of steps steps to go from $w$ to $e$ is the same as when going from $w^{-1}$ to $e$. Let us verify it here.
W = WeylGroup('A5')
w_list = list(W)
w_list.sort(key=lambda w: w.length())
ok = True
for w in w_list:
we1, we2 = WE(w), WE(w^-1)
if we1.varname < we2.varname:
if sol[we1.var] == sol[we2.var]:
print('OK :: same value {} for {} and the inverse {}'
.format(sol[we1.var], we1.varname, we2.varname))
else:
ok = False
print('*** DIFFERENT VALUES :: {} = {} and {} = {}'
.format(we1.var, sol[we1.var], we2.var, sol[we2.var]))
This gives a lot of confirmation lines and finally ok remains True:
sage: ok
True
A way to argument is as follows. Each path of adjacent flips to get from $w$ to $e$ corresponds to exactly one path from $w^{-1}$ to $e$, apply them in reversed order. This symmetry and the symmetry of the Dynkin diagram, i.e. exchanging simple reflections in the ordered list $(s_1,s_2,s_3,s_4,s_5)$ so that we get them in reversed order, $(s_5,s_4,s_3,s_1,s_1)$, seem to be the only symmetries in the structure.
Here are some explicit values calculated above:
sage: [ (WE(w).var, sol[WE(w).var]) for w in w_list if w.length() < 3 ]
[(x, 0),
(x3, 409694003392678411334887/562573226901324170862),
(x2, 74514494034185062222904137/102388327296040999096884),
(x4, 74514494034185062222904137/102388327296040999096884),
(x1, 18061592492928724555567534/25597081824010249774221),
(x5, 18061592492928724555567534/25597081824010249774221),
(x32, 97237251774773889429499579/102388327296040999096884),
(x34, 97237251774773889429499579/102388327296040999096884),
(x23, 97237251774773889429499579/102388327296040999096884),
(x21, 7932055083392903915602457/8532360608003416591407),
(x43, 97237251774773889429499579/102388327296040999096884),
(x42, 22612046194800912089196392/25597081824010249774221),
(x45, 7932055083392903915602457/8532360608003416591407),
(x31, 22229387237663671307532949/25597081824010249774221),
(x12, 7932055083392903915602457/8532360608003416591407),
(x41, 219680864482149559964339/252187998266110835214),
(x53, 22229387237663671307532949/25597081824010249774221),
(x52, 219680864482149559964339/252187998266110835214),
(x54, 7932055083392903915602457/8532360608003416591407),
(x51, 43713633645486016276491673/51194163648020499548442)]
sage: max([w.length() for w in W])
15
sage: [ (WE(w).var, sol[WE(w).var]) for w in w_list if w.length() > 13 ]
[(x12345123412312, 4107915597637259266379722/3656725974858607110603),
(x23451234123121, 4107915597637259266379722/3656725974858607110603),
(x12345123423121, 1473205929421015577091523/1312670862769756398678),
(x12345123412321, 114943156003573670133682777/102388327296040999096884),
(x12345234123121, 114943156003573670133682777/102388327296040999096884),
(x123451234123121, 136181060295340/121172438079)]
n = $\bf 7$
This case is somehow too big for the pedestrian way of solving systems above. (There was some handy notation for the variables, which has its merits, but in this case this is too expensive.) So we really have to implement the linear system by building its matrix.
def mean_number_of_steps(n, print_A=False, print_x=False):
W = WeylGroup(['A', n-1])
w_list = list(W)
w_list.sort(key=lambda w: w.length())
w_cells = []
w_used_values = []
for w in w_list:
if w in w_used_values:
continue
if w == W.one():
w_cells.append( [w] )
w_used_values.append(w)
continue
cell = [w, w^-1]
word = w.reduced_word()
u = W.from_reduced_word([n-j for j in word])
cell = tuple(set([w, w^-1, u, u^-1]))
w_cells.append(cell)
w_used_values.extend(list(cell))
def get_cell_index(w):
return [ w_cells.index(cell) for cell in w_cells if w in cell ][0]
class WA(object):
"""Associate to each w in W an instance with some more needed structure.
"""
def __init__(self, w):
self.w = w
self.index = get_cell_index(w)
if w == W.one():
self.neighbours = []
else:
self.neighbours = [ get_cell_index(s*w)
for s in W.simple_reflections() ]
f, c = factorial(n), len(w_cells)
A = matrix(QQ, c, c)
for cell in w_cells:
w = cell[0] # pick a representative of the cell
wa = WA(w)
A[wa.index, wa.index] = 1
for j in wa.neighbours:
A[wa.index, j] += -1 / (n-1)
# print(A)
if print_A:
print("The matrix of the system is:")
print(A)
b = vector(QQ, c, [1 if j != 0 else 0 for j in range(c)])
x = A.solve_right(b)
if print_x:
print("The solution of the system is:")
print(x)
return sum([ x[j] * QQ(len(w_cells[j])) for j in range(c) ]) / f
Using this code, the prints
for n in [2..8]:
print(f'\nn = {n}')
M = mean_number_of_steps(n, print_A=(n < 5), print_x=(n < 5))
print(f'\nMean number of steps is:\n {M}\n so approximatively {M.n()}')
are delivering
n = 2
The matrix of the system is:
[ 1 0]
[-1 1]
The solution of the system is:
(0, 1)
Mean number of steps is:
1/2
so approximatively 0.500000000000000
and
n = 3
The matrix of the system is:
[ 1 0 0 0]
[-1/2 1 -1/2 0]
[ 0 -1/2 1 -1/2]
[ 0 0 -1 1]
The solution of the system is:
(0, 5, 8, 9)
Mean number of steps is:
35/6
so approximatively 5.83333333333333
and
n = 4
The matrix of the system is:
[ 1 0 0 0 0 0 0 0 0 0 0 0 0]
[-1/3 1 0 -1/3 -1/3 0 0 0 0 0 0 0 0]
[-1/3 0 1 -2/3 0 0 0 0 0 0 0 0 0]
[ 0 -1/3 0 1 0 -1/3 -1/3 0 0 0 0 0 0]
[ 0 -2/3 0 0 1 0 0 -1/3 0 0 0 0 0]
[ 0 0 0 -1/3 0 1 0 0 -2/3 0 0 0 0]
[ 0 0 0 -2/3 0 0 1 0 -1/3 0 0 0 0]
[ 0 0 0 0 -1/3 0 0 1 -2/3 0 0 0 0]
[ 0 0 0 0 0 -1/3 -1/3 0 1 0 -1/3 0 0]
[ 0 0 0 0 0 0 0 -1/3 0 1 -2/3 0 0]
[ 0 0 0 0 0 0 0 0 -1/3 -1/3 1 0 -1/3]
[ 0 0 0 0 0 0 0 0 -2/3 0 0 1 -1/3]
[ 0 0 0 0 0 0 0 0 0 0 -2/3 -1/3 1]
The solution of the system is:
(0, 625/28, 341/14, 981/28, 405/14, 1153/28, 1081/28, 274/7, 171/4, 621/14, 1273/28, 629/14, 324/7)
Mean number of steps is:
1019/28
so approximatively 36.3928571428571
and
n = 5
Mean number of steps is:
73483980061/379029420
so approximatively 193.874079909153
and
n = 6
Mean number of steps is:
1105216051055620235300660929/1023883272960409990968840
so approximatively 1079.43559607146
and
n = 7
Mean number of steps is:
214998640399563504565106261781990833196638436647758234442887215473549887803722305593765999513740842990149079
/
31218641703910975710483919230896568944120659862343614701479235239401027577533129044990591113216494809020
so approximatively 6886.86722627747
(with a manually rearranged fraction...) and
n = 8
(... still working ...)
I have to stop here, this was a hard day's night, and the next similar day has started...