Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 7 (2002) > Paper 6 open journal systems 


Random Walks on Trees and Matchings

Persi Diaconis, Stanford University
Susan Holmes, Stanford University


Abstract
We give sharp rates of convergence for a natural Markov chain on the space of phylogenetic trees and dually for the natural random walk on the set of perfect matchings in the complete graph on 2n vertices. Roughly, the results show that 1/2 n log n steps are necessary and suffice to achieve randomness. The proof depends on the representation theory of the symmetric group and a bijection between trees and matchings.


Full text: PDF

Pages: 1-17

Published on: January 2, 2002
Bibliography
  1. Aldous, D. J. (1996), Probability Distributions on Cladograms in Random discrete structures (Aldous and Pemantle, eds.) Number 76 in IMA Series. Springer Verlag, NY, 1-18 MR:98d:60018
  2. Aldous, D. J. (1998), Stochastic coalescence In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), number Extra Vol. III, 205-211 (electronic) MR:99i:60171
  3. Aldous, D. J.(1999), Deterministic and stochastic models for coalescence (aggregation and coagulation): a review of the mean-field theory for probabilists. Bernoulli 5, 3-48. MR:2001c:60153
  4. Aldous, D. J. (2000), Mixing time for a Markov chain on cladograms.Combin. Probab. Computing 9, 191-204. MR:2001f:05129
  5. Aldous, D. J. (2001), Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today. Statist. Sci. 16, 23-34. MR:1838600
  6. Aldous, D. J. and Fill, J. (2002), Reversible Markov chains and random walks on graphs. available online at Book web page
  7. Barbour, A. D., Holst, L. and Janson, S. (1992), Poisson approximation The Clarendon Press Oxford University Press, New York. Oxford Science Publications. MR:93g:60043
  8. Diaconis, P. (1988), Group Representations in Probability and Statistics Institute of Mathematical Statistics, Hayward, Calif. MR:90a:60001
  9. Diaconis, P. and Hanlon, P. (1992), Eigen-analysis for some examples of the Metropolis algorithm. In Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991), Amer. Math. Soc., Providence, RI. 99-117. MR:94b:05205
  10. Diaconis, P. and Ram, A. (2000), Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques. Michigan Math. Journ. 4, 157-190. MR:2001j:60132
  11. Diaconis, P. and Saloff-Coste, L. (1993a), Comparison techniques for random walk on finite groups. Ann. Probab. 21, 2131-2156. MR:95a:60009
  12. Diaconis, P. and Saloff-Coste, L.(1993b), Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3, 696-730. MR:94i:60074
  13. Diaconis, P. and Shahshahani, M. (1981), Generating a random permutation with random transpositions. Z. W. 57, 159-179. MR:82h:60024
  14. Diaconis, P. and Shahshahani, M. (1987), Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Anal. 18, 208-218. MR:88e:60014
  15. Diaconis, P. W.and Holmes, S. P. (1998). Matchings and phylogenetic trees. Proc. Natl. Acad. Sci. USA 95, 14600-14602 (electronic). MR:1665632
  16. Durrett, R., Granovsky, B. L., and Gueron, S. (1999). The equilibrium behavior of reversible coagulation-fragmentation processes. J. Theoret. Probab. 12, 447-474. MR:2000g:82013
  17. Ewens, W. J. (1972), The sampling theory of selectively neutral alleles. Theoretical Population Biology 3, 87-112. MR:48:3526
  18. Hammersley, J. M. and Handscomb, D. C. (1964), Monte Carlo Methods. Chapman and Hall, London. MR:36:6114
  19. Holmes, S. (1999), Phylogenies: An overview. In Halloran, E. and Geisser, S., editors, Statistics and Genetics, number 81 in IMA. Springer Verlag, NY. Preprint
  20. Inglis, N. F. J., Richardson, R. W., and Saxl, J. (1990), An explicit model for the complex representations of S_n. Arch. Math. (Basel) 54, 258-259. MR:91d:20017
  21. Ingram, R. E. (1950), Some characters of the symmetric group. Proc. Amer. Math. Soc. 1, 358-369. MR:12,157b
  22. James, G. and Kerber, A. (1981), The representation theory of the symmetric group. Addison-Wesley, Reading, MA. MR:83k:20003
  23. James, A. T. (1968), Calculation of zonal polynomial coefficients by use of the Laplace-Beltrami operator. Ann. Math. Statist 39, 1711-1718. MR:37 #7039
  24. James, A. T.(1982). Analysis of variance determined by symmetry and combinatorial properties of zonal polynomials. In Statistics and probability: essays in honor of C. R. Rao, North-Holland, Amsterdam, 329-341. MR:83h:62076
  25. Jerrum, M. and Sinclair, A. (1989), Approximating the permanent. SIAM Journal on Computing 18, 1149-1178. MR:91a:05075
  26. Jerrum, M., Sinclair, A., and Vigoda, E. (2000), A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Electronic Colloquium on Computational Complexity (ECCC). MR number not available.
  27. Lovász, L. and Plummer, M. D. (1985), Matching Theory. North Holland, Amsterdam. MR:88b:90087
  28. Macdonald, I. G. (1995), Symmetric functions and Hall polynomials. The Clarendon Press Oxford University Press, New York, second edition. With contributions by A. Zelevinsky, Oxford Science Publications. MR:96h:05207
  29. Mayer-Wolfe, E., Zeitouni, O., and Zerner, M. (2001), Asymptotics of certain coagulation-fragmentation processes and invariant Poisson-Dirichlet measures. Technical report, Dept. of Mathematics, Stanford University, Stanford, CA94305. MR number not available.
  30. Page, R. and Holmes, E. (2000), Molecular Evolution, A Phylogenetic Approach. Blackwell Science. MR number not available.
  31. Pulleyblank, W. (1995), Matchings and extensions. In Graham, R. L., M. Grötschel and L. Lovász editors, Handbook of combinatorics. Vol. 1, 2, 179-232, Amsterdam. Elsevier Science B.V. MR:96j:05090
  32. Roussel, S. (2000). Phénomène de cutoff pour certaines marches aléatoires sur le groupe symetrique. Colloq. Math. 86, 111-135. MR:2001m:60019
  33. Sagan, B. E. (2001), The symmetric group. Springer-Verlag, New York, second edition. Representations, combinatorial algorithms, and symmetric functions. MR:2001m:05261
  34. Saloff-Coste, L. (1997), Lectures on finite Markov chains. In Lectures on probability theory and statistics, pages 301-413, Berlin. Lecture Notes in Math., 1665, Springer-Verlag. Lectures from the 26th Summer School on Probability Theory held in Saint-Flour,Edited by P. Bernard. MR:99b:60119
  35. Saxl, J. (1981), On multiplicity-free permutation representations. In Finite geometries and designs (Proc. Conf., Chelwood Gate, 1980), pages 337-353. Cambridge Univ. Press, Cambridge. MR:82i:20018
  36. Scarabotti, F. (1997), Time to reach stationarity in the Bernoulli-Laplace diffusion model with many urns. Adv. Math. 18, 351-371. MR:98d:60014
  37. Schröder, E. (1870), Veir combinatorische probleme. Zeit. für. Math. Phys. 15, 361-376. MR number not available.
  38. Schweinsberg, J. (2001), An O(n2) bound for the relaxation time of a Markov chain on cladograms. Technical Report 572, Dept Statistics, UC Berkeley. Preprint
  39. Serre, J.-P. (1977), Linear representations of finite groups. Springer-Verlag, New York. Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42. MR:56 #8675
  40. Wachs, M. (2001), Topology of matching, homology of matching, combinatorial Laplacian of the matching complex. Technical report, available online at Preprint
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489