35166a5 e30e2f3
================================================================================
ESCAPE IN ONE DIRECTION
the directional zero-one law for random walks in random environments
a complete account, written to be readable by a high school student
================================================================================
This file is plain text on purpose. It must be readable without LaTeX,
without a browser and without a lecturer. Every symbol is defined when it
first appears. Section 15 is a glossary, section 16 lists every result, and
section 17 is a one-page summary of the whole proof.
Results are numbered in the order they appear: L for lemma, P for
proposition, T for theorem. So [L5] is the fifth result, a lemma; [P9] is
the ninth, a proposition. Constants named C, C_0, C_1, c, b, B, eta are
just fixed positive numbers; each one is chosen once and never changes.
================================================================================
0. THE SHORT VERSION
================================================================================
0.1 The question.
A walker stands at the origin of the 3-dimensional grid. At every site of
the grid there are 6 arrows, one to each neighbour, and each arrow carries a
probability; the 6 numbers at a site add up to 1. The whole field of arrows
was drawn once at random, site by site, independently, and then left alone.
The walker takes one step at a time, always using the arrow probabilities of
the site he is standing on. He never sees the numbers; he only feels them.
Fix a direction, say north. Let A be the event that the walker's shadow on
the north arrow drifts off to plus infinity and never comes back. Question:
how big can the probability of A be?
0.2 The answer.
It is 0 or it is 1. Never 1/2, never 1/3, never 0.9999. For every fixed
direction, "the walker escapes that way" is decided for the environment, not
by a coin flip. That is [T1], the main theorem of this file.
0.3 Why that is not obvious.
At first sight a coin flip seems easy to build: imagine that half the
environments have a strong north wind near the origin and half have a strong
south wind. Conditioned on a north wind, the walker leaves north. But the
event A is not "the environment has a north wind near the origin". It is
"the walker, walking forever in this one environment, ends up going north
forever". The walker keeps returning to sites he has already used, so his
future depends on what he learned from the past; the walker and the
environment are entangled. Showing that no such entanglement can manufacture
a genuine coin flip is the whole problem.
0.4 The shape of the proof.
1. Regeneration. The walk can be cut into independent, identically
distributed pieces ("slabs"). This is [L5].
2. One sign or the other. Almost surely the walker escapes in one of
the two opposite directions. This is [L7].
3. Both signs at once => the pieces are small in space, not just in
height. This is [P9].
4. Two rays must be geometrically opposite, so we may work in a
coordinate direction. This is [P10].
5. Put one north-going copy of the walk (read from its top down) and one
south-going copy on the same ruler. They must touch often. Then:
- contacts are rare by an information (entropy) budget: [P14];
- contacts are frequent by a martingale (posterior) estimate: [P19].
The two bounds contradict each other.
0.5 What is new.
All of this works in every dimension d >= 3, for independent environments,
assuming only that every arrow probability is strictly positive. No common
lower bound on the arrows is assumed: a site may have one direction at
0.999999 and the others at 0.0000002. An earlier counterexample by Bramson,
Zeitouni and Zerner shows that independence cannot be dropped even in
uniformly elliptic environments; see section 3.3.
================================================================================
1. THE MODEL
================================================================================
1.1 The grid.
Fix an integer d >= 3. The set of sites is Z^d, the integer points of
d-dimensional space. Let e_1,...,e_d be the unit steps along the axes. The
neighbours of a site x are the 2d sites x + e and x - e. Write
U = { e_1, ..., e_d, -e_1, ..., -e_d },
so U is the set of allowed steps and |U| = 2d.
1.2 Arrows.
At each site x there is a row of numbers
p_x(e), e in U, p_x(e) >= 0, sum over e in U of p_x(e) = 1.
p_x(e) is the probability that the walker, standing at x, steps by e. Think
of p_x as a 2d-sided die kept at site x.
1.3 How the environment is chosen, and strict ellipticity.
Let mu be a probability measure on the set of allowed rows. The environment
is a random assignment, site by site, of rows with law mu; different sites are
independent. We write P (blackboard bold P in the original) for this law on
environments, and E for its expectation.
HYPOTHESIS (strict ellipticity, equation (1.1) of the original):
mu{ p : p(e) > 0 for every e in U } = 1.
In words: with probability 1 a row has all 2d entries strictly positive.
Two remarks that matter.
(i) There is NO common positive lower bound. The hypothesis only says
that each individual entry is positive with probability 1. It allows
entries that are tiny, and it allows the size of the smallest entry to
vary from site to site with no control at all. This is the whole
difficulty. "Uniform ellipticity" would mean p(e) >= eps for one
fixed eps > 0 and all sites; we do not assume that.
(ii) Because there are only countably many sites and countably many
steps, one null set can be removed once and for all, outside which
every site has every entry strictly positive. So statements of the
form "for almost every environment, every site has all entries
positive" are legitimate.
1.4 The walk, quenched and annealed.
The walk starts at the origin and uses the rows: the walker's position X_n
satisfies X_0 = 0 and, given the environment and the past,
Prob( X_{n+1} = X_n + e ) = p_{X_n}(e).
For a fixed environment we get a Markov chain; its law is the quenched law,
written P_{x,omega} when the environment is omega and the walker starts at x.
Averaging over the environment gives the annealed law:
P_x(B) = integral over environments of P_{x,omega}(B) dP(omega),
with expectation E_x. If both the environment and the path matter, use the
joint law P_x(d omega, dX) = P(d omega) P_{x,omega}(dX). All probabilities in
this file are annealed unless the word "quenched" appears.
1.5 Directions, shadows and escape.
Let v be any nonzero vector in R^d, for example v = e_1 (north). Its shadow
functional is the linear function
h(x) = x . v,
the dot product. "The walker's shadow grows" means h(X_n) grows.
The escape event in direction v is
A_v = { h(X_n) = X_n . v tends to plus infinity }.
Two warnings.
* A_v is stronger than "the walker goes to infinity". A walker who swings
around in a huge spiral goes to infinity but does not escape any single
direction. A_v says: after some time the shadow is always past any level
and never dips back below it.
* The direction v may be any real vector, not only a coordinate axis. The
theorem is stated for every nonzero real v, and the proof never rounds v
to a rational direction.
1.6 Words and their weights.
A finite word is a sequence gamma = (x_0, x_1, ..., x_m) of sites with
x_{j+1} - x_j in U. Its departure set is
Dep(gamma) = { x_0, ..., x_{m-1} },
the sites the walker steps out of. The last site x_m is an arrival, not a
departure, unless the word visits it earlier and leaves it.
The annealed weight of the word is
W(gamma) = E [ product over j=0..m-1 of p_{x_j}(x_{j+1} - x_j) ].
Because the rows are independent and the word uses each site once per visit,
this is exactly the annealed probability that the walker begins with gamma:
W(gamma) = P_{x_0}( X_1 = x_1, ..., X_m = x_m ).
Translation invariance of the environment law gives W(gamma + z) = W(gamma)
for any fixed shift z: the weight depends on the shape of the word only.
1.7 Three worked examples of weights.
Take d = 2 for these examples, v = e_1, and write
q = E p_0(e_1) (average chance of stepping north)
r = E p_0(-e_1) (average chance of stepping south).
(a) gamma = (0, e_1, 2e_1). Two departures, at 0 and at e_1, which are
different sites. Hence the two rows are independent and
W = q * q = q^2.
(b) gamma = (0, e_1, 0). Departures at 0 and e_1, still different sites,
W = q * r. Note that W(gamma) is NOT the probability of returning,
because the return step is at the site e_1, whose row is independent of
the row at 0.
(c) gamma = (0, e_1, 2e_1, e_1, 2e_1). Here site 2e_1 is departed from
twice. Its row is ONE random variable, and it enters the product
squared. So
W = E [ p_0(e_1) p_{e_1}(e_1) p_{2e_1}(-e_1) p_{2e_1}(e_1) ]
= q^2 E [ p_0(-e_1) p_0(e_1) ],
which cannot be written as a product of averages. Revisits create
correlations between the factors. Every delicate step in this file is
a bookkeeping of exactly this phenomenon.
1.8 Where the difficulty lives.
Because revisits correlate factors, one cannot simply multiply averages.
The engine that repairs this is [L2] in section 5: at places where the word
uses only rows it has never used, the factors DO multiply. The whole proof
is a careful arrangement of the walk so that the rows needed are either
fresh (then multiply) or cheap (then pay a bounded price).
================================================================================
2. THE THEOREM
================================================================================
T1 (main theorem; Theorem 1.1 of the original).
Let d >= 3. Let the environment be independent and identically distributed
at different sites and strictly elliptic, as in 1.3. Let v be any nonzero
vector in R^d. Then
P_0(A_v) is either 0 or 1.
2.1 What T1 does not say.
* It does not say which directions have probability 1. Whether the answer
for north is 0 or 1 depends on the environment law and is a hard question
in general (it is the question of the limiting velocity). T1 says only
that the answer is never a coin flip.
* It does not give a speed. Nothing here proves that the walker moves at a
linear rate, and no moment of the time between regeneration cuts is
obtained.
* It does not claim one exceptional null set works for all directions at
once. The theorem is a statement about each fixed direction separately,
and the proof never needs a uniform null set.
2.2 Why the sign-union law is weaker.
The classical statement is about the union of the two signs:
P_0( A_v union A_-v ) = 1,
"the walker escapes in one of the two opposite directions". That union
statement allows 50-50 splits between v and -v and is much older; see 3.1.
T1 is the sharper statement about one sign alone.
2.3 Equivalent ways to say T1.
* The event A_v is trivial for the annealed measure: its probability does
not see the randomness of the environment at all.
* There is no annealed coupling in which the walker flips an independent
coin to decide whether to escape north.
* The two-sided statement "P(A_v) is not in (0,1)" is exactly the
statement "no direction is half-possible".
================================================================================
3. HISTORY, AND WHY EACH HYPOTHESIS IS THERE
================================================================================
3.1 The sign-union law.
Kalikow (1981) proved the zero-one law for the union of the two signs in
uniformly elliptic environments, and posed the directional question. The
extension of the union law to strictly elliptic environments is due to Zerner
and Merkl (2001, Proposition 3), recalled as equation (1) of Zerner (2007).
3.2 Dimension two.
Zerner and Merkl (2001, Theorem 1) proved the one-sign directional law in
dimension d = 2 for independent strictly elliptic environments; Zerner (2007)
gave a shorter proof. In the plane, two paths that go in opposite directions
must cross by geometry, and crossing is what forces the contradiction. In
higher dimensions two paths can dodge each other, and a quantitative
replacement for crossing is needed. That replacement is section 11-12.
Slonim (2024, Theorem 2.1) extended the planar law to bounded jumps, under
the assumption that almost surely there is a unique infinite communicating
class reachable from every site.
3.3 Higher dimensions, and why independence is needed.
Berger (2008, Theorem 1.1) proved that in dimensions d >= 5 an independent
uniformly elliptic walk has at most one nonzero limiting velocity. That
leaves room for a second velocity equal to ZERO, and a zero velocity does not
rule out escaping in two opposite directions at sublinear speed. So Berger's
theorem does not settle T1.
Bramson, Zeitouni and Zerner (2006, Theorem 3) built STATIONARY, polynomially
mixing, uniformly elliptic environments in d >= 3 in which linear escape in
two opposite directions both happen with positive probability. Their Open
Problem 3 is the higher-dimensional question for independent uniformly
elliptic environments. Consequence for us: independence is not decoration.
The proof below uses independence at exactly one place: the rows at distinct
sites are independent, which is what [L2] needs.
3.4 A special non-uniformly elliptic class.
If each row is Dirichlet distributed, Sabot and Tournier (2011, Theorem 1)
get positive-probability transience in coordinate directions with positive
mean drift. Bouchet (2013, Corollary 4) proved the fixed-direction zero-one
law in that class for d >= 3 by an accelerated walk and an invariant law for
the environment viewed from the particle. Tournier (2015, Corollary 1)
identified the asymptotic direction with the initial drift when it is
nonzero. All of these use reversal identities special to Dirichlet rows.
The argument in this file uses arbitrary strictly positive rows and only
translations of its path pieces.
3.5 Other tools.
Sznitman and Zerner (1999) introduced the regeneration structure used in
section 6. Simenhaus (2007, Proposition 1) proved that two distinct
deterministic asymptotic directions occurring with positive probability must
be opposite; his existence theorem assumes transience on an open set of
directions. Drewitz and Ramirez (2010, Theorem 1.8) gave a two-ray
description under sign-union transience on an open set. Those hypotheses do
not follow from a single-direction assumption, so section 8-9 proves what is
needed, self-contained: first the rays, then their antipodality.
================================================================================
4. THE TOOLBOX (AND A PROMISE THAT IT IS ENOUGH)
================================================================================
You need six tools. Each is stated here in one line, with the precise
version in Appendix A.
(1) Conditioning and the Markov property. "Given the present, the future
of a Markov chain does not depend on the past." The quenched version
is the strong Markov property, valid at stopping times.
(2) Stopping times. A time T is a stopping time if the event {T <= n} is
decided by X_0,...,X_n. The strong Markov property applies at stopping
times. Crucially, a time defined using the FUTURE (such as "the first
record that is never undercut") is NOT a stopping time, and we will
never pretend otherwise. The repair is [L5], an exact factorization of
weights instead of a Markov property.
(3) Martingales and Ville's inequality. A martingale is a process whose
expected future value equals its present value. Ville's inequality is
the maximal inequality for nonnegative martingales; it turns "expected
size" into "probability of a big maximum". Used once, in [L17].
(4) The strong law of large numbers, and Borel-Cantelli. Averages of
independent identically distributed variables converge; and if events
have summable probabilities, only finitely many of them occur.
(5) Renewal processes. If you drop points on the line at independent
identically distributed distances, the number of points up to h is
about h divided by the mean distance. Used for the widths of slabs.
(6) Entropy, and relative entropy. Entropy measures how many yes/no
questions are needed to describe a random object; relative entropy
measures the price of pretending the object has a different law.
Used once, in section 11. A high school summary:
- if a variable is uniform on N outcomes, its entropy is log N;
- if it is concentrated, its entropy is smaller;
- swapping the true law for a wrong law costs, per observation,
the relative entropy; if the wrong law gives an event much smaller
probability than the true law, then the event's probability is
bounded by the price divided by the logarithm of the ratio.
The last sentence is the only place where entropy becomes a
probabilistic bound; it is the "binary divergence" step in 11.6.
Everything else in this file is walking, records and arithmetic.
================================================================================
5. THE ENGINE: FRESH ROWS
================================================================================
5.1 The problem, again.
A word's weight is an expectation of a product. A product of expectations is
not the expectation of the product, unless the factors are independent. The
factors are the rows at the departure sites. So if we can guarantee that the
rows used by a piece of walk are distinct sites never used by the other
pieces, then the weights multiply, and the annealed computation becomes
exactly a product of annealed weights.
5.2 L2 (transfer through unused departure rows).
Let gamma = (x_0,...,x_m) be a finite word, let Dep(gamma) be its departure
set, and let f(omega) be a nonnegative function of the rows outside
Dep(gamma). Then
E [ ( product over j<m of p_{x_j}(x_{j+1}-x_j) ) f ] = W(gamma) E[f].
Consequently: two words whose departure sets are disjoint have joint annealed
weight W(gamma_1) W(gamma_2), whether we sample them independently or sample
them conditionally independently in one shared environment.
PROOF. The product in the expectation depends only on the rows in
Dep(gamma). Those rows are independent of the rows outside Dep(gamma), and
f depends only on the rows outside. So the expectation factors into
E[product] * E[f] = W(gamma) E[f]. For two words, conditional independence
in a shared environment makes the joint quenched weight the product of the
quenched weights, and the identity above factors its expectation.
The identity has one more face that we will need in section 12. Suppose a
second walk is stopped the first time it enters Dep(gamma). A stopped walk
never uses the row of the site where it stops, because it does not step out of
that site. Hence every event of the stopped walk is a function of the rows
outside Dep(gamma), including the event that the stopping time is infinite.
So the identity applies with f equal to any indicator of a stopped-walk event.
5.3 The one rule of the whole proof.
Apply [L2] FIRST, and classify SECOND.
This sounds like a slogan, so here is the trap it avoids. Suppose we want to
use [L2] with f equal to an indicator of some event that depends on the
environment in a way we can only describe after seeing the other walk. Then f
is not a function of "rows outside Dep(gamma)" alone and the identity is false.
The proof therefore always does the following, in this order:
step 1: write the probability as an integral of unclassified path weights
over path pairs;
step 2: apply [L2] to factor those weights;
step 3: only then, inside the shared environment, classify sites by
quenched quantities such as exit probabilities.
Sections 11 and 12 each perform this three-step dance once. Both times the
phrase "the transfer is made before the classification" is doing real work.
================================================================================
6. RECORDS, TRUE CUTS AND SLABS
================================================================================
The plan of this section is the following. The walker's shadow (the height h)
climbs. We single out the times when the walker sets a new all-time high, and
then the special highs that are never undercut afterwards: the true cuts. The
pieces of walk between two true cuts turn out to be independent and
identically distributed. That is the regeneration structure. It is the only
structural fact about the walk used in the entire proof.
6.1 Heights, records, and the non-backtracking event.
Fix a nonzero direction v in R^d and normalize it so that
||v||_infinity = 1,
i.e. at least one coordinate of v has absolute value 1. Then for any step e
in U we have h(e) = e . v in [-1,1], and there is a step a in U with
h(a) = +1 and a step with h(a) = -1.
Define the non-backtracking event in direction v:
D_v = { h(X_n) >= 0 for all n >= 0 },
p_v = P_0(D_v),
P_hat_v = P_0( . | D_v ) when p_v > 0.
So D_v is the event that the walker never goes below its starting shadow.
Note h(X_0) = 0, so D_v is an event about the future only.
The ordinary strict records are the times
rho_0 = 0,
rho_{i+1} = the first time n > rho_i with h(X_n) > h(X_{rho_i}),
and all later times are set to infinity if one is infinite. So rho_1 is the
first time the shadow exceeds 0, rho_2 the first time it exceeds that, and so
on.
A finite record time rho_i, i >= 1, is a TRUE CUT if
h(X_n) >= h(X_{rho_i}) for every n >= rho_i.
Truth of a cut depends on the future after the cut, so it is NOT measurable at
time rho_i, and rho_i is not a stopping time at which we may apply the Markov
property. Everything is repaired by weight factorization, in [L5] below.
When true cuts exist, list them in increasing order as tau_1, tau_2, ...
6.2 L3 (finite height supremum).
Almost surely under P_0,
sup over n of h(X_n) < infinity implies h(X_n) tends to minus infinity.
In particular a finite height interval cannot contain the walk forever. The
same holds from every translated starting site, and holds quenched for almost
every environment simultaneously for all starting sites.
Idea of the proof: a path that stays below b and does not run away downwards
must visit the strip [-k,b] infinitely often. The strip meets each line of
sites parallel to the step a only finitely often, so either some fixed site is
visited infinitely often, or infinitely many different lines are involved. In
both cases we get infinitely many opportunities to try a fixed "script" of m
upward steps, and each attempt has a chance bounded below. In the second case
the rows used by the script are brand new, so the chance is exactly q_a^m for
a number q_a > 0 that does not depend on the site or on the environment. That
is where strict ellipticity without a uniform lower bound is enough.
PROOF. Fix integers b and k >= 0, a step a in U with h(a) = 1, and an integer
m > b + k. It is enough to rule out
E_{b,k} = { h(X_n) <= b for all n, and h(X_n) >= -k infinitely often }.
Regard the lattice as a pile of parallel lines (columns) in direction a: the
sets x + Z a. Along such a line the height changes by exactly 1 at each
site, so a line contains only finitely many sites with height in [-k,b].
Case 1: only finitely many lines are visited at height >= -k. Then on E_{b,k}
some fixed site x with height in [-k,b] is visited infinitely often. Fix an
environment whose entries are all positive. At every visit to this ONE site,
the quenched probability of the script "take m steps a" is
q_x(omega) = product over j=0..m-1 of p_{x+ja}(a) > 0,
a fixed positive number, because the product is finite and all factors are
positive. Take as trials the first visit, then the first visit at least m
steps after the preceding trial. These are stopping times. By the quenched
strong Markov property, r trials are finite and all fail with probability at
most (1 - q_x(omega))^r. Infinity many visits give infinitely many trials,
and a successful script crosses above b. So the event has quenched
probability zero. Averaging over countably many x and countably many (b,k)
handles case 1. Note that we never needed a bound on q_x(omega) that is
uniform in x or in omega.
Case 2: infinitely many lines are visited at height >= -k. For each line,
take its first visit to the part of the line at height >= -k; those eligibility
decisions are visible in the path prefix. Take as trial starts the first
eligible time, and then each next eligible time at least m steps after the
previous trial start. At an eligible time every earlier visit in the same line
was at height below -k, so the m scripted departure sites, all at height at
least -k, are distinct and have never been used before. Conditional on any
fixed eligible prefix, those m rows therefore keep their original independent
laws, and the annealed conditional probability of the script is exactly
q_a^m, where q_a = E p_0(a) > 0.
Strict ellipticity gives q_a > 0; it does not give a lower bound for
p_x(a) for a single x. Again r trials fail with probability at most
(1 - q_a^m)^r, so infinitely many trials succeed, and the script crosses above
b. So case 2 is null too.
The union over b and k proves the implication, because a path with finite
height supremum that does not tend to minus infinity lies in E_{b,k} for some
b and k. Translation handles other starting sites. For the quenched
statement, integrate the quenched probabilities of the null events and
intersect over countably many starting sites and integer levels.
6.3 L4 (a positive chance of escape gives a positive non-backtracking
chance).
If P_0(A_v) > 0 then p_v = P_0(D_v) > 0.
PROOF. On A_v the heights tend to plus infinity, so they have a global
minimum. Hence A_v is contained in the countable union over n >= 0 and x in
Z^d of
{ X_n = x, and h(X_{n+k}) >= h(x) for every k >= 0 }.
One of these events has positive probability. Put
q_v(x,omega) = P_{x,omega}( h(X_k) >= h(x) for every k >= 0 ).
For a deterministic time n the quenched Markov property gives
E [ P_{0,omega}(X_n = x) q_v(x,omega) ] > 0,
so E q_v(x,omega) > 0, and translation invariance turns that expectation into
p_v. The point of using a deterministic time is that the time of the global
minimum is not a stopping time.
6.4 L5 (slabs: the walk is a sequence of independent pieces).
Suppose p_v > 0. Then:
(a) Under P_hat_v there are almost surely infinitely many true cuts
0 = tau_0 < tau_1 < tau_2 < ..., where time 0 counts as the initial
boundary.
(b) The relative words from one cut to the next are independent and
identically distributed. Their common law nu_v is given by the
annealed weight:
nu_v(gamma) = W(gamma)
for every regeneration word gamma in direction v (definition below),
and zero otherwise.
(c) Every departure site of a slab has height in [0, L) relative to the
slab's starting height, where L = L(gamma) = h(z) > 0 is the slab's
width.
(d) Under the raw (unconditioned) law, on the event {sup h = infinity} a
first true strict record exists almost surely, and conditioned on its
finite prefix the translated future has law P_hat_v.
Definitions. A word gamma = (0 = x_0, ..., x_m = z) is a REGENERATION WORD in
direction v if m >= 1 and
(i) 0 <= h(x_j) < h(z) for every 0 <= j < m; and
(ii) whenever 1 <= j < m is a strict record inside the word, there is a
k with j < k < m and h(x_k) < h(x_j).
Condition (ii) says: every intermediate record was already cancelled (the walk
went back below it) before the word ended, so the only surviving record is the
terminal one. Its width is L(gamma) = h(z) > 0, and its spatial radius is
R(gamma) = max over 0 <= j <= m of ||x_j||_2.
PROOF. Existence by trials. Examine the first ordinary strict record. If
the walk later drops below it, wait until the first strict record above the
maximum of everything seen up to that failure, and examine again. Candidates,
and the times at which failures are noticed, are stopping times. By the
fresh-suffix identity proved below (display (6.1)), the probability that the
first r tested candidates are finite and all fail is at most (1 - p_v)^r. On
{sup h = infinity} a new candidate appears after every detected failure (L3
says a finite height supremum forces escape to minus infinity, which is the
opposite). Hence a true cut exists there almost surely.
Under P_hat_v, the height supremum is infinite almost surely: L3's alternative
conclusion (tend to minus infinity) contradicts D_v. So the first true cut is
finite under P_hat_v, and iterating the argument after each cut gives (a).
The law. Fix a regeneration word gamma = (0,...,z) of length m, and a
measurable event B for the translated infinite suffix. Claim:
(6.1) P_0( (X_0,...,X_m) = gamma, tau_1 = m, (X_{m+k} - z)_{k>=0} in B )
= W(gamma) P_0( B intersected with D_v ).
Why. The first true cut word is gamma exactly when the prefix is gamma and
the suffix from z never goes below h(z) = the level of z. Necessity: an
earlier record that the prefix did not cancel could never be cancelled by a
future that stays at or above h(z), so there would be an earlier true cut.
Sufficiency: the word condition says all intermediate records are cancelled
inside the word, and the terminal record is never undercut by the suffix.
Now the bookkeeping. The prefix uses only rows at sites of height strictly
below h(z) (condition (i)). The suffix, constrained by D_v, uses only rows at
sites of height at least h(z). These two sets of rows are disjoint. So by
[L2] with f = the indicator of the translated suffix event, the probability
factors as in (6.1).
The event on the left implies D_v, so dividing (6.1) by p_v gives
(6.2) P_hat_v( Gamma_1 = gamma, (X_{tau_1+k} - X_{tau_1})_{k>=0} in B )
= W(gamma) P_hat_v(B),
where Gamma_1 is the first relative word. Since tau_1 < infinity almost
surely, summing (6.2) over all words shows that the weights of all regeneration
words sum to one (this is a by-product, not an assumption). Then (6.2) says:
the first word is gamma, independently of the future, and the conditional law
of the translated future is D_v conditioned again, i.e. P_hat_v. Iterating
gives independence and the identical distributions in (b). Condition (c) is
part of the definition of a regeneration word.
For (d): enumerate words whose prefix may go below zero, as long as the
endpoint is a strict global record and every earlier strict record was
cancelled before that endpoint. The suffix factor is again
P_0(B intersected with D_v), so its conditional translated law is P_hat_v.
We call these words SLABS. Note carefully what we have: the complete law of a
slab, as a whole spatial object, not only the law of its displacement. That
is what allows us to place slabs at different spatial positions in section 10.
6.5 L6 (finite mean width).
Suppose p_v > 0 and ||v||_infinity = 1. Let S be the number of ordinary strict
records inside a slab, counting the terminal record and starting from the
initial boundary. Then
0 < E_{nu_v} L <= E_{nu_v} S <= 1/p_v < infinity.
Note what is, and is not, claimed: the width L in the real direction v need not
be an integer, no moment of the DURATION (number of time steps) of a slab is
claimed, and S counts records, not steps.
PROOF. For i >= 1 let
B_i = { rho_i < infinity, and h(X_n) >= 0 for 0 <= n <= rho_i }.
Freshness at rho_i plus cancellation of the conditioning probability gives
(6.3) P_hat_v( i is a true-record index )
= P_0( B_i, rho_i is true ) / p_v = P_0( B_i ) >= p_v.
The middle equality is the fresh-suffix identity (6.1) at the record rho_i,
and the last inequality holds because D_v implies the height supremum is
infinite (L3) and therefore every ordinary record index is reached before the
walk goes below 0; so D_v is contained in B_i.
At a true cut, the cut's height is the maximum of the entire past, so the
ordinary records after it are exactly the records of the translated suffix. By
L5(b), the successive true-record indices are the partial sums of independent
identically distributed positive integers S_1, S_2, ... with the law of S. Let
N(n) = the number of k >= 1 with S_1 + ... + S_k <= n.
Summing (6.3) over the true-record indices up to n gives
E_hat_v [ N(n)/n ] >= p_v.
If E S were infinite, then the strong law applied to the truncations S_j
capped at a would give (S_1+...+S_k)/k tending to infinity, hence N(n)/n
tending to 0 almost surely; dominated convergence (0 <= N(n)/n <= 1)
contradicts the lower bound. So E S is finite. The ordinary strong law and
the same inversion now give N(n)/n tending to 1/E S, and dominated convergence
gives E S <= 1/p_v.
Finally, each ordinary record raises the running maximum by at most 1: the
step into the record departs from a site no higher than the previous maximum
and raises the height by at most ||v||_infinity = 1. Adding the gains of the
records inside one slab gives L <= S. And L > 0 almost surely, so its mean is
strictly positive.
================================================================================
7. ONE SIGN OR THE OTHER
================================================================================
7.1 L7 (the two directional signs).
For every fixed nonzero real direction v, if P_0(A_v) > 0 then
P_0( A_v union A_{-v} ) = 1.
More precisely, up to null sets: infinite height supremum implies A_v, and
finite height supremum implies A_{-v}.
PROOF. Normalize ||v||_infinity = 1. L4 gives p_v > 0. On the event of
infinite height supremum, L5(d) gives a first true cut followed by independent
slabs. By L6 the slab widths have a finite, strictly positive mean, so the
successive base heights of the slabs tend to plus infinity. Every later slab
stays at or above its base (condition (i) of a regeneration word, with the
height measured from the slab's start). So h(X_n) tends to plus infinity,
which is A_v.
The finite-supremum alternative is exactly L3: h(X_n) tends to minus infinity,
which is A_{-v}. The two alternatives exhaust all paths.
7.2 Consequence.
Suppose 0 < P_0(A_v) < 1. By L7, P_0(A_v) + P_0(A_{-v}) >= 1, so
P_0(A_{-v}) > 0 as well: both signs have positive probability. This is the
standing assumption of sections 8 and 9. Conversely, if both signs have
positive probability, then neither is almost sure, so P_0(A_v) is strictly
between 0 and 1 -- the situation we will eventually prove impossible.
================================================================================
8. COEXISTENCE FORCES SMALL SLABS IN SPACE
================================================================================
The regeneration estimates of section 6 control only how far a slab advances in
the direction v. A slab could be a huge, wide zigzag that advances by 1 in
height while travelling a million sites sideways. The main result of this
section says: if both signs escape with positive probability, then the mean
SPATIAL radius of a slab is finite, for both signs. So slabs are not merely
narrow, they are small.
The idea, in one paragraph. Suppose huge lateral excursions happened with
probability not tending to zero. Take the first slab with radius much larger
than the accumulated displacement before it. Somewhere on that excursion,
measured with a slightly tilted functional (tilt the direction v by a small
multiple of a coordinate step), we have a brand new record: a site that beats
everything the path has done so far in the tilted functional. From that site,
force a short run straight down in height, and then run an independent
opposite-going copy of the walk. Because the down-run and the template stay in
fresh rows, the probability of this continuation is a fixed positive number,
independent of the scale. The result is: the walk's final height maximum lies
in a window whose bottom grows with the scale, with probability bounded below.
The two terms in that statement cannot both stay bounded below while the bottom
of the window goes to infinity. Contradiction.
8.1 L8 (initial averages of a stationary sequence).
Let Z_1, Z_2, ... be a stationary sequence of nonnegative integrable random
variables. For every a > 0 and n >= 1,
P( max over 1 <= k <= n of (Z_1 + ... + Z_k)/k > a ) <= E Z_1 / a.
PROOF. Call an integer s a bad start if some interval beginning at s, of
length at most n, has sum greater than a times its length. Among the starts
1,...,M take the leftmost bad start, choose a witnessing interval, skip all its
indices, and repeat. The chosen intervals are disjoint, they cover every bad
start, and they lie in {1,...,M+n}. Their total length is at least the number
of bad starts, so
a * (number of bad starts <= M) <= Z_1 + ... + Z_{M+n}.
Take expectations, use stationarity for the right side, and let M tend to
infinity.
This is the classical maximal ergodic inequality (Hopf; the short proof is
Garsia's). We use it once, to see that "most initial portions of the slab
sequence have total radius at most a times their index".
8.2 P9 (spatial radius under coexistence).
Let the environment be independent identically distributed and strictly
elliptic, and let v be nonzero. Suppose P_0(A_v) > 0 and P_0(A_{-v}) > 0. For
each sign sigma in {+1,-1}, let nu_{sigma v} be the slab law of L5 in direction
sigma v. Let R be the spatial radius of a slab. Then
integral of R with respect to nu_v + integral of R with respect to nu_{-v}
< infinity.
We prove this in 8.3-8.8. Two sentences first, to fix the roles of the two
signs: the coasting sign supplies a huge excursion (that is where the
contradiction is manufactured), and the opposite sign supplies a continuation
that stays on top of the tilted record forever.
8.3 The scale argument.
Rescale so that ||v||_infinity = 1. For either sign, under P_hat_{sigma v} let
(L_i, R_i), i >= 1, be the widths and radii of its independent slabs, and put
H_k = L_1 + ... + L_k with H_0 = 0. Write E_sigma for expectation in this
slab sequence. By L6, 0 < E_sigma L < infinity.
A point in slab k+1 has signed height at least H_k, and the displacement of any
point reached during slabs 1..k has norm at most R_1 + ... + R_k.
Suppose the conclusion of P9 is false:
I(t) := sum over signs of E_sigma min(R, t) tends to infinity.
The function I is increasing and concave, I(0) = 0 and I(t)/t tends to 0 (by
bounded convergence, since R is finite almost surely). Fix constants: by the
two width strong laws choose c > 0 and finite C, C_0 >= 0 with
(8.1) P_hat_{sigma v}( c k - C_0 <= H_k <= C k + C_0 for every k ) > 0.95.
Then fix, in this order, an integer C_1 and numbers b, B, eta > 0 with
(8.2) C_1 c > C + 4,
b > 1/c,
(B - 1)/sqrt(d) - b (C + 2) > 2,
4 C_1 eta < 0.15.
The roles: C_1 gives the opposite continuation enough slabs to descend below
height zero; b makes that descent dominate the lateral displacement in the
tilted functional; B makes a big excursion produce a new tilted record; eta
controls the probability that an initial portion exceeds its displacement
allowance.
For large a let N = N(a) be the smallest positive integer with I(aN) >= eta a.
Such N exists, and N(a) tends to infinity because I(am)/a tends to 0 for fixed
m. For large a, minimality plus concavity gives
(8.3) eta a <= I(aN) <= (N/(N-1)) I(a(N-1)) < 2 eta a.
8.4 Good prefixes.
In either sign and for m >= 0 let R_m be the event that for every k <= m,
c k - C_0 <= H_k <= C k + C_0 and R_1 + ... + R_k <= a k.
Claim:
(8.4) P_hat_{sigma v}( R_m ) > 0.8 for m = C_1 N.
To see it, put n = C_1 N, A = a n, and truncate each radius at A: call the
result R_jhat = min(R_j, A). Concavity and (8.3) give
E_sigma Rhat <= I(A) <= C_1 I(aN) < 2 C_1 eta a.
L8 bounds by 2 C_1 eta the probability that any of the first n running averages
of the truncated radii exceeds a. Also, by Markov's inequality in the form
P(R > A) <= E min(R,A)/A,
P_hat_{sigma v}( some j <= n has R_j > A ) <= n E_sigma min(R,A) / A
<= 2 C_1 eta.
Intersecting with (8.1) gives (8.4) since 0.95 - 4 C_1 eta > 0.8. In
particular R_{i-1} has probability above 0.8 for i <= N, and R_{i-1} depends
only on the first i-1 slabs.
8.5 A large slab after a good prefix.
Choose i_0 so large that
(8.5) sum over signs of sum over i >= i_0 of P_hat_{sigma v}(L > i)
< eta/(4B),
possible because widths have finite mean. Increase i_0 if necessary so that for
every i >= i_0,
(8.6) c(i-1) - C_0 >= c i / 2 and C(i-1) + C_0 + i <= (C+2) i.
Then take a so large that N >= i_0 and I(B a i_0) < eta a / 4.
For i_0 <= i <= N call
G_i = { R_i > B a i, L_i <= i }
the large-slab event, and put lambda_sigma = sum over i_0 <= i <= N of
P_hat_{sigma v}(G_i). Integrating the decreasing radius tails gives
sum over signs of sum over i_0 <= i <= N of P_hat(R > B a i)
>= ( I(B a (N+1)) - I(B a i_0) ) / (B a),
sum over signs of sum over 1 <= i <= N of P_hat(R > B a i)
<= I(B a N) / (B a) <= 2 eta.
For the lower bound use I(Ba(N+1)) >= I(aN) >= eta a (monotonicity, since
B > 1) and subtract (8.5). The result is
eta/(2B) <= lambda_+ + lambda_- <= 2 eta,
because G_i also needs L_i <= i and the L-tail is at most eta/(4B) per sign.
So at least one sign, possibly depending on the scale, has
lambda_sigma >= eta/(4B).
In that sign consider
Z = sum over i_0 <= i <= N of 1_{R_{i-1}} 1_{G_i}.
Independence of slab i from the preceding slabs gives E_sigma Z >= 0.8
lambda_sigma. The summands of Z are not independent, but Z is dominated by
sum_i 1_{G_i}, whose summands ARE independent, so
E_sigma Z^2 <= lambda_sigma + lambda_sigma^2,
and the second-moment bound gives
P_hat_{sigma v}( Z > 0 ) >= 0.64 lambda_sigma / (1 + lambda_sigma)
>= 0.64 eta / (4B (1 + 2 eta)) =: delta > 0.
This delta does not depend on i_0 or on a. So, with a probability that is
uniform in the scale, we have found a slab whose excursion is much larger than
the accumulated displacement before it, while its width is at most its index.
8.6 The tilted record.
Write h for the height in the selected sign (so h = sigma v . x). On
R_{i-1} intersected with G_i the initial site of slab i has norm at most
a(i-1), so some point of slab i has norm greater than (B-1) a i. At that point
some signed coordinate u satisfies
u . X > (B-1)/sqrt(d) * a i.
Throughout that slab the running h-maximum is at least H_{i-1} >= c i / 2 and
at most H_i <= (C+2) i, by (8.6).
Define the tilted functional
Y(x) = u . x - b a h(x).
Before slab i, nonnegative height together with R_{i-1} gives Y(X) <= a(i-1).
At the selected point,
Y(X) > ( (B-1)/sqrt(d) - b (C+2) ) a i > 2 a i
by (8.2). So there is a strict Y-record while the running h-maximum lies in
the window
(8.7) W = [ c i_0 / 2 , (C+2) N ].
Now fix sigma, u, i_0 and a. Let T be the first positive time such that: the
prefix has nonnegative h-height; Y(X_T) is a strict record; and the running
h-maximum belongs to W. These are conditions on the observed prefix, so T is
a stopping time. It is not a regeneration time. Summing over the 2d signed
coordinates and removing the conditioning:
(8.8) P_hat_{sigma v}(T < infinity) >= delta/(2d),
P_0(T < infinity) >= p_* delta/(2d), p_* = min(p_v, p_{-v}) > 0.
The site X_T has not appeared in the earlier prefix, because it is a strict
Y-record: an earlier visit would have had a Y-value that T's value strictly
exceeds, so it could not have been a visit to the same site.
8.7 The script, and the opposite template.
Since ||v||_infinity = 1 there is a step e with h(e) = -1. From X_T force M
repetitions of that step, M a fixed integer chosen below. Each step raises Y
by at least b a - 1, so for large a the scripted sites have strictly increasing
Y, starting above the strict record X_T. Hence every scripted departure site
is distinct and unused by the prefix. Conditional on any fixed prefix
realizing T, the script has exactly the raw probability
( E p_0(e) )^M >= alpha^M,
alpha := min over e' in U of E p_0(e') > 0.
alpha is positive because U is finite and each entry is positive almost surely;
it is NOT a lower bound on individual entries of one environment. The
independence used here is across distinct departure sites, not across entries
of one row (see 1.7).
At the script's endpoint, consider a translated opposite-going template with
law P_hat_{-\sigma v}, and require R_{C_1 N} for its first C_1 N true-cut slabs.
That requirement has probability above 0.8 by (8.4). Two separations must be
checked.
First separation, against the original prefix. At a point of template slab
k+1 with 0 <= k < C_1 N, the displacement in direction u is at least -a(k+1),
and the displacement in h is at most -c k + C_0. So the total Y-increment
from the launching record is at least
(8.9) M(ba - 1) - a(k+1) + ba(ck - C_0)
= a ( M b - 1 - b C_0 + (b c - 1) k ) - M.
Choose M once and for all so that M b > 1 + b C_0 + 1. Since b c > 1, the
expression in (8.9) is strictly positive for all k in question and all large a.
So the template stays strictly above every Y-value of the original prefix,
whose Y-values are at most the launching record.
Second separation, against the script. The whole template stays at or below
its own initial h-height, whereas every scripted departure lies strictly above
that height. So the template avoids all scripted departure sites, including in
its infinite tail.
Third, the descent below zero. After C_1 N template slabs the template's
absolute h-height is at most
(C+2) N - M - c C_1 N + C_0 < 0
for large N, by C_1 c > C + 4. That endpoint is a true opposite cut, so the
remaining tail stays below zero, and it avoids the original prefix (all of
whose heights are nonnegative). Nothing here assumes that the script itself
stays above zero.
Because of all these separations, the use of fresh rows is exact. Condition on
a fixed finite prefix realizing T, and then on the forced script. The
conditional environment differs from the original independent law only at the
departure sites of these two finite words. Under an independent raw law, the
probability of
D_{-\sigma v} intersected with R_{C_1 N}
is at least 0.8 p_{-\sigma v}. Every path in that event avoids all the old
departure sites, by the separations, and [L2] identifies its probability with
the corresponding fresh-row probability after the prefix and the script. In
detail: kill both the continuation and an independent raw chain on arrival at
the same set of old departure sites; the finite-word identity gives equality of
their cylinder probabilities, hence of their killed path laws; then restrict to
D_{-\sigma v} intersected with R_{C_1 N}, whose paths never hit that set.
Repeated sites inside the template remain in its raw path weights.
Consequently, from every qualifying prefix, the script followed by the required
continuation has conditional probability at least 0.8 p_* alpha^M. The script
decreases h, and the template never exceeds its own starting height, so the
final supremum of h on this continuation is the running supremum at T, which
lies in the window W of (8.7).
8.8 The contradiction.
Combining (8.8) with 8.7 gives, for every sufficiently large i_0 and then for
all sufficiently large a,
(8.10) P_0( sup over n of sigma v . X_n lies in [ c i_0/2 , (C+2)N(a) ] )
>= rho,
rho := 0.8 p_*^2 alpha^M delta / (2d) > 0,
with rho independent of the scale. For each sign let M_sigma = sup over n of
sigma v . X_n, allowing +infinity. Then
sum over signs of P_0( c i_0/2 <= M_sigma < infinity ) >= rho
for every sufficiently large i_0. But each term on the left tends to zero as
i_0 tends to infinity, because the events decrease to the empty set. A
contradiction. So I(t) is bounded, and monotone convergence proves P9.
What P9 gives us, concretely: the slab displacements have finite mean, and the
error between a slab's endpoint and the path inside it has finite mean. Those
are used in section 9 (to get honest rays) and section 10 (to get finite mean
common blocks).
================================================================================
9. THE TWO RAYS, AND REDUCTION TO A COORDINATE
================================================================================
9.1 P10 (reduction to a coordinate direction).
Suppose the annealed walk satisfies 0 < P_0(A_v) < 1 for some nonzero v. Then
there is a coordinate i with
P_0(A_{e_i}) > 0 and P_0(A_{-e_i}) > 0.
Idea: under each sign the walk leaves a straight line behind it (a ray). Two
rays of ONE walk that are not the same line must be exactly opposite, because
otherwise a tilted direction would also be escaped with probability 1, and then
the ray in that tilted direction would be a deterministic function of the
tail of the slab sequence -- a single value, which cannot be two different
rays. Once the two rays are opposite, some coordinate grows to plus infinity
along one ray and to minus infinity along the other.
PROOF. Normalize ||v||_infinity = 1. By L7 both signs of v have positive
probability, and P_0(A_v union A_{-v}) = 1.
For sigma in {+1,-1} let D_j^sigma be the displacement of the j-th slab of the
sigma v sequence, and R_j^sigma its radius. P9 and the bound |D_j| <= R_j give
the mean vector
b_sigma = E_sigma D_1^sigma, with b_sigma . (sigma v) = E_sigma L > 0;
the inner product is positive because the v-height gained across a slab is
exactly its width, and widths have positive mean (L6). In particular
b_sigma is not zero.
The strong law gives that the k-th slab endpoint divided by k converges to
b_sigma. Moreover, for each eps > 0,
sum over k of P_hat_{sigma v}( R_k^sigma > eps k ) < infinity,
so R_k^sigma / k tends to 0 almost surely. Between the k-th and (k+1)-st
endpoints the displacement from the former is at most R_{k+1}^sigma. The number
of completed slabs tends to infinity. Therefore the whole trajectory, after
its first true cut, has limiting unit direction
r_sigma = b_sigma / |b_sigma|.
L5 transfers this to the raw law on A_{sigma v}. This argument counts slabs,
not time, so it needs no moment of a slab's duration.
The two rays are distinct: their projections on v have opposite signs. Now the
antipodality. We prove the special case of Simenhaus's principle needed here.
Claim: r_- = -r_+. Suppose not, and put w = r_+ + r_-. Then
w . r_+ = w . r_- = 1 + r_+ . r_- > 0.
The endpoint and radius estimates above then give A_w on both directional
events, so P_0(A_w) = 1.
Under P_hat_w, the limiting ray therefore exists almost surely. By L5 that law
is represented by an independent identically distributed sequence of finite
relative slab words. Deleting finitely many words removes a finite time
prefix and translates all remaining positions by a fixed vector; since A_w
holds, positions tend to infinity in norm, and both operations preserve the
limiting ray. So the ray is a tail function of the independent word sequence.
The tail zero-one law, applied to a countable sequence of Borel sets that
determines a unit vector, makes the ray deterministic.
Finally the raw walk has a first true w-cut almost surely (L5(d), since A_w
holds), and its conditional future there has law P_hat_w. So its raw limiting
ray must be that same deterministic ray. But the raw ray is r_+ on A_v and r_-
on A_{-v}, both of positive probability, and they are different. Contradiction.
So the two rays are opposite.
Choose a coordinate e_i with nonzero projection on r_+. On A_v and on A_{-v}
the i-th coordinate of the walk tends to opposite infinities, which is
P10.
9.2 Consequence, and the standing assumption from here on.
It now suffices to rule out a mixed coordinate direction. Relabel coordinates
so that the mixed one is e_1, and write
p_+ = p_{e_1} > 0, p_- = p_{-e_1} > 0,
P_hat_+ = P_hat_{e_1}, P_hat_- = P_hat_{-e_1},
nu_+ = nu_{e_1}, nu_- = nu_{-e_1}.
From L6 and P9 applied to the coordinate direction,
(9.1) E_+ L < infinity, E_- L < infinity, E_+ R < infinity,
E_- R < infinity.
All heights in the remaining proof are INTEGER first coordinates. Two
consequences worth naming, because they are used repeatedly.
(a) A walk started inside a finite first-coordinate interval exits it almost
surely. Indeed a path confined to that interval would have finite height
supremum without tending to minus infinity, contrary to L3. Translation
and integration upgrade this to: for almost every environment, for all
integer barriers and all starting sites, the walk leaves. Only a
countable intersection of null sets is needed. No uniform ellipticity is
involved.
(b) In a regeneration word for a coordinate direction, the last step into the
terminal site rises by exactly 1 in height, because heights are integers
and the terminal site is strictly higher than every departure site. So
that last step is exactly +e_1. This is used in section 10.2 to produce
one guaranteed contact.
================================================================================
10. TWO TAPES ON ONE RULER
================================================================================
We now have a coordinate direction e_1 with both signs positive, both slab laws
of finite mean width and finite mean spatial radius (9.1), and integer heights
everywhere. This section builds the object whose two properties will
contradict each other: two independent copies of the walk, one going up and one
going down, laid on the same ruler of depth, and the contacts between them.
10.1 L11 (exact-cut bridges and the numbers u_H).
For either sign sigma in {+1,-1}, starting at 0, define
T_j = first time n >= 0 with sigma X_n . e_1 = j, j in Z,
u_j = P_0( T_j < T_{-1} ),
F(j) = nu_sigma( L > j ), j >= 0.
(u_j is the chance to reach height j before dropping below -1; F is the width
tail of a slab.) Then
(a) u_0 = 1 and 1 >= u_H >= u_{H+1} >= p_sigma for all H >= 0;
(b) under P_hat_sigma the probability that a slab cut occurs at height H is
u_H;
(c) conditional on a cut at height H, the list of slabs up to that cut has
law B_H, given by
B_H(gamma_1,...,gamma_m) = (1/u_H) * W(gamma_1) * ... * W(gamma_m)
for lists with total width L(gamma_1) + ... + L(gamma_m) = H, and zero
otherwise;
(d) concatenating such a list gives exactly the raw path stopped at its first
hit of H, conditioned on reaching H before -1 in the signed height;
(e) reversing the order of the list preserves B_H, and every word is still
traversed in its original chronological direction.
PROOF. On {T_H < T_{-1}} every departure before T_H has height below H, so the
future from the fresh endpoint may use the non-backtracking event, whose
probability is p_sigma; its factor cancels the denominator in the conditioning
on D_sigma. That gives (b). The hitting events {T_H < T_{-1}} are nested in H,
and a non-backtracking walk reaches every height, which gives (a).
For (c): a finite path that first hits H before -1 has a unique decomposition
into slabs. Its cuts are the strict record times whose heights are never
undercut before the terminal time, together with the initial boundary. Between
two consecutive cuts every intermediate record is cancelled before the second
cut -- these are precisely the regeneration words of L5. Conversely,
concatenating any such list of total width H gives such a bridge. Different
words have disjoint departure height ranges, so their raw weights multiply by
[L2], and their total mass is u_H. That gives B_H and identifies the bridge.
Reversal preserves the total width and the product of weights, and is a
bijection on admissible lists, which gives (e). For H = 0 the list is empty.
10.2 L12 (renewal tail comparison).
For either sign and all integers n' >= n >= 0,
(10.1) 0 <= u_n - u_{n'} <= (n' - n) F(n),
and the dyadic width tails are summable:
(10.2) sum over l >= 0 of 2^l F(2^l) < infinity.
PROOF. The cut heights form a renewal process with increments L. Splitting
according to the last cut at or before n gives the identity
sum over k=0..n of F(k) u_{n-k} = 1.
(The term F(k) u_{n-k} is the mass of "there is a cut at height n-k and the next
gap exceeds k"; the gaps are i.i.d. by L11 and the two factors are independent.)
Subtract the identity at n+1 from the identity at n; since u_0 = 1,
sum over k=0..n of F(k) (u_{n-k} - u_{n+1-k}) = F(n+1).
Every term on the left is nonnegative and F(0) = 1, so u_n - u_{n+1} <= F(n+1)
<= F(n); telescoping gives (10.1). For (10.2): sum over k >= 0 of F(k) equals
E L < infinity by L6, and grouping that sum into dyadic intervals gives (10.2)
because F is decreasing.
10.3 The arrangement.
Fix an integer sample of two independent tapes of independent slabs:
A_1, A_2, A_3, ... i.i.d. with law nu_+ (the POSITIVE tape)
B_1, B_2, B_3, ... i.i.d. with law nu_- (the NEGATIVE tape)
with joint law and expectation written P2 and E2.
Depth. For a site x, its DEPTH is -x_1, its distance below the top level
x_1 = 0. Only translations of slabs are used, and every word keeps its
chronological orientation.
Positive tape. Place A_1 so that its terminal site is the top site 0. Place
A_2 so that its terminal site is the starting site of A_1. Continue: A_{i+1}
is placed with terminal at the start of A_i. So the tape is read downwards in
chronological order, and the i-th word occupies depths (H_{i-1}^+, H_i^+] and
departs only from depths in that band (lifespan of the word).
Negative tape. Place B_1 so that its starting site is -e_1, the site directly
below the top. Place B_2 with its starting site at the terminal site of B_1,
and so on. So the words of the negative tape are read downwards in their
ordinary chronological order, and B_i departs only from depths in
( H_{i-1}^- + 1 , H_i^- + 1 ].
Here H_i^- = L(B_1) + ... + L(B_i). Read the last line against the positive
one: the negative tape's departure bands are shifted down by exactly one level
relative to the positive bands. That one-level shift is the price of starting
the negative walk at -e_1 instead of at 0, and it buys a guaranteed contact (see
below). Every estimate below only uses dyadic bands of block indices, so a
shift by one inside a block index changes nothing except constants; this is
spelled out in 10.5.
A small example, to fix the picture. Suppose the widths are
L(A_1), L(A_2), L(A_3), ... = 2, 3, 4, ... cumulative H^+ = 2, 5, 9, ...
L(B_1), L(B_2), L(B_3), ... = 1, 4, 4, ... cumulative H^- = 1, 5, 9, ...
The common depths where both cumulative sequences are equal are 0, 5, 9, ...
These are the common cuts. They divide both tapes into blocks: block 1 is
depths 0 to 5 (A_1, A_2 on the positive side; B_1, B_2 on the negative side),
block 2 is depths 5 to 9, and so on. Inside block 1 the positive departures
lie in depths (0,2] and (2,5], i.e. in (0,5]; the negative departures lie in
depths (0+1,1+1] = (1,2] and (1+1,5+1] = (2,6]. So at depth 1 the negative
tape has a departure from B_1 and the positive tape from A_1; at depths 3,4,5
both tapes have departures. Overlaps are what "contact" counts.
Contact. A site x is a CONTACT if it is a departure site of the positive
placed path and also a departure site of the negative placed path.
One contact is guaranteed: by 9.2(b), the last step of a positive word into its
terminal rises by exactly 1, so it departs from the site directly below the
terminal. The terminal of A_1 is the top site 0, so that departure is -e_1,
which is also the first departure of the negative tape. Hence -e_1, the site
at depth 1, is a contact. (This is the entire purpose of the offset.)
10.4 L13 (common blocks).
The pairs of lists in successive common blocks are independent and identically
distributed. If K is the total width of one block, then
(10.3) E2 K <= 1/(p_+ p_-) < infinity.
Let V_+ and V_- be the sums of the actual chronological lateral displacements
of the positive and negative words in one block. Then
(10.4) E2 ( |V_+| + |V_-| ) < infinity.
Passing down through a block, the lateral gap between the negative and the
positive lower anchors increases by S = V_+ + V_-, and E2 |S| < infinity.
PROOF. First allow the first positive common width K to be infinite. The
event that it is reached after i positive and j negative words is determined by
those two finite prefixes (their widths agree and no earlier positive partial
sum agrees). The unused tails are therefore again independent tapes with their
original laws, independent of the completed block. To see this without a
stopping-time convention, condition separately on each pair (i,j), factor the
law of the unused tails, and sum over (i,j). Repeating gives the renewal
property at every common cut that exists.
Let c_n = u_n^+ u_n^- be the probability that depth n is a common cut (it is a
product by independence of the tapes, and c_0 = 1). Splitting according to the
last common cut at or before n gives
sum over i=0..n of c_{n-i} P2(K > i) = 1.
Since c_j >= p_+ p_- > 0 by L11(a), we get (p_+ p_-) sum over i=0..n of
P2(K > i) <= 1; letting n tend to infinity proves (10.3). In particular K is
finite almost surely, and restarting at each common cut justifies the i.i.d.
block sequence.
For the lateral moment, let N_+ be the number of positive words in the first
common block. The event {N_+ >= i} says no H_1^+ ,..., H_{i-1}^+ belongs to the
negative renewal set; it depends only on the previous positive words and on the
negative tape, hence is independent of the whole word A_i. So by Tonelli and
the independence,
E2 sum over i=1..N_+ of R(A_i)
= sum over i >= 1 of P2(N_+ >= i) E_+ R
= E2 N_+ * E_+ R
<= E2 K * E_+ R < infinity,
using L >= 1 for the middle inequality and (10.3), (9.1) for the last one. The
same holds on the negative tape, and |a(gamma)| <= R(gamma) turns this into
(10.4) and into the moment bound for S.
Finally, across a block the positive lower anchor moves by -V_+ in lateral
coordinates while the negative anchor moves by V_-, so their difference
(negative minus positive) increases by V_+ + V_-.
10.5 The contact count m(J).
Let K_j be the successive common widths and put W_0 = 0 and
W_j = K_1 + ... + K_j. Both tapes' departures in block j lie in the depth band
(W_{j-1}, W_j] for the positive tape and (W_{j-1}+1, W_j+1] for the negative
tape, so a contact at depth z belongs to positive block index
i_+(z) = min { i : H_i^+ >= z }
and to negative block index
i_-(z) = min { j : H_j^- >= z - 1 }.
These two indices agree with the common block index
i(z) = min { i : W_i >= z }
up to at most one. Concretely: i_-(z) differs from i_+(z) only when z is
exactly a common cut depth, and then by one; and i_+(z) = i(z) by definition.
All bounds below are expectations summarised over dyadic bands of block indices,
and adding or removing the boundary block of a band changes a sum by one term,
which is absorbed into the constants C. We therefore write "block j" for the
block containing a contact, meaning any index within one of the true one.
For integers 0 <= a < b let C(a,b] be the event that at least one contact occurs
in at least one block with index a < j <= b. The quantity to be estimated is
(10.5) m(J) = sum over j=1..J of P2( C(2^j, 2^{j+1}] ), J >= 1,
the expected number of dyadic block-index bands that contain a contact.
Section 11 proves m(J) = O(J / log J). Section 12 proves
m(J) >= c J / log log(3+J). The two cannot both hold, and that is the whole
proof of the theorem.
================================================================================
11. CONTACTS ARE RARE: THE ENTROPY UPPER BOUND
================================================================================
11.1 P14 (entropy upper bound for contacts).
Suppose both coordinate signs have positive escape probability. In the
opposed arrangement of section 10, let m(J) be as in (10.5), the expected
number of dyadic common-block bands j = 1..J that contain a contact. Then
m(J) = O( J / log J ) as J tends to infinity.
11.2 The plan, in plain words, and the role of every object.
We would like to compare a piece of the real arrangement with a "clean"
reference object in which the two tapes are independent bridges of prescribed
heights. The clean object has one decisive property: a contact is very
unlikely there (11.7). The price of the comparison is relative entropy, and we
can bound the price (11.5). The price per dyadic scale is O(1) bit, while an
event whose reference probability is small costs logarithmically many bits to
distinguish (11.6). Summing over J scales then gives the bound.
The three ingredients are therefore:
(i) a window of the arrangement, with RANDOM counts, so that specifying
the window's heights is cheap (11.3);
(ii) a reference law that keeps the heights and the lateral alignment but
replaces the slab lists by independent bridges at those heights
(11.4);
(iii) the two estimates: price O(1) per scale (11.5), and contact
probability small under the reference law (11.7).
Why random counts. If we fixed the number of blocks in a window, we would have
to pay log of the number of possible heights. By choosing the count
uniformly from n possibilities and then reversing the accounting, the height
specification costs exactly log n, which cancels against the 1/n in the count.
That is the content of the display in the proof of L15.
Notation warning. From here on H(V) denotes the entropy of a random variable
V, and kappa_k denotes the entropy of the sum of k i.i.d. lateral gap
increments S_1 + ... + S_k. This H is NOT the height function h(x) of earlier
sections.
11.3 The window.
Fix an integer n >= 1. We want to surround the common blocks with indices in
(4n, 8n] by a middle chunk, with an outer chunk on each side of height at least
n, and a buffer above all three chunks. The buffer's role is to supply an
independent lateral gap d_0.
Independently of the tapes, choose four integer counts
(11.1) U, I_1, I_3 uniform on {n, ..., 2n-1},
I_2 uniform on {7n, ..., 8n-1}.
Read, downwards from the top, a buffer of U common blocks followed by three
chunks of I_1, I_2 and I_3 common blocks. Write d_0 for the lateral gap after
the buffer (the sum of its gap increments). For chunk i let A_i and B_i be the
positive and negative slab lists in their downward tape order, and let H_i be
their common total width. Write
H = (H_1, H_2, H_3), A = (A_1, A_2, A_3), B = (B_1, B_2, B_3).
The chunks are independent, and (U, d_0) is independent of all of them: by
conditioning on the four external counts, the product law of the common blocks
factorises, and a chunk's law depends only on its own count. The first and
third count windows give the outer heights; the longer middle window makes the
middle chunk start before block 4n and end after block 8n.
Now define the alignment variables. Put q = d - 1, and let X_{A,i} and X_{B,i}
in Z^q be the sums of the lateral displacements of the words of A_i and B_i
taken in the words' actual chronological direction (that is: the total lateral
displacement of the whole chunk, which determines where the chunk's bottom lies
relative to its top). Put
(11.2) X_A = X_{A,1} + X_{A,2} + X_{A,3},
X_B = X_{B,1} + X_{B,2} + X_{B,3},
Z = d_0 + X_A,
T = U + I_1 + I_2 + I_3.
The placement that explains Z. Put N_* = H_1 + H_2 + H_3. Place the positive
chunks from height 0 and lateral position 0, in the order 3, 2, 1, reversing the
list order inside each chunk (every word is still traversed in its original
direction). Place the negative chunks in the order 1, 2, 3 from height N_* - 1
and lateral position Z. Let E_mid be the event that the two middle chunks have
a departure contact.
For the actual chunk data this placement reproduces the infinite opposed
arrangement after its buffer, up to a translation. Check the alignment at the
top of the middle chunk: the lateral gap there (negative minus positive) is
Z + X_{B,1} - (X_{A,3} + X_{A,2}) = d_0 + X_{A,1} + X_{B,1},
which is exactly the gap in the original arrangement. Subsequent list
placements agree as well. From (11.1), the middle chunk starts after at most
4n - 2 common blocks and ends after at least 9n blocks, so it contains the
deterministic band (4n, 8n] of block indices.
Let P_n be the actual law of (H, Z, A, B) obtained this way.
11.4 The reference law.
Define Q_n as follows. First sample (H, Z) with its ACTUAL joint marginal.
Given those values, sample the six lists independently, list A_i with the
bridge law B_{H_i}^+ and list B_i with B_{H_i}^- (L11). Then apply the same
placement rule. The reference law keeps the dependence between the heights and
the lateral alignment; it changes ONLY the conditional law of the lists.
Because E_mid is one fixed measurable event for both experiments, the original
contact probability over block indices (4n, 8n] is at most the actual
probability P_n(E_mid) of the middle contact.
11.5 L15 (the price of the comparison).
There is a constant C, independent of n, with
D(P_n || Q_n) <= C + kappa_{14n} - kappa_n.
Here D is relative entropy (the price), and kappa_k is the entropy of the sum
of the first k i.i.d. lateral gap increments S_1 + ... + S_k of the common
blocks.
PROOF. There are two costs: imposing the random chunk heights, and then
keeping the aligned starting displacement Z.
First condition on H alone. For a specified pair of slab lists of common
total width h, let r be the number of their common positive cumulative widths,
including h. The pair parses uniquely into its first r common blocks. If r
lies in the count window for chunk i, its actual unconditioned mass is
(1/n) * product over a in A_i of W(a) * product over b in B_i of W(b),
and it is zero otherwise. The independent exact-cut bridge pair at height h
has mass equal to the same product divided by u_h^+ u_h^- (L11(c)). Hence the
conditional density of the actual pair, on its support, is
(11.3) u_h^+ u_h^- / ( n P_n(H_i = h) ).
Let D_0 be the averaged conditional relative entropy of (A,B) given H with
respect to these independent bridges. The three chunks are independent, so
(11.3) and u_h <= 1 give
D_0 <= sum over i of ( H(H_i) - log n ) <= C.
For the last inequality: E H_i <= 8n E K by L13, and a positive integer variable
with mean a has entropy at most 1 + log(a+1) (compare it with a geometric
distribution, which maximises entropy at fixed mean). Since the reference law
conditional on H factorises between the two tapes,
(11.4) I( A ; B | H ) <= D_0.
Second, keep the alignment Z. By the chain rule, adding Z at its actual
marginal costs exactly its conditional mutual information with the lists:
(11.5) D(P_n || Q_n) = D_0 + I( Z ; A, B | H )
= D_0 + H(Z | H) - H(d_0).
Now the trick that makes the price telescoping-small. Conditional on A and H,
Z is obtained by adding the independent d_0. So by data processing with (11.4),
I( Z ; B | H ) <= D_0.
Instead of bounding H(Z | H) directly (that would cost O(log n), too much after
summing over scales), add the negative tape's displacement to Z. Their sum is
the total common-block gap, whose entropy can be compared with the buffer's;
conditioning on the negative tape costs at most D_0:
(11.6) H(T, Z + X_B) >= H(T, Z + X_B | B, H) = H(T, Z | B, H)
>= H(Z | H) - D_0 + H(T | Z, A, B, H)
= H(Z | H) - D_0 + H(U | d_0).
The last equality: the two lists of each chunk determine the chunk's common
count, so knowing the lists and Z fixes both T - U and d_0 = Z - X_A; and the
buffer pair is independent of the chunks.
Now evaluate the two entropies. The vector Z + X_B is the sum of the first T
common gap increments, and the count T is independent of the underlying i.i.d.
tape (we are not conditioning on the observed chunks here). So
H(T, Z + X_B) = H(T) + E kappa_T,
H(U, d_0) = log n + E kappa_U.
Here n <= U < 2n and 10n <= T <= 14n - 4, so T takes at most 4n values and
H(T) <= log(4n). Monotonicity of kappa in the index gives
(11.7) H(T, Z + X_B) - H(U, d_0) <= log 4 + kappa_{14n} - kappa_n.
Subtract H(d_0) in (11.6) and use (11.5) together with (11.7):
D(P_n || Q_n) <= 2 D_0 + log 4 + kappa_{14n} - kappa_n.
The bound for D_0 is uniform in n, so twice that bound is absorbed into C.
That proves L15.
How small is the price? By (10.4) the gap increments S_j have a finite first
moment, so for a Z^q-valued variable with finite first moment, comparison with
weights proportional to exp(-|x|/(k+1)) gives
(11.8) kappa_k <= C + q log(k + 1).
The normalising sum is at most C_q (k+1)^q and the expected comparison energy is
at most k E|S_1|/(k+1). Also kappa_k is nondecreasing (condition on the last
summand, use translation invariance of entropy, then remove the conditioning).
Inserting (11.8) into L15 gives
D(P_n || Q_n) <= C + q log( (14n + 1)/(n + 1) ) = O(1),
a PRICE PER DYADIC SCALE THAT DOES NOT GROW WITH n. That is the whole point of
the randomisation: the number of blocks is random, so the height specification
costs precisely what the count distribution can pay.
11.6 From relative entropy to a probability bound.
Fact (binary divergence). Let P and Q be laws on the same space, let E be an
event with a = P(E) and b = Q(E), and suppose b > 0. Then
(11.9) a log(1/b) <= D(P || Q) + 2 log 2.
PROOF. Applying the (data processing) map 1_E cannot increase relative
entropy, so the binary divergence bin(a,b) = a log(a/b) + (1-a) log((1-a)/(1-b))
is at most D(P || Q). Now bound below: a log(a/b) = a log(1/b) + a log a, and
-a log a <= 1/e <= log 2, and (1-a) log((1-a)/(1-b)) is at least -log 2 in the
worst case. Hence a log(1/b) <= D(P||Q) + 2 log 2.
In words: if the reference law thinks an event is b times unlikely, then the
event's actual probability is at most the price divided by log(1/b). The price
per scale is O(1) by 11.5, so an event of reference probability delta costs
log(1/delta) bits against a budget of O(1) bits per scale.
11.7 L16 (contacts are rare under the reference law).
For the reference experiment of 11.4,
Q_n( E_mid ) <= delta_n := min { 1, C n ( F_+(n) + F_-(n) ) },
where F_+ and F_- are the width tails of the two slab laws (10.1).
PROOF. Fix (H, Z) in its retained support; in particular H_1 >= n and
H_3 >= n. Write N = N_*. By the list-reversal invariance of L11(e), the placed
chronological chunks have their respective raw bridge laws.
Step 1: retain prefixes. Retain the complete positive lower and middle chunks,
concatenated into a path alpha from height 0 to its first hit of N - H_1.
Retain the negative upper and middle chunks only up to their first arrival at a
departure site of alpha. If a middle contact happens, that arrival occurs
before the negative middle endpoint at height H_3 - 1, so the contact site y
satisfies
(11.10) H_3 <= y_1 <= N - H_1 - 1.
Thus each path has made at least n progress in its OWN signed height (the
positive one upward, the negative one downward) before the contact, and neither
has crossed the global barriers -1 and N.
Step 2: bookkeeping. The unused positive upper chunk and negative lower chunk
integrate to one. The remaining four bridge normalisations are bounded by
p_+^{-2} p_-^{-2}. Consecutive bridges within one sign have disjoint departure
layers, so their raw weights multiply to the raw weight of their concatenation.
Summing over the negative completion after its retained prefix, and dropping
its remaining bridge requirements, costs at most that prefix's raw weight: in
each fixed environment the total conditional completion probability is at most
one, and averaging preserves the inequality. This allows the completion to
revisit its prefix's departure rows; no independence is assumed there. The
first-hit chunk boundaries determine the splits, so no extra multiplicity
appears.
Step 3: transfer to one environment. The retained negative prefix has no
departure site in Dep(alpha): its terminal is the first arrival there.
Repeated sites inside either path cause no difficulty. So [L2] identifies the
product of the two raw weights with the weight of the two paths sampled
independently conditional on one shared i.i.d. environment. For each alpha the
first contact fixes the negative prefix uniquely, and alpha itself is stopped at
a fixed first-hit height. Hence we may sum these joint prefix weights without
overcounting, and extend both paths as raw trajectories in the common
environment.
Step 4: classify, only now. In the shared environment define, for interior
sites,
Q_y^omega = P_{y,omega}( T_{-1} < T_N ),
with barriers at absolute first-coordinate heights -1 and N. Two cases.
If Q_y^omega >= 1/2 at the contact, then the positive raw path has visited such
a site after reaching height n and before exiting the global slab. Condition
on the environment and stop the positive path at its first such visit; the
subsequent exit at -1 has conditional probability at least 1/2. Hence the
annealed probability of that visit event is at most
2 P_0( T_n < T_{-1} < T_N ) = 2 ( u_n^+ - u_N^+ ) =: 2 Delta_+.
If Q_y^omega < 1/2, the negative marginal gives the same bound with
2 Delta_- in place of 2 Delta_+. The a.s. finite-interval exit property of
9.2(a) holds quenched for all these starting sites and barriers, outside one
null set, which is exactly what is needed to say that "the other exit" has
probability greater than 1/2 with no lower bound on individual entries.
Measured from the negative start N - 1, the global barriers N and -1 have
signed relative heights -1 and N; lateral translation by Z does not change the
annealed law.
Step 5: assemble. Combining the two alternatives with the bounded
normalisations gives, uniformly in (H,Z),
(11.11) Q_n( E_mid | H, Z )
<= C ( Delta_+ + Delta_- )
<= C N ( F_+(n) + F_-(n) ),
where the last step is (10.1) with n' = N. Finally E N <= 12 n E K by (11.1)
and L13, so averaging over the retained joint marginal of (H,Z) and taking the
minimum with 1 proves L16.
11.8 Proof of P14: summing over scales.
For l >= 2 take n = 2^{l-2} and write delta_l = delta_n. Under the actual law
the event E_mid contains the original contact event over common blocks
(2^l, 2^{l+1}], so it is enough to bound P_n(E_mid) for each scale.
Suppose first that delta_l > 0. By (11.9) with L15,
(11.12) P_n(E_mid) log(1/delta_l) <= C + kappa_{14n} - kappa_n.
The right side is O(1) uniformly in l, by (11.8) and the ratio
(14n+1)/(n+1) < 15.
The reference probabilities are summable over scales:
(11.13) sum over l >= 2 of delta_l < infinity,
because delta_l <= C 2^l (F_+(2^{l-2}) + F_-(2^{l-2})) and both dyadic tails are
summable by (10.2).
Now split the scales. Among 2 <= l <= J at most C sqrt(J) of them have
delta_l > J^{-1/2}, because the sum in (11.13) is finite; those contribute at
most C sqrt(J) to m(J). For every other index with delta_l > 0, the logarithm
in (11.12) is at least (1/2) log J, so by (11.12) that scale contributes at most
C / log J, and there are at most J of them.
It remains to check that the entropy increments telescope. Since
14 * 2^{l-2} <= 2^{l+2} = 16 * 2^{l-2} and kappa is nondecreasing,
sum over l=2..J of ( kappa_{14 * 2^{l-2}} - kappa_{2^{l-2}} )
<= sum over l=2..J of ( kappa_{2^{l+2}} - kappa_{2^{l-2}} )
<= 4 kappa_{2^{J+2}} = O(J),
by (11.8) with q = d - 1 fixed. Each dyadic scale appears at most four times
in the telescoping sum.
Adding the initial scale gives
m(J) <= 1 + C sqrt(J) + C J / log J = O( J / log J ),
which is P14.
================================================================================
12. CONTACTS ARE FREQUENT: THE POSTERIOR LOWER BOUND
================================================================================
12.1 What changes, and why a martingale is needed.
The upper bound compared the arrangement with independent bridges of prescribed
heights, and the comparison CHEAPENED the contact: under the bridge law a
contact is unlikely. For a lower bound we must do the opposite: start from a
situation in which the two paths are forced to be close, and show that contacts
cannot be avoided.
The new difficulty is that the positive path is a BRIDGE: it ends at a random
endpoint E, and the negative path is started at that same E. The two paths are
therefore coupled through the endpoint. Worse, the endpoint is a quantity of
the future of the positive path, so we may not apply the Markov property at the
moment of first contact.
The repair has two parts.
(i) Weight counting: first contact prefixes are counted by raw weights and
transferred to one shared environment by [L2] while the posteriors are
still unrevealed; the environment is revealed only afterwards.
(ii) A martingale bound: the sum of the running maxima of the posterior
functions of the possible endpoints, over about N^2 endpoints, has an
exponential tail on the log N scale. That is L17.
12.2 L17 (posterior maxima).
Let m >= 1, and let (w_i(e)), i >= 0, 1 <= e <= m, be nonnegative martingales
for a filtration (F_i) with
sum over e=1..m of w_i(e) <= 1 almost surely, for every i.
Write A_i(e) = max over 0 <= j <= i of w_j(e), and A_i = sum over e of A_i(e),
and A_infinity(e) = lim A_i(e), A_infinity = lim A_i. Then there are absolute
constants c > 0 and C with
(12.1) E exp( c * A_infinity / log(m+1) ) <= C,
and for ANY event V on a joint probability space whose marginal is the
martingale path, with p = P(V),
(12.2) E[ A_infinity * 1_V ] <= C log(m+1) * p log(e/p),
with the right side read as zero when p = 0. The event V need not belong to any
F_i.
Two reading notes. (12.1) says: the typical size of the sum of the running
maxima is of order log m, with an exponential tail beyond that. (12.2) says:
conditioning an event of small probability makes the sum larger by at most a
logarithmic factor. Crucially (12.2) is an inequality about a marginal, so it
survives the appearance of new randomness (the revealed environment) that would
destroy the martingale property.
PROOF. Write B = log(m + 1). First claim: at every almost surely finite
stopping time rho,
(12.3) E[ A_infinity - A_rho | F_rho ] <= B.
For one coordinate put a = A_rho(e) and p_e = w_rho(e), so 0 <= p_e <= a <= 1.
The conditional maximal inequality for a nonnegative martingale gives
P( max_{j >= rho} w_j(e) > a + u | F_rho ) <= p_e / (a + u). Integrating over
levels u > 0,
E[ A_infinity(e) - a | F_rho ] <= integral from 0 to infinity of
p_e / (a + u) du = p_e log(1/a) <= p_e log(1/p_e),
and the case a = 0 contributes zero (a martingale with zero conditional
expectation at every later time stays zero in expectation of its maximum).
Summing over e and adding the missing mass gives at most the entropy of a
probability vector on m + 1 elements, hence at most B. That is (12.3).
Second, the tail. At each time the increase of a coordinate maximum is at most
that coordinate's current value, so
A_0 <= 1, 0 <= A_i - A_{i-1} <= sum over e of w_i(e) <= 1.
Set b = 2B + 1 and look at the thresholds 1 + k b, k >= 1. At a first strict
crossing the overshoot is at most 1, so after a crossing, reaching the next
threshold requires a further increase greater than b - 1 = 2B. By the
conditional Markov inequality and (12.3), the conditional probability of that
next crossing is at most 1/2; the first crossing has the same bound because
A_0 <= 1. Applying this at finite horizons and letting the horizon grow,
P( A_infinity > 1 + k b ) <= 2^{-k}.
Because B >= log 2, this is an exponential tail on scale B, and integrating it
proves (12.1).
Third, the event weight. For p > 0, conditional Jensen gives
exp( c E[A_infinity | V] / B )
<= E[ exp( c A_infinity / B ) | V ] <= C / p,
so E[A_infinity | V] <= (B/c) log(C/p); multiplying by p and adjusting the
absolute constant gives (12.2). Only a marginal exponential moment is used, so
this applies to events in a larger joint space.
12.3 P18 (first contact after a prescribed height).
Fix an integer N >= 3. Let Y be the annealed bridge from 0 to its first
arrival at height N, conditioned on reaching N before -1:
law of (Y_n : 0 <= n <= T_N) = P_0( . | T_N < T_{-1} ),
stopped at T_N.
Write E = pi Y_{T_N} for the lateral part of the endpoint. Independently
sample a negative path B with law P_hat_-, and translate it to start at
(N-1, E):
beta_j = (N-1, E) + B_j, j >= 0.
Thus the negative path is independent of the positive bridge as a relative
path, but its absolute position depends on the bridge's endpoint. Call a site
y an interior site if k <= y_1 < N, and write
Q_y^omega = P_{y,omega}( T_{k-1} < T_N )
for the quenched chance to exit at the bottom of the strip before the top.
Finally, for integers 0 < k < r < N, let
tau = inf{ i >= T_k : i < T_N and Y_i belongs to { beta_j : j >= 0 } },
Delta = u^+_{r-k} - u^+_{N-k},
with tau = +infinity if the set is empty, and with u^+ as in L11. Then
(12.4) P( T_r <= tau < T_N, min over T_k <= i <= tau of (Y_i)_1 >= k,
||E|| <= N^2 )
<= C log(2N) * Delta * log^2(e / Delta),
and the right side is zero when Delta = 0.
The estimate is useful when the remaining gap N - r is small compared with the
height r - k already crossed. By L12, Delta <= (N-r) F_+(r-k); section 12.4
arranges exactly this scale separation.
Note that tau refers to the WHOLE negative trajectory and is not a stopping
time for the positive path. That is why we enumerate finite prefixes.
PROOF, in five steps.
Step 1: the lower prefix and the endpoint likelihood. Let E_N be the set of
lateral offsets with norm at most N^2; its cardinality satisfies
(12.5) log( |E_N| + 1 ) <= C log(2N).
Enumerate a word a_0 from 0 to its first arrival at height k before hitting -1;
its departures have height below k. Write z for its terminal site. For each
e in E_N enumerate a word a from z to the first contact arrival: words that
stay in heights k,...,N-1 and reach height r no later than their terminal time.
For such a prefix define
w(a_0 a; e) = P_0( T_N < T_{-1}, pi X_{T_N} = e | X begins with a_0 a ),
a deterministic function of the two words and e. The departure sets of a_0 and
a are disjoint, so the prefix and completion have raw weight
(12.6) W(a_0) W(a) w(a_0 a; e).
For a raw negative walk started at (N-1,e), let B(a) be the event that it never
rises above height N-1, avoids Dep(a) at every time, and visits the terminal
site of a. This avoidance-plus-visit is exactly the first-contact condition.
(If the terminal site of a occurred earlier as a departure of a, then B(a) is
empty; this automatically excludes the degenerate case.) Summing (12.6) times
the raw probability of B(a) over words and endpoints, then dividing by
u_N^+ p_-, gives the probability on the left of (12.4).
Step 2: transfer and unique prefix counting. For a fixed word a, the quenched
probability of B(a) uses no row of Dep(a): the walk can be killed on first
arrival at that set, before any such row is used. This remains true for the
infinite avoidance event by passage from finite paths. Hence by [L2],
(12.7) W(a) P_{(N-1,e)}( B(a) )
= E[ p_omega(a) P_{(N-1,e),omega}( B(a) ) ],
where p_omega(a) is the quenched product along the word. This identity has not
been restricted by any environment-dependent condition; the classification is
still to come.
Keep W(a_0) as a scalar. In a fresh i.i.d. environment sample a raw walk Z from
z and a raw negative walk from (N-1,e), independently conditional on the
environment; call Z the comparison path. Then (12.7) expresses the sum over a
as an integral over these two full paths. For each realized pair at most ONE
prefix a of Z satisfies the avoidance-and-visit condition, because its terminal
is the first point of Z in the range of the entire negative path. This is a
pathwise uniqueness, no optional stopping at contact is used. The requirements
"stays above k-1" and "reaches r" are retained at this stage.
Step 3: stopped posteriors on the comparison path. Fix a_0 and consider the
original raw positive law conditioned on this lower prefix, in its natural
continuation filtration, with the environment unrevealed. The functions
w_i(e) = P_0( T_N < T_{-1}, pi X_{T_N} = e | a_0, continuation to time i )
are nonnegative martingales with sum at most 1 (they are conditional
expectations of the endpoint indicator). Stop them at the first arrival at
height k-1 or at height N. All departures up to that stop have height at least
k, so these rows are fresh under the conditioning on a_0, and the stopped
continuation has exactly the path law of Z stopped at
sigma = T_{k-1}(Z) and T_N(Z), whichever is first.
Arrival at the lower boundary uses a row at height k, not a departure row at
height k-1; the equality of laws therefore includes the terminal arrival. The
stopping time sigma is finite almost surely by L3 (a path that never leaves a
finite height interval would have a finite height supremum without tending to
minus infinity), and the quenched version holds for almost every environment,
for all starting sites and integer intervals.
Freeze the posterior functions on the observed prefixes of Z at sigma. At the
moment of arrival at k-1 their values need not vanish: they still describe
success before the original lower barrier -1, and that completion may use rows
affected by a_0. So we neither recompute them in the fresh environment nor
continue them below k. Put
M(e) = max over 0 <= i <= sigma of w_i(e), S_* = sum over e in E_N of M(e).
Then L17 with (12.5), applied in the path filtration of the stopped comparison
walk, gives uniformly in a_0:
(12.8) E[ S_* 1_V ] <= C log(2N) P(V) log(e / P(V))
for every event V on the joint space of the fresh environment and Z; in
particular E S_* <= C log(2N). It is the event-weight inequality (12.2), not a
martingale statement after revealing the environment, that permits the next
step.
Step 4: quenched exit-probability bins. For k <= y_1 < N define
Q_y^omega as above. Almost surely every transition entry at every site is
strictly positive, and a finite block of downward steps from y reaches k-1
before N with positive quenched probability, while a finite block of upward
steps reaches N first with positive probability. So 0 < Q_y^omega < 1, with no
common bound away from either endpoint. Partition these values into dyadic
bins [a, 2a), where a = 2^{-j}, j >= 1, and write D_a^omega for the set of
interior sites in one bin.
Let V_a be the event that, at or after its first arrival at height r and before
sigma, the comparison path visits an interior site with Q_y^omega >= a. With
the environment fixed, stop at the first such visit; the quenched Markov
property gives
(12.9) a P(V_a) <= P_z( T_r < T_{k-1} < T_N ) = Delta.
(Equality follows from nested first-hit events plus a.s. exit from the height
interval, again by L3.) On the other side, for almost every environment the
raw negative walk has probability at most 2a of satisfying D^- and hitting
D_a^omega: take its first visit to that set; on D^- the negative walk's height
supremum is finite, so by L3 (quenched, for all starting sites, outside one
null set) the height tends to minus infinity, and after that first visit it must
hit k-1 before N, with conditional probability at most Q_y^omega < 2a.
Now use the unique prefix from step 2. In the transferred integral, classify
the contact site by its Q^omega bin and bound its endpoint factor by M(e).
Dropping the exact-contact condition leaves V_a for the comparison path and
D^- intersected with {the negative path hits D_a^omega} for the negative path.
There is no sum over competing prefixes. After integrating out the negative
path, every endpoint e leaves the same fresh joint marginal, so the bin's total
contribution, summed over endpoints, is at most
(12.10) 2a E[ S_* 1_{V_a} ].
Step 5: summing the bins. If Delta = 0 then every V_a is null by (12.9), which
gives the required zero bound. Suppose Delta > 0.
* For bins with a < Delta, use (12.10) with the crude bound E S_* <= C log(2N),
and sum over the geometric family: sum over a < Delta of 2a <= 4 Delta.
* For bins with a >= Delta, use (12.8) and P(V_a) <= Delta/a; the contribution
is at most C log(2N) Delta log(e a / Delta) per bin.
There are O(log(e/Delta)) such bins, and their logarithms sum to
O(log^2(e/Delta)). Hence, for each fixed a_0, all contributions are at most
C log(2N) Delta log^2( e / Delta ).
Finally sum over a_0: sum of W(a_0) = u_k^+ <= 1, and 1/(u_N^+ p_-) <=
1/(p_+ p_-). Restoring these factors proves (12.4). The constants lose only
these fixed non-backtracking probabilities and the endpoint-cardinality factor;
no lower bound for Q_y^omega and no inverse-transition moment has been used.
12.4 P19 (many contact scales).
Suppose both coordinate signs have positive escape probability. In the opposed
arrangement of section 10, with m(J) as in (10.5), there are constants c > 0 and
J_0 < infinity such that
m(J) >= c J / log log(3 + J) for J >= J_0.
The proof has five movements: a bridge ending at a prescribed depth; an
uncovered band forcing a late first contact; averaging over the many cuts in
that band; removing the conditioning; and translating depths into block
indices.
PROOF. All constants may depend on the two slab laws. Take J large and put
(12.11) N = 2^{2J}, G = ceiling( 4 log_2 log(2 + J) ) + 3.
For large J we have 3 <= G < J. The factor 2^{-G} is of order
(log J)^{-4}, which compensates the logarithmic losses below, while
G = O(log log J) leaves enough contact scales.
Movement 1: a bridge ending at a prescribed depth. Let C_N be the event that
the positive tape has a cut at depth N, and let Q_N = P2( . | C_N ). By L11(a),
P2( C_N ) = u_N^+ >= p_+ > 0.
Under Q_N, reverse the list of positive slabs through that cut and translate the
bottom to the origin. The resulting chronological path is called Y, and T_a
denotes its first hit of height a. By L11(c), Y has law P_0( . | T_N < T_{-1} )
stopped at T_N; the steps inside each slab keep their original order. Write E
for the lateral endpoint, so the endpoint is (N, E). The negative trajectory
starts at (N-1, E) and, relative to that starting point, has the independent law
P_hat_-.
The endpoint has a crude tail bound. On C_N there are at most N positive slabs
before depth N, because widths are positive integers. The norm of their total
lateral displacement is at most the sum of their radii, hence at most the sum of
the first N positive tape radii. P9 and Markov's inequality give
(12.12) E_{Q_N} |E| <= N E_+ R / p_+,
Q_N{ |E| > N^2 } <= C / N.
Only a spatial first moment is used here.
Movement 2: an uncovered band forces a late first contact. Call l a contact
DEPTH LABEL if a contact occurs at some integer depth in [2^l, 2^{l+1}). For
G < l <= J let U_l be the event that none of the labels l-G, ..., l is a
contact depth label; equivalently, there is no contact at depths in
[2^{l-G}, 2^{l+1}).
Fix a positive cut depth s in I_l = [2^l, (3/2) 2^l], and put k = N - s. After
the list reversal this cut occurs at the bridge's first hit T_k, and the
remaining bridge stays at or above height k: every earlier slab has departure
heights below k, every later slab has departure heights at least k. This is a
property of the words, not a stopping-time assertion about the cut.
There is a contact after T_k and before T_N: the last positive departure is
(N-1, E), which is the starting departure site of the negative trajectory. Let
tau be the first contact since T_k, defined pathwise against the entire negative
trajectory. Its depth is at most s < 2^{l+1}. On U_l it must therefore be
strictly less than 2^{l-G}. With
r = N - 2^{l-G},
the nearest-neighbour path must have reached height r before this contact. So
(12.13) T_r <= tau < T_N, Y_n . e_1 >= k for T_k <= n <= tau.
No restriction on drawdowns from the running maximum is needed.
For each deterministic s in I_l let A_{l,s} be the event (12.13) together with
|E| <= N^2, whether or not s is a cut. P18 applies with upper stopping height N.
By L12 and s - 2^{l-G} >= 2^{l-1},
(12.14) Delta_{l,s} = u^+_{s-2^{l-G}} - u^+_s
<= 2^{l-G} F_+(s - 2^{l-G}) <= 2^{-G} a_l,
where a_l := 2^l F_+(2^{l-1}),
and the same lemma gives
(12.15) A := sum over l >= 1 of a_l < infinity.
With phi(x) = x log^2(e/x) for 0 < x <= 1 and phi(0) = 0, (12.4) is
(12.16) Q_N( A_{l,s} ) <= C log(2N) phi( Delta_{l,s} ).
Movement 3: averaging over the cuts. Let mu_+ = E_+ L. The renewal-count
strong law gives, almost surely under the positive tape law,
the number of positive cuts in I_l = 2^{l-1}/mu_+ + o(2^l).
Fix c_0 = 1/(4 mu_+), and let Good_J be the event that each interval I_l with
G < l <= J contains at least c_0 2^l positive cuts. Since G tends to infinity
with J, the almost sure statement gives P2( Good_J^c ) = o(1), and
(12.17) Q_N( Good_J^c ) <= P2( Good_J^c ) / p_+ = o(1).
No independence between the cut at N and the density event is required.
On Good_J intersected with {|E| <= N^2}, every uncovered label l produces A_{l,s}
for each ACTUAL cut s in I_l. Hence
(12.18) 1_{U_l} 1_{Good_J} 1_{|E| <= N^2}
<= (1/(c_0 2^l)) * sum over s in I_l of 1_{A_{l,s}}.
The right side has dropped the cut requirement on s, which is what allows the
deterministic-barrier estimate (12.16); the number of summands is O(2^l) and
cancels the averaging factor.
The logarithmic losses. For J >= 3 put
B_J = sum over l=1..J of a_l log_+^2(1/a_l),
with log_+ x = max(log x, 0) and zero summands read as zero. Terms with
a_l >= J^{-2} contribute at most 4 A log^2 J. On (0, J^{-2}) the function
x log^2(1/x) is increasing, so the remaining at most J terms contribute at most
4 J^{-1} log^2 J. Hence
(12.19) B_J <= 4 (A + 1/J) log^2 J.
For large J, 2^{-G} a_l <= 1/e uniformly in l, since a_l <= A. The function
phi is increasing on [0, 1/e], so by (12.14), uniformly over s in I_l,
phi(Delta_{l,s}) <= C 2^{-G} a_l ( G + 1 + log_+(1/a_l) )^2.
Take expectations in (12.18), then use (12.12), (12.16), (12.17):
(12.20) sum over l=G+1..J of Q_N(U_l)
<= J Q_N(Good_J^c) + C J / N
+ C log(2N) 2^{-G} ( A (G+1)^2 + B_J )
= o(J).
Indeed log(2N) = O(J), and (12.11) gives 2^{-G} = O(log^{-4}(2+J)), so by
(12.19) the last term is O( J / log^2(2+J) ).
Movement 4: removing the conditioning. Let H_J count contact depth labels in
{1,...,J}. Equation (12.20) and Markov's inequality imply that, with
Q_N-probability tending to 1, at most J/4 of the tested labels are uncovered.
Since G = o(J), at least J/2 labels are then covered. A single contact depth
label h can cover only the labels h, h+1, ..., h+G. Hence
(12.21) Q_N( H_J >= J / (2(G+1)) ) tends to 1.
For large J all depths counted here are less than 2^{J+1} < N, so on C_N they
are fully represented in the positive list ending at depth N. Undoing the
translation and the list reversal leaves exactly the contacts in the original
opposed arrangement. Hence
(12.22) P2( H_J >= J / (2(G+1)) ) >= p_+ - o(1).
Only a probability bounded away from zero is asserted after removing the
conditioning, and that is enough for an expectation lower bound.
Movement 5: from depths to block indices. Write K_1, K_2, ... for the common
block widths and W_i = K_1 + ... + K_i. By L13, mu := E2 K_1 < infinity and
W_i / i converges to mu almost surely. In particular, eventually
(mu/2) i <= W_i <= 2 mu i. An integer depth z >= 1 belongs to the unique block
i(z) = min{ i >= 1 : W_i >= z },
with W_{i(z)-1} < z <= W_{i(z)}. (The departure-height convention makes this
correct even at a common cut depth.) For every sufficiently large z the
strong-law bounds give
(12.23) z / (2 mu) <= i(z) < 2z/mu + 1.
Define the dyadic index label of a block i > 1 by j(i) = ceiling(log_2 i) - 1,
so that 2^{j(i)} < i <= 2^{j(i)+1}. Then (12.23) gives a deterministic integer
c_1, depending only on mu, with
(12.24) | j(i(z)) - l | <= c_1 whenever 2^l <= z < 2^{l+1},
eventually, above a finite random depth. So the probability that (12.24) holds
for every contact with ceiling(sqrt J) <= l <= J tends to one.
Intersect that event with the event of (12.22): the intersection still has
probability at least p_+ - o(1). Discard the first ceiling(sqrt J) depth
labels, losing o( J/(G+1) ) labels. Each remaining contact depth label supplies
a contact block whose index label lies within c_1 of it, and conversely one
index label accounts for at most 2 c_1 + 1 depth labels. Hence, on the
intersection, at least c_2 J/(G+1) of the index labels 1,...,J+c_1 contain a
contact, for a fixed c_2 > 0 and large J. Taking expectations,
m(J + c_1) >= c_3 J / (G + 1).
Since G + 1 = O(log log(3+J)), this proves P19.
================================================================================
13. THE CONTRADICTION, AND THE PROOF OF T1
================================================================================
T1 (restated). Let d >= 3, let the rows be independent identically
distributed and strictly elliptic, and let v be any nonzero real vector. Then
P_0(A_v) is 0 or 1.
PROOF. Suppose toward a contradiction that for some nonzero v,
0 < P_0(A_v) < 1.
Step 1: both signs of v. By L7, P_0(A_v) + P_0(A_-v) >= 1, so
P_0(A_-v) > 0 as well (7.2).
Step 2: small slabs. By P9, the slab radii in both signs of v have finite
mean.
Step 3: opposite rays, hence a coordinate. By P10 there is a coordinate i with
P_0(A_{e_i}) > 0 and P_0(A_{-e_i}) > 0. Relabel so that i = 1. From here on
the direction is the coordinate e_1, all heights are integers, and both signs
are positive with p_+ > 0 and p_- > 0.
Step 4: build the two tapes. Sections 10 constructs the opposed arrangement of
two independent tapes of slabs, with the common blocks of L13 and the contact
count m(J) of (10.5). No further assumption enters.
Step 5: contacts are rare. By P14, m(J) = O(J / log J).
Step 6: contacts are frequent. By P19, m(J) >= c J / log log(3+J) for all
large J, with a fixed c > 0.
Step 7: the comparison. For large J,
c J / log log(3+J) <= m(J) <= C J / log J.
Divide by J: c / log log(3+J) <= C / log J. But log log J grows slower than
log J, so for large J the left side exceeds the right side. A contradiction.
Hence no direction has probability strictly between 0 and 1, and P_0(A_v) is 0
or 1. T1 is proved.
13.1 What was used, and what was not.
Each numbered result contributed exactly one of the following:
L2 independence of distinct rows (the only use of "iid")
L3 strict ellipticity without a uniform lower bound
L4 positivity of p_v, and the floor u_H >= p_sigma in L11
L5 the regeneration structure (slabs, i.i.d. and exact law)
L6 finite mean width, hence a legitimately growing height
L7 the sign union, hence "both signs" from "one mixed sign"
P9 finite mean spatial radius, hence honest rays
P10 reduction to a coordinate direction
L11 bridge laws, hence the reference law of section 11
L12 renewal tails, hence summable reference probabilities
L13 common blocks with finite mean width and lateral moment
L8 the maximal inequality that makes "most prefixes are good"
P14 m(J) = O(J/log J)
L17 the posterior estimate, hence the endpoint coupling is affordable
P18 first contact after a prescribed height
P19 m(J) >= cJ/loglog(3+J)
Nothing else was used. In particular: no uniform ellipticity, no reversibility
or balance, no drift or speed assumption, no logarithmic moment of the
transition probabilities, no inverse-transition moment, no moment of a slab's
DURATION, and no null set uniform in the direction.
13.2 On the hypothesis d >= 3.
The hypothesis d >= 3 marks the range where the statement was open: for d = 1
the statement is trivial (one step up, one step down), and for d = 2 it is
Zerner and Merkl's theorem. The argument above does not visibly use d >= 3
anywhere: the tilts need one signed coordinate (so d >= 2), the entropy
exponent is q = d - 1, and the tape bookkeeping is one-dimensional in depth.
We claim nothing beyond the stated theorem. If a reader wants to check where
three dimensions could ever matter, the honest answer is: nowhere in this
proof, and that is worth noticing rather than hiding.
================================================================================
14. WHAT EACH HYPOTHESIS IS FOR
================================================================================
Here is the complete list of assumptions, each with the exact place it is used
and what fails without it.
14.1 Independence of the rows at distinct sites.
Used at exactly one place: [L2], the factorization of a word's weight against
the rows outside its departure set. Consequences: the slab law is the annealed
weight W(gamma) (L5); words with disjoint departure sets have multiplicative
weights (L11, L16, P18); the lateral gap increments of common blocks are i.i.d.
(L13).
Without independence: Bramson, Zeitouni and Zerner (2006) constructed
STATIONARY, polynomially mixing, uniformly elliptic environments in d >= 3 in
which linear escape happens in two opposite directions, both with positive
probability. In those environments the conclusion of T1 fails for some
direction, so no amount of mixing replaces independence. (Their Open Problem 3
asks the i.i.d. question, which is T1.)
14.2 Strict ellipticity: every entry positive almost surely, no common lower
bound.
Used at four places:
* L3, second case: q_a = E p_0(a) > 0, so the fixed upward script succeeds
eventually. This is the only place where a genuinely fresh-row probability
is computed from the environment law.
* P9: alpha = min over e' of E p_0(e') > 0, the cost of the forced downward
script, and p_* = min(p_+, p_-) > 0.
* L11(a): u_H >= p_sigma > 0, so common cuts are not too rare (L13).
* 9.2(a): the walk exits every finite interval, quenched, for almost every
environment, for all starting sites and barriers.
Note that the third and fourth items need only positivity of each entry at each
individual site, with NO uniform bound: the quenched exit property follows by
combining L3's almost sure statement with countability of the barriers and
starting sites. This is the conceptual core of why uniform ellipticity is not
needed.
Without any positivity (allowing zero entries): a site could be a trap, or a
line could be a wall, and the whole regeneration structure can fail.
14.3 Nearest-neighbour steps.
Used for: heights changing by at most 1 per step (L6's L <= S, and the
"column" argument in L3); the integer height structure in a coordinate
direction (9.2(b), hence the guaranteed contact); and the depth bands of the
tapes.
Without it, the constants change but a much longer argument is needed (Slonim
2024 does bounded jumps in the plane under an extra communicating-class
condition).
14.4 Dimension d >= 3.
Marks the open range; not visibly used (13.2).
14.5 A real direction v, not only rational ones.
Nothing in the proof rounds v. Heights in a real direction may be non-integer,
which is why L6 counts RECORDS rather than levels, and why the widths have
finite mean but are not lattice valued. Once P10 reduces to a coordinate
direction, the integer structure of heights is used freely.
14.6 What is NOT assumed, and why that is surprising.
* No uniform ellipticity (see 14.2).
* No reversibility, no balance condition, no vanishing of a local drift.
* No assumption that A_v has positive probability: that enters only as a
hypothesis for the contradiction.
* No inverse-transition moment. The classical proofs often need control of
ratios p_x(e)/p_x(-e); here the quenched classification of section 12 uses
only one-sided probabilities.
* No speed, ballisticity, or moment of slab duration. P9 is a purely
spatial moment statement, proved by a scale argument with a tilted
functional, not by a ballistic estimate.
================================================================================
15. GLOSSARY
================================================================================
The grid and the walk
d dimension, d >= 3 in the theorem.
Z^d the sites, integer points.
e_1,...,e_d unit coordinate steps.
U the 2d allowed steps: +e_i and -e_i.
p_x(e) transition probability at site x in direction e.
mu the law of one row; rows at different sites are independent.
P, E the environment law and its expectation.
P_x annealed law of the walk started at x; E_x its expectation.
P_{x,omega} quenched law, environment omega held fixed.
X_n the walker's site at time n.
strict ellipticity p_x(e) > 0 for every e, for almost every environment;
no common lower bound.
uniform ellipticity p_x(e) >= eps for one fixed eps > 0; NOT assumed.
Directions and escape
v a nonzero direction; h(x) = x . v is the shadow.
A_v { X_n . v tends to +infinity }.
D_v { h(X_n) >= 0 for all n }, the non-backtracking event.
p_v, P_hat_v P_0(D_v) and the law conditioned on it.
sup, inf supremum, infimum; a path with finite height supremum must
tend to minus infinity (L3).
Words, slabs, records
word gamma a finite nearest-neighbour path x_0,...,x_m.
Dep(gamma) its departure sites x_0,...,x_{m-1}.
W(gamma) annealed weight, the probability of the word (1.6).
rho_i the i-th ordinary strict record time.
tau_i the i-th true cut (finite record never undercut afterwards).
regeneration word a word with 0 <= h < h(z) at every departure and every
internal record cancelled before the end (6.4).
slab the relative word between two true cuts.
nu_v the slab law: nu_v(gamma) = W(gamma). Also written nu_+,
nu_-.
L(gamma) width, = h(z) > 0. R(gamma) spatial radius.
S number of ordinary records in a slab (L6).
E_sigma expectation in a slab sequence of the sign sigma.
Bridges and renewal
T_j first hit of signed height j.
u_j P_0(T_j < T_{-1}); the cut probability at height j (L11).
F(j) nu(L > j), the width tail.
B_H the bridge law of slab lists of total width H (L11).
kappa_k entropy of S_1 + ... + S_k, the gap after k common blocks.
The two tapes
A_i, B_i the i-th positive and negative slab.
P2, E2 joint law of the two tapes and its expectation.
depth of x -x_1, distance below the top site 0.
H_i^+, H_i^- cumulative positive and negative slab widths.
K_j, W_j common block widths and their partial sums.
i(z) block index containing depth z.
contact a site that is a departure of both placed tapes.
C(a,b] event that some block with a < j <= b contains a contact.
m(J) expected number of dyadic block bands 1..J with a contact.
Information
H(V) entropy of the variable V (classical, base e).
D(P||Q) relative entropy of P with respect to Q.
I(X;Y|Z) conditional mutual information.
P_n, Q_n the actual and reference laws of the window (section 11).
delta_n the reference contact bound C n (F_+(n) + F_-(n)).
E_mid the middle-chunk contact event.
Q_y^omega quenched chance to exit the strip at the bottom before the
top, from site y; the classifier in section 12.
Constants
C, C_0, C_1, c, b, B, eta, rho, delta, alpha, p_*, mu, mu_+, c_0, c_1, c_2,
c_3, G, N, J, n, l, a, i_0, M fixed positive numbers, each introduced once
and never changed.
================================================================================
16. INDEX OF RESULTS
================================================================================
L2 (5.2) Fresh rows: a word's weight factors against everything outside its
departure set. The only place independence is used.
L3 (6.2) Finite height supremum forces escape to minus infinity.
L4 (6.3) Escape in direction v with positive probability gives p_v > 0.
L5 (6.4) Slabs exist, are i.i.d., and have law W; the exact factorization.
L6 (6.5) 0 < E L <= E S <= 1/p_v < infinity.
L7 (7.1) P_0(A_v union A_-v) = 1; infinite supremum gives A_v.
L8 (8.1) Hopf's maximal inequality for initial averages.
P9 (8.2) Coexistence of both signs gives finite mean slab radius, both
signs, proved by a tilted-record scale argument.
P10 (9.1) A mixed real direction yields a mixed coordinate direction.
L11 (10.1) Exact-cut bridges: cut probabilities u_H, bridge law B_H, list
reversal invariance.
L12 (10.2) Renewal tail 0 <= u_n - u_n' <= (n'-n) F(n), and summable dyadic
width tails.
L13 (10.4) Common blocks are i.i.d., E K <= 1/(p_+ p_-), finite mean lateral
displacement.
P14 (11.1) Contacts are rare: m(J) = O(J / log J).
L15 (11.5) Entropy comparison: D(P_n||Q_n) <= C + kappa_{14n} - kappa_n, and
the price per dyadic scale is O(1).
L16 (11.7) Under the reference law a middle contact has probability at most
C n (F_+(n) + F_-(n)).
L17 (12.2) Posterior maxima: exponential tail on scale log m, and the marginal
event-weight bound (12.2).
P18 (12.3) First contact after a prescribed height: bound
C log(2N) Delta log^2(e/Delta).
P19 (12.4) Contacts are frequent: m(J) >= c J / log log(3+J).
T1 (13) The directional zero-one law.
================================================================================
17. THE WHOLE PROOF ON ONE PAGE
================================================================================
1. Regeneration (L5, L6). Look at the record heights of the shadow h(X_n).
The heights that are never undercut are the true cuts. The pieces of walk
between cuts are independent, identically distributed slabs, and the
probability of a particular slab is its annealed weight W. A slab's width
has finite, positive mean.
2. One sign or the other (L7). Because the mean width is positive and finite,
the cut heights climb to infinity on the event of infinite height
supremum, and the alternative event forces descent to minus infinity.
Hence P(A_v union A_-v) = 1.
3. Small slabs (P9). If both signs escape, big lateral excursions are
impossible: a huge excursion yields a new record for a tilted functional,
from which a forced short descent plus a fresh opposite-going copy keeps
the walker's final maximum in a window whose bottom grows with the scale,
with probability bounded below. That is impossible. So slab radii have
finite mean, and the walk leaves honest rays behind it.
4. Opposite rays (P10). Two different rays of one walk must be opposite,
because otherwise a tilted direction is escaped with probability one and
its ray would be a deterministic tail function, hence unique. So some
coordinate has both signs. Reduce to e_1; from now on heights are
integers.
5. Two tapes (section 10). Place one tape of positive slabs with its terminal
at the top, and one tape of negative slabs starting one level below the
top. Depth is -x_1. Both tapes' departures live in the depth bands of
their words, up to a one-level shift; the shift buys one guaranteed
contact. The fronts where both tapes cut are the common blocks; their
widths and lateral moments have finite mean (L13). Let m(J) count dyadic
bands of blocks containing a contact.
6. Contacts are rare (P14, via L15, L16). Replace a window of three chunks by
independent bridges at the same heights and with the same lateral
alignment. That swap costs O(1) bits per dyadic scale, because the number
of blocks in each chunk is random. Under the bridge law, a middle contact
forces both paths to cross a fixed height inside a finite slab; whichever
path does it must pay a quenched exit probability of at least 1/2, which
costs at most u_n - u_N <= N(F_+ + F_-). A probability delta can pay for
at most 1/log(1/delta) minus the entropy price, so summing over J scales
gives m(J) = O(J/log J).
7. Contacts are frequent (P19, via L17, P18). Condition on a cut at a huge
depth N. Reverse the list; the positive path becomes a bridge from the
bottom to a random endpoint E, and the negative path starts at (N-1,E).
If a whole band of depths near the bottom had no contact, then the first
contact above any cut in that band must occur very near the top, which
costs about log^2(1/Delta) in the first-contact estimate. The endpoint
coupling is affordable because the sum of the running maxima of the
endpoint posteriors has an exponential tail on the log N scale (L17), and
because the classification into dyadic quenched exit probabilities is made
only after the fresh-row transfer. Averaging over the many cuts in each
band leaves at most J/4 uncovered bands among J, hence at least J/(2(G+1))
contacts with G about 4 log log J, i.e. m(J) >= cJ/loglog(3+J).
8. Contradiction. J/log J cannot be at least cJ/loglog J for ever. So no
direction has escape probability strictly between 0 and 1.
The two halves are genuinely different, and both are needed:
the upper bound is an INFORMATION statement (a contact is rare unless the
walker's displacement carries enough information to align the tapes);
the lower bound is a FORCING statement (near a high cut, the two tapes have
no room to avoid each other, and the endpoint randomness is affordable).
================================================================================
APPENDIX A. THE SIX TOOLS, PRECISELY
================================================================================
A.1 Markov chains and the strong Markov property. For a fixed environment the
walk is a Markov chain: conditional on X_n = x, the law of the future is
P_{x,omega}. This holds at any stopping time T, in the form
P_{x,omega}( future in B | F_T ) = P_{X_T,omega}(B) on {T < infinity}. We use
it in L3 (trials at first visits), in 6.4 (candidate records), and in section
12 step 4 (first bin visit). We never use it at a time defined with the future.
A.2 Stopping times. T is a stopping time if {T <= n} is in
sigma(X_0,...,X_n). Ordinary records rho_i are stopping times; true cuts tau_i
are not. For future-dependent times, the replacement is the exact weight
factorization of L5.
A.3 Martingales and Ville's inequality. A sequence (Z_n) is a martingale if
E[Z_{n+1} | F_n] = Z_n. If Z is a nonnegative martingale and lambda > 0, then
P( sup_n Z_n >= lambda ) <= E Z_0 / lambda (Ville). The conditional form used
in L17 is: for a nonnegative martingale started at p <= a, and levels u > 0,
P( sup_n Z_n > a + u | F_0 ) <= p/(a+u). Integrating over levels turns this
into E[sup_n Z_n - a] <= p log(1/a).
A.4 Strong law and Borel-Cantelli. Averages of i.i.d. integrable variables
converge to their mean; and summable probabilities give finitely many
occurrences almost surely. Used for the width and radius laws (L6, P9, 9.1),
for the cut density in P19 (movement 3), and for summable width tails (L12).
A.5 Renewal processes. Points at i.i.d. distances L_i on the line: the count
up to height h is h/E L + o(h) almost surely when E L < infinity (used in P19
movement 5), and the renewal identity sum_k F(k) u_{n-k} = 1 holds exactly
(L12). The strong law for the truncated distances is what rules out
E L = infinity (L6).
A.6 Entropy and relative entropy. For a countable variable V,
H(V) = - sum_v P(V=v) log P(V=v). For laws P, Q on a countable space,
D(P||Q) = sum_x P(x) log( P(x)/Q(x) ), infinite if P is not absolutely
continuous with respect to Q. Used facts, each proved by factoring joint
probabilities into marginal times conditional:
(i) chain rule: D(P(x,y)||Q(x,y)) = D(P(x)||Q(x))
+ averaged D( P(y|x) || Q(y|x) );
(ii) data processing: applying a measurable map cannot increase D;
(iii) nonnegativity: D >= 0 (Jensen);
(iv) a positive integer variable with mean a has entropy at most
1 + log(a+1) (its weights are dominated by a geometric law with the
same mean);
(v) binary divergence: an event of P-probability a and Q-probability b > 0
satisfies a log(1/b) <= D(P||Q) + 2 log 2 (11.6);
(vi) countable spaces need no finiteness assumption: first use finite
partitions, then pass to the increasing limit.
A.7 Countability. The grid, the set of finite words, and the set of integer
barriers are countable. Every "for every site / every word / every barrier"
statement is obtained by intersecting countably many almost sure statements.
This is how the quenched exit property of 9.2(a) is upgraded from a single
starting site to all of them.
================================================================================
APPENDIX B. CORRECTIONS AND CLARIFICATIONS RELATIVE TO THE ORIGINAL
================================================================================
This rewrite was made from directional_zero_one_ellipticity_original.txt. The
following points are either corrected or made explicit; nothing else about the
mathematical content was changed.
B.1 The one-level shift of the negative tape (10.3, 10.5). The original says
that a word of width L, preceded by total tape width s, "has all its departures
in the progress interval (s, s+L] on either tape". For the positive tape that
is correct as stated. For the negative tape, placed chronologically from -e_1,
the departures lie in the depth band (s+1, s+L+1]: the offset of one level is
exactly what makes the guaranteed contact at -e_1 exist, and it cannot be
removed without losing that contact. Consequently the original's statement
that a contact "always belongs to the same unique common block on both tapes"
holds only up to one block index, as spelled out in 10.5. All estimates
survive: they are dyadic sums, and shifting a block index by one changes a sum
by one boundary term, absorbed into the constants.
B.2 The guaranteed contact (10.3). The original writes "the last positive step
into the top is axial". The reason it is +e_1 and not merely axial needs the
integer-height structure: after the reduction of P10, heights in a coordinate
direction are integers, the terminal site is a strict maximum of the word, and
the step into it departs from a site of relative height at least L-1, so the
gain is exactly +1. This is now 9.2(b), and 10.3 cites it.
B.3 Statement of the coordinate reduction (P10, 9.1). The original states the
proposition with the hypothesis "0 < P_0(A_v) < 1" and then uses "both signs of
v have positive probability"; that inference needs L7, and is now made
explicit as 7.2.
B.4 Sum of the two final-maximum terms (8.8). The original takes the sum over
both signs of P( c i_0/2 <= M_sigma < infinity ) and lets i_0 grow. No
disjointness of the two events is needed: each term tends to zero because the
events decrease to the empty set. This is stated in 8.8.
B.5 The lower stopping barrier in the first-contact estimate (12.3, step 3).
The strip is the integer height interval [k-1, N), and the comparison path is
stopped on ARRIVAL at height k-1 or N. Arrival at k-1 uses the row at height
k, which is a departure row, not a row at height k-1. That is why the stopped
path law agrees with the fresh comparison walk, and the original's remark about
"the terminal arrival" is now expanded into that sentence.
B.6 Notational clash. The original uses h for both the height functional
h(x) = x . v and the gap entropy h_k = H(S_1 + ... + S_k). This rewrite writes
kappa_k for the entropy, so no display depends on the reader guessing which h is
meant.
B.7 Randomised window counts (11.3). The original's display for the four
counts, the four-value range "10n <= T <= 14n-4" and the containment of the band
(4n, 8n] are all present, but the reason for the randomisation is now stated
before the computation: the log n cost of specifying a chunk's height is exactly
what the uniform count distribution pays for.
B.8 Minimality and concavity (8.3). The chain in (8.3) uses both minimality of
N(a) and concavity of I; the original writes it in one line. Concavity is
stated in 8.3 so that the inequality can be checked rather than trusted.
B.9 The constant in (8.4). The original requires "4 C_1 eta < .15" and
concludes P(R_m) > .8. The arithmetic is 0.95 - 4 C_1 eta > 0.8, which is now
displayed once.
B.10 Dimension. The original states the theorem for d >= 3. As noted in
13.2, nothing in the argument visibly uses d >= 3; d = 2 is Zerner-Merkl and
d = 1 is trivial. This is a remark about the proof, not a new theorem.