Random Discrete Structures

1. Front Matter

   Pages i-xviii

   PDF

2. Probability Distributions on Cladograms

   • David Aldous

   Pages 1-18

3. Stability of Self-Organizing Processes

   • Robert M. Burton, William G. Faris

   Pages 19-23

4. Some Examples of Normal Approximations by Stein’s Method

   • Amir Dembo, Yosef Rinott

   Pages 25-44

5. Large Deviations for Random Distribution of Mass

   • Amir Dembo, Ofer Zeitouni

   Pages 45-53

6. Random Minimax Game Trees

   • Luc Devroye, Olivier Kamoun

   Pages 55-80

7. Metrics on Compositions and Coincidences among Renewal Sequences

   • Persi Diaconis, Susan Holmes, Svante Janson, Steven P. Lalley, Robin Pemantle

   Pages 81-101

8. The No Long Odd Cycle Theorem for Completely Positive Matrices

   • John H. Drew, Charles R. Johnson

   Pages 103-115

9. A Note on Triangle-Free Graphs

   • Paul Erdős, Svante Janson, Tomasz Łuczak, Joel Spencer

   Pages 117-119

10. Intersections and Limits of Regenerative Sets

    • Bert Fristedt

    Pages 121-151

11. Random Processes of the Form X _n+1 = a _n X _n + b _n (mod p)where b _n takes on a Single Value

    • Martin Hildebrand

    Pages 153-174

12. The Second Moment Method, Conditioning and Approximation

    • Svante Janson

    Pages 175-183

13. How Fast and where does a Random Walker Move on a Random Tree?

    • Russell Lyons

    Pages 185-198

14. A Note on Recurrence, Amenability, and the Universal Cover of Graphs

    • Sam Northshield

    Pages 199-206

15. On which Graphs are All Random Walks in Random Environments Transient?

    • Robin Pemantle, Yuval Peres

    Pages 207-211

16. Energy, and Intersections of Markov Chains

    • Thomas S. Salisbury

    Pages 213-225

The articles in this volume present the state of the art in a variety of areas of discrete probability, including random walks on finite and infinite graphs, random trees, renewal sequences, Stein's method for normal approximation and Kohonen-type self-organizing maps. This volume also focuses on discrete probability and its connections with the theory of algorithms. Classical topics in discrete mathematics are represented as are expositions that condense and make readable some recent work on Markov chains, potential theory and the second moment method. This volume is suitable for mathematicians and students.

• Markov chain
• Probability distribution
• algorithms
• graphs
• random walk
• combinatorics

• Department of Statistics, University of California, Berkeley, USA

  David Aldous

• Department of Mathematics, University of Wisconsin-Madison, Madison, USA

  Robin Pemantle

Policies and ethics