Ebook: Random Discrete Structures

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.

---

---

Content:
Front Matter....Pages i-xviii
Probability Distributions on Cladograms....Pages 1-18
Stability of Self-Organizing Processes....Pages 19-23
Some Examples of Normal Approximations by Stein’s Method....Pages 25-44
Large Deviations for Random Distribution of Mass....Pages 45-53
Random Minimax Game Trees....Pages 55-80
Metrics on Compositions and Coincidences among Renewal Sequences....Pages 81-101
The No Long Odd Cycle Theorem for Completely Positive Matrices....Pages 103-115
A Note on Triangle-Free Graphs....Pages 117-119
Intersections and Limits of Regenerative Sets....Pages 121-151
Random Processes of the Form X n+1 = a n X n + b n (mod p)where b n takes on a Single Value....Pages 153-174
The Second Moment Method, Conditioning and Approximation....Pages 175-183
How Fast and where does a Random Walker Move on a Random Tree?....Pages 185-198
A Note on Recurrence, Amenability, and the Universal Cover of Graphs....Pages 199-206
On which Graphs are All Random Walks in Random Environments Transient?....Pages 207-211
Energy, and Intersections of Markov Chains....Pages 213-225

---

Content:
Front Matter....Pages i-xviii
Probability Distributions on Cladograms....Pages 1-18
Stability of Self-Organizing Processes....Pages 19-23
Some Examples of Normal Approximations by Stein’s Method....Pages 25-44
Large Deviations for Random Distribution of Mass....Pages 45-53
Random Minimax Game Trees....Pages 55-80
Metrics on Compositions and Coincidences among Renewal Sequences....Pages 81-101
The No Long Odd Cycle Theorem for Completely Positive Matrices....Pages 103-115
A Note on Triangle-Free Graphs....Pages 117-119
Intersections and Limits of Regenerative Sets....Pages 121-151
Random Processes of the Form X n+1 = a n X n + b n (mod p)where b n takes on a Single Value....Pages 153-174
The Second Moment Method, Conditioning and Approximation....Pages 175-183
How Fast and where does a Random Walker Move on a Random Tree?....Pages 185-198
A Note on Recurrence, Amenability, and the Universal Cover of Graphs....Pages 199-206
On which Graphs are All Random Walks in Random Environments Transient?....Pages 207-211
Energy, and Intersections of Markov Chains....Pages 213-225
....