Probability on Discrete Structures
Most probability problems involve random variables indexed by space and/or time. These problems almost always have a version in which space and/or time are taken to be discrete. This volume deals with areas in which the discrete version is more
- PDF / 38,441,952 Bytes
- 358 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 233 Views
Probability Theory Subseries Editors: A.-S. Sznitman S.R.S. Varadhan
Springer-Verlag Berlin Heidelberg GmbH
Harry Kesten (Editor)
Probability on Discrete Structures
Springer
Harry Kesten Cornell University Department of Mathematics Malott Hall310 14853-4201Ithaca,}lY USA e-mail: [email protected]
Founding editor of the Encyclopaedia of Mathematical Sciences: R. V. Gamkrelidze
Mathematics Subject Classification (2ooo): 6oB99, 6oCo5, 6oF17, 60G5o, 6oJ10, 6oJ27, 6oK35
ISBN 978-3-642-05647-5 ISBN 978-3-662-09444-0 (eBook) DOI 10.1007/978-3-662-09444-0
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 196s, in its current version, and permission for use must always be obtained from Springer-Verlag Berlin Heidelberg GmbH. Violations are liable for prosecution under the German Copyright Law. http://www.springer.de 0 Springer-Verlag Berlin Heidelberg 2004 Originally published by Springer-Verlag Berlin Heidelberg New York in 2004 Softcover reprint of the hardcover 1st edition 2004 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typeset by L£-TEX Jelonek, Schmidt & Vllckler GbR, Leipzig Cover Design: £. Kirch.ner, Heidelberg, Germany Printed on acid-free paper 41/3142 db s4 3 2 1 o
Preface
Probability on discrete structures covers a wide area. Most probability problems involve random variables indexed by space and/ or time. Almost always these problems have a version in which space and/ or time are taken discrete. Roughly speaking this volume deals with some areas in which the discrete version is more natural than the continuous one, or perhaps even the only one which can be formulated without complicated constructions and machinery. Clear examples of this situation can be found in the articles in this volume on the random cluster model (by Grimmett) and on first-passage percolation (by Howard) and in most of the problems in the forthcoming book "Probability on Trees and Networks" by R. Lyons andY. Peres. The article by Howard actually also discusses a continuous variant - called Euclidean first-passage percolation - but this came later and even though this continuous version has some clear advantages, its analysis brings in extra difficulties. Problems on discrete structures can often be stated with minimal prerequisites, and sometimes only "elementary" (but by no means easy) probability theory is needed for their solution. Often the arguments have more of a combinatorial flavor than an analytic one, but the articles here
