Daniel W. Stroock
An Introduction to Markov Processes
4y Springer
Daniel W. Stroock MIT Department of Mathematics, Rm. 272 Massachusetts Ave 77 02139-4307 Cambridge, USA dws @math.mit.edu Editorial Board S. Axler Mathematics Department San Francisco State University San Francisco, CA 94132 e
d
u
F. W. Gehring Mathematics Department East Hall University of Michigan Ann Arbor, MI 48109
K. A. Ribet Mathematics Department University of California at Berkeley Berkeley, CA 94720-3840
USA
[email protected]
USA
[email protected]
Mathematics Subject Classification (2000): 60-01, 60J10, 60J27 ISSN 0072-5285 ISBN 3-540-23499-3 Springer Berlin Heidelberg New York Library of Congress Control Number: 20041113930 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 microfilms or in any other way, and storage in databanks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable for prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springeronline.com © Springer-Verlag Berlin Heidelberg 2005 Printed in Germany 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. Typesetting: Camera-ready by the translator Cover design: design & production GmbH, Heidelberg Printed on acid-free paper 41/3142 XT - 5 4 3 2 1 0
This book is dedicated to my longtime colleague: Richard A. Holley
Contents
Preface
xi
Chapter 1 Random Walks A Good Place to Begin 1.1. Nearest Neighbor Random Walks on Z 1.1.1. Distribution at Time n 1.1.2. Passage Times via the Reflection Principle 1.1.3. Some Related Computations 1.1.4. Time of First Return 1.1.5. Passage Times via Functional Equations 1.2. Recurrence Properties of Random Walks 1.2.1. Random Walks on Z d 1.2.2. An Elementary Recurrence Criterion 1.2.3. Recurrence of Symmetric Random Walk in Z2 1.2.4. Transience in Z 3 1.3. Exercises
1 1 2 3 4 6 7 8 9 9 11 13 16
Chapter 2 Doeblin's Theory for Markov Chains 2.1. Some Generalities 2.1.1. Existence of Markov Chains 2.1.2. Transition Probabilities & Probability Vectors 2.1.3. Transition Probabilities and Functions 2.1.4. The Markov Property 2.2. Doeblin's Theory 2.2.1. Doeblin's Basic Theorem 2.2.2. A Couple of Extensions 2.3. Elements of Ergodic Theory 2.3.1. The Mean Ergodic Theorem 2.3.2. Return Times 2.3.3. Identification of n 2.4. Exercises
23 23 24 24 26 27 27 28 30 32 33 34 38 40
Chapter 3 More about the Ergodic Theory of Markov Chains 3.1. Classification of States 3.1.1. Classification, Recurrence, and Transience 3.1.2. Criteria for Recurrence and Transience 3.1.3. Periodicity 3.2. Ergodic Theory without Doeblin 3.2.1. Convergence of Matrices
45 46 46 48 51 53 53