Sorting by Swaps with Noisy Comparisons∗
Tomáš Gavenčiak1,3
Barbara Geissmann2,4
Johannes Lengler2

arXiv:1803.04509v1 [] 12 Mar 2018

1

Charles University in Prague
2
ETH Zurich

Abstract
We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability p < 1/2. We use
this process as prototype for the behaviour of randomized, comparisonbased optimization heuristics in the presence of noisy comparisons. As
quality measure, we compute the expected fitness of the stationary distribution. To measure the runtime, we compute the minimal number of
steps after which the average fitness approximates the expected fitness of
the stationary distribution.
We study the process where in each round a random pair of elements
at distance at most r are compared. We give theoretical results for the
extreme cases r = 1 and r = n, and experimental results for the intermediate cases. We find a trade-off between faster convergence (for large r)
and better quality of the solution after convergence (for small r).

1

Introduction

Randomized optimization heuristics like evolutionary algorithms (EAs) have become important practical tools for optimization problems that are too complex
to solve exactly [11], and some efforts have been made to understand such search
heuristics theoretically [6, 23, 31]. Mostly, the optimization problem is given by
some unknown fitness function f : S → R to be minimized (or maximized),
where the search space S is the set of all possible solutions.
An important and classical aspect of EAs is how robust their performance is
in the presence of noise [15, 8]. This theme has gained increased attention in the
last few years, [16, 29, 9, 3, 5, 4, 1, 27, 34, 33, 20], see [35] for a comprehensive
review. Mostly, noise is modeled by imperfect fitness function evaluations that –
instead of the exact fitness value – return a perturbed value (e.g., by a Gaussian
additive term). This model is very accurate for algorithms which explicitly
use the fitness function. In particular, in the setting of black-box optimization,
∗ An extended abstract of this paper has been presented at Genetic and Evolutionary
Computation Conference (GECCO 2017).
3 Research supported by the Czech Science Foundation (GAČR) project 17-10090Y “Network optimization”.
4 Research supported by the Swiss National Science Foundation (SNSF), project number
200021 165524.
gavento@kam.mff.cuni.cz, {barbara.geissmann, johannes.lengler}@inf.ethz.ch

1

the function f can be accessed (exclusively) by evaluating f (s) for any search
point s ∈ S that the algorithm may choose. However, it may be less useful
for algorithms which do not fall into this category. In particular, a broad class
of EAs are comparison-based, i.e., they do not evaluate f (s), but rather they
only compare which one of two given search points s and s0 is the better one.
For example, if genetic algorithms are used to optimize chess engines, then the
selection process will not rely on fitness values, but rather on comparisons (e.g.,
by tournaments) between different engines.
Another interesting example is sorting by swaps, the topic of this paper: In
order to compare two permutations s and s0 that differ by a single swap, it is
sufficient to consider the two elements that were swapped, and their positions.
While there are global fitness functions that measure the unsortedness of a
permutation (cf. Definition 5 below), the information that comparison-based
EAs consider in each round does not generally suffice to predict how much this
unsortedness will decrease, which makes it inappropriate to model the noise by
a perturbed fitness function. Therefore, we rather assume that the process of
comparing itself is error-prone. More precisely, we assume that every comparison
gives a false output with some probability p < 1/2. This algorithms falls into
the class of noisy comparison-based (1 + 1) EAs, as described by Algorithm 1.
The general approach can be extended to the more general class of (µ + λ)
algorithms, which keep a whole population in the memory rather than a single
search point. However, there are some additional subtleties which we want to
avoid here – for example, which of the µ individuals of the last population the
algorithm actually chooses as output.
There are some problems that make it more complicated to define a theoretical evaluation of comparison-based EAs in the presence of noise. For example,
the standard measure for the runtime of an EA in theoretical studies is the number of fitness evaluations until an optimal solution is hit for the first time. This
is arguably unsuitable for noisy comparison-based algorithms, because even if
they do find an optimum, due to the noisy measurements, the algorithm might
not be able to recognise it as a best-so-far solution. Moreover, in a noisy environment the global optimum may not have a practical advantage over some
other search points. Thus if we expect the algorithm to find the global optimum,
we force it to spend possibly a lot of time on searching through the set of all
solutions, which are practically indistinguishable. An alternative which avoids
the aforementioned problems is the fixed-budget approach, in which we ask for
the best solution that the algorithm obtains within a fixed budget B of function evaluations. However, this approach has the disadvantage that it needs
an additional parameter: the budget B. Instead, we aim for parameter-free
alternatives.
As a solution, we regard the algorithm as a Markov chain over the search
space S [15]. As such, the algorithm converges to some stationary distribution
of states, and the fitness of the output can naturally be defined as the expected
fitness of the stationary distribution. Moreover, there is a well-established notion of mixing time, which is a natural measure for the time after which the
solution does not change further. However, this notion is not necessarily a good
measure for the time until good solutions are found. The mixing time measures
the time until the genotypical distribution of solutions becomes stable, i.e., until
the distribution on S has converged. But if there is, for example, a large plateau
of almost-optimal solutions, then the time to reach this plateau may be signifi2

cantly shorter than the mixing time. Thus we rather measure the runtime of the
algorithm by the minimal time until the expected fitness of the solution is close
to the expected fitness of a solution of the stationary distribution. This issue,
that for algorithms in noisy environments one should not analyze the hitting
time of the optimum, but rather of some neighbourhood, has also been studied
in [10, 25]. In EA jargon, this resembles (though not exactly) convergence of
the phenotypical distribution instead of the genotypical distribution.
As mentioned before, we study the notions discussed above for the sorting
problem, i.e., the individuals are permutations of the set {1, . . . , n}. This problem has been introduced in the seminal paper of Scharnow, Tinnefeld and Wegener [37], and it has been studied in different encodings [14]. Several mutation
operators are discussed in [37], one of which is the swap operator Swap(s, i, j),
which exchanges the elements at positions i and j in s. In this paper we will only
consider Swap operations since they are the only ones for which the algorithm
can decide in constant time whether the operation is advantageous or not (i.e., if
the two elements were in the wrong order before swapping or not). Thus Swap
operations allow naturally to compare parent and offspring without explicitly
accessing the fitness of either search point. For 0 < p < 1/2 and 1 ≤ r ≤ n we
will study the algorithm SwapSortp,r as given by Algorithm 1, which produces
a random offspring by choosing uniformly at random two elements in distance
at most r and swapping them. The comparison between offspring and parent
yields the correct answer with probability 1 − p, and the wrong answer with
probability p. While the extreme cases r = 1 (adjacent swaps) [18, 7] and r = n
(arbitrary swaps) [18, 37] have been studied before in related settings, this is
the first time that general r is considered. However, we will see that both extreme cases have their drawbacks in terms of speed of convergence (for r = 1)
and quality of the final solution (for r = n). A similar trade-off has also been
observed in [18] in a slightly different noise model. Thus we also include general
values of r in our analysis to interpolate between both cases. Note that the parameter r determines the size of the neighborhood of each permutation, which
is Θ(rn) and ranges from Θ(n) for r = 1 to Θ(n2 ) for r = n.
To measure the quality of the solution, we need to assume a ground truth,
i.e., an unknown underlying fitness function. We consider the following options
Algorithm 1: The noisy algorithm SwapSortp,r maintains a permutation
π ∈ Sn of {1, . . . , n}. In each round it chooses two random indices i < j of
distance at most r, and compares πi with πj . The comparison is noisy, so
with probability p it gives the errroneous result. If the algorithm believes
that the elements πi and πj are in correct order, then it does nothing;
otherwise it swaps them.
Initialize: Sample π (0) uniformly at random from Sn .
Optimize: for t = 1, 2, 3, . . . do
Choose i, j uniformly at random with 1 ≤ j − i ≤ r.
(t−1)
(t−1)
if IsOrderedp (πi
, πj
) then
π (t) ← π (t−1) .
else
π (t) ← Swap(π (t−1) , i, j).

3

for a permutation π of the set {1, . . . , n}, see Section 2 for formal definitions.
• D(π) is the total dislocation, i.e., the sum of all distances of elements i
from their positions π(i), also known as Spearman’s footrule [13].
• I(π) is the number of inversions, i.e., the number of pairs (i, j), i < j such
that π(i) > π(j) [37].
• W (π) is the weighted number of inversions, where each inversion (i, j) is
weighted by j − i [18].

1.1

Relations to other areas

The process of sorting by random comparisons and swaps and its variants have
been studied in other contexts as well.
Similar Markov chains are studied as (biased) card shuffling processes with a
focus on the mixing time as a measure of efficiency of the shuffling [7]. In biased
card shuffling, cards are swapped to be in the sorted order with probability 1−p
and anti-sorted otherwise.
The 0-1 sequence sorting considered in Lemma 16 is related to the asymmetric exclusion process, studied in statistical physics to model the dynamics of
continuous particle diffusion in an infinite one-dimensional space [38, 39]. We
can model the process SwapSortp,1 as a canonical ensemble using I as the
energy function1 and temperature 1/ log(1/p − 1). We omit the details in this
paper.
Any particular sequence of comparison operations performed by the SwapSort
process gives rise to a comparator network 2 since the selection of pairs to compare is independent of the actual values. Therefore our results directly translate to random comparator networks generated by appending comparators on
uniformly chosen wires in distance at most r. We omit the straightforward reformulation of the results. Sorting networks with unreliable comparators have
been studied by, e.g., [2, 28].
The results of Giesen et al. [19] imply that for every  > 0, every pre-sorting
algorithm (and therefore also every comparator network) that achieves a permutation π with E(D(π)) = O(n2− ) (or E(I(π)), equivalently) in expectation
requires Ω(n log n) comparisons. This also implies a lower bound of Ω(n log n)
1 Using

W or D as the energy leads to different, less local error probability functions.
not a sorting network since the resulting networks are generally not sorting
every input.
2 Generally

Algorithm 2: The operator IsOrderedp (a, b) checks whether a < b, but
makes an error with probability p.
IsOrderedp (a, b)
With probability p, set error ← True; otherwise set error ← False.
if a < b then
ordered ← True.
else
ordered ← False.
return (ordered ⊕ error).

4

on the number of steps of any random noisy almost-sorting process to stabilize
at E(I(π)) = O(n2− ). Experimentally, it seems this is the case for r = n1− .
However, the experiments suggest that for such r, the runtime is actually closer
to n2 /r = n1+  n log n.
To the best of our knowledge, the results of this paper have not been known
in the above contexts unless explicitly referenced.

1.2

Algorithm

Let Sn be the set of all permutations of {1, . . . , n}, i.e., the set of all bijective
functions π : {1, . . . , n} → {1, . . . , n}. For convention, let π(i) denote the
position of element i in π and let πi be the element at position i. For π ∈ Sn and
1 ≤ i, j ≤ n, i 6= j, we define the operator Swap(π, i, j) to be the permutation
π 0 given by πj0 = πi and πi0 = πj , and πk0 = πk for all other indices i 6= k 6=
j. For a parameter r ∈ {1, . . . , n} and a parameter 0 < p < 1/2, we define
SwapSortp,r to be the (1 + 1) evolutionary algorithm given by Algorithm 1,
where the IsOrderedp -operator is given by Algorithm 2.
We say that a particular swap Swap(π, i, j) is good if πi and πj are correctly
sorted after swapping, i.e., if i < j and πi > πj , or if i > j and πi < πj , before
the swap. Similarly, we say that a swap Swap(π, i, j) is bad if πi and πj are
wrongly sorted after swapping.
Hereafter, we will regard this sorting algorithm as a Markov chain (consider
Section 2.1 for definitions and a short introduction to Markov chains). We use
Sp,r to denote the Markov chain associated with the algorithm SwapSortp,r .
Each iteration in Algorithm 1 corresponds to one transition step of the Markov
chain [32].
We use Sp,r (π) to denote the process Sp,r starting from permutation π, and
t
(π) to denote its probability distribution after t transition steps. If
we use Sp,r
Sp,r (π) is clear from the context, then we use π (t) to denote a random permutation after t steps. Furthermore, we write Sp,r,n to denote the process
∞
starting from a uniformly random n-element permutation, and Sp,r,n
to denote
the unique stationary distribution (which exists and to which Sp,r converges,
since Sp,r is irreducible and aperiodic as discussed in Section 3.1).
Note that the definition of Sp,r as well as I and W (in Remark 6) can be
extended to all n-element sequences (even with repeated elements) since for
comparison-based sorting, the actual multi-set of values does not matter and
does not change in the process. For the number of inversions, the properties
of the Markov chain and the upper bounds on the result quality would also
carry over since we can perturb the values of the identical elements, which only
increases I. We leave the details to the interested reader.

1.3

Our Results

We study the problem of sorting the set {1, . . . , n} and we consider the Markov
chain Sp,r over the state space Sn for the two extreme cases r = 1 (adjacent
swaps only) and r = n (arbitrary swaps), as well as for the general case 1 ≤ r ≤ n
(bounded-range swaps). We now provide an overview of the most important
theorems, the proofs however will follow in Sections 3.2 to 3.4.

5

For a probability distribution q over all permutations in Sn , we use E(I(q))
to denote the expected number of inversions of a random permutation π chosen
with probability q(π), i.e.,
X
E(I(q)) :=
q(π) · I(π) .
π∈Sn

Similarly, we use E(W (q)) and E(D(q)) for the expected weighted number of
inversions and the expected total dislocation, respectively.
1.3.1

Adjacent swaps

We first consider Sp,1 , which only swaps adjacent elements. Our first result
shows that this process has high fitness in the stationary distribution. In particular, even the weighted number of inversions is only of linear order, i.e., on
average each element is contained in at most a constant number of inversions,
and the worst inversion of each element bridges on average only a constant
distance.
Theorem 1 (Adjacent Swaps). Let pmax < 1/3 be constant. Then for any
0 < p < pmax it holds
∞
∞
p · (n − 1) ≤ E(I(Sp,1
)) ≤ E(W (Sp,1
)) ≤ n ·

2p
+ 2−Ω(n) .
(1 − 3p)

∞
Moreover, for a random permutation π from Sp,1
, with high probability3 ,

I(π) ≤ W (π) = O(n log n) ,
and the maximum dislocation is
max |i − π(i)| = O(log n) .

1≤i≤n

Note that for a fixed pmax the bounds on the expectations are asymptotically
tight. For sufficiently small p and large n, the ratio of the upper and lower
bounds is close to 2 for both I and W . This is illustrated in Figure 6 together
∞
with experimental results. Experiments of Section 4.4 suggest that E(I(Sp,1
)) '
∞
f1 (p) · n and E(W (Sp,1 )) ' f2 (p) · n for some (unknown) functions f1 and f2 .
Our next result shows that the good fitness in the stationary distribution
for r = 1 comes at the cost of a large convergence time of Θ(n2 ) for both I and
W . Let
(
)
t
(π)))}
maxπ∈Sn {E(I(Sp,1
I
Tconv () := min t ∈ N :
−1 < ,
∞ ))
E(I(Sp,1
(
)
t
maxπ∈Sn {E(W (Sp,1
(π)))}
W
Tconv () := min t ∈ N :
−1 <
∞ ))
E(W (Sp,1
be the times until Sp,1 has approached the quality of its stationary distribution
up to an error of ε.
3 That

is with probability at least 1 − 1/n.

6

Theorem 2 (Convergence Time). For any constant 0 < p < 1/2 and any constant error ε > 0,
I
Tconv
() = Θ(n2 )

and

W
Tconv
() = Θ(n2 ) .

We also run experiments on the convergence times in Section 4.2. For
p ≤ 0.2, the measured convergence times are between n2 and 2n2 (within 95 %
confidence).
1.3.2

Arbitrary swaps

Now we turn to Sp,n , which may swap any pair of elements. We do not provide
theoretical results on the convergence time in this case but refer to future work,
since the analysis is more complicated as this Markov chain is not reversible.
Experiments of Section 4.2, however, suggest that the convergence time is almost
n times faster than for r = 1, and in particular suggest convergence time to be
bounded by O(n log n). This would also be consistent with the mixing time of a
random card-swapping process shown to be O(n log n) by Diaconis [12, chapter
3D]. However, this increase in speed comes at a high cost, since the quality of
the solution is dramatically worse than for Sp,1 .
Theorem 3 (Arbitrary Swaps). For any 0 < p < 1/2,
Ω(pn2 ) =
and

p(n2 − 1)
∞
∞
≤ E(D(Sp,n
)) ≤ 2 · E(I(Sp,n
)) = O(p1/3 n2 )
6
pn3
∞
Ω(pn3 ) =
≤ E(W (Sp,n
)) = O(p1/2 n3 ) .
648

In particular, if p is a constant
∞
E(D(Sp,n
)) = Θ(n2 ),

∞
E(I(Sp,n
)) = Θ(n2 ),

∞
E(W (Sp,n
)) = Θ(n3 ) .


For a random permutation π ∈ Sn , it holds that E(I(π)) = 21 n2 , E(D(π)) =

1 n+1
n2 −1
(see Lemma 8). Thus, for a fixed p, the al3 , and E(W (π)) = 2
3
gorithm achieves only a multiplicative constant improvement over a random
permutation. Similarly to the case where only adjacent elements are swapped,
∞
experiments of Sp,n in Section 4.4 indicate that E(I(Sp,n
)) ' f3 (p) · n2 and
∞
3
E(W (Sp,n ) ' f4 (p) · n for some (unknown) functions f3 and f4 . In particular,
for p → 1/2, both E(I) and E(W ) smoothly converge to their expected values
for a random permutation.
1.3.3

Bounded-range swaps

Since both the cases r = 1 and r = n have severe drawbacks, we also study the
intermediate range, 1 < r < n. Indeed, experiments suggest a smooth transition
between the above results, namely E(I(π)) = Θ(nr) and E(W (π)) = Θ(nr2 ) for
any fixed p ≤ 0.3 (see for instance Figure 7). Thus is seems that intermediate
values of r allow to find a compromise between high fitness (for smaller r) and
low convergence time (for larger r). Again we do not provide theoretical results
on the convergence time, but we do prove lower bounds on the average fitness
that make the experimental findings.

7

Theorem 4 (Bounded-Range Swaps). For any 0 < p < 1/2 and any r ∈
{1, . . . , n},
E(I(Sp,r )) = Ω(prn),

E(D(Sp,r )) = Ω(prn),

E(W (Sp,r )) = Ω(pr2 n).

It remains an open problem to show that these lower bounds are tight, as
experiments suggest.

1.4

Relation to the Conference Version

An extended abstract of this work has appeared in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2017) [17]. In comparison, the present version gives more background information (Sections 1.1, 2.1,
and 2.2), and it gives relations between the three different fitness functions (Lemmas 11, 12, 13) that have so far been missing in the literature since they have
not been studied concurrently before. We have also extended the experimental
results in Section 4 by Figures on W . Furthermore, all theorems now contain explicit dependencies on p: While p was assumed to be a constant in the GECCO
version, the results in this version also apply to varying p = p(n). In particular
we allow the case p → 0. Finally, we corrected and tightened one upper bound
in Theorem 1 (a special thank for the reviewer who adverted to this issue).

1.5

Outline

The rest of this work is structured as follows. In Section 2 we first provide a
short introduction to Markov chains, afterwards we formally define the three
fitness functions and show some of their properties and relations. Then we turn
to the theoretical analysis of our Markov chain in Section 3 and prove the results
stated above. Finally, we present some experimental results in Section 4.

2
2.1

Notation and Formal Definitions
Preliminary definitions on Markov chains

We introduce some definitions on finite Markov chains, which are used in this
work (see Levin et al. [26] for more details). A finite Markov chain is a process
that operates on a finite state space S and is specified by a transition matrix
P as follows: for any two states s and s0 of S, P (s, s0 ) gives the probability
of going from s to s0 in one step. Consequently, the probability of going from
one state to another state in t steps is given by the tth power of the transition
matrix.
The term P t (s, ·) gives the probability distribution over all states after t
steps, when starting in state s. If a probability distribution q over the states in
S satisfies
q = qP ,
then we say that q is a stationary distribution of the Markov chain.
A Markov chain is irreducible if it can eventually reach every state from
every state, that is for all states s and s0 there exists a t such that P t (s, s0 ) > 0.
Every irreducible chain has a unique stationary distribution (Corollary 1.17
in [26]). Furthermore, if for all states s of an irreducible chain, P (s, s) > 0,
8

the chain is called aperiodic, and every irreducible aperiodic chain eventually
converges to its unique stationary distribution q: For any two states s and s0 ,
limt→∞ P t (s, s0 ) = q(s0 ) (Theorem 4.9 (Convergence Theorem) in [26]).
If there is a probability vector q such that for all s and s0 ,
q(s)P (s, s0 ) = q(s0 )P (s0 , s) ,
we say that q satisfies the detailed balance condition. In this case, q is a stationary distribution of the corresponding Markov chain and we say that the chain
is reversible (Proposition 1.20 in [26]).
An equivalent characterization of reversibility is given by looking at cycles
over the states. A Markov chain is reversible if for a given starting state s,
every sequence of transitions (i.e., steps from one state to another) that returns
to s, thus forms a cycle, has the same probability whether it is followed in one
direction or the other. The Kolmogorov reversibility criterion (see [24], Chapter
1.5, Theorem 1.7) states that a chain is reversible if and only if for any cycle C,
that is a sequence of transitions ((s, s0 ), (s0 , s00 ), . . . , (s000 , s)), it holds
Y
Y
P (s, s0 ) =
P (s0 , s) .
(s,s0 )∈C

(s,s0 )∈C

To measure the similarity of two probability distributions u and v over S,
we compute their total variation distance, i.e.,
1X
|u(s) − v(s)| .
||u − v||T V =
2
s∈S

This distance is used to compute the mixing time of a Markov chain, which
is defined as the smallest time t needed, such that for any starting state s,
|P t (s, ·) − q| is sufficiently small:
Tmix () := min{t ∈ N | max{||P t (s, ·) − q||T V } ≤ } .
s∈S

2.2

Fitness Functions and their Properties

We consider the following three functions, which have been already mentioned
in the introduction, as fitness functions to be minimized: The total dislocation
in a permutation π is the sum of displacement of all elements, where the displacements of an element is the absolute difference between its positions in π
and in the sorted n-element sequence π0 = (1, . . . , n); the number of inversions
is the number of pairs of elements in π that are placed in a different order than
in π0 ; the weighted number of inversions is the sum of all absolute differences in
value of inverse pairs. The formal definitions of the three fitness functions are
as follows:
Definition 5. Let π ∈ Sn be a permutation of the set {1, . . . , n}. The number
of inversions of π is
X
I(π) :=
1.
i<j : π(i)>π(j)

The weighted number of inversions of π is
X
W (π) :=
i<j : π(i)>π(j)

9

j−i .

The total dislocation (or Spearman’s footrule) of π is
X
D(π) :=
|i − π(i)| .
i∈{1,...,n}

Remark 6. For general n-element sequences s (even with duplicates), the number of inversions
and the weighted number
P
P of inversions are equivalently given
by I(s) := i<j : πi >πj 1, and W (s) := i<j : πi >πj πi − πj , respectively.
Note that any of these fitness functions decreases with a successful swap.
Therefore, the function SwapSortp,r can equivalently be defined by first creating a new mutation π 0 from the current permutation π by a random swap of
two indices of distance at most r, then comparing the fitness of π and π 0 , and
returning the fitter with probability 1 − p, and the less fit with probability p.
We used the previous definition to emphasize that IsOrdered can be defined
without reference to any explicit fitness function.
The (non-absolute) dislocations of the single elements permit equivalent ways
to express the weighted number of inversions in any permutation π ∈ Sn :
Lemma 7. For any π ∈ Sn ,
X

W (π) =

i(i − π(i)) =

i∈{1,...,n}

1
2

X

(i − π(i))2 .

i∈{1,...,n}

P
Proof. The first equality has been shown in [18]: In the sum i<j : π(i)>π(j) j − i,
each element i is added si and subtracted li times, where si is the number of
smaller elements on the right of i and li the number of larger elements on its left.
The difference di = si − li is equal to i’s dislocation to the left, i.e., di = i − π(i).
Thus, i · di is exactly the contribution of i to W (s).
The second equality follows immediately by the observation that
X
X
i2 =
(π(i))2 ,
i∈{1,...,n}

i∈{1,...,n}

which implies
X
i∈{1,...,n}

X

(i − π(i))2 =

2i2 − 2iπ(i) .

i∈{1,...,n}

To provide the reader with a feeling for the different fitness functions, the
following lemma provides for each of them a tight upper bound. We also give
the expected value for a random permutation.
Lemma 8. For any π ∈ Sn ,
 


n
n+1
I(π) ≤
,
W (π) ≤
,
2
3
For π chosen uniformly at random from Sn ,
 


1
n
1
n+1
E(I(π)) = ·
,
E(W (π)) = ·
,
2
2
2
3
10


n2
D(π) ≤
.
2


E(D(π)) =

n2 − 1
.
3

Proof. We first show the
 upper bounds. The number of different pairs in a
set of n elementsis n2 . Therefore, the maximum number of inversions in a
permutation is n2 . The total sum of the absolute differences of all pairs in the

Pn−1
set {1, . . . , n} is k=1 (n − k)k = n+1
3 : For every k ∈ {1, . . . , n − 1}, there are
exactly n − k pairs with absolute difference k. The identity is trivial for n = 2
and follows by induction for larger n, i.e.,
n−1
X
k=1

(n−1)−1

(n − k)k =

X

((n − 1) − k)k +

k=1

n−1
X

k=

k=1

    

n
n
n+1
+
=
.
3
2
3
2

The maximum total dislocation of a permutation on n elements is b n2 c (see [30],
Corollary 2.3). These three upper bounds are all tight for the reversed sorted
permutation (n, . . . , 1).
In a random permutation of n elements, the expected number of inversions
is 21 n2 , since any pair of elements is inverse with probability one half. For

the same reason, the expected weighted number of inversions is 12 n+1
3 . The
2
expected total dislocation is n 3−1 (see again [30], Remark 2.7).
We continue with a handful of non-trivial upper and lower bounds that
set the three fitness functions into relation. There are two existing results for
the number of inversions and total dislocation. We use Ex(π) to denote the
minimum number of successive (any pair) swaps needed to sort a permutation
π:
Lemma 9 (Diaconis and Graham 1977 [13]). For any π ∈ Sn ,
I(π) + Ex(π) ≤ D(π) ≤ 2 · I(π) .
Lemma 10 (Hadjicostas and Monico 2015 [22]). For any π ∈ Sn ,
D(π) ≤ I(π) + Ex(π) + bn/2c (bn/2c − 1) .
While the three fitness functions do not determine each other, a small (large)
value in one of them does determine upper (lower) bounds on the other two.
The following three lemmas collect inequalities between the different fitness
functions. Apparently these bounds have not been published before, probably
because previous work used to pick only one function. We first state all three
lemmas, and give the proofs afterwards.
Lemma 11. For any π ∈ Sn ,
I(π) ≤ W (π) ≤

n
· I(π) .
2

Lemma 12. For any π ∈ Sn ,
I(π)2 ≤ 2n · W (π) .
Lemma 13. For any π ∈ Sn ,
1
n−1
· D(π) ≤ W (π) ≤
· D(π) .
2
2
11

of Lemma 11. Since every inversion weighs at least 1, the lower bound is trivial.
It is tight if and only if only elements that differ by one are inverted. There is also
a permutation for which the upper bound is tight, namely π = (n, 1, 2, . . . , n−1).
We now show the upper bound by induction on n with the claim straightforward for n ≤ 2. Assume that
n
W (π [n] )
≤
[n]
2
I(π )
holds for any permutation π [n] ∈ Sn . Let π [n+1] be any permutation in Sn+1
and let k be the position of element (n + 1).
[n+1]
Moving (n + 1) to position n + 1 by shifting the elements between πk+1
[n+1]

and πn+1 each left by one position, results in a permutation π [n] with (n + 1)
appended. We observe the changes in W and I:
∆(W ) := W (π [n+1] ) − W (π [n] ) ,

∆(I) := I(π [n+1] ) − I(π [n] ).

(1)

Performing an adjacent swap of (n + 1) with every element at positions k + 1
to n + 1, decrements the number of inversions in every swap since (n + 1) is the
largest element. Thus,
∆(I) = n + 1 − k.
(2)
To upper bound ∆(W ) we use that (n + 1) is shifted to the right by n + 1 − k
positions and n + 1 − k elements are shifted to the left by one position. By
Lemma 7,
n+1
X [n+1]
∆(W ) = (n + 1 − k)(n + 1) −
πi
.
(3)
i=k+1

Let Σ :=

[n+1]
i=k+1 πi

Pn+1

Σmin

and observe that



  
n+2−k
n+1
k
:=
≤Σ≤
−
=: Σmax ,
2
2
2

(4)

since these elements have a value between 1 and n, and the n + 1 − k smallest
(largest) sum up to Σmin (Σmax ). Note that
Σmin + Σmax = (n + 1)(n + 1 − k).

(5)

Before we continue the proof, we shall show the following claim.
Claim. For any permutation π [n] ∈ Sn and k ≥ 1, it holds for the sum of the
last n + 1 − k elements Σ that
Σ ≥ Σmax − I(π [n] ) .

(6)

Proof. Split the elements between positions k − 1 and k into a left and a right
set, and count for each element on the right its inversions with elements on the
left:
[n]

[n]

Iik := |{j < k | πj > πi }|

∀i ≥ k .

The sum of all Iik is equal to the number
Pnof inversions between the first k − 1
and the last n + 1 − k elements. Thus, i=k Iik ≤ I(π [n] ).
12

Moreover, the sum of all Iik is exactly what we lose in Σ compared to Σmax .
To see this, assume that, w.l.o.g., the elements of the right set are sorted in[n]
creasingly. In this case, πi + Iik = i, for all k ≤ i ≤ n, and consequently
Σ+

n
X
i=1

Iik =

n
X

[n]

(πi + Iik ) =

i=k

n
X

i = Σmax .

i=k

Continuing the Proof of Lemma 11. By the induction hypothesis, W (π (n) ) ≤
n/2 · I(π (n) ). Using Equations (1) and (2) we write:
n
· I(π (n) )
2
n+1
1
=
· I(π (n) ) − · I(π (n) )
2
2
n+1
(n + 1)(n + 1 − k) 1
=
· I(π (n+1) ) −
− · I(π (n) ) .
2
2
2

W (π (n) ) ≤

(7)

Finally, we bound W (π (n+1) ) using Equations (1), (3), (4), (5), (6), and (7):
W (π (n+1) ) = ∆(W ) + W (π (n) )
≤ (n + 1 − k)(n + 1) − Σ
(n + 1)(n + 1 − k) 1
n+1
· I(π (n+1) ) −
− · I(π (n) )
2
2
2
Σmin + Σmax
n+1
1
=
−Σ+
· I(π (n+1) ) − · I(π (n) )
2
2
2
(n)
Σmin + Σ + I(π )
n+1
1
≤
−Σ+
· I(π (n+1) ) − · I(π (n) )
2
2
2
n+1
≤
· I(π (n+1) ) .
2
+

This concludes the proof.
of Lemma 12. Let Ii (π) denote the number
of smaller elements than i among
Pn
I
(π)
= I(π). Similarly, let Wi be
the positions π(i) + 1 to n. Then,
i
i=1
analogue to Ii but for weighted inversions:
X
Wi (π) :=
i − j.
j<i : π(j)>π(i)

Since all elements are unique (by our assumption on the ground set), no two

elements j < i have the same difference to i. Therefore, Wi (π) ≥ Ii (π)+1
,
2
which implies that

n
n
n 
X
X
Ii (π) + 1
1X
Ii (π)2 .
(8)
W (π) =
Wi (π) ≥
≥
2
2
i=1
i=1
i=1
By the relation
and the quadratic mean of n values it
pPnbetween the arithmetic
Pn
2 /n ≥
holds that
I
(π)
I
(π)/n
= I(π)/n , which we can rewrite as
i
i
i=1
i=1
n
X

Ii (π)2 ≥

i=1

13

I(π)2
.
n

(9)

Finally, by Equations (8) and (9) we conclude W (π) ≥

I(π)2
2n .

of Lemma 13. The lower bound is implied by Lemmas 9 and 11, and it is tight
if and only if there are only inversions between elements that differ by one.
For the upper bound, consider the following procedure that sorts π: While
π is not sorted, swap two inverse elements πi > πj with i < j, such that their
difference d = πi − πj is maximum among all inversions. By this maximality,
πj < πk < πi for any i < k < j. Therefore, πk was inverse to both πi and
πj and these inversions are removed by the swap, while no new inversions are
introduced. Let m = j − i − 1 denote the number of these elements and note
that m ≤ d − 1. For each such πk , the two inversions that are removed weighted
(πi − πk ) − (πk − πj ) = (πi − πj ) = d. Also the inversion between πi and πj itself
weighted d. Thus, the decrease of the total weighted inversion4 is d(m + 1). By
the maximality of d, it holds that πj < i and πi > j. Thus the total dislocation
decreases by 2(m + 1) for d(m + 1) decrease in W , or 2 for d independent
of m. We obtain the claim with d ≤ n − 1. The upper bound is tight for
π = (n, 2, . . . , n − 1, 1).

3

Theoretical analysis

3.1

General properties of the Markov chain

We first show that all Markov chains that we consider in this work are irreducible
and aperiodic. This then implies (by Corollary 1.17 and Theorem 4.9 in [26])
that they converge to a unique stationary distribution. Note that we show this
property for general n-element sequences, because in Section 3.2, we consider
Sp,1 also on 0-1 sequences.
Lemma 14. For any n-element sequence s, the Markov chain Sp,r (s) is aperiodic and irreducible.
Proof. The chain Sp,r is aperiodic, since in each transition, the state does not
change with a positive probability: Observe that SwapSortp,r always makes a
swap with probability at most 1 − p, independent whether the swap is bad or
good. Therefore, it is true that in the transition matrix P , P (s, s) ≥ p > 0.
The chain is irreducible, since one can achieve every permutation s0 of the
elements of s by a sequence of adjacent swaps: Every element in s can move
to any position by repeated swaps with its left or right neighbour. Thus, the
elements of s01 , s02 , . . . , s0n in s can iteratively move to their target positions 1 to
n, respectively. Since every element moves by at most O(n) positions, there is
a t ∈ O(n2 ), such that P t (s, s0 ) > 0.
In the rest of this section, we will first analyze the sorting algorithm with adjacent swaps (Section 3.2), then the sorting algorithm where we allow any swaps
(Section 3.3), and finally the algorithm with bounded range swaps (Section 3.4).
4 Observe

that the decrease of the total number of inversions is (1 + 2m).

14

3.2

Sorting with adjacent swaps

Here we theoretically analyze Sp,1 , the sorting algorithm with adjacent swaps,
and its Markov chain Sp,1 . A main tool will be a sorting process of 0-1 sequences,
which is analyzed in Section 3.2.1, and coupled to Sp,1 in Section 3.2.2.
We first show that for any 0 < p < 1/2 and any n > 1, the process Sp,1 (s)
on any sequence s = (s1 , . . . , sn ) is reversible, which implies together with
Lemma 14 that its stationary distribution is unique. In the following lemma,
we view Sp,1 as a process on arbitrary sequences in order to get the same result
also for 0-1 sequences.
Lemma 15. For any 0 < p < 1/2 and any n-element sequence s, the Markov
chain Sp,1 (s) is reversible and has a unique stationary distribution q with
q(s0 ) =

1
·
Z



p
1−p

I(s0 )
,

for any permutation s0 of s, where Z is a normalizing constant for the distribution (only depending on p and the composition of s).
Proof. Let P be the transition matrix of Sp,1 (s). The chain is reversible if all
states s and s0 satisfy the detailed balance condition: q(s0 ) · P (s0 , s) = q(s) ·
P (s, s0 ). If s and s0 differ by more than one adjacent swap, then P (s0 , s) =
P (s, s0 ) = 0. Otherwise, without loss of generality assume I(s0 ) = I(s) + 1.
Then the probabilities to go from s to s0 and vice versa are P (s, s0 ) = p/(n − 1)
and P (s0 , s) = (1 − p)/(n − 1). These satisfy the detailed balance condition
from above.
By Proposition 1.19 in Levin et al. [26], q is thus a stationary distribution
for the Markov chain Sp,1,n . The uniqueness of q follows from irreducibility and
aperiodicity (Lemma 14).
3.2.1

Sorting 0-1 sequences

Let Bp,n,k = Sp,1 (0k 1n−k ), e.g., the sorting process of k zeroes and n − k ones,
∞
and let Bp,n,k
denote its stationary distribution. The Markov process is irreducible, aperiodic and with a unique stable distribution by Lemmas 14 and 15
(with the preceding remark). Since the stationary distribution is unique, the
starting state choice is just a convenience.
Lemma 16. Let pmax < 1/3 be constant. Then for any 0 < p < pmax , and any
n and 0 < k < n, we have
∞
E(I(Bp,n,k
)) ≤

2p
+ 2−Ω(n) .
(1 − 3p)

Moreover, for some λ(p) depending only on p, any l ≥ 0, and c̄ = 2p/(1 − p),
∞
P[I(Bp,n,k
) > λ(p) + l] < c̄ l .

Proof. For a 0-1 sequence s = (s1 , . . . , sn ), let u = |{si | si < si+1 ∧ 1 ≤ i ≤
n − 1}| and d = |{si | si > si+1 ∧ 1 ≤ i ≤ n − 1}| be the number of up-transitions
and down-transitions of s, respectively. Obviously, d − 1 ≤ u ≤ d + 1.
15

In the state with sequence s, the probability that I(s) increases in one step
up
, since this happens only when an up-transition pair is selected
by 1 is p↑ = n−1
and the elements are sorted as descending. Analogously, the probability I(s)
decreases by 1 is p↓ = d(1−p)
n−1 . Note that I(s) may not change by more than 1
in a single step.
For the sequence of values of I, we can observe that whenever d > 0 and
u > 0 it holds that
up
(d + 1)p
2p
p↑
=
≤
≤
.
p↓
d(1 − p)
d(1 − p)
1−p
The only state with d = 0 is the sorted state with I = 0 and the only state
with u = 0 is the reversed sorted state with I = Imax = k(n − k), i.e., all ones
on the left and all zeros on the right, such that each of the k ones has n − k
inversions. In all other states, the ratio p↑ /p↓ depends only on u and d and is
upper bounded by 2p/(1 − p).
To upper bound E(I), consider the random walk I¯ on 0, . . . , Imax with p̄↑ =
2p/(p+1) and p̄↓ = (1−p)/(p+1), so p̄↑ + p̄↓ = 1. In the stationary distribution
¯ P[I¯ = i] = c̄ i /Z, where c̄ = p̄↑ /p̄↓ = 2p/(1−p) and Z = (1−c̄Imax +1 )/(1−c̄)
of I,
is a normalizing constant. This follows directly by analyzing the ratios P[I¯ =
i]/P[I¯ = i + 1].
By a direct series summation we get
¯ =
E(I)

IX
max

i · c̄ i ·

i=0

1
Z

(1 − c̄)
c̄ · (1 + Imax · c̄Imax +1 − (Imax + 1) · c̄Imax )
·
(1 − c̄)2
(1 − c̄Imax +1 )
c̄
(1 ± O(Imax · c̄Imax ))
=
·
.
(1 − c̄)
(1 − c̄Imax +1 )
=

1
Ω(n)
Using n − 1 ≤ Imax < n2 and 0 < c̄ < 1, as well as (1−c̄Imax
), we
+1 ) ≤ (1 + c̄
conclude
¯ = 2p ± 2−Ω(n) .
E(I)
1 − 3p
Since p↑ /p↓ ≤ p̄↑ /p̄↓ , the random walk I¯ stochastically dominates the se¯ in the stationary
quence of values of I, and in particular, we get E(I) ≤ E(I)
distributions.

For the second part of the lemma, note that
P[I¯ > l] ≤

∞
X

c̄i /Z = c̄ l+1 /((1 − c̄)Z) = c̄ l c̄ 1−logc̄ ((1−c̄)Z) .

i=l+1

With λ(p) = logc̄ ((1 − c̄)Z) we get P[I¯ > λ(p) + l] < c̄l , and the bound for I
¯
follows from being stochastically dominated by I.
3.2.2

Sorting permutations (Proof of Theorem 1)

We recall Theorem 1:
16

i

i+1

π=

3

2

4

5

1

W = 11

T1 (π) =

1

1

1

1

0

I=4

T2 (π) =

1

0

1

1

0

I=4

T3 (π) =

0

0

1

1

0

I=2

T4 (π) =

0

0

0

1

0

I=1

Figure 1: A single step of the coupled processes.
Theorem 1 (Adjacent Swaps). Let pmax < 1/3 be constant. Then for any
0 < p < pmax it holds
∞
∞
p · (n − 1) ≤ E(I(Sp,1
)) ≤ E(W (Sp,1
)) ≤ n ·

2p
+ 2−Ω(n) .
(1 − 3p)

∞
Moreover, for a random permutation π from Sp,1
, with high probability5 ,

I(π) ≤ W (π) = O(n log n) ,
and the maximum dislocation is
max |i − π(i)| = O(log n) .

1≤i≤n

Proof. Let π0 = (1, 2, . . . , n) be the sorted n-element sequence. By Lemma 15,
∞
∞
the stationary distribution Sp,1,n
is the same as Sp,1
(π0 ), so we analyze the
n
latter. For a permutation π, let Tk (π) ∈ {0, 1} be the k-th threshold 0-1
sequence, where Tk (π)i = 1 if πi > k and Tk (π)i = 0 if πi ≤ k. So Tk (π)
contains exactly k zeroes and n − k ones.
We decouple the process Sp,1 (π0 ) into n − 1 processes (Bp,n,1 , . . . , Bp,n,n−1 ):
The state π of the process Sp,1 (π0 ) corresponds to the states (T1 (π), . . . , Tn−1 (π))
of the 0-1 process Bp,n,k . The coupled processes share the following event space:
In every step we randomly choose two adjacent positions (i, i+1) to be compared
and with probability p choose to order their values in the descending (wrong)
order, or ascending (right) order otherwise. The same event then decides the
change in all the coupled processes. It is straightforward to see that starting
from corresponding states of Sp,1 and (Bp,n,1 , . . . Bp,n,n−1 ), the resulting states
after one event are again corresponding. See Figure 1 for an illustration.
Now observe that an inversion of weight w in a permutation π is present
in exactly w of the coupled binary strings: Assume that πi > πj and i < j,
then Tk (π)i = 1 and Tk (π)j = 0 for every k ∈ {πj + 1, . . . , πi }. Thus, for any
Pn−1
permutation π, we have W (π) = k=1 I(Tk (π)) by reordering the summation:
W (π) =

X
i<j :
πi >πj

5 That

πi − πj =

n−1
X

X

k=1 i<j :
πi >k
πj ≤k

is with probability at least 1 − 1/n.

17

1=

n−1
X
k=1

I(Tk (π)) .

(10)

∞
In the stationary distribution of the coupled processes, we have E(W (Sp,1,n
)) =
Pn−1
∞
k=1 E(I(Bp,1,k )). By Lemmas 11 and 16, we conclude that
∞
∞
E(I(Sp,1,n
)) ≤ E(W (Sp,1,n
)) ≤ n ·

2p
+ 2−Ω(n) ,
(1 − 3p)

which proves the upper bound of the first part of the theorem.
∞
We show the lower bound on E(I(Sp,1,n
)) to hold after any number of steps:
Consider any finite length realization of the random process starting from a
random permutation π0 with the last permutation being π. Divide the n − 1
pairs of adjacent positions into three groups: A is the set of pairs that have never
had a swap, B is the set of pairs whose last swap was bad, and C is the set of
pairs whose last swap was good. It is easy to see that E(|C|) ≤ (1 − p)(n − 1)
and so E(|A| + |B|) ≥ p(n − 1). In π we find one inverted pair for each B: The
pair that was last swapped in B has to be also inverted in π. For each position
in A, the expected number of inversions of π0 between the elements left of A and
right of A is at least 1 whenever n ≥ 3, and all these inversions are also present
in π. The claim follows from linearity of expectation and the observations that
all the inverted pairs counted for A and B are distinct.
∞
To see the upper bound on W (Sp,1,n
) that holds with high probability, we
use the tail bounds of Lemma 16: For any k and β > 0,
∞
P[I(Bp,n,k
) > λ(p) + β log n] < c̄ β log n .

For β big enough we get c̄ β log n = O(n−3 ) and by a union bound over n − 1
∞
events, I(Bp,n,k
) > λ(p) + β log n for k = 1, . . . , n − 1. Together with Equation (10), this implies the bound on W . The bound for I follows from Lemma 11.
Finally, we show the bound on the maximum dislocation: Consider any
permutation π, any element 1 ≤ k ≤ n, and let j = π(k). The dislocation of k
is thus |k − j|. If j < k, then Tk (π)j = 1 and necessarily I(Tk (π)) ≥ k − j. By
Lemma 16, P[k − j > β log n] < n−3 in the stationary distribution for some β
only depending on p. A symmetric argument shows that P[j−k > β log n] < n−3
for j > k. By union bound of the events “element k has dislocation at least
β log n” for all 1 ≤ k ≤ n, we obtain the maximum dislocation claim.
3.2.3

Convergence speed (Proof of Theorem 2)

Recall Theorem 2:
Theorem 2 (Convergence Time). For any constant 0 < p < 1/2 and any constant error ε > 0,
I
Tconv
() = Θ(n2 )

and

W
Tconv
() = Θ(n2 ) .

Proof. Benjamini et al. [7] show that for any constants p < 1/2 and ε > 0,
the mixing time of the Markov chain Sp,1,n is Tmix (ε) = O(n2 ). After mixing,
the relative errors of probabilities of the resulting permutations compared to
the stationary distribution are below , and so are the relative errors for the
∞
distributions of the marginals I and W . This gives us (1 − )E(I(Sp,1,n
)) <
(t)
∞
E(I(x )) < (1 + )E(I(Sp,1,n )) for any t ≥ Tmix (), and similarly for W .
On the other hand, every swap of adjacent elements can reduce the number
of inversions by at most one. So in expectation, Ω(n2 ) swaps are needed to go
18

from a random permutation (with Θ(n2 ) expected inversions, see Lemma 8) to a
permutation with O(n) inversions. By Theorem 1, a permutation in the stationary distribution has E(I) = O(n) and E(W ) = O(n), and since by Lemma 11
we have W (π) ≥ I(π), the lower bounds follow.

3.3

Sorting with any swaps

We now analyze sorting with arbitrary swaps, i.e., we consider the Markov chain
Sp,n . Observe that the Markov chain for any such process that allows nonadjacent swaps is not reversible by the Kolmogorov reversibility criterion [24].
Lemma 17. The Markov chain Sp,n over the state space Sn with n > 2 is not
reversible.
Proof. Let π = (1, 2, 3, . . . ) be the sorted permutation, π 0 = (2, 1, 3, . . . ) be the
permutation obtained from s by the swap of positions 1 and 2, π 00 = (2, 3, 1, . . . )
the permutation obtained from s0 by the swap of positions 2 and 3, and π 000 =
(3, 2, 1, . . . ) the permutation obtained from π 00 by the swap of positions 1 and 2
again. Observe that one can also obtain π 000 from s by the swap of positions 1 and
3. Consider now the cycle of transitions C = ((π, π 0 ), (π 0 , π 00 ), (π 00 , π 000 ), (π 000 , π))
as in Section 2.1:
Y
Y
P (i, j) = p3 (1 − p)
and
P (j, i) = (1 − p)3 p ,
(i,j)∈C

(i,j)∈C

which implies by the Kolmogorov reversibility criterion (recalled in Section 2.1)
that the chain is not reversible.
Finally, we prove Theorem 3:
Theorem 3 (Arbitrary Swaps). For any 0 < p < 1/2,
Ω(pn2 ) =
and

p(n2 − 1)
∞
∞
≤ E(D(Sp,n
)) ≤ 2 · E(I(Sp,n
)) = O(p1/3 n2 )
6
pn3
∞
Ω(pn3 ) =
≤ E(W (Sp,n
)) = O(p1/2 n3 ) .
648

In particular, if p is a constant
∞
E(D(Sp,n
)) = Θ(n2 ),

∞
E(I(Sp,n
)) = Θ(n2 ),

∞
E(W (Sp,n
)) = Θ(n3 ) .

Proof. For the lower bounds, consider the following equivalent way to describe
one step in Sp,n : With probability (1 − 2p), arrange the two randomly chosen
elements correctly, and with probability 2p, arrange them randomly (swap or
do not swap them, each with probability p).
Let permutation π be some state after a sufficiently large number of steps of
Sp,n,n . In particular, we assume that every element has been compared at least
once. Let R+ be the set of all elements in π whose last step during the process
was a random swap. Let R be a subset of R+ as follows. If the last step for two
elements in R+ was the same random swap, we let only one of them be in R
and decide which one at random. Otherwise, flip a fair coin to decide whether
to include an element in R. Clearly, for each element, the probability to be in
R is p2 , (p to be in R+ and 12 to be in R if being in R+ ), and E(|R|) = p2 n.
19

By construction of R, each element of R got placed to a uniformly random
position in π. Thus, the expected dislocation of an element in R is


n  
X
n+1
n
1 1
1
i
2
= −
· ·2·
,
= 2·
3
n n
n
3
3n
2
i=1
where the identity
follows
by [21] (Chapter 5.1, Equation 5.10, i.e.,
 sumn+1

Pn of the
i
for m, n ≥ 0 :
i=0 m = m+1 ). Therefore, by linearity of expectation, the
expected total dislocation is at least


1
p(n2 − 1)
n
∞
−
=
.
E(D(Sp,n,n
)) ≥ E(|R|)
3
3n
6
2

∞
)) ≥ p(n12−1) .
By Lemma 9, it holds that I ≥ 21 D, thus E(I(Sp,n,n
The order in which the elements of R appear in π is random. Moreover, the
ranks of the elements in R are uniformly distributed between 1 and n, as are
their positions in which they appear in π. Consider the first 13 n positions in π:
The expected number of elements from R that are larger than 23 n and appear
in one of these positions is 91 |R|. By the pigeon hole principle, the number of
elements that are smaller than 12 n and appear in the middle or last third of π
is at least 16 n. All elements of this set are inverse to all elements in the first set
1
∞
and differ by at least 61 n. Therefore, E(W (Sp,n,n
)) ≥ 61 n · 19 |R| · 16 n ≥ 648
pn3 .

For the upper bounds we will use that for any permutation π ∈ Sn ,
X
W (π) =
(j − i)

(11)

i<j : π(i)>π(j)

X

=6

(π(i) − π(j)) .

(12)

i<j : π(i)>π(j)

Furthermore, we consider ∆+ (π) and ∆− (π) as the absolute expected increase
and absolute expected decrease of W (π) by the next Swap, respectively:
∆+ (π) :=

p

n
2

∆− (π) :=

X

(j − i)(π(j) − π(i)) ,

i<j
π(i)<π(j)

1−p

n
2

X

(j − i)(π(i) − π(j)) .

i<j
π(i)>π(j)

To see why these formulas hold, observe that the swap of two elements i and
j also removes or adds inversions between i or j and elements k with π(k)
between π(i) and π(j), while all other inversions remain unchanged. For the
latter elements, the weights of their inversions change by exactly j −i, and there
are exactly |π(i) − π(j)| − 1 such elements.
We now analyse ∆+ (π) and ∆− (π) in the stationary distribution of the
process. In the stationary distribution the expected change in W (π) is 0 =
6 By

P
Lemma 7, W (π) = i∈{1,...,n} i(i − π(i)). Furthermore, since π is a permutation of
P
P
the numbers {1, . . . , n}, i∈{1,...,n} i2 = i∈{1,...,n} π(i)2 .

20

∆+ (π) − ∆− (π). There is an easy upper bound on ∆+ (π) ≤ O(pn2 ) since every
summand is in O(n2 ). We will now show a lower bound for ∆− (π).
Observe that since every summand in Equation (11) is smaller than n, there
must be at least Wn(π) summands, i.e., inversions. Also observe that the number
of pairs i < j such that j − i = x, is at most n, for any x ≥ 1. Therefore,
Equation (11) contains at most n summands of the same value. Now assume we
(π)
summands and let R be the set of inverse pairs
do not count the smallest W2n
(i, j) that correspond to the remaining summands. By this greedy argument,
the value of every remaining summand is at least W2n(π)
2 . Moreover, both the
sum in Equation (11) and the sum in Equation (12) are at least W 2(π) , since we
(π)
ignore at most a total value of W2n
· n. Therefore, we get
∆− (π) ≥

1−p X

(j − i)(π(i) − π(j))
n
2

≥

(i,j)∈R

1 − p W (π) X
 ·
(π(i) − π(j))
n
2n2
2
(i,j)∈R

1 − p W (π) W (π)
≥ n ·
·
2n2
2
2


2
W (π)
=Ω
.
n4
Notice that we can ignore the factor 1 − p, since by the assumption of the
theorem, the factor is larger than 21 and smaller than 1.
By Jensen’s inequality and linearity of expectation we get that
!!
!
∞
∞
W (Sp,n,n
)2
E(W (Sp,n,n
))2
−
∞
E(∆ (Sp,n,n )) ≥ Ω E
≥Ω
.
n4
n4
If we combine this lower bound with the upper bound for ∆+ (π) we can
conclude
!
∞
))2
E(W (Sp,n,n
∞
∞
Ω
≤ ∆− (Sp,n,n
) = ∆+ (Sp,n,n
) ≤ O(pn2 ) ,
n4
√
∞
which implies that E(W (Sp,n,n
)) ≤ O( p n3 ).
We proceed in a similar way to derive the upper bound for D(π) and I(π).
I(π)
This time we ignore the I(π)
3 smallest summands in Equation (11) and the 3
smallest summands in Equation (12). By pigeon hole principle, we remain with
2
at least I(π)
summands for ∆− (π) that each have a value of at least I(π)
3
9n2 .
Therefore,


I(π)3
−
∆ (π) ≥ Ω
.
n4
For ∆+ (π) we get the analogue upper bound of O(pn2 ). Finally, for a stationary
state,
!
∞
E(I(Sp,n,n
))3
∞
∞
Ω
≤ ∆− (Sp,n,n
) = ∆+ (Sp,n,n
) ≤ O(pn2 ) ,
n4

21

∞
∞
which implies that E(I(Sp,n,n
)) ≤ O(p1/3 n2 ). The upper bound for D(Sp,n,n
)
follows by Lemma 9.

3.4

Sorting with bounded-range swaps

Finally, we turn to the general process, where we allow swaps between elements
that lie at most r positions apart, i.e., we consider the Markov chain of Sp,r .
Observe that this chain is not reversible, since for r ≥ 2 the same example as in
the proof of non-reversibility of Sp,n (see Lemma 17) applies.
Recall Theorem 4:
Theorem 4 (Bounded-Range Swaps). For any 0 < p < 1/2 and any r ∈
{1, . . . , n},
E(I(Sp,r )) = Ω(prn),

E(D(Sp,r )) = Ω(prn),

E(W (Sp,r )) = Ω(pr2 n).

Proof. The proof is similar to the one of Theorem 3: We consider again the
equivalent process description and the sets R+ (the set of all elements whose
last step was a random swap) and R (the subset of R+ that includes each
element with probability 12 ), with E(|R|) = pn
2 .
For each element in R, its new expected dislocation will be larger than Ω(r),
since the element is placed to a random position inside a radius r compared to
its old position. Therefore, E(D(π)) ≥ |R| · Ω(r) = Ω(prn), and by [13], also
E(I(π)) ≥ Ω(prn).
For the weighted number of inversions, we observe the following: If an element i has dislocation di , then it is inverse to at least di pairwise different
larger or smaller elements (no such element can have the same difference to
i), and its contribution to W is at least 12 di2+1 , where the factor 12 is to

prevent double counting. The expected value of di2+1 is in Ω(r2 ). Thus,
E(W (π)) ≥ |R| · Ω(r2 ) = Ω(pr2 n).

4

Experimental results

We complement the theoretical analysis of Section 3 with experimental observations.

4.1

Methodology

The experimental results were obtained by simulating the process for a given
number of steps or until the fitness function converged (for the convergence criterion see Section 4.2). The simulation is implemented in a combination of C++
and Python, the sources are freely available on GitHub7 . For reproducibility,
the simulation uses a pseudo-random generator with a deterministic seed.
Every plot is based on 300 independent runs. We generally use n around
512, as the experimental results are consistent already for n ≥ 128. All the plots
include 95 % confidence interval error bars even where these are too small to be
visible.
To illustrate the evolution of the solution quality over time, see Figure 2.
7 https://github.com/gavento/swap-sorting-experiments

22

5000

200000

r

r
1
2
16
48
128

4000

I

W

3000

1
2
16
48
128

150000

100000

2000
50000
1000

0

0
0

5000

10000

15000

20000

25000

0

5000

10000

T

15000

20000

25000

T

Figure 2: Illustration of development and stabilization of I (left) and W (right)
over time for different values of r (swap distance) with n = 512 and p = 0.1.
Mean and 95 % confidence intervals over 300 runs.

4.2

Convergence time criterion

In all the experiments, we use the convergence of I(π (t) ) as the main stopping
criterion8 . Based on experiments, we assume the sequence I(π (t) ) for t = 0, 1, . . .
is a monotonically decreasing function with an additive noise term. We define
the convergence time Tconv as the smallest time t when for a random starting
permutation π ∈ Sn ,
∞
E(I(π (t) )) ≤ (1 + )E(I(Sp,r,n
)) .

For an overview and discussion on various stopping criteria, see [36].
To estimate E(I(π (t) )), we average over a sliding window starting at time t.
To choose an appropriate size of the window proportional to the convergence
time, we estimate the convergence time as
n2
,
r(1 − 2p)
Pr
Pr
where r̄ is the average swap length, e.g., r = ( i=1 i(n − i))/( i=1 (n − i)). The
experiments show that this estimate is within 0.2 to 2.3 multiplicative error of
the measured mean Tconv on our data. Note that the asymptotic behavior may
be different and we need only a rough estimate.
We choose  = 0.05 and window size w = d0.05Test e = Ω(n). We also set a
sampling rate s = dTest /1000e to speed up the computations.
In step t, such that t is divisible by s and t > 3w, we compute the mean I
of windows starting at t and 3/2 t:
Test =

I(π (t) ) =

t+w−1
1 X
I(π (i) )
w i=t

and I(π (3/2 t) ) =

2
t

2t
X

I(π (i) ) .

i=3/2 t+1

If I(π (t) ) ≤ (1 + )I(π (3/2 t) ), then we estimate Tconv = t.
∞
If t ≥ 2/3 · Tconv , then I(π (3/2 t) ) is an estimate for E(I(Sp,r,n
)). On the other
2
3
hand if t < /3 · Tconv , then t and /2 t are both in the not-converged phase.
8 Experiments show that the convergence behavior of W (π) is very similar and the convergence would differ by less than 5%.

23

Therefore, only a very small average descent of I between the windows would
imply to a wrong estimate.

4.3

Convergence time results

See Figure 3 for the plots of mean Tconv for the extreme cases r = 1 and r = n,
and Figure 4 for a dependency on r.
The experimental results indicate that for a fixed p and r = 1, Tconv = Θ(n2 )
(in accordance with Theorem 2). The results for r = n are less conclusive but
might suggest Tconv ∼ n log n.
Note that for r close to n, the time measurements might be less accurate
due to large fitness changes and the fitness of the stationary distribution being relatively close to that of a random permutation (see Figure 6). However,
any imprecision of convergence time measurement should have no effect on the
converged fitness measurements.

4.4

Converged state quality

We estimate the qualitative properties I and W of the stationary distribution
as the distribution of the values in the range [3/2 · Tconv , 2 · Tconv ] over 300
independent process runs. In all the data, note that the 95 % confidence error
bars are very small and generally not visible.
∞
For values of p ≤ 0.3 and n ≤ 1024, we observe that estimates I(Sp,1,n
)'
∞
∞
∞
) ' f4 (p) · n3
) ' f3 (p) · n2 , and W (Sp,n,n
f1 (p) · n, W (Sp,1,n
) ' f2 (p) · n, I(Sp,n,n
(for some fixed unspecified functions f1 , . . . , f4 ) are surprisingly accurate. See
Figure 5.
To estimate the dependency on p (e.g., the functions f1 , . . . f4 ), see Figure 6.
Finally, see Figure 7 for the experimental dependency of I and W on r. This
trade-off corresponds to the lower bounds of Theorem 4. Note the non-linearity
at r ≥ 128 is likely to be caused by the average swap-distance r̄ being lower
than r/2 (while r̄ ' r/2 when r  n).

5

Conclusion

We have studied sorting by random swaps with a noisy comparison operator.
We considered swaps of elements in distance at most r, and we found a tradeoff between fast convergence (for large r) and high quality of the solution (for
small r). As most of our theoretical results are for the extreme cases r = 1 and
r = n, a natural next step is to verify theoretically the experimental results for
arbitrary r, in particular, to prove upper bounds that match the lower bounds
in Theorem 4, and to compute the convergence time for general r. On the other
hand, one can regard the limiting case p = p(n) → 0; in this regime there is still
a gap (p vs. p1/3 and p vs. p1/2 ) in Theorem 3.
Since all parameter choices have strengths and weaknesses, an important
question is whether an adaptive algorithm that decreases r over time (similar to
Simulated Annealing) can be strictly superior to any fixed-parameter choice: In
particular, can such an algorithm achieve a linear expected (weighted) number
of inversions in the stationary distribution with a sub-quadratic convergence
time? We leave this question open for future research.

24

2.0
1.9
1.8

Tconv /n2

1.7

p

1.6

0.05
0.1
0.2

1.5
1.4
1.3
1.2
1.1
32

64

128

256

512

1024

256

512

1024

n
10

p

9

0.05
0.1
0.2

8

Tconv /n

7
6
5
4
3
2
1
32

64

128

n

Figure 3: Top: Tconv normalized by n2 for r = 1. Bottom: Tconv normalized by
n for r = n. Both: mean and 95 % confidence intervals over 300 runs for each
choice of n and p.

25

220

p

219
2

0.05
0.1
0.2
0.3

18

217

Tconv

216
215
214
213
212
211
210
29
1

2

4

8

16

32

64

128

256

512

r

Figure 4: Tconv for n = 512 and various p and r (mean and 95 % confidence
intervals over 300 runs).

0.20

I/n2 , W/n3 (dashed)

I/n, W/n (dashed)

0.6
0.5
0.4
0.3
0.2
0.1
0.0

0.15
0.10
0.05
0.00

32

64

128

256

512 1024

32

64

128

256

512 1024

n

n

p
0.05

0.1

0.2

Figure 5: Stability of converged I/n and W/n with increasing n for various p.
Left: I/n and W/n for r = 1. Right: I/n2 and W/n3 for r = n. In both:
Converged phase means and 95 % confidence intervals (too small to see) over
300 runs.

26

n

1.0

I/n, W/n (dashed)

64
512
0.8

0.6

0.4

0.2

0.0
0.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16

0.18

0.2

p
0.25

I/n2 , W/n3 (dashed)

0.20

0.15

0.10

n

0.05

64
512
0.00
0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

p

Figure 6:
Top: Converged I/n (solid) and W/n (dashed) for r = 1 and
various n and p. Note that n = 64 and n = 512 overlap. The dotted lines
are the upper and lower bounds on both E(I/n) and E(W/n) from Theorem 1.
Bottom: Converged I/n2 (solid) and W/n3 (dashed) for r = n and various n
and p. The horizontal lines indicate the expectation of a random permutation.
Both: Converged phase mean and 95 % confidence intervals over 300 runs.

27

216
215
214
213
212

I

211
210
29

p

28
2

0.05
0.1
0.2
0.3

7

26
25
24
1

2

4

8

16

32

64

128

256

512

r
223
221
219
217

W

215
213
211

p

29

0.05
0.1
0.2
0.3

27
25
23
1

2

4

8

16

32

64

128

256

512

r

Figure 7: Dependence of the converged I (top) and W (bottom) on r for n = 512
with various p (converged phase mean and 95 % confidence intervals over 300
runs). The dashed line is the direction of the lower-bound from Theorem 4
(ignoring a multiplicative factor depending on p).

28

References
[1] Y. Akimoto, S. A. Morales, and O. Teytaud. Analysis of runtime of optimization algorithms for noisy functions over discrete codomains. Theoretical Computer Science, 605:42–50, 2015.
[2] S. Assaf and E. Upfal. Fault tolerant sorting networks. SIAM Journal on
Discrete Mathematics, 4(4):472–480, 1991.
[3] S. Astete-Morales, M. Cauwet, J. Liu, and O. Teytaud. Simple and cumulative regret for continuous noisy optimization. Theoretical Computer
Science, 617:12–27, 2016.
[4] S. Astete-Morales, M. Cauwet, and O. Teytaud. Evolution strategies with
additive noise: A convergence rate lower bound. In J. He, T. Jansen,
G. Ochoa, and C. Zarges, editors, Proceedings of the 2015 ACM Conference
on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom,
January 17 - 20, 2015, pages 76–84. ACM, 2015.
[5] S. Astete-Morales, M. Cauwet, and O. Teytaud. Analysis of different types
of regret in continuous noisy optimization. In T. Friedrich, F. Neumann,
and A. M. Sutton, editors, Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Denver, CO, USA, July 20 - 24, 2016,
pages 205–212. ACM, 2016.
[6] A. Auger and B. Doerr. Theory of randomized search heuristics: Foundations and recent developments, volume 1 of Series On Theoretical Computer
Science. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 2011.
[7] I. Benjamini, N. Berger, C. Hoffman, and E. Mossel. Mixing times of the
biased card shuffling and the asymmetric exclusion process. Transactions
of the American Mathematical Society, 357(8):3013–3029, 2005.
[8] H.-G. Beyer. Evolutionary algorithms in noisy environments: Theoretical
issues and guidelines for practice. Computer methods in applied mechanics
and engineering, 186(2):239–267, 2000.
[9] M. Cauwet, J. Liu, B. Rozière, and O. Teytaud. Algorithm portfolios
for noisy optimization. Annals of Mathematics and Artificial Intelligence,
76(1-2):143–172, 2016.
[10] D. Dang, T. Jansen, and P. K. Lehre. Populations can be essential in
tracking dynamic optima. Algorithmica, 78(2):660–680, 2017.
[11] D. Dasgupta and Z. Michalewicz. Evolutionary algorithms in engineering applications. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1st
edition, 1997.
[12] P. Diaconis. Group Representations in Probability and Statistics, volume 11.
Institute of Mathematical Statistics, 1988.
[13] P. Diaconis and R. L. Graham. Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological),
39(2):262–268, 1977.
29

[14] B. Doerr and E. Happ. Directed trees: A powerful representation for sorting
and ordering problems. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2008, June 1-6, 2008, Hong Kong, China, pages
3606–3613. IEEE, 2008.
[15] S. Droste. Analysis of the (1+1) EA for a noisy OneMax. In K. Deb,
R. Poli, W. Banzhaf, H. Beyer, E. K. Burke, P. J. Darwen, D. Dasgupta,
D. Floreano, J. A. Foster, M. Harman, O. Holland, P. L. Lanzi, L. Spector,
A. Tettamanzi, D. Thierens, and A. M. Tyrrell, editors, Genetic and Evolutionary Computation - GECCO 2004, Genetic and Evolutionary Computation Conference, Seattle, WA, USA, June 26-30, 2004, Proceedings, Part
I, volume 3102 of Lecture Notes in Computer Science, pages 1088–1099.
Springer, 2004.
[16] T. Friedrich, T. Kötzing, M. S. Krejca, and A. M. Sutton. The compact
genetic algorithm is efficient under extreme gaussian noise. IEEE Transactions on Evolutionary Computation, 21(3):477–490, 2017.
[17] T. Gavenciak, B. Geissmann, and J. Lengler. Sorting by swaps with noisy
comparisons. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, July 15-19, 2017, pages
1375–1382, 2017.
[18] B. Geissmann and P. Penna. Sort well with energy-constrained comparisons. ArXiv e-prints, 2016.
[19] J. Giesen, E. Schuberth, and M. Stojaković. Approximate sorting. Fundamenta Informaticae, 90(1-2):67–72, 2009.
[20] C. Gießen and T. Kötzing. Robustness of populations in stochastic environments. Algorithmica, 75(3):462–489, 2016.
[21] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics: A
Foundation for Computer Science. Addison-Wesley Professional, Reading,
MA, USA, 2nd edition, 1994.
[22] P. Hadjicostas and C. Monico. A new inequality related to the DiaconisGraham inequalities and a new characterisation of the dihedral group. Australasian Journal of Combinatorics, 63(2):226–245, 2015.
[23] T. Jansen. Analyzing Evolutionary Algorithms - The Computer Science
Perspective. Natural Computing Series. Springer Science & Business Media,
2013.
[24] F. Kelly. Reversibility and stochastic networks. Wiley series in probability
and mathematical statistics: Tracts on probability and statistics. J. Wiley,
1979.
[25] T. Kötzing, A. Lissovoi, and C. Witt. (1+1) EA on generalized dynamic
OneMax. In Proceedings of the 2015 ACM Conference on Foundations of
Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17 - 20,
2015, pages 40–51, 2015.

30

[26] D. Levin and Y. Peres. Markov chains and mixing times: Second Edition.
MBK. American Mathematical Society, 2017.
[27] J. Liu, D. L. St-Pierre, and O. Teytaud. A mathematically derived number
of resamplings for noisy optimization. In Proceedings of the Companion
Publication of the 2014 Annual Conference on Genetic and Evolutionary
Computation, GECCO Comp ’14, pages 61–62, New York, NY, USA, 2014.
ACM.
[28] Y. Ma. Fault-tolerant sorting networks. PhD thesis, Massachusetts Institute
of Technology, 1994.
[29] J. Merelo, Z. Chelly, A. Mora, A. Fernández-Ares, A. I. Esparcia-Alcázar,
C. Cotta, P. de las Cuevas, and N. Rico. A statistical approach to dealing
with noisy fitness in evolutionary algorithms. In Computational Intelligence: International Joint Conference, IJCCI 2014 Rome, Italy, October
22-24, 2014 Revised Selected Papers, pages 79–95. Springer International
Publishing, 2016.
[30] L. H. Mitchell. Maximal total absolute displacement of a permutation.
Discrete Mathematics, 274(1-3):319–321, 2004.
[31] F. Neumann and C. Witt. Bioinspired computation in combinatorial optimization: algorithms and their computational complexity. Springer-Verlag
New York, Inc., New York, NY, USA, 1st edition, 2010.
[32] A. E. Nix and M. D. Vose. Modeling genetic algorithms with markov chains.
Annals of Mathematics and Artificial Intelligence, 5(1):77–88, 1992.
[33] C. Qian, Y. Yu, Y. Jin, and Z. Zhou. On the effectiveness of sampling for
evolutionary optimization in noisy environments. 8672:302–311, 2014.
[34] C. Qian, Y. Yu, and Z.-H. Zhou. Analyzing evolutionary optimization in
noisy environments. Evolutionary computation, 2015.
[35] P. Rakshit, A. Konar, and S. Das. Noisy evolutionary optimization algorithms - A comprehensive survey. Swarm and Evolutionary Computation,
33:18–45, 2017.
[36] M. D. Safe, J. A. Carballido, I. Ponzoni, and N. B. Brignole. On stopping criteria for genetic algorithms. In Advances in Artificial Intelligence SBIA 2004, 17th Brazilian Symposium on Artificial Intelligence, São Luis,
Maranhão, Brazil, September 29 - October 1, 2004, Proceedings, pages 405–
413, 2004.
[37] J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical
Modelling and Algorithms, 3(4):349–366, 2004.
[38] F. Spitzer. Interaction of markov processes. Advances in Mathematics,
5(2):246 – 290, 1970.
[39] C. A. Tracy and H. Widom. Asymptotics in asep with step initial condition.
Communications in Mathematical Physics, 290(1):129–154, 2009.

31

