[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

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
(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

More information about the ringing-theory mailing list