[r-t] random call changes

[Alexander Holroyd]

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