Nội dung

“Four legs good, two legs better ” A modified version of the Animal Farm’s Constitution. “Two logs good, p logs better ” The original Constitution of mathematicians. RAN D O M WALK IN RANDOM AND N O N- RAND O M ENVIRONMENTS h E C D N D E D I T I O N This page intentionally left blank L RANDEOM WALK IN RANDOM AND N NONN-- RANDOMM ENVIRONMENTS ENVIRO E C O N EDITION 0 D Pal Revesz Technische Universitat Wien, Austria Technical University of Budapest, Hungary N E W JERSEY * LONDON * Scientific 10;World - SINGAPORE BEIJING * SHANGHAI HONG KONG * TAIPEI - CHENNAI Published by World Scientific Publishing Co. Pte.Ltd. 5 Toh Tuck Link, Singapore 596224 USA ofice; 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK ofice: 57 Shelton Street, Covent Garden, London WC2H 9HE Library of Congress Cataloging-in-PublicationData Random walk in random and non-random environments / Pfll RCvCsz.--2nd ed. p. cm. Includes bibliographical references and indexes. ISBN 981-256-361-X (alk. paper) 1. Random walks (Mathematics). I. Title. QA274.73 .R48 2005 5 19.2’82--dc22 2005045536 British Library Cataloguing-in-PublicationData A catalogue record for this book is available from the British Library. Copyright 0 2005 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof; may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. Printed in Singapore by Mainland Press Preface to the First Edition “I did not know that it was so dangerous to drink a beer with you. You write a book with those you drink a beer with,” said Professor Willem Van Zwet, referring to the preface of the book Csorgo and I wrote (1981) where it was told that the idea of that book was born in an inn in London over a beer. In spite of this danger Willem was brave enough t o invite me t o Leiden in 1984 for a semester and to drink quite a few beers with me there. In fact I gave a seminar in Leiden, and the handout of that seminar can be considered as the very first version of this book. I am indebted to Willem and to the Department of Leiden for a very pleasant time and a number of useful discussions. I wrote this book in 1987-89 in Vienna (Technical University) partly supported by Fonds zur Forderung der Wissenschaftlichen Forschung, Project Nr. P6076. During these years I had very strong contact with the Mathematical Institute of Budapest. I am especially indebted t o Professors E. Csaki and A. Foldes for long conversations which have a great influence on the subject of this book. The reader will meet quite often with the name of P. Erdos, but his role in this book is even greater. Especially most results of Part I1 are fully or partly due to him, but he had a significant influence even on those results that appeared under my name only. Last but not least, I have t o mention the name of M. Csorgo, with whom I wrote about 30 joint papers in the last 15 years, some of them strongly connected with the subject of this book. P. Rkvksz Technical University of Vienna Wiedner Hauptstrasse 8-10/107 -4-1040 Vienna Austria Vienna, 1989. V This page intentionally left blank Preface to the Second Edition If you write a monograph on a new, just developing subject, then in the next few years quite a number of brand-new papers are going t o appear in your subject and your book is going t o be outdated. If you write a monograph on a very well-developed subject in which nothing new happens, then it is going t o be outdated already when it is going to appear. In 1989 when I prepared the First Edition of this book it was not clear for me that its subject was already overdeveloped or it was a still developing area. A year later Erd6s told me that he had been surprised to see how many interesting, unsolved problems had appeared in the last few years about the very classical problem of coin-tossing (random walk on the line). In fact Erdos himself proposed and solved a number of such problems. I was happy to see the huge number of new papers (even books) that have appeared in the last 16 years in this subject. I tried t o collect the most interesting ones and to fit them in this Second Edition. Many of my friends helped me to find the most important new results and to discover some of the mistakes in the First Edition. My special thanks t o E. CsAki, M. Csorgo”,A. Foldes, D. Khoshnevisan, Y . Peres, Q. M. Shao, B. T6th, Z. Shi. Vienna, 2005. vii This page intentionally left blank Contents Preface to the First Edition V Preface to the Second Edition vii Introduction xv . I SIMPLE SYMMETRIC RANDOM WALK IN Z’ Notations and abbreviations 3 1 Introduction of Part I 1.1 Randomwalk . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Dyadic expansion . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Rademacher functions . . . . . . . . . . . . . . . . . . . . . 1.4 Coin tossing . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 The language of the probabilist . . . . . . . . . . . . . . . . 9 9 10 10 11 11 Distributions 2.1 Exact distributions . . . . . . . . . . . . . . . . . . . . . . . 2.2 Limit distributions . . . . . . . . . . . . . . . . . . . . . . . 13 13 19 3 Recurrence and the Zero-One Law 3.1 Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The zero-one law . . . . . . . . . . . . . . . . . . . . . . . . 23 23 25 2 4 F’rom the Strong Law of Large Numbers to the Law of Iterated Logarithm 27 4.1 Borel-Cantelli lemma and Markov inequality . . . . . . . . 27 4.2 The strong law of large numbers . . . . . . . . . . . . . . . 28 4.3 Between the strong law of large numbers and the law of iterated logarithm . . . . . . . . . . . . . . . . . 29 4.4 The LIL of Khinchine . . . . . . . . . . . . . . . . . . . . . 31 5 Lbvy Classes 5.1 Definitions . . . . . . . . . . . . 5.2 EFKPLIL . . . . . . . . . . . . . 5.3 The laws of Chung and Hirsch 5.4 When will S, be very large? . . ix ............... ............... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 33 34 39 39