Print

---

Please note that updated Statistical Laboratory seminar lists are shown
on our web page at

            http://www.statslab.cam.ac.uk/Seminars/statsemeast2000.html


                             SEMINARS
                      STATISTICAL LABORATORY
                      UNIVERSITY OF CAMBRIDGE

                   ********************************
                   *  ALL INTERESTED ARE WELCOME  *
                   ********************************
                       


                  

Seminars are in Meeting Room 12, Centre for Mathematical Sciences 
****************************************************************


                   *******************************
                        Friday 19  May 2000
                   *******************************

2pm Bob Griffiths (University of Oxford)

THE AGE OF A MUTATION IN A GENERAL BINARY COALESCENT TREE}

Kimura and Ohta showed that the expected age of a neutral
mutation observed to be of frequency $x$ in a population is
$-2x(1-x)^{-1}\log x.$
This classical result is put in a general coalescent process context that 
allows questions to be asked about mutations in the sample, as well as in
the population.  In the general context coalescence joins have 
an exchangeable distribution and coalescence times are have an arbitary 
distribution.
Assuming a point mutation it is possible to find the 
distribution of the age of a mutation given its frequency in a sample,
or population.  It is also of interest to study the characteristics of the 
subtree under a mutation.



****************************************************

                   *******************************
                        Friday 26 May 2000
                   *******************************

2pm David B. Wilson (Microsoft Research)

MIXING TIMES OF LOZENGE TILING AND CARD SHUFFLING MARKOV CHAINS

We introduce a simple technique that can be applied to a number of classes
of Markov chains to obtain upper bounds and lower bounds on their mixing 
times, the number of steps the Markov chains take to approach their 
equilibrium distribution. One application is to a class of Markov chains 
introduced by Luby, Randall, and Sinclair to generate random tilings of 
regions by lozenges. The mixing time bounds derived here improve substantially
upon the previous results. In another application we resolve  a few 
questions raised by Diaconis and Saloff-Coste, by lower bounding the 
mixing time of various card shuffling Markov chains. Our lower bounds are 
within a constant factor of their upper bounds. When we apply this technique 
to modify an analysis of Bubley and Dyer, we obtain an O(n^3 log n) upper 
bound on the mixing time of the Karzanov-Khachiyan Markov chain for linear 
extensions. Using this same technique we obtain a lower bound on the mixing 
time of the random walk on high-dimensional product graphs, which is only 
a factor of 1-o(1) smaller than a known upper bound.


****************************************************




Seminar organizer: Susan Pitts

Please see also the /~grg/seminars/probsem.html -  Informal Probability
Seminars.



UNIVERSITY OF CAMBRIDGE
STATISTICAL LABORATORY
CENTRE FOR MATHEMATICAL SCIENCES
WILBERFORCE ROAD
CAMBRIDGE CB3 0WB
Tel: (01223) 337958
Fax: (01223) 337956







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%