A DIRECTIONAL ZERO-ONE LAW FOR FINITE-RANGE-DEPENDENT
RANDOM ENVIRONMENTS
a complete proof, written to be read straight through
CONTENTS
0. How to read this
1. The question
2. The model
3. The marking trick
4. Cuts
5. The regeneration law
6. Sign union
7. Finite mean width
8. Finite mean radius
9. Limiting rays, and reduction to a coordinate axis
10. Two tapes and common blocks
11. Exact-cut bridges and the width tail
12. Upper bound on contacts, by entropy
13. Lower bound on contacts, by posterior martingales
14. The contradiction, and the theorem
A. Two elementary lemmas used above
B. Index of notation
0. HOW TO READ THIS
Every statement below is proved here, or is a two line consequence of
something proved here. Nothing is imported from the literature except
the two classical inequalities collected in Appendix A.
The proof is long, but the plot is short.
- If the walker escaped upwards and also downwards with positive
probability, we could build two independent infinite paths, one
climbing, one descending, and lay them against each other.
- Those two paths must come close to each other, in a precise sense
("contacts"), about J/(log log J) times among the first J scales.
- An entropy computation says at most about J/log J times.
- J/(log log J) eventually beats J/log J, and both estimates are
honest, so coexistence is impossible.
Each of those two estimates is where the work is. Everything else is
machinery for manufacturing two genuinely independent paths inside a
dependent environment. That machinery is Section 3 and Section 4, and
it is the only genuinely new idea in the paper.
1. THE QUESTION
Picture a speck moving on a huge grid. At every site it looks at a set
of arrows drawn on the floor and picks one at random with the
probabilities written next to it. It steps that way, looks at the new
site's arrows, and repeats.
Two different kinds of randomness are in play. The walker rolls dice,
and the floor itself was drawn at random once and for all. The second
kind is what makes the problem hard: the same arrows are waiting
whenever the walker comes back, so the past never fully washes out.
A basic question: can the walker, with probability strictly between 0
and 1, drift off to infinity in a fixed direction? The answer is no.
That is the theorem. Escape in a direction is an all-or-nothing event.
This is not the same as asking for a law of large numbers, and not the
same as asking for a speed. It is only about whether escape happens at
all.
2. THE MODEL
2.1 The grid.
Fix a dimension d >= 3. Sites are the points of Z^d. The permitted
steps are the 2d coordinate unit vectors; write
U = { +e_1, ..., +e_d, -e_1, ..., -e_d }.
2.2 The environment.
The environment is a random function omega assigning to every site x and
every permitted step e a number omega(x, e) in [0, 1]. Read omega(x, e)
as the probability of stepping from x by e. Each row sums to one:
sum over e in U of omega(x, e) = 1.
The law of the whole random field omega is a fixed probability Q.
2.3 The walker.
Fix one environment omega. Then P_{x, omega} denotes the law of the
Markov chain that starts at x and at a site y jumps by e with
probability omega(y, e). Averaging over the environment gives the
annealed law
P_x = integral of P_{x, omega} with respect to Q.
Write X_0, X_1, X_2, ... for the positions of the walker. The number of
steps taken does not matter for us; only the positions do.
2.4 The three assumptions.
(i) Stationary and ergodic. Sliding the whole environment by any
lattice vector does not change Q. And every event that is
unchanged by all such slides has Q-probability 0 or 1.
(ii) Uniform ellipticity. There is a constant kappa > 0 with
Q{ omega(x, e) >= kappa for every site x and step e } = 1.
So no step is ever impossible, or even unlikely, uniformly in the
environment.
(iii) Finite range dependence. There is an integer R >= 0 with the
following property. If A and B are two sets of sites whose l_inf
distance is greater than R, then the rows at sites of A and the
rows at sites of B are independent. Here
dist_inf(A, B) = inf over a in A and b in B of
max over i of |a_i - b_i|,
and the requirement covers infinite sets A and B as well.
In words: far apart regions of the floor carry no information
about each other.
2.5 Escape in a direction.
Fix a nonzero vector v. Put
A_v = { v . X_n tends to +infinity as n grows }.
So A_v is the event that the walker eventually leaves every slab
perpendicular to v on the positive side, and never comes back.
2.6 The theorem.
Assume 2.4 (i), (ii), (iii). Then for every fixed nonzero v,
P_0(A_v) is either 0 or 1.
The direction v is chosen before the randomness is sampled, and it may
be irrational. Note what the theorem does not say: not that the walker
has a velocity, not that it moves at positive speed, not that limits of
X_n / |X_n| exist. Only that escape is all or nothing.
3. WHY THIS IS NOT AUTOMATIC, AND THE MARKING TRICK
3.1 The obstruction.
If all rows were independent, one could use classical regeneration:
after certain random times the walk forgets its past and continues as a
fresh independent copy of itself. With finite range dependence that is
false for two separate reasons.
- Two pieces of the path may be disjoint in space and still use rows
that are correlated, if the pieces pass within distance R.
- A piece of path we have already observed tells us something about
nearby rows, which a future piece may want to use.
So we need a way for the walker to travel a long distance using coin
flips that carry no environmental information at all. Then it ends up
surrounded by rows that are independent of everything seen so far. This
is an old idea of Comets and Zeitouni; what is new here is bookkeeping
the rows a path actually touched.
3.2 The marking.
Fix lambda > 0 with 2 lambda < kappa. Enrich each step with a mark, one
of 0, 1, *. Given the environment and the past, a step from x by e has
joint probabilities
P(x -> x+e, mark 0) = lambda,
P(x -> x+e, mark 1) = lambda,
P(x -> x+e, mark *) = omega(x, e) - 2 lambda.
These are nonnegative by 2 lambda < kappa, and they sum to omega(x, e).
So the marginal law of the walker is exactly the original one: we have
only added an extra independent coin flip to each step. A step marked 0
or 1 is chosen with a probability that does not depend on the
environment at all.
Call a law raw if no side condition is imposed on the walker.
3.3 Words, weights, and the rows a word uses.
A finite marked word gamma is a list of positions
x_0, x_1, ..., x_t
with consecutive differences in U, together with the mark of each of the
t steps. Two sets of positions matter:
Dep(gamma) = { x_0, ..., x_{t-1} }, the departure sites,
Act(gamma) = { x_j : 0 <= j < t and step j has mark * }.
Write p_omega(gamma) for the product of the marked transition
probabilities of the steps of gamma, and
W(gamma) = E_Q[ p_omega(gamma) ]
for the annealed probability of seeing exactly that marked word. By
stationarity W is unchanged when all positions of gamma are translated.
Only rows in Act(gamma) can appear in p_omega(gamma):
- a mark 0 or 1 contributes the constant lambda whatever the row says;
- the final arrival uses no row at all.
That is the whole point of the marks.
3.4 Lemma (separated weights).
Let gamma be a fixed finite marked word, and B a deterministic set of
sites with dist_inf(Act(gamma), B) > R. (If Act is empty there is
nothing to check.) Let f >= 0 be a function of the rows at sites of B.
Then
E_Q[ p_omega(gamma) f(omega) ] = W(gamma) E_Q[ f(omega) ].
Proof. The factor p_omega(gamma) is a function of the rows on
Act(gamma), or constant when Act is empty. Those rows are independent of
the rows on B by finite range dependence, and independence is exactly
the statement that the expectation of a product of a function of one and
a function of the other factorises. QED
3.5 Lemma (killing outside a set).
Let F be a deterministic set of sites. The law of the marked walk
stopped at its first arrival in F, including the arrival site, depends
only on the rows at sites outside F. Consequently the probability of any
event that forces the walker to avoid F forever also depends only on
rows outside F.
Proof. Before the first arrival the walker departs only from sites of
the complement of F, so every factor used so far is a row outside F,
including the factor of the arrival step itself. The stopped law is a
limit of stopping-prefix probabilities, which are determined by those
finitely many prefixes. An event that forbids entry into F is decided by
the killed trajectory: it is false on killed paths and keeps its meaning
on surviving ones. QED
One more remark, used constantly. Suppose two prescribed words have
departure sets at distance greater than R. Then their joint weight in a
common environment with conditionally independent walks equals the
product of their weights. Lemma 3.4 says exactly this, one factor at a
time. And it applies to a whole infinite continuation, not only to
finite words, because of Lemma 3.5.
4. CUTS
4.1 Setting.
Fix a nonzero direction v and rescale it so that |v|_inf = 1. Put
h(x) = v . x,
the height of x. Choose a coordinate step a_v in U with h(a_v) = 1;
this is possible exactly because |v|_inf = 1. Fix an integer
M > d R + 1
once and for all, the same M for every direction ever considered. Set
xi = lambda^M.
4.2 The script.
The script in direction v is this fixed sequence of M steps: take the
step a_v, M times in a row, the first of them marked 0 and the remaining
M-1 marked 1. The annealed probability of the script is
lambda * lambda^{M-1} = lambda^M = xi,
a constant, independent of the environment and of where the script is
used.
Two occurrences of the script cannot overlap in a step. The leading 0 of
a second copy would have to sit on a 1 of the first copy. This is the
only reason marks 0 and 1 are distinguished at all; it makes the cuts
below unambiguous.
4.3 Records, candidates, cuts.
Time 0 counts as a record. A time n > 0 is an ordinary record if h(X_n)
is strictly greater than each of h(X_0), ..., h(X_{n-1}). A candidate is
the endpoint of a script that started at a record. A candidate t is a
cut if from then on the walker never goes below it:
h(X_n) >= h(X_t) for every n >= t.
Every candidate is a strict record, because the M script steps raise the
height by M.
4.4 The gap, and why M is bigger than dR.
Two heights differ by at most d times the l_inf distance:
|h(x) - h(y)| <= d |x - y|_inf for all sites x, y. (4.1)
Suppose a marked prefix ends at a record of height r. Then every
departure of the prefix has height strictly below r. The script that
follows has no active departure at all, its steps being marked 0 and 1.
And a continuation that never drops below its own starting height r + M
departs only from sites of height at least r + M. By (4.1) and M > dR,
each such site is at l_inf distance greater than R from every active
departure of the prefix. So the continuation never uses a row that
correlates with the observed past.
4.5 The key identity.
Write
D_v = { h(X_n) >= 0 for every n >= 0 },
p_v = P_0(D_v),
Phat_v = P_0( . | D_v ), the nonbacktracking law.
Let gamma_0 be a fixed marked prefix ending at a record, and let B be any
event for a continuation, measured relative to the continuation's own
starting site. Then
P_0{ prefix gamma_0, then the script,
then a continuation in B that also lies in D_v }
= W(gamma_0) * xi * P_0( B and D_v ). (4.2)
The script contributes the constant xi. The continuation contributes a
factor that depends only on rows far from the active departures of
gamma_0, by 4.4. Lemma 3.4 factors the product. Stationarity identifies
the continuation factor with the unconditioned probability. QED
Reading (4.2) with B the whole space, the probability that the script
follows a record prefix and ends at a cut is exactly
xi * p_v. (4.3)
So a scripted cut is found with a uniformly positive conditional
probability, no matter what happened earlier, as long as p_v > 0.
4.6 The walker cannot sit still, and on D_v it must climb.
A walker inside a slab { a <= h <= b }, with a and b finite, leaves it
almost surely under every quenched law. Indeed take m > b - a; from any
site inside, m consecutive steps a_v leave the slab, and that has
probability at least kappa^m. Running independent trials in successive
blocks of m steps kills the chance of never leaving. It follows that
under Phat_v, which forbids negative heights, the walker cannot stay
forever below any fixed level b. So on D_v the height supremum is almost
surely infinite.
4.7 Slabs.
A finite marked word starting at 0 is a regeneration word, or slab, if
(i) all its heights are nonnegative,
(ii) it ends at a candidate,
(iii) every earlier candidate inside the word is undercut later inside
the word, meaning some subsequent height is strictly smaller.
Its width L is the height of its endpoint. Since the final script starts
at height L - M and every earlier height is below L,
L >= M, 0 <= h(x) < L for x in Dep,
h(x) < L - M for x in Act. (4.4)
The last inequality is the one that buys independence: all active rows
of a slab sit far below its endpoint.
5. THE REGENERATION LAW
5.1 The statement, and why it is the engine of everything.
If p_v > 0, the walker conditioned to stay nonnegative in height can be
chopped into independent identically distributed slabs. Each slab ends
where the next begins, and the future beyond a boundary is independent
of the past before it. In an iid environment this is the classical
Sznitman-Zerner regeneration. Here the proof uses the gap of 4.4 instead
of iid-ness.
5.2 Theorem (regeneration).
Fix a direction v with |v|_inf = 1 and suppose p_v > 0. Write nu_v for
the law that puts mass W(gamma) on each slab gamma.
(i) Under the raw law P_0, on the event that the height supremum is
infinite, there is a cut almost surely.
(ii) Under Phat_v there are infinitely many cuts. Counting time 0 as
an initial boundary, the relative marked words between
successive boundaries are iid with law nu_v, and they
concatenate to the whole path.
(iii) Under the raw law, conditional on a realised prefix through the
first cut, the translated suffix has law Phat_v.
Note that nu_v is a probability law: the masses W(gamma) over slabs sum
to one. That is part of what (ii) says, and it is proved, not assumed.
5.3 Proof of (i).
Test for a scripted cut starting at time 0. Failure of the test is
detected in finite time: either the next M steps are not the script, or
they are the script and the walker afterwards dips below the endpoint.
After a detected failure, wait until the height exceeds the maximum
attained up to the detection time, and test again. The successive test
starts are stopping times of the marked filtration.
At every test the conditional probability of success is exactly xi p_v,
by (4.3). So the probability that the first j tests all occur and all
fail is at most (1 - xi p_v)^j. If the height supremum is infinite, then
after every detected failure another test start eventually occurs. Let j
grow. QED
5.4 Proof of (ii), first cut.
Suppose gamma is a slab ending at height z. A path that begins with
gamma and then stays at or above height z has its first cut exactly at
the endpoint of gamma. Indeed all earlier candidates of gamma are
undercut inside gamma, so none of them is a cut; and the terminal
candidate is a strict record that is never undercut afterwards.
Conversely, a path that stays nonnegative in height up to its first cut
gives such a slab. For if an earlier candidate were not undercut before
the terminal record, it could not be undercut afterwards either, the
suffix staying above that record, and then it would already have been a
cut, contradicting the firstness.
Now apply (4.2) with B any event for a translated suffix:
P_0{ first-cut prefix is gamma, translated suffix in B }
= W(gamma) P_0( B and D_v ). (5.1)
Dividing by p_v = P_0(D_v) shows that under Phat_v the first slab has
mass W(gamma), and that the translated suffix has law Phat_v,
independent of the slab. There are only countably many finite marked
words, and by 4.6 the first cut is finite almost surely under Phat_v, so
the masses add up to one. This proves the first-cut part of (ii) and
also (iii).
5.5 Proof of (ii), iteration.
A cut is a strict record, so records of the translated suffix are also
records of the whole path. A script cannot straddle the boundary: it
would overlap the script that just ended, by 4.2. So the cuts of the
suffix are exactly the subsequent cuts of the whole path. Applying the
first-cut statement again to the suffix, and again, gives iid slabs.
Every slab is finite and contains at least M steps, so the boundaries
tend to infinity and the slabs cover the whole path. QED
5.6 Remark.
Nothing in 5.3-5.5 used the Markov property at a cut. A cut is selected
using the future, so it is not a stopping time, and pretending otherwise
is the standard way to get this proof wrong. Instead we enumerated
finite prefixes: (5.1) is a statement about fixed finite words gamma,
and only then did we divide.
6. SIGN UNION
6.1 The statement.
For every fixed nonzero v,
P_0(A_v) > 0 implies p_v > 0 and P_0(A_v or A_{-v}) = 1.
Moreover, when p_v > 0: infinite height supremum forces A_v, and finite
height supremum forces A_{-v}.
So in a fixed direction exactly one of three things happens: the walker
climbs, it descends, or it oscillates with bounded height range. The
third possibility is excluded.
6.2 Proof that on infinite supremum the walker climbs.
Assume p_v > 0 and suppose the height supremum is infinite. By 5.2 (i)
there is a first cut, and by 5.2 (iii) the translated suffix has the iid
slab law Phat_v. Under Phat_v the slab bases increase by at least M each
time, and inside a slab the walker never goes below its base. Each slab
is finite. So h(X_n) tends to +infinity. QED
6.3 Proof that finite supremum forces descent.
Fix integers m, b >= 0 and consider the event
E(m, b) = { h(X_n) <= m for all n, and h(X_n) >= -b infinitely often }.
From a visit to height at least -b, a run of m + b + 1 consecutive steps
a_v crosses height m, and that run has probability at least
kappa^{m+b+1} whatever the environment says. Take successive visit
trials at least m + b + 1 steps apart. The chance that the first j
trials all happen and all fail to cross m is at most
(1 - kappa^{m+b+1})^j, so E(m, b) is null. Taking the countable union
over m and b, finite supremum implies h(X_n) tends to -infinity. QED
6.4 Proof that a positive escape probability forces p_v > 0.
On A_v the heights tend to +infinity, so the global minimum of the
height sequence is attained at some finite time, say at time n at site x.
It follows that for some deterministic n >= 0 and some site x the event
{ X_n = x and h(X_{n+j}) >= h(x) for every j >= 0 }
has positive annealed probability. Let q_x(omega) be the quenched
probability, starting at x, of never dropping below height h(x). By the
Markov property at time n the displayed probability equals
E_Q[ P_{0, omega}(X_n = x) q_x(omega) ],
which is at most E_Q[ q_x ] = p_v by stationarity. Hence p_v > 0. QED
6.5 Remark.
6.4 is the only place where we convert a statement about escape into a
statement about nonbacktracking. It is cheap, and it is why we may
assume p_v > 0 from here on, without ever assuming anything about speed.
7. FINITE MEAN WIDTH
7.1 The statement.
For every direction v with |v|_inf = 1 and p_v > 0, the slab law nu_v
satisfies
E_{nu_v}[ L ] < infinity. (7.1)
That is, the typical slab does not rise an enormous distance.
7.2 Records, and why width is bounded by record count.
Let S(gamma) be the number of ordinary records inside the slab gamma,
not counting the initial boundary and counting the terminal record.
Every step changes the height by at most 1, so the running maximum can
increase by at most one per step. Hence S is at least the terminal
height:
L(gamma) <= S(gamma). (7.2)
Now the record indices of successive cuts, with index 0 at the initial
boundary, are sums of iid copies of S. For the terminal height of a slab
is the running maximum so far, so record counts simply concatenate
across boundaries.
7.3 A lower bound on the rate of cut indices.
For i >= 0 let rho_i be the time of the i-th ordinary record of the raw
walk, with rho_0 = 0 and rho_i = infinity if that record never comes.
Put
D'(v, i) = { rho_i < infinity and h(X_j) >= 0 for 0 <= j <= rho_i }.
A script starting at record i creates exactly M consecutive strict
records, so a cut of record index i + M occurs exactly when the prefix
realises D'(v, i), the script follows, and its suffix stays above its
endpoint. Summing (4.2) over the possible record prefixes and dividing
by p_v gives
Phat_v{ i + M is a cut index }
= xi P_0( D'(v, i) ) >= xi p_v. (7.3)
The inequality holds because on D_v the height supremum is infinite
almost surely by 4.6, so every ordinary record is reached and D'(v, i)
contains D_v.
7.4 Finishing.
Let N_rec(n) be the number of cut indices in {1, ..., n}. Averaging
(7.3) over i = 0, ..., n - M gives
liminf over n of E_{Phat_v}[ N_rec(n) ] / n >= xi p_v > 0. (7.4)
Suppose for contradiction that E_{nu_v}[ S ] = infinity. Then the
partial sums of iid copies of S, divided by their number, tend to
infinity almost surely: apply the strong law to min(S, K) for each
integer K and let K grow. Inverting these partial sums, the number of
cut indices below n divided by n tends to 0 almost surely. That ratio
lies in [0, 1], so bounded convergence gives the same limit for its
expectation, contradicting (7.4). Hence E S < infinity, and (7.2) gives
(7.1). QED
7.5 Remark.
The argument counts records rather than integer height levels, which is
why it works for irrational directions too: heights need not ever hit a
prescribed real number.
The estimate is about spatial width only. It says nothing about the time
a slab takes. Controlling the full spatial extent of a slab is the next
section, and it is the hardest single step of the proof.
8. FINITE MEAN RADIUS
8.1 The statement.
Say v is normalised if |v|_inf = 1. Define the radius of a slab gamma
with positions x_0, ..., x_m, written relative to x_0 = 0, by
R(gamma) = max over 0 <= j <= m of |x_j|,
the Euclidean norm of the farthest point the slab reaches.
Theorem. If P_0(A_v) > 0 and P_0(A_{-v}) > 0 for a normalised v, then
E_{nu_v}[ R ] + E_{nu_{-v}}[ R ] < infinity. (8.1)
8.2 Why this is the hard step, and what it buys.
Section 7 controlled a slab in the direction of travel. A slab could
still wander a mile sideways while rising one unit, and if it typically
did so, the opposed construction of Section 10 would be worthless: the
two paths would never be anywhere near each other and there would be no
contradiction to be had. So coexistence of up and down must force
sideways moderation. That is (8.1).
The proof is a contradiction that manufactures infinitely many disjoint
events of uniformly positive probability, which is absurd. The
manufacturing uses a large sideways excursion of one slab as a lever: it
produces a record for a cleverly tilted linear functional, and then we
append a separated opposite continuation that never rises above the
level already reached.
8.3 Notation for the proof.
Assume both p_v and p_{-v} are positive, which 6.1 gives. For a sign
sigma, meaning + or -, write sigma v for v or -v, and
P*_sigma = Phat_{sigma v}, E*_sigma its expectation,
L_i, R_i = width and radius of the i-th slab under P*_sigma,
H_0 = 0, H_k = L_1 + ... + L_k.
An unsubscripted L or R refers to one slab. Put p_* = min(p_v, p_{-v}).
8.4 The maximal inequality we need.
It is stated and proved in Appendix A.1. For a stationary sequence
Z_1, Z_2, ... of nonnegative integrable variables, and integers n >= 1
and a > 0,
P{ max over 1 <= k <= n of (Z_1 + ... + Z_k)/k > a }
<= E[ Z_1 ] / a. (8.2)
8.5 The truncated mean.
Suppose (8.1) fails, so at least one of the two expectations is
infinite. Put
I(t) = sum over sigma of E*_sigma[ min(R, t) ], t >= 0.
Then I is nondecreasing and unbounded, it is concave, I(0) = 0, and
I(t)/t tends to 0: the last because each slab has finite radius almost
surely, so dominated convergence applies to E min(R,t).
8.6 Choosing the constants.
By 7.1 and the strong law, pick c, C > 0 and C_0 >= 0 with
c k - C_0 <= H_k <= C k + C_0 for all k, (8.3)
with probability greater than 0.95 under each of the two sign laws.
Then choose, in this order: an integer C_1 >= 1, a real b > 1/c, a real
B > 1, and a real eta > 0, subject to
C_1 c > C + 4,
(B-1)/sqrt(d) - b (C + 2) > 2,
4 C_1 eta < 0.15. (8.4)
All of these are fixed numbers; none depends on the scale parameters a
and i_0 that come next.
8.7 The scale.
For a > 0 large, let N = N(a) be the least positive integer with
I(a N) >= eta a. It exists because I is unbounded, and N tends to
infinity as a grows because I(t)/t tends to 0. Minimality plus concavity
gives
eta a <= I(a N) <= (N/(N-1)) I(a(N-1)) < 2 eta a. (8.5)
8.8 A controlled initial segment.
Let J_m be the event that (8.3) holds up to m and
R_1 + ... + R_k <= a k for 1 <= k <= m.
Then for both signs and all large a,
P*_sigma( J_{C_1 N} ) > 0.8. (8.6)
Proof. Put n = C_1 N and truncate every radius at a n. The mean of a
truncated radius is at most I(a n) <= C_1 I(a N) < 2 C_1 eta a, where the
middle inequality is concavity of I. By (8.2) the probability that some
initial average of the truncated radii exceeds a is at most 2 C_1 eta.
Also
P*_sigma{ R_i > a n for some i <= n } <= n P*_sigma(R > a n)
<= E*_sigma[ min(R, a n) ] / a < 2 C_1 eta.
Together with (8.3), whose failure probability is below 0.05, and with
4 C_1 eta < 0.15, this gives (8.6). QED
8.9 A large sideways excursion after that segment.
Choose an integer i_0 so large that
sum over sigma and over i >= i_0 of P*_sigma( L > i ) < eta/(4B),
c(i-1) - C_0 >= c i / 2 for i >= i_0,
C(i-1) + C_0 + i <= (C+2) i for i >= i_0. (8.7)
The first is possible by 7.1. With i_0 now fixed, take a so large that
N >= i_0, that I(B a i_0) < eta a / 4, and that all previous large-a
requirements hold. For i_0 <= i <= N put
Exc_i = { R_i > B a i and L_i <= i },
Lambda_sigma = sum over i_0 <= i <= N of P*_sigma( Exc_i ).
We claim
eta/(2B) <= Lambda_+ + Lambda_- <= 2 eta. (8.8)
For the upper bound, integrate the decreasing tails:
sum over sigma, sum over 1 <= i <= N of P*_sigma( R > B a i )
<= I(B a N) / (B a) <= 2 eta,
because I(B a N) <= B I(a N) < 2 B eta a by concavity and (8.5).
For the lower bound, the same tail integration from i_0 to N gives at
least
( I(B a (N+1)) - I(B a i_0) ) / (B a) >= (3 eta a / 4) / (B a)
= 3 eta / (4B),
using I(B a (N+1)) >= I(a N) >= eta a and I(B a i_0) < eta a / 4.
Discarding the indices where the width L_i exceeds i costs less than
eta/(4B) by the first line of (8.7). That proves (8.8).
8.10 One index with a controlled past and a large excursion.
Pick a sign sigma with Lambda_sigma >= eta / (4B). Count the indices i in
[i_0, N] for which both J_{i-1} and Exc_i occur. Because the i-th slab is
independent of everything before it, each such index contributes with
probability at least 0.8 by (8.6), so the mean of the count is at least
0.8 Lambda_sigma. Its second moment is at most Lambda_sigma plus
Lambda_sigma squared, since the count is dominated by a sum of
independent indicators. Cauchy-Schwarz therefore gives
P*_sigma{ some i in [i_0, N] has J_{i-1} and Exc_i }
>= (0.8 Lambda_sigma)^2 / (Lambda_sigma + Lambda_sigma^2)
>= delta (8.9)
for a constant delta > 0 depending only on eta and B, hence only on the
environment law, not on a or i_0.
8.11 The tilted record.
Fix the realisation of 8.10 and write h(x) = sigma v . x. All positions
before slab i have norm at most a(i-1), because the radii of the first
i-1 slabs sum to at most a(i-1). Some position X inside slab i is at
distance more than B a i from the slab's start, so
|X| > B a i - a(i-1) > (B-1) a i.
Hence some coordinate step u in U has
u . X > (B-1) a i / sqrt(d),
because the Euclidean norm is at most sqrt(d) times the largest
coordinate.
During slab i the running maximum of h lies between H_{i-1} and H_i,
hence in [c i / 2, (C+2) i] by (8.3) and (8.7). Define the tilted
functional
Y(x) = u . x - b a h(x).
Before slab i we have h >= 0 and u . x <= a(i-1), so Y <= a(i-1). At X,
using (8.4),
Y(X) > (B-1) a i / sqrt(d) - b a (C+2) i > 2 a i.
So Y has a strict jump from at most a(i-1) to more than 2 a i, and
therefore attains a strict record somewhere inside slab i. At that
record the running height maximum lies in the fixed window
W = [ c i_0 / 2, (C+2) N ]. (8.10)
8.12 Packaging the record as a stopping time.
Let T be the first time n > 0 such that
- X_n is a strict record for Y,
- the running maximum of h up to time n lies in W,
- h(X_j) >= 0 for every 0 <= j <= n.
All three conditions concern the past only, so T is a stopping time of
the marked filtration. By 8.11 one of the 2d coordinate steps u works
with P*_sigma-probability at least delta/(2d). Fix that u. Translating
from P*_sigma back to the raw law,
P_0( T < infinity ) >= p_* delta / (2d). (8.11)
8.13 The separated opposite continuation.
Choose a coordinate step e with h(e) = -1. From X_T force m_0
consecutive steps e, all marked 0, where m_0 is a fixed positive integer
with
m_0 b > 1 + b C_0 + R d b + 1. (8.12)
The forced steps carry the constant weight lambda^{m_0} and reveal no
row. Write z = X_T + m_0 e. From z, run a fresh marked walk and ask for
the event
E_opp = { heights in direction -sigma v stay >= 0 from z on,
all cuts in that direction are finite, and the radius sums
of the opposite slabs obey the bound of J_{C_1 N} }.
By 5.2 and (8.6) the raw probability of E_opp is at least 0.8 p_*.
We now check that every position after the connector is at l_inf
distance greater than R from every position of the prefix up to T. Two
geometric estimates do it.
During opposite slab k+1, for 0 <= k < C_1 N, the displacement from z in
the u coordinate is at least -a(k+1) and the displacement in h is at
most -c k + C_0. So the total Y-increment from X_T, connector included,
is at least
m_0 (b a - 1) - a (k+1) + b a (c k - C_0)
= a ( m_0 b - 1 - b C_0 + (b c - 1) k ) - m_0. (8.13)
Since b c > 1 and (8.12) holds, this exceeds R(1 + d b a) uniformly in
k. Every prefix position has Y at most Y(X_T), and
|Y(x) - Y(y)| <= (1 + d b a) |x - y|_inf,
so the first C_1 N opposite slabs are strictly farther than R from the
prefix.
After those slabs the absolute height h is at most
(C+2) N - m_0 - c C_1 N + C_0 < -d R (8.14)
for large a, by (8.4). Everything after that stays at or below this
level, because the opposite walk is conditioned to stay below its own
starting height and the endpoint of the C_1 N-th slab is a cut in
direction -sigma v. The prefix has h >= 0, and
|h(x) - h(y)| <= d |x - y|_inf,
so the whole remaining tail is also farther than R from the prefix.
8.14 Why the weights factor, and the final probability.
Fix a finite marked prefix gamma realising the stopping time T, and let
A_gamma be the set of its positions. By 8.13 every path in E_opp avoids
the closed R-neighbourhood of A_gamma. So the quenched probability of
E_opp can be computed with the walk killed on first entry to that
neighbourhood, which by 3.5 uses only rows outside it. Those rows are
separated by more than R from the active departures of gamma. Lemma 3.4
therefore factors the weight, and stationarity identifies the
continuation factor with the raw probability from z:
weight of (gamma, connector, E_opp)
= W(gamma) lambda^{m_0} P_0( E_opp from z )
>= 0.8 p_* lambda^{m_0} W(gamma).
This is legitimate because gamma is fixed before Lemma 3.4 is used; no
independence is claimed for a randomly chosen region.
The connector lowers h and the continuation never rises above its own
start, so the final supremum of h along the whole path equals the
running supremum at T, which lies in W. Summing over the disjoint
prefixes realising T and using (8.11),
P_0{ sup over n of sigma v . X_n lies in W }
>= rho := 0.8 lambda^{m_0} p_*^2 delta / (2d) > 0. (8.15)
8.15 The contradiction.
The window W depends on a and i_0 through N = N(a) and through the
choice of i_0. Choose these successively so that the resulting windows
are pairwise disjoint: before choosing a new scale, push its lower
endpoint beyond the previous upper endpoint. Then (8.15) puts mass at
least rho in each of infinitely many disjoint events, one for each
window and each sign. Their total mass is at most 2, which is absurd.
Therefore (8.1) holds. QED
8.16 Remark.
Two features of this argument deserve to be named, because they are what
makes it work at finite range.
- The connector buys separation in the tilted functional Y, not in
the height h. In h alone the record could be at a level the
continuation wants to revisit. In Y the prefix is squeezed into a
half space far from where the continuation lives.
- The separation is verified for the actual infinite continuation,
not merely for a long finite piece, using the cut property in the
opposite direction. This is why 5.2 must include the infinite tail.
9. LIMITING RAYS, AND REDUCTION TO A COORDINATE AXIS
9.1 Lemma.
Under the hypotheses of 8.1 with v normalised, there are deterministic
unit vectors r_+ and r_- such that, for each sign,
|X_n| tends to infinity, and X_n / |X_n| tends to r_sigma
P_0-almost surely on A_{sigma v},
and r_+ . v > 0, r_- . v < 0, r_- = -r_+.
Proof. The mean displacement b'_sigma of one slab, taken in the
direction of travel, satisfies
b'_sigma . (sigma v) = E_{nu_{sigma v}}[ L ] > 0,
so b'_sigma is a nonzero vector. Under P*_sigma the k-th cut location
divided by k tends to b'_sigma almost surely, by the strong law applied
to iid slab displacements. Also R_k / k tends to 0 almost surely: for
each epsilon the probabilities P*_sigma(R_k > epsilon k) are summable by
(8.1), so Borel-Cantelli applies. Between two consecutive cuts the
displacement from the earlier cut is bounded by the next radius. Since
the number of completed slabs tends to infinity along the trajectory,
|X_n| tends to infinity and X_n/|X_n| tends to
r_sigma = b'_sigma / |b'_sigma|.
Under the raw law restricted to A_{sigma v}, the first cut is finite and
by 5.2 (iii) the translated suffix has law P*_sigma, so the same holds
there.
The two projections on v have opposite signs, so r_+ and r_- are
distinct. Suppose they are not opposite. Then w = r_+ + r_- is nonzero
and
w . r_+ = w . r_- = 1 + r_+ . r_- > 0.
By 6.1 the two escape events A_v and A_{-v} exhaust probability, so the
limiting rays force P_0(A_w) = 1. Rescale w to have l_inf norm one, so
that the machinery of Section 4 applies to direction w.
Under P*_w the limiting ray exists almost surely. Its value cannot
change if we delete finitely many slabs and translate what remains, so
it is a tail function of the iid slab sequence; the tail zero-one law
makes it deterministic. On the other hand, under the raw law, A_w has
probability one, so the first cut in direction w exists almost surely
and the translated suffix has law P*_w. The limiting ray of that suffix
must therefore equal the deterministic value almost surely. But the raw
walk follows the two distinct rays r_+ and r_- each with positive
probability. Contradiction. Hence r_- = -r_+. QED
9.2 Proposition (reduction to a coordinate axis).
If 0 < P_0(A_v) < 1 for some fixed nonzero v, then for some coordinate
index i,
P_0(A_{e_i}) > 0 and P_0(A_{-e_i}) > 0.
Proof. Normalise v. By 6.1 both signs of escape in direction v have
positive probability. By 9.1 the two limiting rays are exact opposites,
so some coordinate has opposite signs along them: it tends to +infinity
along one ray and to -infinity along the other. Each ray is followed
with positive probability. QED
To prove the theorem it therefore suffices, after permuting coordinates,
to rule out coexistence in the direction e_1. That is what Sections 10
to 14 do. From here on, v = e_1 and "height" means the first coordinate
x_1; the direction v is dropped from the notation.
10. TWO TAPES AND COMMON BLOCKS
# ^C interrupted by user!