[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
More information about the ringing-theory
mailing list