[r-t] random call changes
holroyd at math.ubc.ca
Sat Sep 23 00:54:27 UTC 2006
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).
More information about the ringing-theory