Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 12 (2007) > Paper 42 open journal systems 


Asymptotic evolution of acyclic random mappings

Steven Neil Evans, University of California at Berkeley
Tye Lidman, University of California at Berkeley


Abstract
An acyclic mapping from an $n$ element set into itself is a mapping $varphi$ such that if $varphi^k(x) = x$ for some $k$ and $x$, then $varphi(x) = x$. Equivalently, $varphi^ell = varphi^{ell+1} = ldots$ for $ell$ sufficiently large. We investigate the behavior as $n rightarrow infty$ of a sequence of a Markov chain on the collection of such mappings. At each step of the chain, a point in the $n$ element set is chosen uniformly at random and the current mapping is modified by replacing the current image of that point by a new one chosen independently and uniformly at random, conditional on the resulting mapping being again acyclic. We can represent an acyclic mapping as a directed graph (such a graph will be a collection of rooted trees) and think of these directed graphs as metric spaces with some extra structure. Informal calculations indicate that the metric space valued process associated with the Markov chain should, after an appropriate time and ``space'' rescaling, converge as $n rightarrow infty$ to a real tree ($R$-tree) valued Markov process that is reversible with respect to a measure induced naturally by the standard reflected Brownian bridge. Although we don't prove such a limit theorem, we use Dirichlet form methods to construct a Markov process that is Hunt with respect to a suitable Gromov-Hausdorff-like metric and evolves according to the dynamics suggested by the heuristic arguments. This process is similar to one that appears in earlier work by Evans and Winter as a similarly informal limit of a Markov chain related to the subtree prune and regraft tree (SPR) rearrangements from phylogenetics.


Full text: PDF

Pages: 1051-1180

Published on: September 2, 2007
Bibliography
  1. Aldous, David; Miermont, Grégory; Pitman, Jim. Weak convergence of random $p$-mappings and the exploration process of inhomogeneous continuum random trees. Probab. Theory Related Fields 133 (2005), no. 1, 1--17. MR2197134 (2007f:60009)
  2. Aldous, David J.; Pitman, Jim. Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5 (1994), no. 4, 487--512. MR1293075 (95k:60055)
  3. Aldous, David; Pitman, Jim. The asymptotic distribution of the diameter of a random mapping. C. R. Math. Acad. Sci. Paris 334 (2002), no. 11, 1021--1024. MR1913728 (2003e:60014)
  4. Bertoin, Jean; Pitman, Jim. Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math. 118 (1994), no. 2, 147--166. MR1268525 (95b:60097)
  5. Chiswell, Ian. Introduction to $Lambda$-trees. World Scientific Publishing Co., Inc., River Edge, NJ, 2001. xii+315 pp. ISBN: 981-02-4386-3 MR1851337 (2003e:20029)
  6. Drmota, Michael; Gittenberger, Bernhard. Strata of random mappings---a combinatorial approach. Stochastic Process. Appl. 82 (1999), no. 2, 157--171. MR1700003 (2000g:05016)
  7. Drmota, Michael; Gittenberger, Bernhard. The width of Galton-Watson trees conditioned by the size. Discrete Math. Theor. Comput. Sci. 6 (2004), no. 2, 387--400 (electronic). MR2081482 (2005f:60180)
  8. Dress, Andreas; Moulton, Vincent; Terhalle, Werner. $T$-theory. An overview. Sém. Lothar. Combin. 34 (1995), Art. B34b, approx. 23 pp. (electronic). MR1399749 (97i:57002)
  9. Dress, Andreas; Moulton, Vincent; Terhalle, Werner. $T$-theory: an overview. Discrete metric spaces (Bielefeld, 1994). European J. Combin. 17 (1996), no. 2-3, 161--175. MR1379369 (97e:05069)
  10. Dress, Andreas W. M. Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Adv. in Math. 53 (1984), no. 3, 321--402. MR0753872 (86j:05053)
  11. Drmota, Michael; Soria, Michèle. Images and preimages in random mappings. SIAM J. Discrete Math. 10 (1997), no. 2, 246--269. MR1445035 (98c:05011)
  12. Dress, A. W. M.; Terhalle, W. F. The real tree. Adv. Math. 120 (1996), no. 2, 283--301. MR1397084 (97d:54051)
  13. Ethier, Stewart N.; Kurtz, Thomas G. Markov processes. Characterization and convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1986. x+534 pp. ISBN: 0-471-08186-8 MR0838085 (88a:60130)
  14. Evans, Steven N.; Pitman, Jim; Winter, Anita. Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields 134 (2006), no. 1, 81--126. MR2221786 (2007d:60003)
  15. Steven~N. Evans, Probability and real trees, Lecture Notes in Mathematics, vol. 1920, Springer-Verlag, Berlin, 2007, Lecture notes from the Ecole d'Ete de Probabilites de Saint-Flour XXXV-2005.
  16. Evans, Steven N.; Winter, Anita. Subtree prune and regraft: a reversible real tree-valued Markov process. Ann. Probab. 34 (2006), no. 3, 918--961. MR2243874 (Review)
  17. Gittenberger, Bernhard; Louchard, Guy. On the local time density of the reflecting Brownian bridge. J. Appl. Math. Stochastic Anal. 13 (2000), no. 2, 125--136. MR1768499 (2001h:60134)
  18. Andreas Greven, Peter Pfaffelhuber, and Anita Winter, Convergence in distribution of random metric measure spaces: ($Lambda$-coalescent measure trees), 2006, Pre-print available at http://front.math.ucdavis.edu/math.PR/0609801.
  19. Knight, Frank B. Essentials of Brownian motion and diffusion. Mathematical Surveys, 18. American Mathematical Society, Providence, R.I., 1981. xiii+201 pp. ISBN: 0-8218-1518-0 MR0613983 (82m:60098)
  20. Jean-François Le Gall, Random real trees, Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), no. 1, 35--62.
  21. Pitman, Jim. Random mappings, forests, and subsets associated with Abel-Cayley-Hurwitz multinomial expansions. Sém. Lothar. Combin. 46 (2001/02), Art. B46h, 45 pp. (electronic). MR1877634 (2002m:60017)
  22. Sturm, Karl-Theodor. On the geometry of metric measure spaces. I. Acta Math. 196 (2006), no. 1, 65--131. MR2237206 (Review)
  23. Sturm, Karl-Theodor. On the geometry of metric measure spaces. II. Acta Math. 196 (2006), no. 1, 133--177. MR2237207 (Review)
  24. Terhalle, Werner F. $R$-trees and symmetric differences of sets. European J. Combin. 18 (1997), no. 7, 825--833. MR1478827 (99e:05035)
  25. Zambotti, Lorenzo. A reflected stochastic heat equation as symmetric dynamics with respect to the 3-d Bessel bridge. J. Funct. Anal. 180 (2001), no. 1, 195--209. MR1814427 (2002c:60108)
  26. Zambotti, Lorenzo. Integration by parts on Bessel bridges and related stochastic partial differential equations. C. R. Math. Acad. Sci. Paris 334 (2002), no. 3, 209--212. MR1891060 (2002m:60104)
  27. Zambotti, Lorenzo. Integration by parts on $delta$-Bessel bridges, $delta>3$ and related SPDEs. Ann. Probab. 31 (2003), no. 1, 323--348. MR1959795 (2003m:60175)
















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