Figure 1

Comparison of two simple algorithms for sorting: on the long run the algorithm doing only adjacent comparisons gives a better result compared to the one doing all comparisons. The weighted number of inversions ($y$ axis) is a measure of the “disorder” of the current sequence. Both algorithms operate under the same conditions (same input sequence and identical error probabilities of comparisons). In particular, the input sequence is $\left(50,49,\cdots ,1\right)$ which has the highest weighted number of inversions, while the sorted sequence is $(1,2,...50)$ with zero weighted number of inversions. The probability of errors is controlled by a parameter $\lambda$ (in this experiment $\lambda =e^{\frac{1}{15}}$, though the same behavior occurs for essentially any fixed $\lambda$ as shown in Sec. 6).

Figure 2

The three chains for sorting three elements $\mathrm{abc}$; A transition with label $w$ has probability $\frac{{\lambda }^w}{{\lambda }^w+{\lambda }^{-w}}$; for clarity, we only show forward transitions.

Figure 3

Idea of the coupling (proof of Lemma t14). On the left: arrows show how to obtain sequences $x_{\mathsf{i}}^{*}\times \mathsf{k}$ and $y_{\mathsf{j}}^{*}\times \mathsf{k}$, respectively. On the right: arrows show how to obtain sequences $x_{\mathsf{j}}^{*}\times \mathsf{k}$ and $y_{\mathsf{i}}^{*}\times \mathsf{k}$, respectively. In either case, the resulting sequences are identical.

Figure 4

A comparison of ${\mathcal{M}}_{\mathrm{adj}}$ (adjacent swaps) and ${\mathcal{M}}_{\mathrm{any}}$ (arbitrary swaps) on the long run.

We measure the average, maximum, and minimum weighted number of inversions for a certain number of steps after both algorithms have approached their stationary distribution. The elements to be sorted are $(100,199,...,1)$.

From top to bottom: The first graph shows the evolution of the weighted number of inversions for increasing $\mathrm{noise}$, where $\lambda =e^{1/\text{noise}}$, from 0 to 100. Similarly, in the second graph the noise is increased from 100 to 1000 and in the third graph from 1000 to 10 000.

The graphs indicate that by increasing the value of $\mathrm{noise}$, the stationary behavior of ${\mathcal{M}}_{\mathrm{any}}$ degrades much earlier than that of ${\mathcal{M}}_{\mathrm{adj}}$.

Figure 5

A comparison of the three algorithms ${\mathcal{M}}_{\mathrm{adj}}$ (adjacent swaps), ${\mathcal{M}}_{\mathrm{any}}$ (arbitrary swaps), and ${\mathcal{M}}_{\mathrm{any}}^{*}$ (arbitrary swaps reversible). For three different values of noise, we plot for each algorithm the evolution of the weighted number of inversions starting from the sequence $(100,99,\cdots ,1)$. After every 20 steps of the algorithm, the weighted number of inversions is plotted. From top to bottom: The plots are for the noise values 0.5, 50, and 65, where $\lambda =e^{1/\text{noise}}$. The three graphs indicate that for some values of noise, ${\mathcal{M}}_{\mathrm{any}}^{*}$ possesses good features from the other two algorithms: the weighted number of inversions decreases faster than ${\mathcal{M}}_{\mathrm{adj}}$, while its stationary distribution is of course better than ${\mathcal{M}}_{\mathrm{any}}$, which is evident in the second plot. Note that the number of steps matches the number of comparisons made in ${\mathcal{M}}_{\mathrm{adj}}$ and ${\mathcal{M}}_{\mathrm{any}}$, but not in ${\mathcal{M}}_{\mathrm{any}}^{*}$.

Figure 6

A comparison of the two algorithms ${\mathcal{M}}_{\mathrm{adj}}$ (adjacent swaps) and ${\mathcal{M}}_{\mathrm{any}}$ (arbitrary swaps). For each algorithm and for increasing values of noise, we measure the probability of hitting the sorted sequence among a certain number of samples after both algorithms have converged. The noise increases from 0.2 to 2.8, where $\lambda =e^{1/\text{noise}}$, the initial sequence is $(10,9,...,1)$. The plot indicates that, for increasing values of noise, the stationary probability of the sorted sequence decreases faster in ${\mathcal{M}}_{\mathrm{any}}$ than in ${\mathcal{M}}_{\mathrm{adj}}$.

Figure 7

A comparison of the two algorithms ${\mathcal{M}}_{\mathrm{adj}}$ (adjacent swaps) and ${\mathcal{M}}_{\mathrm{any}}$ (arbitrary swaps) on binary sequences. For each algorithm and for increasing values of noise, we measure the percentage of hits of the sorted sequence after both algorithms have reached their stationary distribution. The set of elements is $\{1,1,1,1,1,1,1,1,1,2\}$. From top to bottom: In the first plot, the values of the noise lie between 0 and 3, where $\lambda =e^{1/\text{noise}}$. In the second plot, the values of the noise lie between 3 and 50. The plots show that, for increasing values of noise, the stationary probability of the sorted sequence decreases much faster and is always lower in ${\mathcal{M}}_{\mathrm{any}}$ than in ${\mathcal{M}}_{\mathrm{adj}}$.

Figure 8

All paths from (bca) to (bac). There are no bad trees for these two states.

Figure 9

All paths from (bac) to (abc). Bad trees include path (c) or (d).

Figure 10

All paths from (cba) to (bca). Bad trees include path (d) or (e).

Figure 11

All paths from (acb) to (abc). Bad trees include path (d) or (e).

Figure 12

All paths from (cab) to (acb). There are no bad trees for these two states.

Figure 13

All paths from (cba) to (cab). Bad trees include path (c) or (d).

Figure 14

Bad tree with path 9: $\left(\mathrm{bac}\right)\to \left(\mathrm{cab}\right)\to \left(\mathrm{cba}\right)\to \left(\mathrm{bca}\right)\to \left(\mathrm{acb}\right)\to \left(\mathrm{abc}\right)$, and good tree with path 9: $\left(\mathrm{bac}\right)\to \left(\mathrm{bca}\right)\to \left(\mathrm{acb}\right)\to \left(\mathrm{cab}\right)\to \left(\mathrm{cba}\right)\to \left(\mathrm{abc}\right)$.

Figure 15

Bad trees with path 9: $\left(\mathrm{bac}\right)\to \left(\mathrm{cab}\right)\to \left(\mathrm{acb}\right)\to \left(\mathrm{abc}\right)$.

Figure 16

Good trees with path 9: $\left(\mathrm{bac}\right)\to \left(\mathrm{bca}\right)\to \left(\mathrm{acb}\right)\to \left(\mathrm{abc}\right)$.

Figure 17

Good trees with path 9: $\left(\mathrm{bac}\right)\to \left(\mathrm{bca}\right)\to \left(\mathrm{cba}\right)\to \left(\mathrm{abc}\right)$.

Figure 18

Good trees with path 9: $\left(\mathrm{bac}\right)\to \left(\mathrm{cab}\right)\to \left(\mathrm{cba}\right)\to \left(\mathrm{abc}\right)$.