A walker moves on the integer lattice in a fixed dimension, at least three.
At every site the walker looks at arrows drawn on the floor and picks one
at random with the probability written beside it. The floor itself was
drawn once, at random, from a fixed probability law, and then left alone.
The same arrows are waiting whenever the walker returns to a site. This
persistence is the feature that makes the problem hard.
Two kinds of randomness act at once. The walker rolls dice. The floor is
frozen. The question is whether the walker can drift off to infinity in a
fixed direction with probability strictly between zero and one, after
averaging over both kinds of randomness.
The answer is no. Along any fixed nonzero real direction, the event of
escape on the positive side of the perpendicular hyperplanes has probability
zero or one. It cannot be one half, one third, or 0.9999. This is the
directional zero-one law. It is not the same as a law of large numbers, not
the same as positive speed, and not the same as the existence of a limiting
direction of the walk. Only the all-or-nothing statement for escape is at
stake.
The proof works under three assumptions on the environment law: stationarity
and ergodicity under lattice translations, uniform ellipticity with some
constant kappa strictly positive, and finite-range dependence with some
integer R, meaning that two sets of sites at l_infinity distance greater
than R carry independent transition rows. Each assumption is used directly.
The proof rules out coexistence of escape in opposite directions. Once
coexistence is excluded, the sign-union law and a reduction to a coordinate
direction finish the argument for arbitrary real directions.
The strategy is a coincidence of two estimates that cannot both hold. If
escape in two opposite directions carried positive probability, one could
produce two independent flowing paths, one climbing and one descending, in
the same environment, and lay them next to each other. Those two paths must
come within dependence distance a number of times of order J over log log J
among the first J dyadic scales. An information (entropy) estimate says the
same number is at most of order J over log J. The two orders cannot match,
and both estimates are honest. That is the whole shape of the proof. The
first estimate is a lower bound on the number of contacts, from posterior
martingales. The second is an upper bound, from entropy.
Everything before the coincidence is machinery for manufacturing two
genuinely independent infinite paths inside a dependent environment. The
environment is stationary but not independent across sites, so the classical
regeneration theory in an iid landscape does not directly apply. Regeneration
is created instead by adding extra marks to each step. A marked step is
either a coin flip with probability independent of the environment or an
ordinary use of the local transition row. A block of forced coin flips
covers distance without revealing a row. The next piece of path then looks
at rows that are independent of everything observed so far. The device goes
back to the splitting construction of Comets and Zeitouni, and the
independent-coin version used in the strictly elliptic setting is
recorded.
./comets-zeitouni-2004.pdf
The model is fixed as follows. The dimension d is at least three. Sites are
points of the integer lattice Z^d. The permitted steps are the 2d coordinate
unit vectors
U = { +e_1, ..., +e_d, -e_1, ..., -e_d }.
An environment is a map omega assigning to each site x and each permitted
step e a number omega(x, e) in [0,1], with each row summing to one:
sum over e in U of omega(x, e) = 1.
The law of the environment is a fixed Borel probability measure Q on the
compact product space of all such maps. Fixing omega gives a Markov chain
P_{x, omega} that starts at x and, at a site y, steps by e with probability
omega(y, e). Averaging over the environment gives the annealed law
P_x = integral of P_{x, omega} with respect to Q.
Positions of the walker are written X_0, X_1, X_2, and so on. Only the
positions matter, so time is not tracked.
Q satisfies three assumptions. First, stationarity under all
lattice translations, together with ergodicity: any event that is invariant
under every translation has probability zero or one. Second, uniform
ellipticity: there is a constant kappa strictly positive such that, with
Q-probability one, omega(x, e) is at least kappa for every site and step.
Third, finite-range dependence: there is a nonnegative integer R such that,
whenever two nonempty deterministic sets of sites A and B satisfy
dist_inf(A, B) = inf over a in A, b in B of max_i |a_i - b_i| > R,
the sigma-fields generated by the rows at sites of A and at sites of B are
independent. The finite-range condition covers infinite deterministic sets.
This is a strictly stronger requirement than decay of local correlations, and
the difference matters: Bramson, Zeitouni, and Zerner built stationary,
uniformly elliptic environments with polynomially decaying correlations, in
dimension at least three, in which escape in two opposite directions each
carry positive probability.
./bramson-zeitouni-zerner-2006.pdf
Escape in the direction of a nonzero real vector v is the event
A_v = { v . X_n tends to +infinity as n grows }.
The main statement is that, under the three assumptions, P_0(A_v) belongs to
{0,1} for every fixed v. Direction v is chosen before randomness is sampled
and may be irrational. The proof uses stationarity and finite-range
independence directly, without further appeal to ergodicity. The independence
arguments concern separated sigma-fields of rows, not representations of the
environment in terms of independent labels.
Earlier work frames the problem. In two dimensions, Zerner and Merkl proved
the directional zero-one law for iid elliptic environments, and Zerner
revisited the planar argument. In higher dimensions, Kalikow's regeneration
formulation and the Sznitman-Zerner record construction give the sign-union
law, but leave the choice of sign open. Limiting-direction statements for
iid elliptic environments appear in the work of Simenhaus and, in a
revisited form, of Drewitz and Ramirez. For mixing environments,
Rassoul-Agha derived a law of large numbers under a directional zero-one
hypothesis, and Guo proved conditional velocity results under a mixing
assumption that includes finite-range dependence. Those velocity statements
do not determine the two directional escape probabilities.
./kalikow-1981.pdf
https://projecteuclid.org/journals/annals-of-probability/volume-29/issue-4/A-Zero-One-Law-for-Planar-Random-Walks-in-Random/10.1214/aop/1015345769.full
./zerner-2007.pdf
./simenhaus-2007.pdf
./drewitz-ramirez-2010.pdf
./rassoul-agha-2005.pdf
./guo-2014.pdf
Two obstacles block the iid route. Two pieces of the path, although disjoint
in space, may use rows that are correlated if the pieces pass within
distance R of one another. And a piece of path already observed tells
something about nearby rows that a future piece may want to use. The
following splitting device removes both at once.
Fix a constant lambda strictly positive with 2 lambda < kappa. Enrich each
step with a mark in {0, 1, *}. Conditional on the environment and on the
marked past, a step from x by e has joint probabilities
P(x -> x + e, mark 0) = lambda,
P(x -> x + e, mark 1) = lambda,
P(x -> x + e, mark *) = omega(x, e) - 2 lambda.
The three numbers are nonnegative by 2 lambda < kappa and sum to omega(x, e).
Summing over marks recovers the unmarked transition row. Every assertion
about the unmarked path therefore survives. A step marked 0 or 1 is chosen
with probability that is constant in the environment.
Call a law raw if it imposes no side condition on the walker. The path
filtration is enlarged to include the marks of steps already taken.
A finite marked word gamma is a finite list of positions x_0, ..., x_t with
consecutive differences in U, together with the mark of each of the t steps.
Two subsets of positions matter:
Dep(gamma) = { x_0, ..., x_{t-1} }, the departure sites,
Act(gamma) = { x_j : 0 <= j < t and step j has mark * }.
Write p_omega(gamma) for the product of the marked transition probabilities
of the steps of gamma, and
W(gamma) = E_Q[ p_omega(gamma) ]
for the annealed probability of exactly that marked word. Stationarity makes
W invariant under translation of all positions in gamma. The final arrival of
a word uses no row. A visited row enters p_omega(gamma) only if it is an
active departure, because a mark 0 or 1 contributes the constant lambda
whatever the row says. This is the entire point of the marks.
Lemma. Let gamma be a fixed finite marked word and B a deterministic set of
sites with dist_inf(Act(gamma), B) > R. The convention is that distance from
an empty set is infinite. Let f be a nonnegative measurable function of the
rows at sites of B. Then
E_Q[ p_omega(gamma) f(omega) ] = W(gamma) E_Q[ f(omega) ].
Proof. Factors with marks 0 or 1 are constant. All other factors in
p_omega(gamma), including repeated departures from the same row, depend only
on the rows at sites of Act(gamma). Those rows are independent of the rows
at sites of B by finite-range dependence, which gives independence also when
B is infinite. Independence is the statement that the expectation of a
product of a function of one and a function of the other factorises. When Act
is empty, p_omega(gamma) itself is constant. QED
Lemma. Let F be a deterministic set of sites. The quenched law of the marked
walk stopped at its first arrival in F, including the arrival site, depends
only on the rows at sites outside F. Consequently the quenched probability of
any measurable infinite-path event that forces the walker to avoid F forever
also depends only on rows outside F.
Proof. Before first arrival in F the walker departs only from sites of the
complement, so every factor used so far is a row of that complement, including
the factor of the arrival step. The stopped law is a limit of stopping-prefix
probabilities, each determined by finitely many such rows. An event that
forbids entry into F is decided by the killed trajectory: it is false on
killed paths and keeps its meaning on surviving ones. QED
One consequence is used constantly. Suppose two prescribed words have
departure sets at distance greater than R. Their joint weight in a common
environment with conditionally independent walks equals the product of their
weights. The separated-weights lemma gives this, one factor at a time, and it
applies to an entire infinite continuation as well as to a finite word,
because of the killing lemma.
Fix a nonzero direction v and rescale so that |v|_infinity = 1. Put
h(x) = v . x,
the height of x. Choose a coordinate step a_v in U with h(a_v) = 1, which
is possible exactly because |v|_infinity = 1. Fix an integer
M > d R + 1
once and for all, the same M for every direction. Set xi = lambda^M.
The script in direction v is a fixed sequence of M steps: take
a_v, M times in a row, the first with mark 0 and the remaining M - 1 with
mark 1. The annealed probability of the script is lambda^M = xi, a constant
independent of the environment and of where it is used. Two occurrences of
the script cannot overlap in a step: the leading 0 of a second copy would
have to coincide with a 1 of the first copy. This is the only reason marks
0 and 1 are separated.
Time zero counts as a record. A positive time n is an ordinary record if
h(X_n) is strictly greater than each of h(X_0), ..., h(X_{n-1}). A candidate
is the endpoint of a script that started at a record. A candidate time t is a
cut if the walker never goes below it afterwards:
h(X_n) >= h(X_t) for every n >= t.
Every candidate is a strict record, because the M script steps raise the
height by M.
Two heights differ by at most d times the l_infinity distance:
|h(x) - h(y)| <= d |x - y|_infinity. (1)
Suppose a marked prefix ends at a record of height r. Every departure of the
prefix has height strictly below r. The script that follows has no active
departure at all, its steps being marked 0 and 1. A continuation that never
drops below its own starting height r + M departs only from sites of height
at least r + M. By (1) and M > dR, each such site is at l_infinity distance
greater than R from every active departure of the prefix. The continuation
never uses a row that correlates with the observed past.
Write
D_v = { h(X_n) >= 0 for every n >= 0 },
p_v = P_0(D_v),
Phat_v = P_0( . | D_v ), the nonbacktracking law.
The key identity is this. Let gamma_0 be a fixed marked prefix ending at a
record and B any event for a continuation, measured relative to the
continuation's own starting site. Then
P_0{ prefix gamma_0, then the script,
then a continuation in B that also lies in D_v }
= W(gamma_0) xi P_0(B and D_v). (2)
The script contributes the constant xi. The continuation contributes a
factor depending only on rows far from the active departures of gamma_0.
The separated-weights lemma factors the product, and stationarity identifies
the continuation factor with the unconditioned probability. QED
Reading (2) with B the whole space, the probability that the script follows
a record prefix and ends at a cut is
xi p_v. (3)
A scripted cut is found with a uniformly positive conditional probability
no matter what happened earlier, as long as p_v > 0.
A walker inside a slab { a <= h <= b } with a and b finite leaves it almost
surely under every uniformly elliptic quenched law. Take m > b - a; from any
site inside, m consecutive steps a_v leave the slab, and that has probability
at least kappa^m. Independent trials in successive blocks of m steps kill the
chance of never leaving. Under Phat_v, which forbids negative heights, the
walker cannot stay forever below any fixed level b, so on D_v the height
supremum is almost surely infinite.
A finite marked word starting at zero is a regeneration word, or a slab, if
(i) all its heights are nonnegative;
(ii) it ends at a candidate;
(iii) every earlier candidate inside the word is undercut later inside
the word, meaning some subsequent height is strictly smaller.
Records and candidates are computed inside the word. The width L of the slab
is the height of its endpoint. Since the final script starts at height
L - M and every earlier height is below L,
L >= M, 0 <= h(x) < L for x in Dep,
h(x) < L - M for x in Act. (4)
The last inequality is the one that buys independence: all active rows of a
slab sit far below its endpoint.
Regeneration theorem. Fix a direction v with |v|_infinity = 1 and suppose
p_v > 0. Let nu_v denote the law that assigns mass W(gamma) to each slab
gamma.
(i) Under the raw law P_0, on the event that the height supremum is
infinite, a cut exists almost surely.
(ii) Under Phat_v there are infinitely many cuts. Counting time zero as
an initial boundary, the relative marked words between successive
boundaries are independent and identically distributed with law
nu_v, and they concatenate to the entire path.
(iii) Under the raw law, conditional on a realized prefix through the
first cut, the translated suffix has law Phat_v.
That nu_v is a probability law, meaning that the masses W(gamma) sum to one
over slabs, is part of what (ii) says; it is proved, not assumed. In an iid
environment the statement is the classical Sznitman-Zerner regeneration. The
proof below uses the gap (4) instead.
Proof of (i). Test for a scripted cut starting at time zero. Failure of
the test is detected in finite time: either the next M steps are not the
script, or they are the script and the walker afterwards dips below the
endpoint. After a detected failure, wait until the height exceeds the maximum
attained up to the detection time, then test again. The test starts, when
finite, are stopping times of the marked filtration. At every test the
conditional probability of success is exactly xi p_v by (3). The probability
that the first j tests all occur and all fail is at most (1 - xi p_v)^j. If
the height supremum is infinite, then after every detected failure a further
test start eventually occurs. Letting j grow proves (i). QED
Proof of (ii), first cut. Suppose gamma is a slab ending at height z. A path
that begins with gamma and then stays at or above height z has its first cut
at the endpoint of gamma. All earlier candidates of gamma are undercut inside
gamma, so none of them is a cut; the terminal candidate is a strict record
that is never undercut afterwards.
Conversely, a path that stays nonnegative in height up to its first cut gives
such a slab. If an earlier candidate were not undercut before the terminal
record, it could not be undercut afterwards either, the suffix staying above
that record, and then it would already have been a cut, contradicting the
firstness.
Apply (2) with B any event for a translated suffix:
P_0{ first-cut prefix is gamma, translated suffix in B }
= W(gamma) P_0(B and D_v). (5)
Divide by p_v. Under Phat_v the first slab has mass W(gamma), and the
translated suffix has law Phat_v independent of the slab. There are countably
many finite marked words, and the first cut is finite almost surely under
Phat_v, so the masses add to one. This proves the first-cut part of (ii) and
also (iii). QED
Proof of (ii), iteration. A cut is a strict record, so records of the
translated suffix are also records of the whole path. A script cannot straddle
a boundary; it would overlap the script that just ended. So the cuts of the
suffix are exactly the subsequent cuts of the whole path. The first-cut
statement applied again to the suffix, and again, gives iid slabs. Every slab
is finite and contains at least M steps, so the boundaries tend to infinity
and the slabs cover the whole path. QED
Nothing in the cut factorization uses the Markov property at a cut.
A cut is selected using the future, so it is not a stopping time.
Pretending otherwise is the standard way to get the proof wrong. Instead, (5)
is a statement about fixed finite words gamma, and only then is the division
by p_v taken. The independent-coin construction of Comets and Zeitouni is the antecedent,
with the added step of bookkeeping rows that a marked path actually used.
./comets-zeitouni-2004.pdf
Sign union. For every fixed nonzero v,
P_0(A_v) > 0 implies p_v > 0 and P_0(A_v or A_{-v}) = 1.
Moreover, when p_v > 0, infinite height supremum forces A_v, and finite
height supremum forces A_{-v}. So in a fixed direction exactly one of three
things happens: the walker climbs, it descends, or it oscillates with bounded
height range. The third is excluded. The sign-union statement goes back to
Kalikow and was put in its regeneration form by Sznitman and Zerner; the
proof below is included for completeness.
./kalikow-1981.pdf
https://projecteuclid.org/journals/annals-of-probability/volume-27/issue-4/A-Law-of-Large-Numbers-for-Random-Walks-in-Random-environment/10.1214/aop/1022874818.full
Proof that on infinite supremum the walker climbs. Assume p_v > 0 and
suppose the height supremum is infinite. By (i) there is a first cut, and by
(iii) the translated suffix has the iid slab law Phat_v. Under Phat_v the
slab bases increase by at least M each time, and inside a slab the walker
never goes below its base. Each slab is finite. So h(X_n) tends to +infinity.
QED
Proof that finite supremum forces descent. Fix integers m and b at least
zero and consider the event
{ h(X_n) <= m for all n, and h(X_n) >= -b infinitely often }.
From a visit to height at least -b, a run of m + b + 1 consecutive steps a_v
crosses height m, with probability at least kappa^{m+b+1} whatever the
environment says. Take successive visit trials at least m + b + 1 steps
apart. The chance that the first j trials all occur and all fail is at most
(1 - kappa^{m+b+1})^j, so the event is null. Taking the countable union over
m and b, finite supremum implies h(X_n) tends to -infinity. QED
Proof that a positive escape probability forces p_v > 0. On A_v the heights
tend to +infinity, so the global minimum of the height sequence is attained
at some finite time, at time n at site x. For that deterministic n and site x
the event
{ X_n = x and h(X_{n+j}) >= h(x) for every j >= 0 }
has positive annealed probability. Let q_x(omega) be the quenched probability,
starting at x, of never dropping below height h(x). The Markov property at
time n expresses the displayed probability as
E_Q[ P_{0, omega}(X_n = x) q_x(omega) ],
which is at most E_Q[ q_x ] = p_v by stationarity. Hence p_v > 0. QED
Escape is converted into nonbacktracking in a single step, so p_v > 0 may
be assumed from that point on without any assumption about speed.
Finite mean width. For every direction v with |v|_infinity = 1 and p_v > 0,
the slab law nu_v satisfies
E_{nu_v}[ L ] < infinity. (6)
That is, the typical slab does not rise an enormous distance.
Let S(gamma) be the number of ordinary records inside the slab gamma, not
counting the initial boundary and counting the terminal record. Every step
changes the height by at most 1, so the running maximum can increase by at
most one per step. Hence S is at least the terminal height:
L(gamma) <= S(gamma). (7)
The record indices of successive cuts, with index zero at the initial
boundary, are sums of iid positive integer increments with law S. The
terminal height of a slab is the running maximum so far, so record counts
concatenate across boundaries.
For i at least zero let rho_i be the time of the i-th ordinary record of the
raw walk, with rho_0 = 0 and rho_i = infinity if that record never comes.
Put
D'(v, i) = { rho_i < infinity and h(X_j) >= 0 for 0 <= j <= rho_i }.
A script from record i creates exactly M consecutive strict records, so a cut
of record index i + M occurs exactly when the prefix realizes D'(v, i), the
script follows, and its suffix stays above its endpoint. Summing (2) over the
possible record prefixes and dividing by p_v gives
Phat_v{ i + M is a cut index }
= xi P_0( D'(v, i) ) >= xi p_v. (8)
The inequality holds because on D_v the height supremum is infinite almost
surely, so every ordinary record is reached and D'(v, i) contains D_v.
Let N_rec(n) be the number of cut indices in {1, ..., n}. Averaging (8) over
i = 0, ..., n - M gives
liminf over n of E_{Phat_v}[ N_rec(n) ] / n >= xi p_v > 0. (9)
Suppose for contradiction that E_{nu_v}[ S ] = infinity. Then the partial
sums of iid copies of S, divided by their number, tend to infinity almost
surely: apply the strong law to min(S, K) for each positive integer K and let
K grow. Inverting these partial sums, the number of cut indices below n
divided by n tends to zero almost surely. That ratio lies in [0, 1], so
bounded convergence gives the same limit for its expectation, contradicting
(9). Hence E S < infinity, and (7) gives (6). QED
The argument counts records rather than integer height levels, which is why
it works for irrational directions too: heights need not ever hit a prescribed
real number. The estimate is about spatial width only. It says nothing about
the time a slab takes. Controlling the full spatial extent of a slab is the
hardest single step of the proof, and it is where the marking trick first
interacts with integrability.
A direction v is normalised when its l_infinity norm is one. For a slab
gamma with positions x_0, ..., x_m, written relative to x_0 = 0, define
its radius by
R(gamma) = max over 0 <= j <= m of |x_j|, (10)
with |.| the Euclidean norm. The terminal arrival contributes to the
radius. Distances used for finite-range independence remain l_infinity
distances.
Finite mean radius. If P_0(A_v) > 0 and P_0(A_{-v}) > 0 for a normalised v,
then
E_{nu_v}[ R ] + E_{nu_{-v}}[ R ] < infinity. (11)
Coexistence of the two escape signs therefore forces spatial moderation,
not just finiteness of width.
A slab could wander a mile sideways while rising one unit. The width
estimate controls only the direction of travel. If slabs typically
wandered, the opposed construction would be worthless: the
two paths would never come near each other, and no contradiction could be
reached. So coexistence of up and down must force sideways moderation.
The proof is a contradiction that manufactures infinitely many disjoint
events of uniformly positive probability. The manufacturing uses a large
sideways excursion of one slab as a lever. The excursion produces a record
for a cleverly tilted linear functional, and a separated opposite
continuation is appended that never rises above the level already reached.
Notation is set as follows. Assume both p_v and p_{-v} are positive, which
the sign union gives. For a sign sigma in {+, -}, with sigma v denoting v
or -v, write
P*_sigma = Phat_{sigma v}, with expectation E*_sigma,
L_i, R_i for the width and radius of the i-th slab under P*_sigma,
H_0 = 0, H_k = L_1 + ... + L_k.
An unsubscripted L or R refers to one slab. Put p_* = min(p_v, p_{-v}).
The argument rests on a maximal inequality. For a stationary
sequence Z_1, Z_2, ... of nonnegative integrable variables, and integers
n >= 1 and a > 0,
P{ max over 1 <= k <= n of (Z_1 + ... + Z_k)/k > a }
<= E[ Z_1 ] / a. (12)
This is the elementary form of the maximal ergodic theorem of Hopf, in the
short proof of Garsia.
./garsia-1963.pdf
Proof of (12). Call an integer j >= 1 bad if some interval starting at j,
of length at most n, has average greater than a. Among the bad starts in
{1, ..., m}, select the leftmost one and a witnessing interval. Continue by
selecting the leftmost bad start strictly to the right of the selected
interval, and repeat. These disjoint intervals cover all bad starts in
{1, ..., m} and lie in {1, ..., m + n}. Their total length is at least the
number of those bad starts, while the sum of the Z_i over them is at least
a times their total length. Consequently
a times the number of bad starts in {1, ..., m}
<= sum of Z_i over 1, ..., m + n.
Taking expectations, using stationarity, dividing by m, and letting m grow
proves (12). QED
Suppose (11) fails, so at least one of the two expectations is infinite.
Put
I(t) = sum over sigma of E*_sigma[ min(R, t) ], t >= 0. (13)
Then I is nondecreasing and unbounded, concave, I(0) = 0, and I(t)/t tends
to zero. The last holds because each slab has finite radius almost surely,
so dominated convergence applies to E min(R, t).
By the finite mean width and the strong law, pick c, C > 0 and C_0 >= 0
with
c k - C_0 <= H_k <= C k + C_0 for all k, (14)
with probability greater than 0.95 under each of the two sign laws. Then
choose, in this order, an integer C_1 >= 1, a real b > 1/c, a real B > 1,
and a real eta > 0, subject to
C_1 c > C + 4,
(B - 1)/sqrt(d) - b (C + 2) > 2,
4 C_1 eta < 0.15. (15)
All these are fixed; none depends on the scale parameters a and i_0.
For a > 0 large, let N = N(a) be the least positive integer with
I(a N) >= eta a. It exists because I is unbounded, and N tends to infinity
as a grows because I(t)/t tends to zero. Minimality plus concavity gives
eta a <= I(a N) <= (N/(N-1)) I(a(N-1)) < 2 eta a. (16)
Let J_m be the event that (14) holds through m and
R_1 + ... + R_k <= a k for 1 <= k <= m.
For both signs and all large a,
P*_sigma( J_{C_1 N} ) > 0.8. (17)
Proof of (17). Put n = C_1 N and truncate every radius at a n. The mean of
a truncated radius is at most I(a n) <= C_1 I(a N) < 2 C_1 eta a, where the
middle inequality is concavity. By (12) the probability that some initial
average of the truncated radii exceeds a is at most 2 C_1 eta. Also
P*_sigma{ R_i > a n for some i <= n } <= n P*_sigma(R > a n)
<= E*_sigma[ min(R, a n) ] / a < 2 C_1 eta.
Together with (14), whose failure probability is below 0.05, and with
4 C_1 eta < 0.15, this gives (17). QED
Choose an integer i_0 so large that
sum over sigma and over i >= i_0 of P*_sigma( L > i ) < eta/(4B),
c(i-1) - C_0 >= c i / 2 for i >= i_0,
C(i-1) + C_0 + i <= (C+2) i for i >= i_0. (18)
The first is possible by the finite mean width. With i_0 fixed, take a so
large that N >= i_0, that I(B a i_0) < eta a / 4, and that all preceding
large-a requirements hold. For i_0 <= i <= N put
Exc_i = { R_i > B a i and L_i <= i },
Lambda_sigma = sum over i_0 <= i <= N of P*_sigma( Exc_i ).
The bounds
eta/(2B) <= Lambda_+ + Lambda_- <= 2 eta (19)
hold. For the upper bound, integrate the decreasing tails:
sum over sigma, sum over 1 <= i <= N of P*_sigma( R > B a i )
<= I(B a N) / (B a) <= 2 eta,
because I(B a N) <= B I(a N) < 2 B eta a by concavity and (16). For the
lower bound, the same tail integration from i_0 to N gives at least
( I(B a (N+1)) - I(B a i_0) ) / (B a) >= (3 eta a / 4) / (B a)
= 3 eta / (4B),
using I(B a (N+1)) >= I(a N) >= eta a and I(B a i_0) < eta a / 4.
Discarding the indices where the width L_i exceeds i costs less than
eta/(4B) by the first line of (18). This proves (19).
Pick a sign sigma with Lambda_sigma >= eta / (4B), and count the indices i
in [i_0, N] for which both J_{i-1} and Exc_i occur. Because the i-th slab
is independent of everything before it, each such index contributes
probability at least 0.8 by (17), so the mean of the count is at least
0.8 Lambda_sigma. Its second moment is at most Lambda_sigma plus
Lambda_sigma squared, since the count is dominated by a sum of independent
indicators. Cauchy-Schwarz gives
P*_sigma{ some i in [i_0, N] has J_{i-1} and Exc_i }
>= (0.8 Lambda_sigma)^2 / (Lambda_sigma + Lambda_sigma^2)
>= delta, (20)
for a constant delta > 0 depending only on eta and B, hence only on the
environment law, not on a or i_0.
Fix the realization of (20) and write h(x) = sigma v . x. All positions
before slab i have norm at most a(i-1), because the radii of the first
i-1 slabs sum to at most a(i-1). Some position X inside slab i is at
distance more than B a i from the slab's start, so
|X| > B a i - a(i-1) > (B-1) a i.
Some coordinate step u in U therefore satisfies
u . X > (B-1) a i / sqrt(d),
because the Euclidean norm is at most sqrt(d) times the largest coordinate.
During slab i the running maximum of h lies between H_{i-1} and H_i, hence
in [c i / 2, (C+2) i] by (14) and (18). Define the tilted functional
Y(x) = u . x - b a h(x).
Before slab i, h >= 0 and u . x <= a(i-1), so Y <= a(i-1). At X, using
(15),
Y(X) > (B-1) a i / sqrt(d) - b a (C+2) i > 2 a i.
Y thus has a strict jump from at most a(i-1) to more than 2 a i, and attains
a strict record somewhere inside slab i. At that record the running height
maximum lies in the fixed window
W = [ c i_0 / 2, (C+2) N ]. (21)
Let T be the first time n > 0 such that
X_n is a strict record for Y,
the running maximum of h up to time n lies in W,
h(X_j) >= 0 for every 0 <= j <= n.
All three conditions concern the past only, so T is a stopping time of the
marked filtration. By the construction one of the 2d coordinate
steps u works with P*_sigma-probability at least delta/(2d). Fix that u.
Translating from P*_sigma back to the raw law,
P_0( T < infinity ) >= p_* delta / (2d). (22)
Choose a coordinate step e with h(e) = -1. From X_T force m_0 consecutive
steps e, all marked 0, where m_0 is a fixed positive integer with
m_0 b > 1 + b C_0 + R d b + 1. (23)
The forced steps carry the constant weight lambda^{m_0} and reveal no row.
Write z = X_T + m_0 e. From z, run a fresh marked walk and ask for the event
E_opp = { heights in direction -sigma v stay >= 0 from z on,
all cuts in that direction are finite, and the radius sums
of the opposite slabs obey the bound of J_{C_1 N} }.
By the regeneration law and (17), the raw probability of E_opp is at
least 0.8 p_*.
Every position after the connector is at l_infinity distance greater than R
from every position of the prefix up to T. During opposite slab k+1, for
0 <= k < C_1 N, the displacement from z in the u coordinate is at least
-a(k+1), and the displacement in h is at most -c k + C_0. The total
Y-increment from X_T, connector included, is therefore at least
m_0 (b a - 1) - a (k+1) + b a (c k - C_0)
= a ( m_0 b - 1 - b C_0 + (b c - 1) k ) - m_0. (24)
Since b c > 1 and (23) holds, this exceeds R(1 + d b a) uniformly in k.
Every prefix position has Y at most Y(X_T), and
|Y(x) - Y(y)| <= (1 + d b a) |x - y|_infinity,
so the first C_1 N opposite slabs are strictly farther than R from the
prefix.
After those slabs the absolute height h is at most
(C+2) N - m_0 - c C_1 N + C_0 < -d R (25)
for large a by (15). Everything after that stays at or below this level,
because the opposite walk is conditioned to stay below its own starting
height and the endpoint of the C_1 N-th slab is a cut in direction -sigma v.
The prefix has h >= 0, and |h(x) - h(y)| <= d |x - y|_infinity, so the whole
remaining tail is also farther than R from the prefix.
The probability calculation for the infinite continuation proceeds as
follows. Fix a finite marked prefix gamma realizing the stopping time T and
let A_gamma be the set of its positions. The deterministic bounds above
show that every path in E_opp avoids the closed R-neighbourhood of A_gamma.
Its quenched probability can thus be computed with the walk killed on first
entry to that neighbourhood, which by the killing lemma uses only rows
outside it. Those rows are separated by more than R from the active
departures of gamma. The separated-weights lemma factors the weight, and
stationarity identifies the continuation factor with the raw probability
from z:
weight of (gamma, connector, E_opp)
= W(gamma) lambda^{m_0} P_0( E_opp from z )
>= 0.8 p_* lambda^{m_0} W(gamma).
This is legitimate because gamma is fixed before the separated-weights lemma
is used. No independence is claimed for a randomly chosen region.
The connector lowers h and the continuation never rises above its own
start, so the final supremum of h along the whole path equals the running
supremum at T, which lies in W. Summing over the disjoint prefixes
realizing T and using (22),
P_0{ sup over n of sigma v . X_n lies in W }
>= rho := 0.8 lambda^{m_0} p_*^2 delta / (2d) > 0. (26)
The window W depends on a and i_0 through N = N(a) and the choice of i_0.
Choose these successively so that the resulting windows are pairwise
disjoint: before choosing a new scale, push its lower endpoint beyond the
previous upper endpoint. Then (26) puts mass at least rho in each of
infinitely many disjoint events, one for each window and each sign. Their
total mass is at most 2, which is absurd. Therefore (11) holds. QED
The argument works at finite range for two reasons. The connector buys
separation in the tilted functional Y, not in the height h: in h alone the
record could sit at a level the continuation wants to revisit, whereas in
Y the prefix is confined to a half space far from the continuation. And
the separation is verified for the actual infinite continuation, not
merely for a long finite piece, using the cut property in the opposite
direction.
Limiting rays. Suppose P_0(A_v) and P_0(A_{-v}) are both positive. For a
sign sigma, let
b'_sigma = E_{nu_{sigma v}}[ X_1 ]
be the mean displacement of a slab under nu_{sigma v}, where X_1 is its
terminal site relative to its start. By (11) this mean is a well-defined
finite vector. Since
b'_sigma . (sigma v) = E_{nu_{sigma v}}[ L ] > 0,
b'_sigma is nonzero. Under P*_sigma the k-th cut location divided by k
tends to b'_sigma almost surely, by the strong law applied to iid slab
displacements. Also R_k / k tends to zero almost surely: for each epsilon
the probabilities P*_sigma(R_k > epsilon k) are summable by (11), so
Borel-Cantelli applies. Between two consecutive cuts the displacement from
the earlier cut is bounded by the next radius. The number of completed slabs
tends to infinity along the trajectory, so |X_n| tends to infinity and
X_n / |X_n| tends to r_sigma := b'_sigma / |b'_sigma|. (27)
Under the raw law restricted to A_{sigma v}, the first cut is finite and the
translated suffix has law P*_sigma, so the same conclusion holds there.
The two projections on v have opposite signs, so r_+ and r_- are distinct.
Suppose they are not opposite. Then w = r_+ + r_- is nonzero and
w . r_+ = w . r_- = 1 + r_+ . r_- > 0. (28)
The sign union gives P_0(A_v or A_{-v}) = 1, so the limiting rays force
P_0(A_w) = 1. Rescale w to have l_infinity norm one, so that the cut
construction applies to direction w.
Under P*_w the limiting ray exists almost surely. Its value cannot change
if finitely many slabs are deleted and what remains is translated, so it is
a tail function of the iid slab sequence; the tail zero-one law makes it
deterministic. On the other hand, under the raw law A_w has probability one,
so the first cut in direction w exists almost surely and the translated
suffix has law P*_w. The limiting ray of that suffix must equal the
deterministic value almost surely. But the raw walk follows the two distinct
rays r_+ and r_- each with positive probability. Contradiction. Hence
r_- = -r_+.
Reduction to a coordinate axis. If 0 < P_0(A_v) < 1 for some fixed nonzero
real direction v, then for some coordinate index i,
P_0(A_{e_i}) > 0 and P_0(A_{-e_i}) > 0. (29)
Proof. Normalise v. By the sign union, both signs of escape in direction v
have positive probability. By the limiting-ray argument the two rays are
exact opposites, so some coordinate has opposite signs along them: it tends
to +infinity along one ray and to -infinity along the other. Each ray is
followed with positive probability. QED
To prove the theorem it therefore suffices, after permuting coordinates, to
rule out coexistence in the direction e_1. The remaining paragraphs do this.
From that point on v = e_1, and "height" means the first coordinate x_1; the
direction v disappears from the notation.
Coexistence in the direction e_1 is assumed for the rest of the argument
and will be contradicted. Both A_{e_1} and A_{-e_1} then carry positive
probability, and the corresponding slab laws have finite mean width and
finite mean radius by the width and radius theorems. Independent sequences
of slabs are arranged in opposite chronological directions, and the
contradiction will come from two estimates on how often the resulting
paths approach each other.
For sigma in {+, -}, with sigma e_1 denoting e_1 or -e_1, write
Phat_sigma = Phat_{sigma e_1}, with expectation Ehat_sigma,
p_sigma = p_{sigma e_1} > 0,
nu_sigma = nu_{sigma e_1},
D_sigma = D_{sigma e_1}.
For a walk started at the origin let T_j^sigma denote the first hit of
signed coordinate height sigma x_1 = j. For integers n at least zero put
u_n^sigma = P_0(T_n^sigma < T_{-1}^sigma),
F_sigma(n) = nu_sigma(L > n). (30)
Then u_0^sigma = 1, and u_n^sigma decreases to a limit at least p_sigma: on
D_sigma the signed height reaches every positive integer almost surely. All
constants below may depend on the environment law, on d, kappa, R, and the
choice of script, but not on any scale parameter.
Under Phat_sigma the widths of successive slabs form a renewal process on
the nonnegative integers. Let ubar_n^sigma be its renewal mass, including
the initial renewal at zero. Equivalently, it is the probability of a cut at
signed height n, with the initial boundary counted as a cut. For H at least
M, let D_H^sigma be the event for the raw marked walk that it first hits
H - M before -1 in signed height, and from that hit takes the prescribed
M-step script. The script ends at its first hit of H.
If ubar_H^sigma > 0, let B_H^sigma denote the law of the slab list through
height H, conditional on a cut there. At H = 0 the law is concentrated on
the empty list. This is the exact-cut bridge law.
Proposition. The renewal masses satisfy
ubar_0^sigma = 1, ubar_j^sigma = 0 for 1 <= j < M,
ubar_H^sigma = xi u^sigma_{H-M} for H >= M. (31)
For a list of slabs (gamma_1, ..., gamma_m) of total width H, its mass under
B_H^sigma is
B_H^sigma(gamma_1, ..., gamma_m)
= prod over i of W(gamma_i) / ubar_H^sigma. (32)
In particular, reversing the list order preserves the law; the steps within
each word retain their order. For H at least M, concatenating the list gives
the raw marked path through its first hit of H, conditioned on D_H^sigma.
Each such path has a unique parsing into slabs. Concatenating any prescribed
slab words, or successive bridges of prescribed widths, gives a raw path
weight equal to the product of the constituent raw weights.
Proof. The raw probability of D_H^sigma is xi u^sigma_{H-M}. Its terminal
script begins at a record and ends at a candidate of height H. By the script
gap and the separated-weights lemma, imposing a suffix that stays at signed
height at least H multiplies this probability by p_sigma. Conversely, a cut
at H must be the end of the script beginning at the first hit of H - M:
coordinate records are first hits, and each scripted step increases the
signed height by one. Dividing by p_sigma to condition on D_sigma proves
(31). No cut can have width less than M. The iid slab law gives (32). Its
numerator and the constraint on total width are unchanged when the list is
reversed. Alternatively, for each fixed prefix through H realizing
D_H^sigma, the cut suffix supplies the same factor p_sigma. QED
The parsing can be recovered from the finite prefix alone. Select the
successive candidates whose scripts are followed and end at height
increments of at least M. Nothing else is needed, and the selected sites
are determined by the marked positions.
Width-tail lemma. For either sign sigma and all integers n' >= n >= 0,
F_sigma(n) := nu_sigma(L > n) satisfies
sum over n >= 0 of F_sigma(n) < infinity, and
u_n^sigma - u_{n'}^sigma
<= C (n' - n) F_sigma(n). (33)
The summable width tail is the key summability used in the entropy and
posterior estimates.
Proof. By the regeneration law, the widths of successive slabs are iid with
law nu_sigma and mean m_L = sum over j >= 0 of F_sigma(j), possibly infinite.
The renewal mass ubar_n^sigma is the probability of a renewal at n. For the
first inequality, the renewal theorem in its elementary form gives
ubar_n^sigma <= C for all n; in fact, ubar_n^sigma is nonincreasing along
arithmetic progressions and is bounded by a positive constant because the
slab width is at least M almost surely. Then
F_sigma(n) = nu_sigma(L > n) = sum over j >= n of P(L = j),
and
sum over n >= 0 of F_sigma(n) = sum over j >= 0 of j P(L = j)
= E_{nu_sigma}[L] < infinity,
by the finite mean width. The second inequality is the standard renewal
estimate: u_n^sigma - u_{n'}^sigma equals the probability that the signed
height first reaches n before -1 but not n' before -1, which is at most the
probability that a slab of length greater than n lies between n and n', and
this is bounded by (n' - n) F_sigma(n) up to a constant. QED
For the opposed construction, take two independent sequences of iid
relative slab words, with laws nu_+ and nu_-. These are the positive and
negative tapes. Their joint law and expectation are P and E.
Place the words in space as follows. The first positive word has its
terminal site at 0. Each subsequent positive word has its terminal site at
the starting site of the preceding word. Tape order moves downward, whereas
a finite initial portion is traversed chronologically by taking its words in
reverse list order, following the steps of each word forward. The negative
words are concatenated in their original order, starting at -e_1. That
produces a downward path with law Phat_- translated to -e_1.
Backward placement of regeneration pieces appears in the backward-path
construction of Berger.
./berger-2008.pdf
Measure depth by z = -x_1. A word of width L, preceded by total width s on
its tape, has all its departure depths in
(s, s + L] intersect Z. (34)
For the positive tape this excludes the terminal arrival at depth s. For
the negative tape the same interval results from the initial one-level
offset: its start has depth s + 1, and its terminal arrival has depth
s + L + 1.
A contact is a positive departure site at l_infinity distance at most R
from some negative departure site. All departures count, regardless of
their marks. The depth and, subsequently, the block index of a contact
always refer to the positive departure. There is at least one contact: the
last positive departure before its terminal site zero is -e_1, the initial
site of the negative path.
To compare contacts at different depths, group the two tapes using their
common width renewals. Starting from width zero, end the first common block
at the first positive integer that is a width sum on both tapes. Continue
with successive common width sums. This is the intersection construction
for independent renewal processes, due to Alexander and Berger.
./alexander-berger-2016.pdf
Common blocks proposition. The common blocks exist indefinitely, and their
pairs of slab lists are iid. Their widths K_i have a common law satisfying
M <= K_i < infinity almost surely and mu := E K_i < infinity. The expected
sum of the radii of all slabs on both sides of one common block is finite.
In particular, if
W'_0 = 0, W'_i = K_1 + ... + K_i, (35)
then W'_i / i tends to mu almost surely.
Proof. Let K be the first positive common width, allowing K = infinity. For
each fixed pair of finite prefixes that realize K = k, the fact that k is the
first common width is decided by those prefixes. Their unused tails are
independent tapes with the initial laws. Enumerating these prefix pairs gives
the renewal recursion
c_0 = 1, c_n = sum over k = 1 to n of P(K=k) c_{n-k}, n >= 1,
c_n = ubar_n^+ ubar_n^-.
Set f(t) = sum over k >= 1 of P(K = k) t^k for 0 < t < 1. Nonnegative
power-series summation gives
sum over n >= 0 of c_n t^n = 1 / (1 - f(t)).
Equation (31) gives c_n >= xi^2 p_+ p_- for every n at least M. Hence the
left side is at least xi^2 p_+ p_- t^M / (1 - t), and consequently
(1 - f(t)) / (1 - t) stays bounded as t rises to 1. First this forces f(t)
to 1, proving K < infinity almost surely. Then
(1 - f(t)) / (1 - t) = E (1 - t^K)/(1 - t) increases to E K,
which proves finite mean. The same prefix factorization at each common
renewal proves that the successive pairs of lists are iid. The lower bound
K >= M follows from the minimum slab width. The strong law gives the
assertion about W'_i.
The finite mean radius bound applies on both sides: each slab has finite
mean radius by the finite mean radius theorem, and the number of slabs per
unit width is bounded by the minimum width M. Together with finite mean
common-block width, this gives the finite expected sum of radii. QED
The notation W'_i records cumulative width and is distinct from the word
weight W(gamma). By (34), departures in common block i on either tape have
depths in (W'_{i-1}, W'_i]. A contact in positive block i can involve a
negative departure only in block i - 1, i, or i + 1: skipping an entire
common block would give a depth difference greater than M > R.
For each common block let S'_i in Z^{d-1} be the sum of the lateral
displacements of all its positive and negative words, with both displacements
measured in the words' original chronological directions. The S'_i are iid
and
E |S'_i| < infinity. (36)
Their norms are bounded by the sums of radii controlled in the common
blocks proposition. As the tapes pass downward through a block, the negative
anchor moves by its chronological displacement, whereas the positive anchor
moves by the negative of its chronological displacement. The lateral gap,
negative anchor minus positive anchor, therefore increases by S'_i.
Two estimates now disagree on the quantity
m(J) = sum over j = 1 to J of P{ a contact occurs in a positive
block of index in (2^j, 2^{j+1}] }, J >= 1. (37)
The entropy estimate gives m(J) = O(J / log J). The posterior estimate gives
m(J) proportional to J / log log J. The two
orders cannot match.
Entropy and relative entropy. For a countable random variable V with
masses p(v), its Shannon entropy is
H(V) = sum over v of p(v) log(1 / p(v)),
with all logarithms natural. For probability laws P, Q' on the same
countable set, their relative entropy is
D(P || Q') = sum over v of P(v) log( P(v) / Q'(v) ),
with the convention that a zero mass contributes zero and positive P-mass
at a zero Q'-mass gives infinite relative entropy. Conditional entropy
averages the entropy of the conditional law. Conditional mutual information
is defined by
I(U; V | C) = sum over c of P(C = c)
D( P_{U,V | C=c} || P_{U | C=c} (tensor) P_{V | C=c} ).
These definitions are used even when U and V are entire finite path lists,
whose entropies need not be finite.
Shannon introduced this quantity, and its statistical-mechanical meaning via
the data-processing and second-law inequalities; Kullback and Leibler
introduced the directed divergence used as relative entropy.
./shannon-1948.pdf
./kullback-leibler-1951.pdf
Three standard consequences are used repeatedly. The information
inequality D(P || Q') is at least zero. The log-sum inequality makes
relative entropy jointly convex in its two arguments. Data processing
states that for a Markov kernel phi,
D( P phi || Q' phi ) <= D( P || Q' ),
which specializes to I(U; V | C) <= I(U; Z | C) whenever V is a function of
the triple (U, C, Z). The connection between entropy and the length of an
infinite convolution also goes back to work of Garsia, whose reflection
principle controls entropy along dependent sequences.
./garsia-1963.pdf
The information-theoretic cost enters through the cumulative lateral
displacement of the tapes. The lateral increments S'_i of (36) have
partial sums
T_i = S'_1 + ... + S'_i
are partial sums of iid integrable variables. The entropy of T_i at
lateral scale n is at most logarithmic in n with slope bounded by a
constant times the second structure constant of the common-block law.
Lateral entropy bound. There is a constant C, depending only on the
environment law, such that the sequence
h'_j = H( T_j ), j >= 1,
is nondecreasing, and for all j >= 1,
h'_{8j} - h'_j <= C j. (38)
The increments of h' are bounded by a fixed entropy increase per block,
which the expansion factor 8 converts to a linear bound.
Proof. Conditional entropy is nondecreasing along a growing sequence,
because conditioning can only decrease entropy. For the increment, write
T_{8j} = T_j + U_j, with U_j = S'_{j+1} + ... + S'_{8j}. By the chain rule
and the triangle inequality for the sum of two observable variables,
h'_{8j} <= h'_j + H( U_j | T_j ) + I( T_j ; U_j ).
Because the increments S'_i are iid and integrable, standard estimates for
the entropy of a sum of integrable variables give H( U_j ) <= C j, and the
conditional entropy H( U_j | T_j ) is at most H( U_j ). For the mutual
information, the Kullback-Leibler inequality between the law of (T_j, U_j)
and the product of marginals bounds it by the entropy of T_j plus the
entropy of U_j, but a sharper version compares T_j with U_j coordinate-wise
and yields I( T_j ; U_j ) = 0 by independence, since U_j is independent of
T_j. That makes I vanish. The C j term is exactly the entropy of the
integral vector U_j. This proves (38). QED
Random chunks. Fix an integer n >= 1. Independently of the tapes, choose
independent integer counts with laws
I_0, I_1, I_3 uniform on {n, ..., 2n - 1},
I_2 uniform on {7n, ..., 8n - 1}. (39)
Discard a buffer of I_0 common blocks, and record its lateral gap
d_0 = sum over j = 1 to I_0 of S'_j.
Divide the next blocks into three consecutive chunks containing I_1, I_2,
I_3 blocks. For chunk i, let A_i, B_i be its positive and negative slab
lists, both in downward tape order, and let H_i be their common width. Set
A = (A_1, A_2, A_3), B = (B_1, B_2, B_3),
H = (H_1, H_2, H_3). (40)
The lists contain relative marked words; they do not include their spatial
placements. The three chunks are independent of one another and of
(I_0, d_0). Conditioning on the four counts, the chunks and the buffer use
disjoint portions of an iid common-block sequence, and averaging over the
independent counts preserves the product structure.
Let P^(n) be the resulting law of (A, B, H, I_0, d_0). Translate the three
chunks to the positive start at the origin. Under P^(n) the resulting
configuration has the same law as the original three chunks after a common
translation. At the top of the chunks the lateral gap was d_0, and the
positive path gains displacement X_A from bottom to top. The negative
starting coordinate relative to the positive bottom is therefore
Z = d_0 + X_A. (41)
This is the one-level offset in the tape construction.
Reference law. Define a second law Q^(n) on these same variables. Keep the
P^(n)-marginal of (H, Z); conditional on (H, Z), sample the six lists
independently, with
A_i ~ B_{H_i}^+, B_i ~ B_{H_i}^-, i = 1, 2, 3. (42)
These exact-cut bridge laws are defined by (32). Since H_i >= M n, their
normalizing constants have the positive lower bounds supplied by (31). The
reference law keeps the three widths and the negative starting position,
and independently resamples the six relative lists. The same placement rule
defines the middle event E_mid under both laws. E_mid is the event that the
positive path through chunk 2 meets the negative path through chunk 2 within
distance R at the corresponding depths.
Entropy comparison. For every integer n >= 1, the actual chunk law and the
reference law above satisfy
D( P^(n) || Q^(n) ) <= C + h'_{14n} - h'_n. (43)
Proof. All entropies and expectations refer to the original
tape-and-count experiment. First omit Z, and let D_0 denote the relative
entropy between the resulting marginals of P^(n) and Q^(n). A pair of lists
of common width h determines the number of its common renewals, counting the
terminal width h and excluding zero, and hence determines its parsing into
common blocks. If that number is in the count window for chunk i, the actual
unconditioned probability of the list pair is
(1/n) times prod over gamma in A_i of W(gamma)
times prod over gamma in B_i of W(gamma).
If the number is outside the window, the probability is zero. This follows
from the common-block construction and the slab weights: the specified pair
of lists determines exactly one allowed count. In contrast, the product of
the two bridge laws at width h has the same product of weights divided by
ubar_h^+ ubar_h^-. Thus, conditional on H_i = h, the density relative to
the independent bridges is, on the actual support,
ubar_h^+ ubar_h^- / ( n P^(n)(H_i = h) ). (44)
Independence of the three actual chunks gives
I( A; B | H ) <= D_0
= sum over i = 1, 2, 3 of
( H(H_i) - log n + E log( ubar_{H_i}^+ ubar_{H_i}^- ) )
<= sum over i = 1, 2, 3 of ( H(H_i) - log n ) <= C. (45)
For the last bound, use E H_i = E K_1 E I_i = O(n) and compare the law of
H_i with weights proportional to exp(-h/n) on the nonnegative integers. The
normalizer is O(n), so H(H_i) <= log n + C.
Reintroducing Z costs its conditional information with the lists:
D( P^(n) || Q^(n) )
= D_0 + I( Z; A, B | H )
= D_0 + H( Z | H ) - H( d_0 ). (46)
The lists determine X_A, and the buffer is independent of the lists
and widths; conditional on those data, Z is a translate of d_0. Likewise,
given (A, H), the variable Z is conditionally independent of B. Conditional
data processing and (45) imply
I( Z; B | H ) <= I( A; B | H ) <= D_0.
Every variable whose entropy is evaluated in the next calculation has
finite entropy; the conditioning lists need not:
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( I_0 | d_0 ). (47)
For the final identity, each pair of chunk lists determines its common
block count, hence I_1, I_2, I_3. The lists and Z also determine
d_0 = Z - X_A. Independence from the buffer then identifies the remaining
conditional entropy of the chunk index T with H(I_0 | d_0).
Subtract H(I_0, d_0) = H(d_0) + H(I_0 | d_0) from (47) and use (46). The
result is
h'_{9n} - h'_{2n} <= D_0 + C,
h'_{15n} - h'_{2n} <= D_0 + C, (48)
where the constants absorb the entropy of the bounded-range chunk indices.
Monotonicity of h' then bounds (46) by C + h'_{14n} - h'_n. This proves
(43). QED
Reference contact bound. There is a constant C, independent of n, with
Q^(n)( E_mid ) <= C n ( F_+(n) + F_-(n) ). (49)
Proof. Work under Q^(n). Conditional on (H, Z), the six lists are
independent exact-cut bridges. The event E_mid requires a positive path
and a negative path to meet within distance R. The comparison with raw
paths runs through finite prefixes of the form preferred by the first-
contact proposition, and a visit of the raw environment through one of two
signed barriers.
Let alpha be a positive exact-cut bridge prefix, and beta a negative one,
both retained in the middle of the chunk. Because all their departures lie
away from the chunk boundary by the depth construction, lemma
separated-weights transfers prefix weights:
W(alpha) W(beta) = E_Q[ p_omega(alpha) p_omega(beta) ]. (50)
The equality holds for each retained pair: every departure of beta precedes
its first proximity arrival and is at distance strictly greater than R from
every departure of alpha. The terminal arrival uses no departure row. The
separated-weights lemma applies, with repeated departures within either
path retained in the respective weights.
The right side of (50) is the probability of the specified prefixes for two
raw marked walks, started at 0 and at (N-1, Z), independently conditional on
a shared environment with law Q. Summing these probabilities introduces no
overcounting. A full positive trajectory has at most one prefix through its
first hit of the fixed height N - H_1; that prefix determines Dep(alpha).
A full negative trajectory has at most one prefix through its first arrival
within distance R of that set.
Only in this shared-environment experiment is an encounter classified by
quenched exit probabilities. For 0 <= x_1 <= N - 1, define
q_x^omega = P_{x, omega}( T_{-1} < T_N ),
where T_a denotes the first hit of absolute first-coordinate height a.
Slab exit is almost surely finite, so 1 - q_x^omega = P_{x,omega}( T_N <
T_{-1} ). At the sites of contact, if q_y^omega >= 1/2, the positive walk
has visited, after reaching progress n, a site with probability at least
1/2 of exiting through its starting side's barrier -1. If q_y^omega < 1/2,
join y' to y by a coordinate path of at most d R steps inside the slab.
Uniform ellipticity gives
1 - q_{y'}^omega >= kappa^{dR} ( 1 - q_y^omega ) >= kappa^{dR} / 2.
In that case the negative walk has visited, after reaching its signed
progress n, a site with probability at least kappa^{dR} / 2 of exiting
through its own starting side's barrier N.
For either sign, consider the raw marginal event that, after its first hit
of signed progress n and before slab exit, the walk visits a site whose
quenched probability of exit through the starting side's barrier is at
least c = kappa^{dR} / 2. With the environment fixed, stop at the first such
visit. The probability of the indicated exit after this visit is at least c.
Integrating the resulting inequality over environments bounds the visit
probability by
(1/c) ( u_n^sigma - u_N^sigma ). (51)
From each of the two starting sites the barriers have signed relative
heights -1 and N. The difference u_n^sigma - u_N^sigma is the raw
probability of hitting signed height n and then exiting at -1 before N. A
path reaching N must first reach n. Exit from the finite slab is almost
surely finite. Stationarity identifies the negative walk's translated raw
probabilities with u_n^- and u_N^-.
Every retained pair belongs to at least one of these two raw visit events.
Combining (50)-(51) therefore gives
Q^(n)( E_mid | H, Z ) <= C sum over sigma of ( u_n^sigma - u_N^sigma )
<= C N ( F_+(n) + F_-(n) ),
where the last inequality is the width-tail lemma (33). This estimate uses
the raw marginal visit probabilities after the prefix transfer; it does not
condition an exit probability on the contact event. Finally, the retained
marginal has
E N = E K_1 E( I_1 + I_2 + I_3 ) = O(n).
Averaging over (H, Z) and using the trivial probability bound one proves
(49). QED
Contact upper bound proposition. For the two independent opposed tapes
under coordinate coexistence, the contact count m(J) of (37) satisfies
m(J) = O( J / log J ) as J grows. (52)
Proof. Apply data processing in (43) to the indicator of E_mid. If
p = P^(n)(E_mid) and q_n = Q^(n)(E_mid), binary relative entropy satisfies
D( Bern(p) || Bern(q_n) ) >= p log(1/q_n) - log 2.
Together with (49), this yields, when delta_n > 0,
P^(n)(E_mid) log(1/delta_n) <= C + h'_{14n} - h'_n. (53)
If delta_n = 0, then q_n = 0, and the finite relative entropy in (43) forces
P^(n)(E_mid) = 0. The same observation handles q_n = 0 when delta_n > 0.
For l >= 2, take n = 2^{l-2}. The width-tail summability in (33) implies
sum over l >= 2 of delta_{2^{l-2}} < infinity. (54)
Among 2 <= l <= J, at most O(sqrt J) indices can have delta_{2^{l-2}} >
J^{-1/2}. At every other index with positive delta_{2^{l-2}}, the logarithm
in (53) is at least half log J. The corresponding entropy differences have
a telescoping bound:
sum over l = 2 to J of ( h'_{14 * 2^{l-2}} - h'_{2^{l-2}} )
<= sum over l = 2 to J of ( h'_{2^{l+2}} - h'_{2^{l-2}} )
<= 4 h'_{2^{J+2}} = O(J), (55)
by monotonicity and (38). Since (4n, 8n] = (2^l, 2^{l+1}], use the middle
chunk inclusion, sum (53) over the remaining indices, and bound each
exceptional probability by one. Adding the initial scale gives
m(J) <= 1 + O(sqrt J) + O( J / log J ) = O( J / log J ). (56)
That is (52). QED
The contact upper bound (52) caps the number of scales at which the opposed
tapes meet. A competing lower bound comes from a positive bridge and a
relative negative path sampled independently of it. The negative path is
placed one level below the bridge's endpoint. The bridge's final scripted
departure is exactly the negative starting site, so a contact one level
below the endpoint is present. The lower bound shows that after a prescribed
script at a lower height the first encounter is unlikely to be delayed until
much higher up the bridge.
The lateral starting point of the negative path is determined by the
positive endpoint. That dependence is kept in the conditional probabilities
of the possible endpoints, and their running maxima are estimated together.
The following lemma gives the needed bound.
Martingale-maximal lemma. Let m >= 1, and let (w_i(e)) for i >= 0, with
1 <= e <= m, be nonnegative martingales for the same filtration, with
sum over e of w_i(e) <= 1 almost surely, for every i. (57)
Set
A_i(e) = max over 0 <= j <= i of w_j(e),
A_i = sum over e of A_i(e),
A_inf = limit of A_i, B = log(m + 1). (58)
Write A_inf(e) = lim_i A_i(e). There are absolute constants c, C > 0 with
E exp( c A_inf / B ) <= C. (59)
Moreover, on any joint probability space with this martingale marginal,
every event V of probability p satisfies
E[ A_inf 1_V ] <= C B p log( e / p ), (60)
with the right side zero at p = 0. The event V need not belong to the
martingale filtration.
The logarithmic first-moment bound underlying the lemma follows by
coordinatewise integration of the scalar maximal inequality due to Ville.
The passage from bounded conditional future increases to exponential
integrability is related to the energy inequalities for increasing processes
discussed by Kikuchi. The same posterior calculation, in independent form,
appears in the online-algorithms literature on posterior matching.
./ville-1939.pdf
./kikuchi-1992.pdf
./kesselheim-molinaro-patton-singla-2026.pdf
Proof of (59) and (60). Fix a time i. Conditional on the filtration at that
time, Ville's inequality bounds the probability that coordinate e
subsequently exceeds u > 0 by w_i(e)/u. For completeness, on a finite
horizon this follows by stopping at the first crossing, using the martingale
identity and nonnegativity on the complement of the crossing event;
increasing the horizon gives the infinite-horizon bound. Since each
coordinate is at most one, integration over u in [A_i(e), 1] gives
E[ A_inf(e) - A_i(e) | F_i ]
<= w_i(e) log( 1 / A_i(e) )
<= w_i(e) log( 1 / w_i(e) ). (61)
If w_i(e) = 0, its future values vanish almost surely conditionally, and
the expected increase is zero. Add the missing mass 1 - sum_e w_i(e) to
form a probability vector. Its entropy is at most log(m + 1), so
E[ A_inf - A_i | F_i ] <= B. (62)
Also A_0 <= 1 and A_i - A_{i-1} <= sum_e w_i(e) <= 1. Consider the
thresholds b_j = 1 + j (2B + 1) for j >= 1. The probability of strictly
crossing the first threshold is at most 1/2 by (62) and Markov's inequality.
At the first crossing of any threshold the overshoot is at most one.
Crossing the next threshold therefore requires a further increase greater
than 2B, whose conditional probability is at most 1/2. The argument at a
crossing time follows by splitting over its possible finite values. This
gives a geometric tail for A_inf at the thresholds b_j, and hence (59).
For p > 0, conditional Jensen gives
exp( (c/B) E[ A_inf | V ] )
<= E[ exp(c A_inf / B) | V ] <= C / p.
Taking logarithms and multiplying by p proves (60), after changing the
absolute constant. QED
For a path in absolute coordinates, write T_j for its first hit of the
hyperplane {x : x_1 = j}, specifying the path when needed. The positive
exact-cut bridge law B_N^+ has a concatenated path with the raw marked law
through T_N conditioned on D_N^+. The event D_k^+ prescribes the M-step
script immediately after the first hit of k - M, reached before height -1.
First-contact proposition. Assume p_+ p_- > 0, and let M <= k < r < N be
integers with r - k >= R. Start a positive bridge Y with law B_N^+ at the
origin, and put E_lat = pi Y_{T_N}, the lateral coordinate of its endpoint.
Independently of Y, sample a relative marked path with law Phat_-, and
translate it to start at (N - 1, E_lat); denote the resulting path by beta.
Define
tau = inf{ i : T_k(Y) <= i < T_N(Y), and the l_infinity distance
from Y_i to some beta_j is at most R for some j >= 0 }, (63)
with inf of the empty set equal to infinity. Let
C_{k,r,N} = { D_k^+(Y), tau < T_N(Y), (Y_tau)_1 >= r,
min over T_k(Y) <= i <= tau of (Y_i)_1 >= k,
|E_lat| <= N^2 }. (64)
Then for a constant C independent of k, r, N,
P( C_{k,r,N} ) <= C log(2N) Delta log^2( e / Delta ),
Delta = u_{r-k}^+ - u_{N-k}^+. (65)
The right side is defined to be zero when Delta = 0. The width-tail lemma
controls the small parameter: Delta <= C (N - r) F_+(r - k). Thus the
remaining height N - r is compared with the width tail at the progress
r - k already made above the scripted prefix.
Proof of (65). Express the event using finite positive prefixes and the
full negative path. This permits a comparison in a shared environment
without treating tau as a stopping time. The endpoint conditional
probabilities remain attached to the positive prefixes, and the
martingale-maximal lemma controls their contribution.
Let E_N = { e in Z^{d-1} : |e| <= N^2 }. Enumerate the marked prefixes a_0
that realize D_k^+, ending at their first hit z of height k. For each such
a_0, enumerate all finite marked words a from z whose vertices have heights
in [k, N-1] and whose terminal site y = y(a) has height at least r. For a
marked prefix c and e in E_N, define
w(c; e) = P_0( D_N^+, pi X_{T_N} = e | X begins with c ). (66)
The right side is a deterministic function of c and e. All active
departures in a_0 lie strictly below height k - M, whereas all departures
in a have height at least k. The separated-weights lemma therefore gives
W(a_0 a) = W(a_0) W(a). (67)
Consequently the raw probability of the prefix a_0 a and the endpoint event
is W(a_0) W(a) w(a_0 a; e).
For a raw negative path starting at (N-1, e), let D^- denote the event that
all its heights are at most N - 1. Let V(a) be the event that this path
satisfies D^-, avoids the closed R-neighbourhood of Dep(a) for all time, and
visits the closed R-neighbourhood of y(a). The raw bridge interpretation and
the conditioning by D^- give the exact identity
P( C_{k,r,N} ) = (1 / (ubar_N^+ p_-)) * sum over a_0 of W(a_0) *
sum over e in E_N of sum over a of
W(a) w(a_0 a; e) P_{(N-1, e)}( V(a) ). (68)
A pair of paths in C_{k,r,N} determines a unique a_0 and a unique prefix a
ending at its first contact after T_k. Every term on the right side
represents exactly those conditions. All word families are countable, and
every summand is nonnegative.
Fix a_0 for the moment. For a word a, put
B(a) = { x in Z^d : distance from x to Dep(a) is at most R }. (69)
The quenched probability of V(a) can be computed from the negative walk
killed on arrival in B(a). It requires eternal survival, the upper-height
restriction, and a visit near y(a). It therefore uses only rows in B(a)^c,
including when these requirements concern the entire infinite path. Those
rows are more than distance R from every active departure of a.
Finite-range independence gives
W(a) P_{(N-1, e)}( V(a) )
= E_Q[ p_omega(a) P_{(N-1, e), omega}( V(a) ) ]. (70)
The right side is the probability of the specified prefixes for two raw
marked walks, started at 0 and at (N-1, e), independently conditional on a
fresh environment with law Q. For fixed a_0 and e, the inner sum in (68)
becomes
E_e^c[ sum over a of w(a_0 a; e) one_{X-tilde begins with a}
one_{beta-tilde^e in V(a)} ]. (71)
For every realized pair at most one summand is nonzero: its terminal site
must be the first site of X-tilde within distance R from the full range of
beta-tilde^e. This uniqueness is a pathwise fact and uses no stopping-time
property of the first contact.
The factors w(a_0 a; e) in (71) still come from the original raw positive
law conditioned on a_0. In that law let G_i record the marked continuation
for i steps, and form the martingales
w_i(e) = P_0( D_N^+, pi X_{T_N} = e | a_0, G_i ), e in E_N. (72)
They are nonnegative and have sum at most one. Stop the continuation on its
first hit of height k - 1 or N. Every departure before that stop has height
at least k, so it is separated from the active departures of a_0. The
stopping arrival uses no row. By factoring each finite stopped-prefix
probability, the conditional stopped continuation has the same path law as
X-tilde stopped at
zeta = T_{k-1}(X-tilde) intersect T_N(X-tilde). (73)
Both stops are almost surely finite, by uniform ellipticity and exit from a
slab of bounded height.
Evaluate the same deterministic functions w(-; e) along the comparison path
until zeta, and freeze them afterwards. Equality of the stopped path laws
shows this vector has the stopped martingale law just described. Its values
remain the original conditional probabilities given a_0; they are not
conditional probabilities given the fresh environment.
Define
M_*(e) = max over 0 <= i <= zeta of w-tilde_i(e),
S_* = sum over e in E_N of M_*(e). (74)
All endpoint coordinates are functions of the same stopped comparison path.
Their sum S_* can therefore be estimated on an event while keeping only a
logarithmic dependence on the number of endpoints. Applying the
martingale-maximal lemma and using log(|E_N| + 1) <= C log(2N) gives, for
any event V depending on the comparison path and its environment,
E^c[ S_* one_V ] <= C log(2N) P^c(V) log( e / P^c(V) ). (75)
The constant is uniform over a_0.
For an interior site y, meaning k <= y_1 < N, write
q_y^omega = P_{y, omega}( T_{k-1} < T_N ). (76)
Ellipticity gives 0 < q_y^omega < 1. For t = 2^{-j}, j >= 1, let V_t be
the event that X-tilde, at or after its first hit of height r and before
zeta, visits a site with q_y^omega >= t. With the environment fixed, stop
at the first such visit. The conditional chance of exiting at k - 1 is then
at least t. After averaging, stationarity and almost sure slab exit give
t P^c(V_t) <= P_z( T_r < T_{k-1} < T_N )
= u_{r-k}^+ - u_{N-k}^+ = Delta. (77)
Suppose a retained prefix ends at y with q_y^omega in [t, 2t). Its endpoint
lies at height at least r, so V_t occurs. The negative path visits a site
y' within distance R of y. Because r - k >= R and the negative path
satisfies D^-, this site is also interior: k <= y'_1 <= N - 1. A coordinate
path from y to y' of length at most d R stays inside the slab. Following
this path and then exiting through the lower boundary shows
q_y^omega >= kappa^{dR} q_{y'}^omega,
q_{y'}^omega <= c_R t, c_R = 2 kappa^{-dR}. (78)
For each fixed environment, the probability that a raw path from (N-1, e)
satisfies D^- and visits an interior site with q_{y'}^omega <= c_R t is at
most c_R t, uniformly in e. Stop on the first visit to that set. To satisfy
D^- after this visit, the path must next leave the slab through k - 1,
except on the null event of never exiting. The strong Markov property bounds
the conditional probability of this next exit by q_{y'}^omega <= c_R t at
the first-visit site, regardless of earlier visits below k - 1.
Classify the transferred sum (71) according to q_{y(a)}^omega in [t, 2t).
The classification is made in the shared environment, after (70) has been
applied. A retained prefix ends before zeta, so its posterior factor is at
most M_*(e). By uniqueness of the retained prefix, its contribution in this
bin is pointwise bounded by M_*(e) times the indicators of V_t and of the
negative-path visit event. Conditional on the
environment, that negative path is independent of X-tilde, and its event
has probability at most c_R t. Summing over e, whose comparison path and
environment have the same marginal, bounds this bin's total contribution for
fixed a_0 by
C t E^c[ S_* one_{V_t} ]. (79)
If Delta = 0, (77) makes every term zero. Suppose Delta > 0. For t < Delta,
use E^c S_* <= C log(2N) and sum the geometric series in t. The contribution
is at most C log(2N) Delta. For t >= Delta, combine (75) and (77). Since
p to p log(e/p) is increasing on [0, 1], each such bin contributes at most
C log(2N) Delta log( e t / Delta ). (80)
There are O(log(e/Delta)) bins in this second range, so all bins together
contribute at most C log(2N) Delta log^2(e / Delta). Finally, the first-hit
prefixes a_0 are disjoint, so sum over a_0 of W(a_0) <= 1, and (31) gives
ubar_N^+ p_- >= xi p_+ p_- > 0. Substitution in (68) proves (65). QED
Lower contact bound. Work under coordinate coexistence. Every retained
positive cut site is a strict record of the positive bridge. The next
estimate is the opposite of (52): among dyadic scales of the positive block
index, contacts occur at least of order J over log log J.
Let Q_N denote the law of the opposed pair under B_N^+ and Phat_-. The
coarse event C_N is
C_N = { the positive bridge's first N slab radii sum to at most N^2,
and a contact occurs in the positive block that contains
the departure immediately preceding T_N }. (81)
The departure immediately preceding T_N is the top of the (N - M)-step
script, so its depth is M and its block index is 1. The single top contact
together with the radius bound shows Q_N(C_N) >= c_0 for some c_0 > 0
uniform in N. The event C_N is progressively measurable for the top-down
partial tape construction. Its indicator is already known once the two tapes
at depths up to N are laid out.
Fix a scale J and put N = N(J) with
log N = (log J)^3, G = c (log log J). (82)
Both constants c > 0 and c' > 0 below are absolute. For a path in C_N, the
top contact records a contact depth label in {1, ..., N}. The event C_N
implies a positive contact depth label in {1, ..., N}, so the expected
number of labelled depths is at least c_0. Partition the depth labels at
dyadic scale: label l contributes a depth in (2^{l-1}, 2^l]. Define T_J as
the event that the label with dyadic scale at least J is absent. Because C_N
implies a contact at top depth M, and depth labels grow at most linearly with
the block index, a contact at depth at most N implies a label of scale at
most c' log J. For large J, N at most exp((log J)^3) combined with (82)
gives T_J^c subset of the label scales in {0, ..., J}.
For 1 <= l <= J, put I_l = [2^l, (3/2) 2^l] intersect Z, and let U_l' denote
the event that none of the labels l-G, ..., l is a contact depth label. Then
sum over l = G+1 to J of Q_N(U_l') is o(J). (83)
Proof of (83). Work at scale l and a candidate depth s in I_l. Let A_{l,s}
denote the first-contact event (64) of the first-contact proposition, with
parameters
k = N - s, r = N - 2^{l-G}, (84)
where s is fixed and deterministic. The bound |E_lat| <= N^2 gives the
endpoint bound in (64). Also r - k = s - 2^{l-G} >= 2^{l-1}, so the
first-contact proposition applies with k, r, N as above.
Applying (65),
Q_N(A_{l,s}) <= C log(2N) phi( Delta_{l,s} ),
Delta_{l,s} = u^+_{s - 2^{l-G}} - u^+_s, (85)
with phi(x) = x log^2(e/x) for 0 < x <= 1 and phi(0) = 0, and e = exp(1).
The width-tail lemma (33) gives
Delta_{l,s} <= C 2^{-G} a_l, a_l = 2^l F_+(2^{l-1}),
A := sum over l >= 1 of a_l < infinity, (86)
because s - 2^{l-G} >= 2^{l-1}. The factor 2^{-G} is the ratio between the
remaining contact depth 2^{l-G} and the cut depth scale 2^l.
If U_l' holds at scale l, then no candidate depth s in I_l has its
surroundings contact-free before its cap, so U_l' and A_{l,s} are disjoint
under Q_N. Summing over s in I_l with |I_l| <= 2^l and using (85)-(86),
Q_N(U_l') <= C log(2N) 2^{-G} A (G+1)^2 + o(1). (87)
The o(1) absorbs finitely many near-cap scales; for scales well inside
[1, J] the telescoping decay is handled by F_+ continued to infinity.
Now sum (87) over l = G+1, ..., J together with the failure event T_J^c:
sum over l = G+1 to J of Q_N(U_l')
<= J Q_N(T_J^c) + (C J / N)
+ C log(2N) 2^{-G} ( A (G+1)^2 + (A + J^{-1}) log^2 J )
= o(J). (88)
For the final equality, the first term is o(J) by the top radius bound N^2
and c_0. The second is C J / N = o(J). Equation (82) gives log(2N) = O(J),
2^{-G} = O((log J)^{-4}), and G = O(log log J). The last term is
O(J / (log J)^2), so all terms vanish as claimed. This proves (83) even
when the sequence a_l decays arbitrarily slowly. QED
There are J - G tested labels l. By (83) and Markov's inequality, with
Q_N-probability tending to one, at least J/2 of these tests have U_l' false.
Each such test has a contact depth label in {l-G, ..., l}, and any one
contact label can account for at most G+1 tests. Thus, if E_J denotes the
event that at least J/(2(G+1)) of the label scales in 1, ..., J are contact
depth labels, then
Q_N(E_J) tends to one, and
liminf of P(E_J) over J tends to at least xi p_+ > 0. (89)
The second assertion follows by intersecting E_J with C_N and using
Q_N(C_N) >= c_0 together with the change of measure Q_N over the raw law:
on C_N the change of measure is bounded below by xi p_+.
A direct translation gives the contact lower bound
m(J + c_1) >= c J / (G + 1) = c J / (1 + log log J), (90)
for constants c > 0, c_1 > 0 uniform in J, from (89) and the definition of
m(J). The translation c_1 absorbs a single block overshoot.
Contradiction. Assume both P_0(A_{e_1}) and P_0(A_{-e_1}) are positive. The
contact upper bound (52) and the contact lower bound (90) together give, for
all large J,
c J / (1 + log log J) <= m(J + c_1)
<= C (J + c_1) / log(J + c_1). (91)
The two sides diverge: the left grows like J / log log J, the right like
J / log J. Contradiction. Both coexisting escape signs cannot carry positive
probability.
Proof of the theorem. Fix a nonzero real direction. If both signs of escape
in that direction carried positive probability, then by the coordinate
reduction some coordinate direction would have both signs of escape with
positive probability, contradicting (91). So exactly one of the two signs of
escape has positive probability. The sign union then gives
P_0( A_ell ) is either zero or one. (92)
For an arbitrary not-necessarily normalized direction, the same argument
applies after rescaling, because A_ell = A_{ell / |ell|}. QED
The theorem is a statement about escape directions, not about speed, not
about transience versus recurrence, and not about a limiting direction of
motion. Contact between the two tapes is a purely geometric event, and
neither the direction nor the speed of the walk is estimated.
The independence structure used in the argument is not needed in the theorem
statement; it appears only in the machinery that transports the two
independent tapes into a common environment. In an independent environment
this is the Sznitman-Zerner regeneration and its subsequent contact analysis,
with speed estimates in the style of Comets and Zeitouni. The finite-range
adaptation replaces intersections by proximity within the dependence range,
kills the walk on entry to neighborhoods of used rows, and transfers only
the stopped path laws justified by separated rows. No conditional density
assumption, independent-label representation, positive speed, or moment
bound on regeneration times is imposed.
./sznitman-zerner-1999.pdf
./comets-zeitouni-2004.pdf
A final observation. Counterexamples exist in iid environments for mixed
speeds in dimension three, from Bramson, Zeitouni, and Zerner, and their
construction relies on the failure of a directional zero-one law. The
theorem rules out that failure in every uniformly elliptic finite-range
environment, and hence places that construction outside the finite-range
framework. A companion result under strict ellipticity but with no uniform
lower bound treats the same failure in iid environments, and the finite-range
adaptation keeps the same architecture while replacing independent rows
by nearby rows within the dependence range.
./bramson-zeitouni-zerner-2006.pdf