# [r-t] random call changes

Alexander Holroyd holroyd at math.ubc.ca
Sat Sep 23 00:54:27 UTC 2006

```Hi folks,

Here is a recent mathematical paper that might be of interest to some on
this list (it can be downloaded as .ps or .pdf from here):

Random Sorting Networks
Omer Angel, Alexander E. Holroyd, Dan Romik, Balint Virag
http://arxiv.org/math.PR/0609538

For those more comfortable with ringing terminology than mathematics, some
highlights are as follows.

Starting in rounds, call the bells into reverse rounds by call changes.
On n bells, the minimum number of calls needed is n(n-1)/2, because this
is the number of pairs of bells, and each pair needs to get swapped
somewhere.  There are many ways to do it in this minimum number of calls;
e.g. one can call 1 up to the back, then 2 up to (n-1)th place, etc; or
one can call plain hunt (but swapping one pair of bells at a time).  Any
way of getting from rounds to back rounds in exactly n(n-1)/2 calls is
called a "sorting network".

Fix the number of bells n, and choose a sorting network at random, in such
a way that all possible sorting networks have the same probability.  This
random object is called a "uniform sorting network" (USN).  E.g. on n=3
bells there are exactly 2 possible sorting networks:

(a) 123 213 231 321
and
(b) 123 132 312 321

so to get a USN, you toss a fair coin an pick (a) if you get Heads or (b)
if you get Tails.

The main question we consider is: what does the USN typically look like
when the number of bells n is very large?  It turns out that one can
conveniently simulate it on a computer; there are some pictures in the
paper.  The results are very surprising.

Conjectures (i.e. things we believe are true but can't prove rigorously):

1. When n is large, all the blue lines typically resemble Sine curves
(i.e. the shape of the graph y=sin(x)), with period n(n-1) (twice the
length of the sorting network) and with random amplitudes and phases.
(See Figure 1 in the paper).

2. Look at the random row at half-time (i.e. after n(n-1)/4 calls), and
plot its graph: i.e. in the 1st column put a dot at height equal to the
number of the bell in 1st place, in the 2nd colum put a dot for the bell
in 2nd place, etc.  When n is large the resulting picture is typically
circlularly symmetric (see Fig 2).

Theorems (things we can prove):

1. Calls in different places occur with different frequencies, e.g. the
middle two bells in the row swap much more often than the bells in places
1 and 2.  More precisely, if you plot a histogram of the frequencies, for
n large it resembles a semicircle.

2. For n large, typically the graph of the half-way row lies within a
certain octagon.  This means for example that bell 1 is very unlikely
to be lower than place cn where c is a certain fixed number (actually
this is true for any c less than 1-sqrt(3)/2 = 0.134).

3. For n large the blue lines converge to curves which are "smooth" in a
certain technical sense (see Theorem 3).

cheers, Ander

```