Discrete Probability and Algorithms

David Aldous, Persi Diaconis, Joel Spencer and J. Michael Steele (Eds.)

Discrete Probability and Algorithms Book Cover

This is a collection of articles that grew out of a series of tutorials and talks given at the Institute for Mathematics and Its Applications during the "Special Year on Emerging Applications of Probability."

One of the designated areas for the Special Year was the interface between probability and algorithms, which includes probabilistic algorithms (where the algorithm makes random choices) and the probabilistic analysis of algorithms (where we typically assume a probability model for the in-put data --- the algorithm can make randomized steps or not.)

The book is now out of print, but the articles themselves can usually be obtained from the authors. A few of these (including my piece on the "Increasing Subsequence Problem") are hot-linked below. If you have trouble getting one of these articles, let me know; I'll probably be able to help.

As I explain below (after the Table of Contents). Springer was not a great partner when it came to the distribution of this book. In fact, it is a modest miracle, the book still has managed to garner a decent number of citations through the years. Hopefully, there are more to come.

line to separated TOC of Probability and Discrete Algorithms from Introduction


On simulating a Markov chain stationary distribution when transition probabilities are unknown (abstract)
David Aldous

A note on network reliability (full article)
Noga Alon

Rectangular arrays with fixed margins (abstract)
Persi Diaconis and Anil Gangolli

Three examples of Monte-Carlo Markov chains: at the interface between statistical computing, computer science, and statistical mechanic (abstract)
Persi Diaconis and Susan Holmes

The move-to-front rule for self-organizing lists with Markov dependent requests (abstract)
Robert P. Dobrow and James Allen Fill

The asymptotic lower bound on the diagonal Ramsey numbers: A closer look
Anant P. Godbole, Daphne E. Skipper, and Rachel A. Sunley

Random walks and undirected graph connectivity: A survey (abstract)
Anna R. Karlin and Prabhakar Raghavan

Sidon sets with small gaps
Joel Spencer and Prasad Tetali

Variations on the monotone subsequence theme of Erdös and Szekeres (full article)
J. Michael Steele

Randomized approximation schemes for Tutte-Grothendieck invariants
Dominic Welsh

Quasi-additive Euclidean functionals (abstract)
J. E. Yukich

line to separated TOC of Probability and Discrete Algorithms from Introduction

How Springer Stuffed this Book into a Black Hole

This volume was published through a joint venture of the Institute for Applied Mathematics and Springer-Verlag. Springer is a long standing partner of the IMA, and I am sure that they do a fine job on most volumes, but this one got a very rough ride --- at least as far as direct distribution goes.

Until August 2006 the Springer Website had a description of the volume that was completely wrong.

The problem? They interchanged the descriptions of volumes 72 and 73. I let them know about this about five years ago --- and then I did not follow up for years! My bad, as they say.

Finally, after at least eight years life as an essentially "dead link," the book is now correctly listed on the Springer website.

Despite the horror of this snafu, the book has by some miracle managed to achieve a decent distribution. At least it is a decent selection of the large library collections.

Springer offers it for sale on its web site, but they do not promise a delivery date, so availability is a little nebulous. It would be a fine item for Springer to release as e-book --- if for no other reason that to kiss and make up.

If you see a source for a used copy on the web, let me know and I will mirror it here.

"Easy Clip" Sourcing Details:

Discrete Probability and Algorithms David Aldous, Persi Diaconis, Joel Spencer and J. Michael Steele (Eds.) IMA Volume 72 Springer-Verlag 1995. (ISBN 0-387-94532-6)


BACK TO: J. Michael Steele's Home Page