Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 14 (2009) > Paper 4 open journal systems 


Note: Random-to-front shuffles on trees

Anders Bjorner, Royal Institute of Technology


Abstract
A Markov chain is considered whose states are orderings of an underlying fixed tree and whose transitions are local ``random-to-front'' reorderings, driven by a probability distribution on subsets of the leaves. The eigenvalues of the transition matrix are determined using Brown's theory of random walk on semigroups.


Full text: PDF

Pages: 36-41

Published on: February 4, 2009
Bibliography
  1. Allen, Brian; Munro, Ian. Self-organizing binary search trees. J. Assoc. Comput. Mach. 25 (1978), no. 4, 526--535. MR0508699 (80a:68034)
  2. Bidigare, Pat; Hanlon, Phil; Rockmore, Dan. A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J. 99 (1999), no. 1, 135--174. MR1700744 (2000m:52032)
  3. Bjorner,A. Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries, in ``Building Bridges'' (eds. M. Grotschel and G. O. H. Katona), Bolyai Soc. Math. Studies 19 (2008), Springer (Berlin) and Janos Bolyai Math. Soc. (Budapest), pp.165--203.
  4. Brown, Kenneth S. Semigroups, rings, and Markov chains. J. Theoret. Probab. 13 (2000), no. 3, 871--938. MR1785534 (2001e:60141)
  5. Brown, Kenneth S.; Diaconis, Persi. Random walks and hyperplane arrangements. Ann. Probab. 26 (1998), no. 4, 1813--1854. MR1675083 (2000k:60138)
  6. Dobrow, Robert P.; Fill, James Allen. On the Markov chain for the move-to-root rule for binary search trees. Ann. Appl. Probab. 5 (1995), no. 1, 1--19. MR1325037 (96d:60100)
  7. Fill, James Allen; Holst, Lars. On the distribution of search cost for the move-to-front rule. Random Structures Algorithms 8 (1996), no. 3, 179--186. MR1603279 (99b:60118)
  8. Stanley, Richard P. Enumerative combinatorics. Vol. 1.With a foreword by Gian-Carlo Rota.Corrected reprint of the 1986 original.Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 1997. xii+325 pp. ISBN: 0-521-55309-1; 0-521-66351-2 MR1442260 (98a:05001)













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


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

Electronic Communications in Probability. ISSN: 1083-589X