THE ART OF RANDOM WALKS
1 INTRODUCTION 2 BASIC DEFINITIONS AND PRELIMINARIES 3 SOME ELEMENTS OF POTENTIAL THEORY 4 ISOPERIMETRIC INEQUALITIES 5 POLYNOMIAL VOLUME GROWTH 6 MOTIVATION OF THE LOCAL APPROACH 7 EINSTEIN RELATION 8 UPPER ESTIMATES 9 LOWER ESTIMATES 10 TWO-SIDED ESTIMATES 11 CLOSING REMARKS 12 PARABOLIC HARNACK INEQUALITY 13 SEMI-LOCAL THEORY REFERENCES CONTENTS INTRODUCTION 1 1 THE BEGINNINGS THE HISTORY OF RANDOM WALKS GOES BACK TO TWO CLASSICAL SCIENTI?C RECOGNITIONS IN 1827 ROBERT BROWN, THE ENGLISH BOTANIST PUBLISHED HIS OBSERVATION ABOUT THE IRREGULAR MOVEMENT OF SMALL POLLEN GRAINS IN A LIQUID UNDER HIS MICROSCOPE HE NOT ONLY DESCRIBED THE IRREGULAR MOVEMENT BUT ALSO POINTED OUT THAT IT WAS CAUSED BY SOME INANIMATE PROPERTY OF NATURE THE IRREGULAR AND ODD SERIES PRODUCED BY GAMBLING, E G , WHILE TOSSING A COIN OR THROWING A DICE RAISED THE INTEREST OF THE MATHEMATICIANS PASCAL, FERMAT AND BERNOULLI AS EARLY AS IN THE MID–16TH CENTURY LET US START WITH THE PHYSICAL MOTIVATION AND THEN LET US RECALL SOME MILESTONES IN THE HISTORY OF THE RESEARCH ON RANDOM WALKS THE ?RST RIGOROUS RESULTS ON BROWNIAN MOTION WERE GIVEN BY EINSTEIN [33] AMONG OTHER THINGS, HE PROVED THAT THE MEAN DISPLACEMENT < XT > OF THE MOTION XT AFTER TIME T IS < XT >= ? 2DT, WHERE D IS THE SO–CALLED DI?USION CONSTANT EINSTEIN ALSO DETERMINED THE DE- PENDENCE OF THE DI?USION CONSTANT ON OTHER PHYSICAL PARAMETERS OF THE LIQUID, NAMELY HE SHOWED THAT D?1 = RT NS WHERE S IS THE RESISTANCE DUE TO VISCOSITY, N IS THE NUMBER OF MOLECULES IN A UNIT VOLUME, T IS THE TEMPERATURE AND R = 8 3 × 10?7 IS THE GAS CONSTANT THESE RESULTS HAVE UNIVERSAL IMPORTANCE FOR OVER HALF OF A CENTURY OUR IDEAS ABOUT DI?USION WERE DETERMINED BY THESE LAWS THE MOST NATURAL MODEL OF DI?USION SEEMS TO BE THE SIMPLE SYMMETRIC RANDOM WALK ON THE D?DIMENSIONAL INTEGER LATTICE, ON ZD IN THIS MODEL THE MOVING PARTICLE, THE (RANDOM) WALKER LIVES ON THE VERTEX SET ZD AND MAKES STEPS OF UNIT LENGTH IN AXIAL DIRECTIONS WITH PROBABILITY P (X, Y) = 2D THE PROCESS IS DESCRIBED IN DISCRETE TIME, STEPS ARE MADE AT EVERY UNIT OF TIME THIS CLASSICAL MODEL IS AN INEXHAUSTIBLE SOURCE OF BEAUTIFUL QUESTIONS AND OBSERVATIONS THAT ARE USEFUL FOR SCIENCES, SUCH AS PHYSICS, ECONOMY AND BIOLOGY IT IS NATURAL TO ASK THE FOLLOWING QUESTIONS: 1 HOW FAR DOES THE WALKER GET IN N STEPS? 2 HOW LONG DOES IT TAKE TO COVER THE A DISTANCE R FROM THE STARTING POINT? 3 DOES THE WALKER RETURN TO THE STARTING POINT? 4 WHAT IS THE PROBABILITY OF RETURNING? 5 WHAT IS THE PROBABILITY OF RETURNING IN N STEPS? 6 WHAT IS THE PROBABILITY OF REACHING A GIVEN POINT IN N STEPS? THESE QUESTIONS ARE THE STARTING POINTS OF A NUMBER OF STUDIES OF RANDOM WALKS THERE ARE NUMEROUS GENERALIZATIONS OF THE CLASSICAL RANDOM WALK THE SPACE WHERE THE RANDOM WALK TAKES PLACE MAY BE REPLACED BY OTHER OBJECTS LIKE TREES, GRAPHS OF GROUP AUTOMORPHISM, WEIGHTED GRAPHS AS WELL AS THEIR RANDOM COUNTERPARTS FOR A LONG PERIOD OF TIME ALL THE RESULTS WERE BASED ON MODELS IN WHICH THE ANSWER TO THE ?RST QUESTION REMAINED THE SAME; IN N STEPS THE WALK TYPICALLY COVERS ?N DISTANCE LET US OMIT HERE THE EXCITING SUB?ELD OF RANDOM WALKS IN RANDOM ENVIRONMENTS WHERE OTHER SCALING FUNCTIONS HAVE BEEN FOUND (CF [58],[82]) THE ANSWER TO THE SECOND QUESTION IS VERY INSTRUCTIVE IN THE CASE OF SIMPLE SYMMETRIC RANDOM WALK ON ZD STARTING AT A GIVEN POINT, IT TAKES IN AVERAGE R2 STEPS TO LEAVE A BALL CENTERED AT THE STARTING POINT WITH RADIUS R WE ADOPT FROM PHYSICS LITERATURE THE PHRASE THAT IN SUCH MODELS WE HAVE THE R ?R2 SPACE–TIME SCALING THE DI?USION IN CONTINUOUS SPACE IS DESCRIBED BY THE HEAT DI?USION EQUA- TION ? ?TU = ?U, (1 1) WHICH HAS THE FOLLOWING DISCRETE COUNTERPART FOR RANDOM WALKS: PUN (X) = Y P (X, Y) UN (Y) = UN+1 (X) , WHERE P IS THE ONE STEP TRANSITION OPERATOR OF THE WALK OF COURSE, THIS CAN BE REWRITTEN BY INTRODUCING THE LAPLACE OPERATOR OF RANDOM WALKS ?= P ?I AND THE DI?ERENCE OPERATOR IN TIME ?NU = UN+1 ?UN USING THIS NOTATION WE HAVE THE DISCRETE HEAT EQUATION: ?NU = ?U (1 2)