Francoise J.-P., Naber G.L., Tsun T.S. (editors) Encyclopedia of Mathematical Physics
Подождите немного. Документ загружается.
obtained by Thoma (see Kerov (2003, 1998) and
Olshanski (2003)). Rephrased in our language, it
says that the functions
ðÞ¼s
j
p
1
¼1;p
k
¼
P
k
i
þð1Þ
kþ1
P
k
i
;k>1
are the extreme points of H(1). Here
i
and
i
are
parameters satisfying
1
2
0;
1
2
0
X
i
þ
i
1
This set is known as the Thoma simplex. The origin
i
=
i
= 0 corresponds to the Plancherel measure.
A general positive-def inite central functions on
S(1) defines a measure on the Thoma simplex. This
measure can be interpreted as a point pr ocess on the
real line, for example, by placing particles at
positions {
i
} and {
i
}. Interesting central func-
tions lead to interesting processes (see Olshanski
(2003)).
Second Example: Kingman Theorem
Let be a partition of the naturals N into disjoint
subsets. For any n = 1, 2, ..., defines the induced
partition
n
of {1, ..., n} and hence a partition (
n
)
of the number n. A measure M on partitions is
called exchangeable if
Mð
n
Þ¼ðð
n
ÞÞ; n ¼ 1; 2; ...
for some function on Y. This implies that is
harmonic for
K
ð; Þ¼
k
where = 1
1
2
2
and = 1
1
2
2
k
k
1
(k þ 1)
kþ1
þ1
. The description of all exchange-
able measures M was first obtained by Kingman.
In our language, it says that the extreme points of
H(
K
)are
ðÞ¼m
j
p
1
¼1; p
k
¼
P
k
i
;k>1
where m
is the monomial symmetric function (sum
of all monomials with exponents )and
i
are
parameters as before. The corresponding m easure
M
can be described as follows. Let X
i
be a
sequence of independent, identically distributed
random variables such that {
i
} are the measures
of atoms of their distribution. This defines a
random partition of N by putting i and j in the
same block of if and only if X
i
= X
j
.Ageneral
exchangeable measure M is then a convex linear
combination of M
, w hich can be viewe d as
making the common distribution of X
i
also
random. See Pitman (n.d.) for a lot more about
Kingman’s theorem.
The multiplicities
K
are gauge equivalent to
multiplicities
VP
ð; Þ¼k
k
½14
which arise in the study of probability measures on
virtual permutations S (Olshanski 2003). By definition,
S ¼ lim
SðnÞ
with respect to the maps S(n) ! S(n 1) that delete n
from the disjoint cycle decomposition of a permutation
2 S(n). For n 5, this is the unique map that
commutes with the right and left action of S(n 1).
Thus, S has a natural S(1) S(1) action; however, it
is not a group. A measure M on S is central if it is
invariant under the action of the diagonal subgroup in
S(1) S(1). Let the push-forward of M to S(n)give
mass () to a permutation with cycle type .Itisthen
easy to see that is harmonic with respect to [14].
Thus, Kingman’s theorem gives a description of
ergodic central measures on S. For example,
i
= 0
corresponds to the -measure at the identity.
Ergodic Method
A unified approach to this type of prob lems was
proposed and developed by Vershik and Ker ov. It is
based on the following ergodic theorem. Let be an
ergodic harmonic function. Then
ðÞ¼lim
dim
=
dim
; jj!1 ½15
for almost a ll with respect to the measure [13]
(Kerov 2003). This is similar to approximating a
Gibbs measure in infinite volume by a sequence of
finite-volume Gibbs measures wi th appropriate
boundary conditions. The ratio on the RHS of [15]
is known as the Martin kernel. Its asymptotics as
jj!1plays the essential role.
Let us call a sequence {(n)} of partitions of n
regular if the limit in [15] exists for all . For 1,
Vershik and Kerov proved that {(n)} is regular if
and only if the following limits exist:
ðnÞ
i
n
!
i
;
ðnÞ
0
i
n
!
i
½16
that is, if the rows and columns of (n), scaled by n,
have a limit. In this case, the limit in [15] is the
harmonic function with Thoma parameters
i
and
i
. This simultan eously proves Thoma classification
and gives a law of large numbers for the correspond-
ing measures [13]. It also gives a transparent
geometric interpretation of Thoma parameters.
Note that the behavior [16] is very different from
the formation of a smooth limit shape that we saw
earlier. For a common generalization of this result
and Kingman’s theorem see Kerov (1998).
352 Random Partitions
See also: Determinantal Random Fields; Growth
Processes in Random Matrix Theory; Integrable Systems
in Random Matrix Theory; Random Matrix Theory in
Physics; Symmetry Classes in Random Matrix Theory.
Further Reading
Aldous D and Diaconis P (1999) Longest increasing subsequences:
from patience sorting to the Baik–Deift–Johansson theorem.
Bulletin of the American Mathematical Society 36(4): 413–432.
Bakalov B and Kirillov A Jr. (2001) Lectures on Tensor
Categories and Modular Functors. University Lecture Series,
vol. 21. American Mathematical Society.
Deift P (2000) Integrable systems and combinatorial theory.
Notices of the American Mathematical Society 47(6): 631–640.
Jones G (1998) Characters and Surfaces: A Survey, The Atlas
of Finite Groups: Ten Years on (Birmingham, 1995),
London Mathematical Society Lecture Note Series, vol. 249,
pp. 90–118. Cambridge: Cambridge University Press.
Kazakov V (2001) Solvable Matrix Models, Random Matrices
and Their Applications, vol. 40. MSRI Publications;
Cambridge: Cambridge University Press.
Kerov S (2003) Asymptotic Representation Theory of the
Symmetric Group and its Applications in Analysis. American
Mathematical Society.
Kerov S, Okounkov A, and Olshanski G (1998) The boundary of
the Young graph with Jack edge multiplicities. International
Mathematics Research Notices 4: 173–199.
Macdonald IG (1995) Symmetric Functions and Hall Polyno-
mials. Oxford: Clarendon.
Mehta ML (1991) Random Matrices, 2nd edn. Boston, MA:
Academic Press.
Miwa T, Jimbo M, and Date E (2000) Solitons. Differential
Equations, Symmetries and Infinite-Dimensional Algebras.
Cambridge: Cambridge University Press.
Nakajima H and Yoshioka K (2003) Lectures on instanton
counting, math.AG/0311058.
Nekrasov N and Okounkov A (2003) Seiberg–Witten theory and
random partitions, hep-th/0306238.
Okounkov A (2002) Symmetric Functions and Random Partitions,
Symmetric Functions 2001: Surveys of Developments and
Perspectives, pp. 223–252, NATO Sci. Ser. II Math. Phys.
Chem., 74. (math.CO/0309074). Dordrecht: Kluwer Academic.
Olshanski G (2003) An introduction to harmonic analysis on the
infinite symmetric group, math.RT/0311369.
Okounkov A (2002) The uses of random partitions, math-ph/
0309015.
Pitman J (n.d.) Combinatorial Stochastic Processes, Lecture Notes
from St. Four Course, available from www.stat.berekeley.edu.
Sagan B (2001) The Symmetric Group. Representations, Combi-
natorial Algorithms, and Symmetric Functions. Graduate Texts
in Mathematics, 2nd edn., vol. 203, New York: Springer.
Stanley R (1999) Enumerative Combinatorics, II. Cambridge:
Cambridge University Press.
Witten E (1991) On quantum gauge theories in two dimensions.
Communications in Mathematical Physics 141(1): 153–209.
Woodward C (2004) Localization for the norm-square of the
moment map and the two-dimensional Yang–Mills integral,
math.SG/0404413.
Random Walks in Random Environments
L V Bogachev, University of Leeds, Leeds, UK
ª 2006 Elsevier Ltd. All rights reserved.
Introduction
Random walks provide a simple conventional model to
describe various transport processes, for example,
propagation of heat or diffusion of matter through a
medium (for a general reference see, e.g., Hughes
(1995)). However, in many practical cases, the medium
where the system evolves is highly irregular, due to
factors such as defects, impurities, fluctuations, etc. It is
natural to model such irregularities as ‘ ‘random
environment,’ ’ treating the observable sample as a
statistical realization of an ensemble, obtained by
choosing the local characteristics of the motion (e.g.,
transport coefficients and driving fields) at random,
according to a certain probability distribution.
In the random walks co ntext, such models are
referred to as ‘‘random walks in random environ-
ments’’ (RWRE). This is a relatively new chapter
in applied probability and physics of disordered
systems initiated in the 1970s. Early interest in
RWRE models was motivated by some problems
in biology, crystallography, and metal physics, but
later applications have spread through numerous
areas (see review papers by Alexander et al. (1981),
Bouchaud and Georges (1990), and a comprehensive
monograph by Hughes (1996)). After 30 years of
extensive work, RWRE remain a very acti ve area of
research, which has been a rich source of hard and
challenging questions and has already led to many
surprising discoveries, such as subdiffusive behavior,
trapping effects, locali zation, etc. It is fair to say that
the RWRE paradigm has become firmly established
in physics of random media, and its models, ideas,
methods, results, and general effects have become an
indispensable part of the standard tool kit of a
mathematical physicist.
One of the central problems in random media
theory is to establish conditions ensuring homogeniza-
tion, whereby a given stochastic system evolving in a
random medium can be adequately described, on some
spatial–temporal scale, using a suitable effective
system in a homogeneous (nonrandom) medium. In
particular, such systems would exhibit classical diffu-
sive behavior with effective drift and diffusion coeffi-
cient. Such an approximation, called ‘‘effective
medium approximation’’ (EMA), may be expected to
Random Walks in Random Environments 353
be successful for systems exposed to a relatively small
disorder of the environment. However, in certain
circumstances, EMA may fail due to atypical environ-
ment configurations (‘‘large deviations’’) leading to
various anomalous effects. For instance, with small but
positive probability a realization of the environment
may create ‘‘traps’’ that would hold the particle for an
anomalously long time, resulting in the subdiffusive
behavior, with the mean square displacement growing
slower than linearly in time.
RWRE models have been studied by various
nonrigorous methods inclu ding Monte Carlo simu-
lations, series expansions, and the renormal ization
group techniques (see more details in the above
references), but only a few models have been
analyzed rigorously, especially in dimensions greater
than one. The situation is much more satisfactory in
the one-dimensional case, where the mathematical
theory has matured and the RWRE dynamics has
been understood fairly well.
The goal of this article is to give a brief
introduction to the beautiful area of RWRE. The
principal model to be discussed is a random walk
with nearest-neighbor jumps in independent and
identically distributed (i.i.d.) random environment
in one dimension, although we sh all also comment
on some generalizations. The focus is on rigorous
results; however, heuristics will be used freely to
motivate the ideas and explain the approaches and
proofs. In a few cases, sketches of the proofs have
been included, which should help appreciate the
flavor of the results and methods.
Ordinary Random Walks: A Reminder
To put our exposition in perspective, let us give
a brief account of a few basic concepts and
facts for ordinary random walks, that is, evolving
in a nonrandom environment (see further details in
Hughes (1995)). In such models, space is modeled
using a suitable graph, for example, a d-dimensional
integer latti ce Z
d
, while time may be discrete or
continuous. The latter distinction is not essential,
and in this article we will mostly focus on the
discrete-time case. The random mechanism of
spatial motion is then determined by the given
transition probabilities (probabilities of jumps) at
each site of the graph. In the lattice case, it is usually
assumed that the walk is translation invariant, so
that at each step distribution of jumps is the same,
with no regard to the current location of the walk.
In one dimension (d = 1), the simple (nearest-
neighbor) random walk may move one step to right
or to the left at a time, with some probabilities p and
q = 1 p, respectively. An important assumption is
that only the current location of the walk determines
the random motion mechanism, whereas the past
history is not relevant. In terms of probability theory,
such a process is referred to as ‘‘Markov chain.’’ Thus,
assuming that the walk starts at the origin, its position
after n steps can be represented as the sum of
consecutive displacements, X
n
= Z
1
þþ Z
n
,
where Z
i
are independent random variables with the
same distribution P{Z
i
= 1} = p, P{Z
i
= 1} = q.
The strong law of large numbers (LLN) states that
almost surely (i.e., with probability 1)
lim
n !1
X
n
n
¼ EZ
1
¼ p q; P-a.s. ½1
where E denotes expectation (mean value) with respect
to P. This result shows that the random walk moves
with the asymptotic average velocity close to p q.It
follows that if p q 6¼0, then the process X
n
,with
probability 1, will ultimately drift to infinity (more
precisely, þ1 if p q > 0and 1 if p q < 0). In
particular, in this case, the random walk may return to
the origin (and in fact visit any site on Z) only finitely
many times. Such behavior is called ‘‘transient.’’
However, in the symmetric case (i.e., p = q = 0.5) the
average velocity vanishes, so the above argument fails.
In this case, the walk behavior appears to be more
complicated, as it makes increasingly large excursions
both to the right and to the left, so that
lim
n !1
X
n
= þ1, lim
n !1
X
n
= 1(P-a.s.). This
implies that a symmetric random walk in one dimen-
sion is ‘‘recurrent,’’ in that it visits the origin (and
indeed any site on Z) infinitely often. Moreover, it can
be shown to be ‘‘null-recurrent,’’ which means that the
expected time to return to the origin is infinite. That is
to say, return to the origin is guaranteed, but it takes
very long until this happens.
Fluctuations of the random walk can be char-
acterized further via the central limit theorem
(CLT), which amounts to saying that the probability
distribution of X
n
is asymptotically normal, with
mean n(p q) and variance 4npq:
lim
n!1
P
X
n
nðp qÞ
ffiffiffiffiffiffiffiffiffiffiffi
4npq
p
x
()
¼ ðxÞ:¼
1
ffiffiffiffiffiffi
2
p
Z
x
1
e
y
2
=2
dy ½2
These results can be extended to more general
walks in one dimensio n, and also to higher dimen-
sions. For instance, the criterion of recurrence for a
general one-dimensional random walk is that it is
unbiased, EðX
1
X
0
Þ= 0. In the two-dimensional
case, in addition one needs EjX
1
X
0
j
2
<1.In
higher dimensions, any random walk (which does
not reduce to lower dimension) is trans ient.
354 Random Walks in Random Environments
Random Environments and Random Walks
The definition of an RWRE involves two ingredi-
ents: (1) the environment, which is randomly chosen
but remains fixed throughout the time evolution,
and (2) the rando m walk, whose transition prob-
abilities are determined by the environment. The set
of environments (sample space) is denoted by
={!}, and we use P to denote the probability
distribution on this space. For each ! 2, we define
the random walk in the environment ! as the (time-
homogeneous) Markov chain {X
t
, t = 0, 1, 2, ...g on
Z
d
with certain (random) transition probabilities
pðx; y;!Þ¼P
!
fX
1
¼ yjX
0
¼ xg½3
The probability measure P
!
that determines the
distribution of the random walk in a given environ-
ment ! is referred to as the ‘‘quenched’’ law. We
often use a subindex to indicate the initial position
of the walk, so that, for example, P
!
x
{X
0
= x} = 1.
By averaging the quenched probability P
!
x
further,
with respect to the environment distribution, we
obtain the ‘‘annealed’’ measure P
x
= P P
!
x
, which
determines the probability law of the RWRE:
P
x
ðAÞ¼
Z
P
!
x
ðAÞ Pðd!Þ¼EP
!
x
ðAÞ½4
Expectation with respect to the annealed measure
P
x
will be denoted by E
x
.
Equation [4] implies that if some property A of the
RWRE holds almost surely with respect to the
quenched law P
!
x
for almost all environments (i.e.,
for all ! 2
0
such that P(
0
) = 1), then this property is
also true with probability 1 under the annealed law P
x
.
Note that the random walk X
n
is a Markov
chain only conditionally on the fixed environment
(i.e., with respect to P
!
x
), but the Markov property
fails under the annealed measure P
x
. This is because
the past history cannot be neglected, as it tells what
information about the medium must be taken into
account when averaging with respect to environ-
ment. That is to say, the walk learns more about
the environment by taking more steps. (This idea
motivat es the method of ‘‘environ ment viewed from
the pa rticle,’’ see related section below. )
The simplest model is the nearest-neighbor one-
dimensional walk, with transition probabilities
pðx; y;!Þ¼
p
x
if y ¼ x þ 1
q
x
if y ¼ x 1
0 otherwise
8
<
:
where p
x
and q
x
= 1 p
x
(x 2Z) are random vari-
ables on the probability space (, P ). That is to say,
given the environment ! 2, the random walk
currently at point x 2Z will make a one-unit step
to the right, with probability p
x
, or to the left, with
probability q
x
. Here the environment is determined
by the sequence of random variables {p
x
}. For most
of the article, we assume that the random probabil-
ities {p
x
, x 2Z} are i.i.d., which is referred to as
‘‘i.i.d. environment.’’ Some extensions to more
general environments will be mentioned briefly in
the sect ion ‘‘Some generali zations and variatio ns.’’
The study of RWRE is simplified under the follow-
ing natural condition called ‘‘(uniform) ellipticity:’’
0 < p
x
1 <1; x 2Z; P-a.s. ½5
which will be frequently assumed in the sequel.
Transience and Recurrence
In this section, we discuss a criterion for the RWRE
to be transient or recurrent. The following theorem
is due to Solomon (1975).
Theorem 1 Set
x
:= q
x
=p
x
, x 2Z, and := E ln
0
.
(i) If 6¼0 then X
t
is transient (P
0
-a.s.); moreover,
if <0 then lim
t !0
X
t
= þ1, while if >0
then lim
t !0
X
t
= 1 (P
0
-a.s.).
(ii) If = 0 then X
t
is recurrent (P
0
-a.s.); moreover,
lim
t !1
X
t
¼þ1; lim
t !1
X
t
¼1; P
0
-a.s.
Let us sketch the proof. Consider the hitting times
T
x
:= min {t 0:X
t
= x} and denote by f
xy
the
quenched first-passage probability from x to y:
f
xy
:¼P
!
x
f1 T
y
<1g
Starting from 0, the first step of the walk may be
either to the right or to the left, hence by the
Markov property the return probability f
00
can be
decomposed as
f
00
¼ p
0
f
10
þ q
0
f
1;0
½6
To evaluate f
10
, for n 1 set
u
x
u
ðnÞ
x
:¼P
!
x
fT
0
< T
n
g; 0 x n
which is the probability to reach 0 prior to n,
starting from x. Clearly,
f
10
¼ lim
n !1
u
ðnÞ
1
½7
Decomposition with respect to the first step yields
the difference equation
u
x
¼ p
x
u
xþ1
þ q
x
u
x1
; 0 < x < n ½8
with the boundary conditions
u
0
¼ 1; u
n
¼ 0 ½9
Random Walks in Random Environments 355
Using p
x
þ q
x
= 1, eqn [8] can be rewritten as
u
xþ1
u
x
¼
x
ðu
x
u
x1
Þ
whence by iterations
u
xþ1
u
x
¼ðu
1
u
0
Þ
Y
x
j¼1
j
½10
Summing over x and using the boundary conditions
[9] we obtain
1 u
1
¼
X
n1
x¼0
Y
x
j¼1
j
!
1
½11
(if x = 0, the product over j is interpreted as 1). In
view of eqn [7] it follows that f
10
= 1 if and only if
the right-hand side of eqn [11] tends to 0, that is,
X
1
x¼1
expðY
x
Þ¼1; Y
x
:¼
X
x
j¼1
ln
j
½12
Note that the random variables ln
j
are i.i.d., hence
by the strong LLN
lim
x !1
Y
x
x
¼ E ln
0
; P-a.s.
That is, the general term of the series [12] for large x
behaves like exp (x); hence, for >0 the condition
[12] holds true (and so f
10
= 1), whereas for <0it
fails (and so f
10
< 1).
By interchanging the roles of p
x
and q
x
, we also
have f
1, 0
< 1if>0 and f
1, 0
= 1if<0. From
eqn [6], it then follows that in both cases f
00
< 1,
that is, the random walk is transient.
In the critical case, = 0, by a general result from
probability theory, Y
x
0 for infinitely many x
(P-a.s.), and so the series in eqn [12] diverges.
Hence, f
10
= 1 and, similarly, f
1, 0
= 1, so by eqn [6]
f
00
= 1, that is, the random walk is recurrent.
It may be surprising that the critical parameter
appears in the form = E ln
0
, as it is probably
more natural to expect, by analogy with the
ordinary random walk , that the RWRE criterion
would be based on the mean drift, E(p
0
q
0
). In the
next section, we will see that the sign of d may be
misleading.
A canonical model of RWRE is specified by the
assumption that the random variables p
x
take only
two values, and 1 , with probabilities
Pfp
x
¼ g¼; Pfp
x
¼ 1 g¼1 ½13
where 0 <<1, 0 <<1. Here = (2 1)
ln (1 þ (1 2)=), and it is easy to see that, for
example, <0if<1=2, <1=2or>1=2,
>1=2. The recurrent region where = 0 splits into
two lines, = 1=2and = 1=2. Note that the first
case is degenerate and amounts to the ordinary
symmetric random walk, while the second one
(except where = 1=2) corresponds to Sinai’s
proble m (see the section ‘‘Sin ai’s local ization’’). A
‘‘phase diagr am’’ for this model, showing various
limiting regimes as a function of the parameters , ,
is presented in Figure 1.
Asymptotic Velocity
In the transient case the walk escapes to infinity,
and it is reasonable to ask at what speed. For a
nonrandom environment, p
x
p,theansweris
given by the LLN, eqn [1]. For the simple
RWRE, the asymptotic velocity was obtained by
Solomon ( 1975). Note that by Jensen’s inequality,
(E
0
)
1
E
1
0
.
Theorem 2 The limit v := lim
t !1
X
t
=t exists
(P
0
-a.s.) and is given by
v ¼
1 E
0
1 þ E
0
if E
0
< 1
1 E
1
0
1 þ E
1
0
if E
1
0
< 1
0 otherwise
8
>
>
>
>
>
<
>
>
>
>
>
:
½14
Thus, the RWRE has a well-defined nonzero
asymptotic velocity except when (E
0
)
1
1
E
1
0
. For instance, in the canonical example
eqn [13] (see Figure 1), the criterion E
0
< 1 for
the velocity v to be positive amounts to the
condition that both (1 )= and (1 )= lie on
the same side of point 1.
η < 0
υ
> 0
η
< 0
υ
= 0
η
> 0
υ
= 0
η
> 0
υ
< 0
α
1
2
α =
1
2
β =
1
β
0
1
Figure 1 Phase diagram for the canonical model, eqn [13].Inthe
regions where <0or>0, the RWRE is transient to þ1or 1,
respectively. The recurrent case, = 0, arises when = 1=2or
= 1=2. The asymptotic velocity := lim
t!0
x
t
=t is given by eqn
[14]. Adapted from Hughes BD (1996) Random Walks and Random
Environments. Volume 2: Random Environments, Ch. 6, p. 391.
Oxford: Clarendon, by permission of Oxford University Press.
356 Random Walks in Random Environments
The key idea of the proof is to analyze the hitting
times T
n
first, deducing results for the walk X
t
later.
More specifically, set
i
= T
i
T
i1
, which is the time
to hit i after hitting i 1 (providing that i > X
0
). If
X
0
= 0 and n 1, then T
n
=
1
þþ
n
. Note that
in fixed environment ! the random variables {
i
}are
independent, since the quenched random walk ‘ ‘for-
gets’ ’ its past. Although there is no independence with
respect to the annealed probability measure P
0
,one
can show that, due to the i.i.d. property of the
environment, the sequence {
i
} is ergodic and therefore
satisfies the LLN:
T
n
n
¼
1
þþ
n
n
! E
0
1
; P
0
-a:s:
In turn, this implies
X
t
t
!
1
E
0
1
; P
0
-a:s: ½15
(the clue is to note that X
T
n
= n).
To compute the mean value E
0
1
, observe that
1
¼ 1
fX
1
¼1g
þ 1
fX
1
¼1g
ð1 þ
0
0
þ
0
1
Þ½16
where 1
A
is the indicator of event A and
0
0
,
0
1
are, respectively, the times to get from 1 to 0 and
then from 0 to 1. Taking expectations in a fixed
environment !, we obtain
E
!
0
1
¼ p
0
þ q
0
ð1 þ E
!
0
0
0
þ E
!
0
1
Þ½17
and so
E
!
0
1
¼ 1 þ
0
þ
0
E
!
0
0
0
½18
Note that E
!
0
0
0
is a function of {p
x
, x < 0} and
hence is independent of
0
= q
0
=p
0
.Averagingeqn
[18] over the e nvironment and using E
0
0
0
= E
0
1
yields
E
0
1
¼
1 þ E
0
1 E
0
if E
0
< 1
1 if E
0
1
8
<
:
½19
and by eqn [15] ‘‘half’’ of eqn [14] follows. The
other half, in terms of E
1
0
, can be obtained by
interchanging the roles of p
x
and q
x
, whereby
0
is
replaced with
1
0
.
Let us make a few remarks concerning Theorems
1and2. First of all, note that by Jensen’s inequality
E ln
0
ln E
0
, with a strict inequality whenever
0
is nondegenerate. Therefore, it may be possible
that, with P
0
-probability 1, X
t
!1 but X
t
=t !0
(see Figure 1). This is quite unusual as compared
to the ordinary random walk (see the subsection
‘‘Ordinary random w alks: a reminder’’), and
indicates some kind of slowdown in the transient
case.
Furthermore, by Jensen’s inequality
E
0
¼ Ep
1
0
1 ðEp
0
Þ
1
1
so eqn [14] implies that if E
0
< 1, then
0 < v 2 Ep
0
1 ¼ E ðp
0
q
0
Þ
and the inequality is strict if p
0
is genuinely random
(i.e., does not reduce to a constant). Hence, the
asymptotic velocity v is less than the mean drift
E(p
0
q
0
), which is yet another evidence of slow-
down. What is even more surprising is that it is
possible to have E(p
0
q
0
) > 0but = E ln
0
> 0, so
that P
0
-a.s. X
t
!1(although with velocity v = 0).
Indeed, following Sznitman (2004) suppose that
Pfp
0
¼ g¼; Pfp
0
¼ g¼1
with >1=2. Then Ep
0
> 1=2if1>>
1=2, hence E( p
0
q
0
) = 2 Ep
0
1 > 0. On the
other hand,
E ln
0
¼ ln
1
þð1 Þln
1
> 0
if is sufficiently small.
Critical Exponent, Excursions, and Traps
Extending the previous analysis of the hitting times,
one can obtain useful information about the limit
distribution of T
n
(and hence X
t
). To appreciate
this, note that from the recursion eqn [16] it follows
s
1
¼ 1
fX
1
¼1g
þ 1
fX
1
¼1g
ð1 þ
0
0
þ
0
1
Þ
s
and, similarly to [17],
E
!
0
s
1
¼ p
0
þ q
0
E
!
0
ð1 þ
0
0
þ
0
1
Þ
s
Taking here expectation E, one can deduce that
E
0
s
1
< 1 if and only if E
s
0
< 1. Therefore, it is
natural to expect that the root of the equation
E
0
¼ 1 ½20
plays the role of a critical exponent responsible for
the growth rate (and hence, for the type of the limit
distribution) of the sum T
n
=
1
þþ
n
. In parti-
cular, by analogy with sums of i.i.d. random
variables one can expect that if >2, then T
n
is
asymptotically normal, with the standard scaling
ffiffiffi
n
p
, while for <2 the limit law of T
n
is stable
(with index ) under scaling n
1=
.
Alternatively, eqn [20] can be obtained from
consideration of excursions of the random walk.
Let T
L
11
be the left-excursion time from site 1, that is
the time to return to 1 after moving to the left at the
first step. If = E ln
0
< 0, then T
L
11
< 1 (P
0
-a.s.).
Fixing an environment !, let w
1
= E
!
1
T
L
11
be the
Random Walks in Random Environments 357
quenched mean duration of the excursion T
L
11
and
observe that w
1
= 1 þ E
!
0
1
, where
1
is the time to
get back to 1 after stepping to 0.
As a matter of fact, this representation and
eqn [19] imply that the annealed mean duration of
the left excursion, E
0
T
L
11
, is given by
Ew
1
¼
2
1 E
0
if E
0
< 1
1 if E
0
1
8
<
:
½21
Note that in the latter case (and bearing in mind <0),
the random walk starting from 1 will eventually drift to
þ1, thus making only a finite number of visits to 0,
but the expected number of such visits is infinite.
In fact, our goal here is to characterize the
distribution of w
1
under the law P. To this end,
observe that the excursion T
L
11
involves at least two
steps (the first and the last ones) and, possibly,
several left excursions from 0, each with mean time
w
0
= E
!
0
T
L
00
. Therefore,
w
1
¼ 2 þ
X
1
j¼1
q
j
0
p
0
ðjw
0
Þ¼2 þ
0
w
0
½22
By the translation invariance of the environment, the
random variables w
1
and w
0
have the same distribu-
tion. Furthermore, similarly to recursion [22],we
have w
0
= 2 þ
1
w
1
. This implies that w
0
is a
function of p
x
with x 1 only, and hence w
0
and
0
are independent random variables. Introducing the
Laplace transform (s) = E exp (sw
1
)andcondition-
ing on
0
,fromeqn [22] we get the equation
ðsÞ¼e
2s
Eðs
0
Þ½23
Suppose that
1 ðsÞas
; s !0
then eqn [23] amounts to
1 as
þ¼ð1 2s þ Þð1 as
E
0
þÞ
Expanding the product on the right, one can see that
a solution with = 1 is possible only if E
0
< 1, in
which case
a ¼ Ew
1
¼
2
1 E
0
We have already obtained this result in eqn [21].
The case <1 is possible if E
0
= 1, which is
exactly eqn [20]. Returning to w
1
, one expects a
slow decay of the distribution tail,
Pfw
1
> tgbt
1=
; t !1
In particular, in this case the anneal ed mean
duration of the left excursion appears to be infinite.
Although the above considerations point to the
critical parameter , eqn [20], which may be
expected to determine the slowd own scale, they
provide little explanation of a mechanism of the
slowdown phenomenon. Heuristically, it is natural
to attribute the slowdown effects to the presence of
‘‘traps’’ in the environment, which may be thought
of as regions that a re easy to enter but hard to leave.
In the one-dimensional case, such a trap would
occur, for example, between two long series of
successive sites where the probabilities p
x
are fairly
large (on the left) and small (on the right).
Remarkably, traps can be characterized quantita-
tively with regard to the properties of the random
environment, by linking them to certain large-
deviation effects (see Sznitman (2002, 2004)). The
key role in this analysis is played by the function
F(u ):= ln E
u
0
, u 2R. Suppose that = E ln
0
< 0
(so that by Theorem 1 the RWRE tends to
þ1, P
0
-a.s.) and also that E
0
> 1 and E
1
0
> 1
(so that by Theorem 2, v = 0). The latter means that
F(1) > 0 and F(1) > 0, and since F is a smooth
strictly convex function and F(0) = 0, it follows that
there is the second root 0 <<1, so that F() = 0,
that is, E
0
= 1 (cf. eqn [20]).
Let us estimate the probability to have a trap in
U = [ L, L] wher e the RWRE will spend anoma-
lously long time. Using eqn [11], observe that
P
!
1
fT
0
< T
Lþ1
g1 expfLS
L
g
where S
L
:= L
1
P
L
x = 1
ln
x
!<0asL !1.
However, due to large deviations S
L
may exceed
level >0 with probability
PfS
L
>g expfLIðÞg; L !1
where I(x):= sup
u
{ux F(u)} is the Legendre trans-
form of F. We can optimize this estimate by
assuming that L ln n and minimizing the ratio
I()=. Note that F(u) can be expressed via the
inverse Legendre transform, F(u) = sup
x
{xu I(x)},
and it is easy to see that if := min
>0
I()=, then
F() = 0, so is the second (positive) root of F.
The ‘‘left’’ probability P
!
1
{T
0
< T
L1
} is esti-
mated in a similar fashion, and one can deduce that
for some constants K > 0, c > 0, and any
0
>, for
large n
P P
!
0
max
kn
jX
k
jK ln n
c
n
0
That is to say, this is a bound on the probability to
see a trap centered at 0, of size ln n, whi ch will
retain the RWRE for at least time n.Itcanbe
shown that, typically, there will be many such traps
bothin[n
0
, 0] and [0, n
0
], which will essential ly
358 Random Walks in Random Environments
prevent the RWRE from moving at distance n
0
from the origin be fore time n. In particular, it
follows that lim
n !1
X
n
=n
0
= 0forany
0
>,so
recalling that 0 <<1, we have indeed a sublinear
growth of X
n
. This result is more informative as
compared to Theorem 2 (the case v = 0), and it
clarifies the role of traps (see more details in
Sznitman (2004)). The nontrivial behavior of the
RWRE on the pre cise growth scale, n
,ischar-
acterized in the next section.
Limit Distributions
Considerations in the previous section suggest that
the exponent , defined as the solution of eqn
[20], characterizes environments in terms of dura-
tion of left excursions. These heuristic arguments
are confirmed by a limit theorem by Kesten et al.
(1975), which specifies the slowdown scale. We
state here the most striking part of their result.
Denote ln
þ
u := max { ln u, 0}; by an arithmetic
distribution one means a probability law on R
concentrated on the set of points of the form
0, c, 2c, ....
Theorem 3 Assume that 1 = E ln
0
< 0
and the distribution of ln
0
is nonarithmetic
(excluding a possible atom at 1). Suppose that
the root of eqn [20] is such that 0 <<1 and
E
0
ln
þ
0
< 1. Then
lim
n!1
P
0
fn
1=
T
n
tg¼L
ðtÞ
lim
t!1
P
0
ft
X
t
xg¼1 L
ðx
1=
Þ
where L
() is the distribution function of a stable
law with index , concentrated on [0, 1).
General information on stable laws can be found
in many probability books; we only mention here
that the Laplace transform of a stable distribution
on [0, 1) with index has the form (s) =
exp { Cs
}.
Kesten et al. (1975) also consider the case 1.
Note that for >1, we have E
0
< (E
0
)
1/
¼ 1, so
v > 0 by eqn [14]. For exampl e, if >2 then, as
expected (see the previous section), there exists a
nonrandom
2
> 0 such that
lim
n !1
P
0
T
n
n=v
ffiffiffi
n
p
t
¼ðtÞ
lim
t !1
P
0
X
t
tv
v
3=2
ffiffi
t
p
x
¼ðxÞ
Let us describe an elegant idea of the proof based
on a suitable renewal structure. (1) Let U
n
i
(i n)be
the number of left excursions starting from i up to
time T
n
, and note that T
n
= n þ 2
P
i
U
n
i
. Since the
walk is transient to þ1, the sum
P
i0
U
n
i
is finite
(P
0
-a.s.) and so does not affect the limit. (2) Observe
that if the environment ! is fixed then the condi-
tional distribution of U
n
j
, given U
n
jþ1
, ..., U
n
n
= 0, is
the same as the distribution of the sum of 1 þ U
n
jþ1
i.i.d.
random variables V
1
, V
2
, ...,eachwithgeo-
metric distribution P
!
0
{V
i
= k} = p
j
q
k
j
(k = 0, 1, 2, ...).
Therefore, the sum
P
n
i = 1
U
n
i
(read from right to
left) can be represented as
P
n 1
t = 0
Z
t
,whereZ
0
=
0, Z
1
, Z
2
, ... is a branching process (in random
environment {p
j
}) with one immigrant at each step
and the geometric offspring distribution with parameter
p
j
for each particle present at time j. (3) Consider
the successive ‘‘regeneration’ ’ times
k
,atwhich
the process Z
t
vanishes. The partial sums
W
k
:=
P
k
t<
kþ1
Z
t
form an i.i.d. sequence, and the
proof amounts to showing that the sum of W
k
has a
stable limit of index . (4) Finally, the distribution of
W
0
can be approximated using M
0
:=
P
1
t = 1
Q
n 1
j = 0
j
(cf. eqn [11] ), which is the quenched mean number of
total progeny of the immigrant at time t = 0. Using
Kesten’s renewal theorem, it can be checked that
P{M
0
> x} Kx
as x !1,soM
0
is in the domain
of attraction of a stable law with index ,andthe
result follows.
Let us emphasize the significance of the regenera-
tion times
i
. Returning to the original random
walk, one can see that these are times at which the
RWRE hits a new ‘‘record’’ on its way to þ1, never
to backtrack again. The same idea plays a crucial
role in the analysis of the RWRE in higher
dimen sions (see the sub sections ‘‘Zero–on e laws
and LLNs’’ and ‘‘Kalikow ’s condition and Sznit man’s
condit ion (T
0
)’’).
Final ly, note that the condit ion 1<0
allows P{p
0
= 1} > 0, so the distribution of
0
may
have an atom at 0 (and hence ln
0
at 1). In view
of eqn [20] , no atom is possible at þ1. The
restriction for the distribution of ln
0
to be
nonarithmetic is important. This will be illustrated
in the section ‘‘Diode model ,’’ where we discu ss the
model of random diodes.
Sinai’s Localization
The results discussed in the previous section indicate
that the less transient the RWRE is (i.e., the critical
exponent decreasing to zero), the slower it moves.
Sinai (1982) proved a remarkable theorem showing
that for the recurrent RWRE (i.e., with
= E ln
0
= 0), the slowdown effect is exhibited in
a striking way.
Random Walks in Random Environments 359
Theorem 4 Suppose that the environment {p
x
} is
i.i.d. and elliptic, eqn [5] , and assume that
E ln
0
= 0, with P{
0
= 1} < 1. Denote
2
:= E ln
2
0
,0<
2
< 1. Then there exists a function
W
n
= W
n
(!) of the random environment such that
for any ">0
lim
n!1
P
0
2
X
n
ln
2
n
W
n
>"
¼ 0 ½ 24
Moreover, W
n
has a limit distribution:
lim
n!1
P W
n
x
fg
¼ GðxÞ½25
and thus also the distribution of
2
X
n
= ln
2
n under
P
0
converges to the same distribution G(x).
Sinai’s theorem shows that in the recurrent case, the
RWRE considered on the spatial scale ln
2
n becomes
localized near some random point (depending on the
environment only). This phenomenon, frequently
referred to as ‘‘Sinai’s localization,’’ indicates an
extremely strong slowdown of the motion as com-
pared with the ordinary diffusive behavior.
Following Re´ve´sz (1990), let us explain heuristi-
cally why X
n
is measured on the scale ln
2
n. Rewrite
eqn [11] as
P
!
1
fT
n
< T
0
g¼ 1 þ
X
n1
x¼1
expðY
x
Þ
!
1
½26
where Y
x
is defined in eqn [12]. By the CLT, the
typical size of jY
x
j for large x is of order of
ffiffiffi
x
p
, and
so eqn [26] yields
P
!
1
fT
n
< T
0
g expf
ffiffiffi
n
p
g
This suggests that the walk started at site 1 will
make about exp {
ffiffiffi
n
p
} visits to the origin before
reaching level n. Therefore, the first passage to
site n takes at least time exp {
ffiffiffi
n
p
}. In other
words, one may expect that a typical displace-
ment after n steps will be of order of ln
2
n (cf. eqn
[24]). This argument also indicates, in the spirit
of the trapping mechanism of slowdown discussed
at the end of the section ‘‘Critical exponent,
excursions, a nd traps,’’ th at there i s typically a
trap of size ln
2
n, which retains the RWRE until
time n.
It has been shown (independently by H Kesten
and A O Golosov) that the limit in [25] coincides
with the distribution of a certain functional of the
standard Brownian motion, with the density
function
G
0
ðxÞ¼
2
X
1
k¼0
ð1Þ
k
2k þ 1
exp
ð2k þ 1Þ
2
2
8
jxj
()
Environment Viewed from the Particle
This important technique, dating back to Kozlov
and Molchanov (1984) , has proved to be quite
efficient in the study of random motions in random
media. The ba sic idea is to focus on the evolution of
the environment viewed from the current position of
the walk.
Let be the shift operator acting on the space of
environments ={!} as follows:
! ¼fp
x
g7!
! ¼fp
x1
g
Consider the process
!
n
:¼
X
n
!; !
0
¼ !
which describes the state of the environment from
the point of view of an observer moving along with
the random walk X
n
. One can show that !
n
is a
Markov chain (with respect to both P
!
0
and P
0
), with
the transition kernel
Tð!; d!
0
Þ¼p
0
!
ðd!
0
Þþq
0
1
!
ðd!
0
Þ½27
and the respective initial law
!
or P (here
!
is the
Dirac measure, i.e., unit mass at !).
This fact as it stands may not seem to be of any
practicaluse,sincethestate space of this Markov
chain is very c omplex. However, the great advan-
tage is that one can find an explicit invariant
probability Q for the kernel T (i.e., such that
QT = Q), which is absolutely continuous with
respect to P.
More specifically, assume that E
0
< 1 and set
Q = f (!)P, where (cf. eqn [14])
f ¼ v ð1 þ
0
Þ
X
1
x¼0
Y
x
j¼1
j
v ¼
1 E
0
1 þ E
0
½28
Using independence of {
x
}, we note
Z
Qðd!Þ¼Ef ¼ð1 E
0
Þ
X
1
x¼0
ðE
0
Þ
x
¼1
hence Q is a probability measure on . Furthermore,
for any bounded measurable function g on we
have
QTg ¼
Z
Tgð!ÞQðd!Þ¼EfTg
¼ E fp
0
ðg Þþq
0
ðg
1
Þ
¼ E g ðp
0
f Þ
1
þðq
0
f Þ
½29
360 Random Walks in Random Environments
By eqn [28],
ðp
0
f Þ
1
¼ vp
1
ð1 þ
1
Þ
X
1
x¼0
Y
x
j¼1
j1
¼ v 1 þ
0
X
1
x¼0
Y
x
j¼1
j
!
¼ v þ
0
1 þ
0
f
and similarly
ðq
0
f Þ ¼v þ
1
1 þ
0
f
So from eqn [29] we obtain
QTg ¼ E ðgf Þ¼
Z
gð!Þ Qðd!Þ¼Qg
which proves the invariance of Q.
To illustrate the environment method, let us
sketch the proof of Solomon’s result on the
asymptotic velocity (see Theorem 2). Set d (x, !):=
E
!
x
(X
1
X
0
) = p
x
q
x
. Noting that d(x, !) =
d(0,
x
!), define
D
n
:¼
X
n
i¼1
dðX
i1
;!Þ¼
X
n
i¼1
dð0;
X
i1
!Þ
Due to the Markov property, the process M
n
:=
X
n
D
n
is a marting ale with respect to the natural
filtration F
n
= {X
1
, ..., X
n
} and the law P
!
0
,
E
!
0
½M
nþ1
jF
n
¼M
n
; P
!
0
-a.s.
and it has bounded jumps, jM
n
M
n1
j2. By
general results, this implies M
n
=n !0(P
!
0
-a.s.).
On the other hand, by Birkhoff’s ergodic
theorem
lim
n!1
D
n
n
¼
Z
dð0;!Þ Qðd!Þ; P
0
-a.s.
The last integral is easily evaluated to yield
Eðp
0
q
0
Þf ¼ vE
X
1
x¼0
Y
x
j¼1
j
ð1
0
Þ
¼ vð1 E
0
Þ
X
1
x¼0
ðE
0
Þ
x
¼v
and the first part of the formula [14] follows.
The case E
0
1 can be handled using a
comparison argument (Sznitman 2004). Observe
that if p
x
~
p
x
for all x then for the corresponding
random walks we have X
t
~
X
t
(P
!
0
- a.s.). We now
define a suitable dominating random medium by
setting (for >0)
~
p
x
:¼
p
x
1 þ
þ
1 þ
p
x
Then E
~
0
= Eq
0
=(p
0
þ ) < 1if is large enough,
so by the first part of the theorem, P
!
0
- a.s.,
lim
n !1
X
n
n
lim
n!1
~
X
n
n
¼
1 E
~
0
1 þ E
~
0
½30
Note that E
~
0
is a continuous function of with
values in [0, E
0
] 3 1, so there exists
such that
E
~
0
attains the value 1. Passing to the limit in
eqn [30] as "
, we obtain lim
n !1
X
n
=n 0
(P
!
0
- a.s.). Similarly, we get the reverse inequality,
which proves the second part of the theorem.
A more prominent advantage of the environment
method is that it naturally leads to statements of CLT
type. A key step is to find a function H(x, t, !) =
x vt þ h(x, !) (called ‘‘harmonic coordinate’’) such
that the process H(X
n
, n, !) is a martingale. To this
end, by the Markov property it suffices to have
E
!
X
n
HðX
nþ1
; n þ 1;!Þ¼HðX
n
; n;!Þ; P
!
0
-a.s.
For (x, !):= h(x þ 1, !) h(x, !) this condition
leads to the equation
ðx;!Þ¼
x
ðx 1;!Þþv 1 þð1 þ vÞ
x
If E
0
< 1 (so that v > 0), there exists a bounded
solution
ðx;!Þ¼v 1 þ 2v
X
1
k¼0
Y
k
i¼0
xi
and we note that (x, !) =(0,
x
!) is a stationary
sequence with mean E(x, !) = 0. Finally, setting
h(0, !) = 0 we find
hðx;!Þ¼
X
x1
k¼0
ðk;!Þ; x > 0
X
x
k¼1
ðk;!Þ; x < 0
8
>
>
>
>
<
>
>
>
>
:
As a result, we have the representation
X
n
nv ¼ HðX
n
; n;!ÞþhðX
n
;!Þ½31
For a fixed !, one can apply a suitable CLT for
martingale differences to the martingale term in eqn
[31], while using that X
n
nv (P
0
-a.s.), the second
term in eqn [31] is approximated by the sum
P
nv
k = 0
(k, !), which can be handled via a CLT for stationary
sequences. This way, we arrive at the following result.
Theorem 5 Suppose that the environment is
elliptic, eqn [5], and such that E
2þ"
0
< 1 for some
">0(which implies that E
0
< 1 and hence v > 0).
Then there exists a nonrandom
2
> 0 such that
lim
n!1
P
0
X
n
nv
ffiffiffiffiffiffiffiffi
n
2
p
x
¼ ðxÞ
Random Walks in Random Environments 361