Discrete Probability and Algorithms
David Aldous, Persi Diaconis, Joel Spencer
and J. Michael Steele (Eds.)
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.
TABLE of CONTENTS
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)