Random Walk in Random and Non-Random Environments

The following sections are included:

• Preface to the First Edition

• Preface to the Second Edition

• Preface to the Third Edition

• Contents

• Introduction

The following sections are included:

• Notations
  • General notations
  • Notations to the increments
  • Notations to the Strassen-type theorems
  • Notations to the local time

• Abbreviations

The following sections are included:

• Random walk

• Dyadic expansion

• Rademacher functions

• Coin tossing

• The language of the probabilist

The following sections are included:

• Exact distributions

• Limit distributions

The following sections are included:

• Recurrence

• The zero-one law

The following sections are included:

• Borel–Cantelli lemma and Markov inequality

• The strong law of large numbers

• Between the strong law of large numbers and the law of iterated logarithm

• The LIL of Khinchine

The following sections are included:

• Definitions

• EFKP LIL

• The laws of Chung and Hirsch

• When will S_n be very large=

• A theorem of Csáki

The following sections are included:

• Four lemmas

• Joining of independent random walks

• Definition of the Wiener process

• Invariance Principle

The following sections are included:

• Long head-runs

• The increments of a Wiener process

• The increments of S_N

The following sections are included:

• The theorem of Strassen

• Strassen theorems for increments

• The rate of convergence in Strassen's theorems

• A theorem of Wichura

The following sections are included:

• Exact distributions

• Limit distributions

• Definition and distribution of the local time of a Wiener process

The following sections are included:

• An invariance principle

• A theorem of Lévy

The following sections are included:

• Strong theorems for ξ(x, n) and ξ(n)

• Increments of η(x, t)

• Increments of ξ(x, n)

• Strassen type theorems

• Stability

The following sections are included:

• On the distribution of the zeros of a random walk

• Local time and the number of long excursions (Mesure du voisinage)

• Local time and the number of high excursions

• The local time of high excursions

• How many times can a random walk reach its maximum?

The following sections are included:

• Favourite sites

• Rarely visited sites

The following sections are included:

• On the Wiener sheet

• The theorem

• Applications

The following sections are included:

• On the location of the maximum of a random walk

• On the location of the last zero

• The Ornstein–Uhlenbeck process and a Darling–Erdős theorem

• A discrete version of the Itô formula

Please refer to the full text

Please refer to the full text

This chapter is devoted to proving the RECURRENCE THEOREM (Pólya, 1921)…

Let W₁(t), W₂(t),…, W_d(t) be a sequence of independent Wiener processes. The Rd valued process W(t) = {W₁(t), W₂(t),…,W_d(t)} is called a d-dimensional Wiener process. We ask how the random walk S_n can be approximated by W(t). The situation is very simple if d = 2…

At first we present the analogue of the LIL of Khinchine of Section 4.4…

The following sections are included:

• ξ(0, n) in ℤ²

• ξ(n) in ℤ^d

• A few further results

The following sections are included:

• The strong law of large numbers

• CLT, LIL and Invariance Principle

• Wiener sausage

The following sections are included:

• The number of heavy points

• Heavy balls

• Heavy balls around heavy points

• Wiener process

It is easy to see (and Theorem 21.1 also implies) that the path of a random walk crosses itself infinitely many times for any d ≥ 1 with probability 1. We mean that there exists an infinite sequence {U_n, V_n} of positive integer valued r.v.'s such that S(U_n) = S(U_n + V_n), and 0 ≤ U₁ < U₂ < …, (n = 1, 2, …). However, we ask the following question: will self-crossings occur after a long time?s For example, we ask whether the crossing S(U_n) = S(U_n + V_n) will occur for every n = 1, 2, … if we assume that V_n converges to infinity with a great speed and U_n converges to infinity much slower. In fact Erdős and Taylor (1960/B) proposed the following two problems…

The following sections are included:

• Completely covered discs centered in the origin of ℤ²

• Completely covered disc in ℤ² with arbitrary centre

• Almost covered discs centred in the origin of ℤ²

• Discs covered with positive density in ℤ²

• Completely covered balls in ℤ^d

• Large empty balls

• Summary of Chapter 24

The following sections are included:

• Long excursions in ℤ²

• Long excursions in high dimension

Theorem 19.5 on the rate of escape suggests that the sphere { x: ||x|| = R } is crossed about R times by the random walk if R is big enough and d ≥ 3. In fact if ||S_n|| = √n for every n then Σ_x∈Z(R) ξ(x , ∞) = O(R) where…

The following sections are included:

• On the Dirichlet problem

• DLA model

• Percolation

Please refer to the full text

The sequence {S_n} of Part I was considered as a mathematical model of the linear Brownian motion. In fact it is a model of the linear Brownian motion in a homogeneous (non-random) environment…

In this chapter we study what might have happened during the creation of the Universe, i.e. the possible properties of the sequence ε are investigated…

The following sections are included:

• The recurrence theorem of Solomon

• Guess how far the particle is going away in an RE

• A prediction of the Lord

• A prediction of the physicist

The following sections are included:

• Two further lemmas on the environment

• On the local time ξ(0, n)

In this chapter we investigate the properties of the sequence ξ(n) = max_k ξ(k,n). A trivial result can be obtained as…

The following sections are included:

• Two theorems of Golosov

• Non-nearest-neighbour random walk

• RWIRE in ℤ^d

• Non-independent environments

• Random walk in random scenery

• Random environment and random scenery

• Reinforced random walk

In Parts I–III we studied random walks in Euclidean lattices. In the last few years some strong interest has been shown in random walks in different graphs. In this Part we consider simple random walks on a few different graphs. Let G = {V, E} be a graph where V is the set of the vertices of G and E is the set of the edges of G. Let d(υ) (υ ∈ V) be the degree of υ, 0 ∈ V be a fixed element of V…

The following sections are included:

• Definitions and legend

• Approximation

• Extremes of a comb-walk

• Local time of a comb-walk

• Large square covered by a comb-random-walk

The following sections are included:

• Comb with crosslines

• A question on a brush with crossings

Let G = G_N = (V_N , E_N) be a graph where…

A half-plane-half-comb (HPHC) is a graph G = (V, E) where V = ℤ² and the vertices v₁ = (x₁, y₁), v₂ = (x₂, y₂) are joined by an edge e ∈ E if…

The following sections are included:

• References

• Author Index

• Subject Index