INDISTINGUISHABLE SCENERIES

ELON LINDENSTRAUSS

Abstract. In this paper we give a counter example to a conjecture mentioned in Benjamini and Kesten (1996) about distinguishing sceneries by observing them along a simple random walk, giving an explicit construction of 2^{ℵ_{0}} sceneries that are all pairwise indistinguishable.

1. Introduction

The basic problem we consider is how well can we distinguish two infinite words (sceneries) by observing these words along a simple random walk. This problem was introduced independently by I. Benjamini and by F. den Hollander and M. Keane, and has stimulated a considerable amount of research (Benjamini and Kesten (1996), Howard (1996), Howard (1997), Kesten (1996), Matzinger (1997)). Most of the results proved so far show that many sceneries can be distinguished by these observations. The result presented in this paper is a negative result, and gives some bounds to just how far the positive results can be pushed. A general survey about problems related to observing sceneries along random walks can be found in Kesten (1997).

Let A be a finite or even infinite alphabet. A scenery is simply a bi-infinite sequence of symbols from the alphabet A. Suppose that we are given a sequence f ∈ A^{ℕ} (a film) that was generated (in a random fashion) from a word w = (…, w_{−1}, w_{0}, w_{1} …) as follows: The first symbol of f is the symbol w_{0}, the second symbol is w_{α_{1}} with α_{1} = −1 or 1 with equal probability, the third is w_{α_{2}} where α_{2} = α_{1} ± 1 (again both possibilities are equally probable), etc. Thus f is simply the symbols in w read in a random order according to a simple random walk, and the terminology alludes to the non mathematical description of this situation as a drunken tourist randomly going about in some (one dimensional) scenery, taking every step a picture of his whereabouts.

There are essentially two questions one can ask, both of them are about how much information knowing f gives us about w. One of them, which will not be of interest for us in this paper, can be roughly stated as can one, for a typical scenery w and a typical film

Date: June 20, 1998.

Key words and phrases. Random walk, sceneries, distinguishability, mutually singular measures.

2 ELON LINDENSTRAUSS

f generated from w, deduce the sequence w from f? (see Matzinger (1997)). The question we consider is more modest: suppose we are given two sceneries w and w′, and a film f which was generated either from w or w′. Can we figure out if f was generated from w or from w′? Clearly, for most pairs the set of possible films from w and the corresponding set for w′ are very far from being disjoint. So, to make the question interesting we need to consider not only what films are a possible outcome of our drunken tourist’s tour, but also the distribution this process induces on the films (naturally, this distribution depends on the scenery). We give a formal definition of this distribution below:

Definition 1.1. For any w ∈ A^{ℤ} (the scenery), we can construct the map

Ψ_{w}: {±1}^{ℕ} → A^{ℕ}

by

Ψ_{w}(ϵ_{0}, ϵ_{1}, …) = (w_{0}, w_{ϵ_{0}}, w_{ϵ_{0}+ϵ1}, …).

If ω is the 0.5, 0.5 Bernoulli measure on {±1}^{ℕ} we define a probability measure ρ(w) on A^{ℤ} (the space of all films) by

ρ(w) = Ψ_{w}(ω).

Intuitively, even if the space of films that correspond to w has a nonempty intersection with the space of films for w′, it can still be true that from a typical film one can decide with arbitrarily high level of certainty whether it belongs to w or to w′. The rigorous way to express this is that the measures ρ(w) and ρ(w′) are mutually singular — that is, there is a set C ⊂ A^{ℕ} so that ρ(w)[C] = 0 but ρ(w′)[C] = 1.

Definition 1.2. Two sceneries w and w′ will be said to be distinguishable if ρ(w) and ρ(w′) are mutually singular. Two sceneries that are not distinguishable, are called indistinguishable.

This notion of distinguishability is somewhat weaker than the usual one, but is more suited for our purposes. We now present a stronger notion of distinguishability, distinguishability by suffixes, that corresponds to the notion of distinguishability in most of the literature on this subject.

Let σ denote both the one sided shift

σ(x_{0}, x_{1}, x_{2}, …) = (x_{1}, x_{2}, …)

and the two sided shift

σ(…, x_{−1}, x_{0}, x_{1}, …) = (…, x_{0}, x_{1}, x_{2}, …)

It should be clear from the context which operation we use.

Definition 1.3. For n ∈ ℕ, and any scenery w, let ρ_{n}(w) the measure σ^{n}(ρ(w)), i.e. the measure corresponding to letters of the alphabet A seen along a simple random walk, after omitting the first n observations.

Definition 1.4. Two points w and w′ will be said to be distinguishable by suffixes if for every n > 0, ρ_{n}(w) and ρ_{n}(w′) are mutually singular.

Clearly, if w is any scenery, and if w̃ is the reflection of w (i.e. w̃|_{n} = w|_{−n} for all n) then the distributions ρ(w) and ρ(w̃) are identical, and so w and w̃ are indistinguishable.

A somewhat more interesting example of indistinguishable sceneries can be obtained by looking at w and σ^{n}w for n even, which are rather often indistinguishable (we will explain this in detail latter in this introduction). In fact, for any even n, w and σ^{n}w are always not distinguishable by suffixes.

Almost any two sceneries can be distinguished (even only by suffixes) — this is shown in Benjamini and Kesten (1996). The conjecture we disprove is that any two sceneries w and w′, such that w′ is neither a translation of w nor a translation of w̃, are distinguishable by suffixes. In fact, we construct an example of an uncountable family of sceneries, every two of which are indistinguishable. We remark that our construction can easily be generalized to more general random walks.

To give some idea of why this example works, and some of the ideas we use in the proof, we show that that w and σ^{n}(w) are indistinguishable if w_{0} = w_{1} = ⋯ = w_{n}. Notice that ρ(σ^{n}w) is the distribution on A^{ℕ} one obtains by reading w along a simple random random walk starting at place n. So, essentially the situation at hand is that we have two drunken tourists, wondering around in the scenery w, one starting at place 0, the other at place n. If we find a way to synchronize the two tourists so that:

• If one looks only at one of the two tourists, the path this tourist goes is a simple random walk ,

• With positive probability, the films the two tourists generate are identical,

then clearly ρ(σ^{n}w) and ρ(w) cannot be mutually singular. A good way to synchronize the two tourists would be if they both went independently of one another, until the following event (which we will denote by Q) happens: at the nth step the tourist starting from place zero returns to place zero, having visited up to this time only the places 0, …,n/2, and the second tourist at the nth step also arrives to the 0th place. If Q happens, the second tourist

4 ELON LINDENSTRAUSS

from now on steps in the same way as the first tourist, who continues in his simple random walk. As n is even, there is a non zero probability of Q occuring, and if Q occurs, the films the two tourist generate will be identical — and so ρ(w) and ρ(σ^{n}w) are not singular. Such a synchronization is called a joining (or coupling) of two simple random walks, and is the technical tool we use in our proof.

Essentially, the idea of the construction is the following observation: w and σ^{n}w are many times indistinguishable. We construct many sceneries that are very nearly translates of one another, but not exactly, so that one the one hand these sceneries are still indistinguishable, but on the other hand we allow ourselves enough degrees of freedom so that there is a noncountable number of these sceneries. We present this construction in the following section. In §3 we develop some technical and more or less standard machinery about joinings which we use in §4 to prove that the example we have constructed in §2 has the required properties. Finally, we give some concluding remarks in §5.

The proof presented here is an improved version of the original proof for this result, and is similar to a proof suggested to the author by Prof. Yuval Peres. I would like to thank Prof. Peres for his kind consent for using his ideas (namely using couplings of random walks to simplify the argument) in this article. I would also like to thank the referee for his (or her) helpful suggestions on how to improve the exposition of this article.

2. The example

We now turn to construct the many indistinguishable sceneries. The sceneries we construct will be taken from a shift invariant closed subset of A^{ℤ}. The words in this shift invariant subset will be in almost 1-1 correspondance to elements of a monothetic group G (a compact commutative group, with an element g_{0} that generates a dense subgroup of G).

The monothetic group will depend on a sequence {m_{k}}_{k=1}^{∞} of positive integers. Define M_{k} = Π_{i=1}^{k}m_{i}, and M_{0} = 1. For k′ > k, the group ℤ/M_{k′}ℤ projects onto ℤ/M_{k}ℤ in the natural way (x ↦ x mod M_{k}), and we can define G to be the corresponding inverse limit

G = G(m_{1}, m_{2}, …) := \underleftarrow{lim}_{k→∞}ℤ/M_{k}ℤ.

We recall the definition of an inverse limit: if we are given a sequence of groups G_{i} and homomorphisms h_{i} from G_{i+1} onto G_{i}, their inverse limit is the group

\underleftarrow{lim}_{k→∞}G_{k} = \{(g_{1}, g_{2}, …) : g_{i} ∈ G_{i} and h_{i}(g_{i+1}) = g_{i} for all i\}  (1)

with the group operation being

(f_{1}, f_{2}, …) + (g_{1}, g_{2}, …) = (f_{1} + g_{1}, f_{2} + g_{2}, …).

INDISTINGUISHABLE SCENERIES 5

Let π_{k} : G → ℤ/M_{k}ℤ be the mod M_{k} map. Define γ_{k}: G → ℤ/m_{k}ℤ by

γ_{k}(g) = ⌊π_{k}(g)/M_{k−1}⌋.

It is possible to view G as a sequence of elements of {ℤ/M_{k}ℤ}_{k=1}^{∞} as in (1). An alternative view is that as a set

G ≅^{Γ} {(γ_{1}, γ_{2}, …) : γ_{i} ∈ {0, 1, …, m_{i} − 1}}

with the (set theoretic) isomorphism being defined by

Γ(g) = (γ_{1}(g), γ_{2}(g), …)

or equivalently by

π_{k}(Γ^{−1}(γ_{1}, γ_{2}, …)) = ∑_{i=1}^{k} γ_{i}M_{i−1}.

Essentially what we have done above is to expand the numbers in ℤ according to the variable base {m_{k}} and then take a natural compactification of this space.

We can define a one-to-one function i: ℤ → G by π_{k}(i(n)) = n mod M_{k} for every k. The subset i(ℤ) of G can be characterized as the set of g’s such that γ_{k}(g) = 0 for k large enough. Let 1 be i(1). By slight abuse of notation we will sometimes write g − n (g ∈ G and n ∈ ℤ) for g − n · 1 ≡ g − i(n).

The subgroups A_{k} = {g ∈ G : π_{k}(g) = 0} of G form a neighbourhood basis at 0 ∈ G. Define A_{0} = G. We designate for g ≠ 0,

r(g) = max{k : g ∈ A_{k}} = min{k : π_{k}(g) ≠ 0} − 1,  (2)

and r(0) = +∞.

Let A be any alphabet. We are now ready to construct a closed shift invariant subset of A^{ℤ} that will be in almost 1-1 correspondence with G. This subset of A^{ℤ} will be constructed using an arbitrary sequence

a = (a_{0}, a_{1}, …) ∈ A^{ℕ},

as well as the group G, and so we will denote it by X_{a,G}.

Definition 2.1. Given a define ϕ_{a,G}: G \ i(ℤ) → A^{ℤ} by

ϕ_{a,G}(g) = (…, a_{r(−g−1)}, a_{r(−g)}, a_{r(−g+1)}, …),

i.e. the nth coordinate of ϕ_{a,G}(g) is a_{r(−g+n·1)}. Set X_{a,G} := cl(ϕ_{a,G}(G \ i(ℤ))), the closure (in the product topology on A^{ℤ}) of the image of ϕ_{a,G}.

Notice that for g ∉ i(ℤ),

ϕ_{a,G}(g − 1) = (…, a_{r(−g)}, a_{r(−g+1)}, a_{r(−g+2·1)}, …) = σ(ϕ_{a,G}(g)).

The sceneries in X_{a,G} are of the following form: if w ∈ X_{a,G}, then most of the symbols of w are a_{0} — all except those symbols that appear at places in some arithmetic progression of the form n_{1} + M_{1}ℤ for some n_{1} ∈ {0, …, m_{1} − 1}. Of these symbols that appear at places in the arithmetic progression n_{1} + M_{1}ℤ, most are a_{1} — all but those that appear at places in n_{2}M_{1} + n_{1} + M_{2}ℤ for some n_{2} ∈ {0, …, m_{2} − 1}, and so on. We summarize this description below:

w = …, a_{0}, \underbrace{a_{1}, a_{0}, …, a_{0}}_{M_{1}}, \overbrace{\underbrace{a_{2}, a_{0}, …, a_{0}}_{M_{1}}, a_{1}, a_{0}, …, a_{0}, a_{1}, a_{0}, …, a_{0}}^{M_{2}}, a_{2}, a_{0}, …

We can relate this picture to the formal definition in Definition 2.1 by noticing that if w and n_{1}, n_{2}, … are as above then

ϕ_{a,G}(Γ^{−1}(n_{1}, n_{2}, …)) = w,

provided Γ^{−1}(n_{1}, n_{2}, …) ∉ i(ℤ). If Γ^{−1}(n_{1}, n_{2}, …) = n · 1 ∈ i(ℤ), then the sequence n_{1}, n_{2}, … need not uniquely determine w — the symbol w|_{n} remains undetermined.

Under reasonable conditions (a is not eventually constant), ϕ_{a,G}(g) is one-to-one on G \ i(ℤ). Indeed, by replacing the sequence {M_{k}} with a subsequence if necessary, we can assume that a_{k} ≠ a_{k−1}. Let w ∈ X_{a,G}. There would be exactly one arithmetic progression n_{1} + M_{1}ℤ such that the symbols of w that appear on places in this progression are not all a_{0}. If w = ϕ_{a,G}(g), this n_{1} must be γ_{1}(g). Proceeding further in this way we can recover all digits of g from ϕ_{a,G}(g).

Let

Λ = {ξ ∈ G : γ_{k}(ξ) = ±1}.

Theorem 2.1. If the m_{k} increase rapidly enough (a precise condition will be given later), and g ∈ G satisfies √m_{k} + 1 < γ_{k}(g) < m_{k} − √m_{k} for every k, then for any two elements ξ^{1}, ξ^{2} ∈ Λ, the scenery ϕ_{a,G}(g + ξ^{1}) is indistinguishable from ϕ_{a,G}(g + ξ^{2}).

There are uncountably many ξs in Λ, and as ϕ_{a,G} is one-to-one we get an uncountable number of indistinguishable sceneries, in stark contrast to the conjecture we wish to disprove.

Notice that |γ_{k}(g + ξ^{i}) − γ_{k}(g)| ≤ 2 (less than or equal to 2 since we might have to compensate for carry from the low order digits — in fact for our g the above difference will always be ±1), and so for all k, γ_{k}(g + ξ^{i}) ≠ 0 if m_{k} are large enough, so g + ξ^{i} ∉ i(ℤ).

3. Preliminaries

We now introduce a sequence of progressively stronger pseudo-metrics (the last element of this sequence D_{∞} will actually be a metric) on the set of (not necessarily σ-invariant) measures on A^{ℕ}.

Definition 3.1. Let ρ^{1}, ρ^{2} be two measures on A^{ℕ}, and denote by J(ρ^{1}, ρ^{2}) the set of joinings of ρ^{1} and ρ^{2}, i.e. the measures ν on A^{ℕ}×A^{ℕ} so that the projection of ν to the first coordinate is ρ^{1}, and the projection to the second coordinate is ρ^{2}. Define the D_{N}-metric of ρ^{1} from ρ^{2} to be

D_{N}(ρ^{1}, ρ^{2}) := inf_{ν∈J(ρ^{1},ρ^{2})} ν(Δ_{N}^{C}) = 1 − sup_{ν∈J(ρ^{1},ρ^{2})} ν(Δ_{N}).

where Δ_{N} ⊂ A^{ℕ} × A^{ℕ} is the set

Δ_{N} := {(x^{1}, x^{2}) ∈ A^{ℕ} × A^{ℕ} : x^{1}|_{1...N} = x^{2}|_{1...N}}

and Δ_{N}^{C} = A^{ℕ} × A^{ℕ} \ Δ_{N} is its complement.

That this is a pseudo-metric is easy to verify: trivially D_{N}(ρ^{1}, ρ^{2}) = D_{N}(ρ^{2}, ρ^{1}), and D_{N}(ρ, ρ) = 0.

A standard argument gives the triangle inequality:

Proposition 3.1. For any ν ∈ J(ρ^{1}, ρ^{2}) and ν′ ∈ J(ρ^{2}, ρ^{3}), and any N ≤ ∞, there is a ν′′ ∈ J(ρ^{1}, ρ^{3}) such that

ν′′(Δ_{N}^{C}) ≤ ν(Δ_{N}^{C}) + ν′(Δ_{N}^{C})

Proof:

Let X^{1}, X^{2} and X^{3} be three copies on A^{ℕ}, with matching σ-algebras F^{1}, F^{2} and F^{3}. We consider ν as a measure on X^{1} × X^{2} and ν′ as a measure on X^{2} × X^{3}. We can construct from these the relative independent joining ν ×_{ρ^{2}} ν′ on X^{1} × X^{2} × X^{3} as follows: for any continuous f^{1} ∈ C(X^{1}), f^{2} ∈ C(X^{2}) and f^{3} ∈ C(X^{3}) define

∫_{X^{1}×X^{2}×X^{3}} f^{1}(x^{1})f^{2}(x^{2})f^{3}(x^{3}) dν ×_{ρ^{2}} ν′ = ∫_{X^{2}} f^{2}(x^{2})E_{ν}(f^{1}|F^{2})(x^{2}) · E_{ν′}(f^{3}|F^{2})(x^{2}) dρ^{2}

As the linear span of such f^{1}(x^{1})f^{2}(x^{2})f^{3}(x^{3}) is dense in C(X^{1} × X^{2} × X^{3}) this determines ν ×_{ρ^{2}} ν′. We define ν′′ to be the projection of the measure ν ×_{ρ^{2}} ν′ on X_{1} × X_{3}. Since

\begin{aligned}∫_{X^{1}×X^{3}} f^{1}(x^{1}) dν′′ & = ∫_{X^{2}} E_{ν}(f^{1}|F^{2})(x^{2}) dρ^{2} \\ & = ∫_{X^{1}×X^{2}} f^{1}(x^{1}) dν = ∫_{X^{1}} f^{1}(x^{1}) dρ^{1}, \end{aligned}

8 ELON LINDENSTRAUSS

ν′′ projects to ρ^{1} on X^{1}, and the same is true for ρ^{3}. Thus ν′′ ∈ J(ρ^{1}, ρ^{3}). Similarly, one can verify that the projection of ν ×_{ρ^{2}} ν′ to X^{1} × X^{2} = ν, and the projection of this measure to X^{2} × X^{3} is ν′. Finally,

ν′′(Δ_{N}^{C}) = ∫_{X^{1}×X^{3}} 1_{Δ_{N}^{C}} (x^{1}, x^{3}) dν′′
≤ ∫_{X^{1}×X^{2}×X^{3}}(1_{Δ_{N}^{C}} (x^{1}, x^{2}) + 1_{Δ_{N}^{C}} (x^{2}, x^{3})) dν ×_{ρ^{2}} ν′
= ν(Δ_{N}^{C}) + ν′(Δ_{N}^{C}).

If N = ∞, then D_{N} is actually a metric, as in this case D_{∞}(ρ^{1}, ρ^{2}) = 0 only if ρ^{1} = ρ^{2}. Another point worth noting is that since Δ_{N} ⊃ Δ_{N′} for any N < N′,

D_{N}(ρ^{1}, ρ^{2}) ≤ D_{N′}(ρ^{1}, ρ^{2}).

Lemma 3.2. Let ρ^{1}, ρ^{2} be two measures on A^{ℕ}. Then

D_{∞}(ρ^{1}, ρ^{2}) = lim_{N→∞} D_{N}(ρ^{1}, ρ^{2})

Proof:

It follows from the monotonicity of the sequence of metrics {D_{N}} that

D_{∞}(ρ^{1}, ρ^{2}) ≥ lim_{N→∞} D_{N}(ρ^{1}, ρ^{2});

we will now prove the opposite direction.

Let J_{N} be a joining of ρ^{1} and ρ^{2} such that

J_{N}(Δ_{N}^{C}) < D_{N}(ρ^{1}, ρ^{2}) + 1 ; N

Let ν be a weak limit of some subsequence J_{N_{i}}. As Δ_{N} is compact,

ν(Δ_{N}) ≥ lim_{i→∞} J_{N_{i}}(Δ_{N}) ≥ lim_{i→∞} J_{N_{i}}(Δ_{N_{i}}) ≥ lim_{i→∞}(1 − D_{N_{i}}(ρ^{1}, ρ^{2}) − 1/N_{i})

= lim_{N→∞}(1 − D_{N}(ρ^{1}, ρ^{2})),

and so

ν(Δ_{∞}) = ν(∩_{N=1}^{∞}Δ_{N}) = lim_{N→∞} ν(Δ_{N}) ≥ lim_{N→∞}(1 − D_{N}(ρ^{1}, ρ^{2})).

By definition, D_{∞}(ρ^{1}, ρ^{2}) ≤ 1 − ν(Δ_{∞}).

Remark: Notice that ρ^{1} and ρ^{2} are mutually singular if and only if D_{∞}(ρ^{1}, ρ^{2}) = 1. Even though this fact is almost self evident, it is very important and explains why the D_{∞} metric is connected to the problem of distinguishing between sceneries. We will only need the “only if” direction — if ρ^{1} and ρ^{2} are mutually singular, there are disjoint sets A^{1} and A^{2} such that ρ^{i}(A^{j}) = δ_{i,j} for i, j = 1, 2. Then for any joining ν ∈ J(ρ^{1}, ρ^{2}) we have

1 = ν(A^{1} × A^{2}) ≤ ν(Δ_{∞}^{C}) ≤ D_{∞}(ρ^{1}, ρ^{2}).

4. Many sceneries cannot be distinguished

Lemma 4.1. Let {m_{k}} and G = G(m_{1}, m_{2}, …) be as above, and assume in addition that √m_{1} < γ_{1}(g) < m_{1} − √m_{1}. Then for any ϵ > 0 there is a F (ϵ) that does not depend on the m_{i}’s and g such that if m_{1} ≥ F (ϵ)

D_{∞} (ρ(ϕ_{a,G}(g + 1)), ρ(ϕ_{a,G}(g − 1))) < ϵ.

The proof of this Lemma follows along similar lines as the proof that under certain circumstances w and σ^{2n}w are indistinguishable we have given in the introduction. This is not too surprising, given the fact that ϕ_{a,G}(g − 1) = σ^{2}(ϕ_{a,G}(g + 1)). The picture behind the proof is the following: recall that ρ(ϕ_{a,G}(g + 1)) is the measure on the set of films, derived by observing the symbols of ϕ_{a,G}(g − 1) = σ^{2}ϕ_{a,G}(g + 1) along a random walk starting at place 2. Thus we take two independent random walks, one starting from place 0 and one from place 2, until they meet. From this moment on, the two random walk step in the same way. Unless at least one of the random walk reached a place with some symbol ≠ a_{0} in it before the two random walks met, the two films that were generated will be identical. Since both random walks start at nearly the same point, at least √m_{1} steps from the nearest non a_{0} symbol, if m_{1} is large enough the probability that this will happen is very small.

Proof: We now describe in detail the joining ν̃ of two simple random walks described above, where as before a joining of two random walks is a measure that projects to a simple random walk in each coordinate. This joining ν̃ of random walks induces a joining ν between ρ(ϕ_{a,G}(g − 1)) and ρ(ϕ_{a,G}(g + 1)) — we generate a ν-random pair of films by observing ϕ_{a,G}(g − 1) and ϕ_{a,G}(g + 1) along random walks chosen according to the distribution ν̃. We shall show that this ν satisfies ν(Δ_{∞}) → 1 uniformly as m_{1} → ∞.

We now define ν̃. If α_{n}^{1} and α_{n}^{2} are two independent simple random walks on ℤ (i.e. α_{0}^{i} = 0, α_{n}^{i} − α_{n−1}^{i} = ±1), we generate a ν̃ random pair of simple random walks (β_{n}^{1}, β_{n}^{2}) as follows:

• First, set n′ to be the smallest positive integer such that α_{n}^{1} = α_{n}^{2} − 2.

• Set β_{n}^{1} = α_{n}^{1} for all n, and

• Set β_{n}^{2} = α_{n}^{2} for n ≤ n′, β_{n}^{2} = α_{n}^{1} + 2 for n > n′.

10 ELON LINDENSTRAUSS

Note that since α_{n}^{1} − α_{n}^{2} is a recurrent random walk on 2ℤ (which will eventually visit every point of 2ℤ infinitely many times), n′ < ∞ almost surely. It is clear ν̃ is a joining. If the n′ defined above is smaller than √m_{1} − 1, then for i = 1, 2 and n < n′

min_{k∈ℤ}|π_{1}(g + (−1)^{i} − β_{n}^{i}) − kM_{1}| ≥ min_{k∈ℤ}|π_{1}(g + (−1)^{i}) − kM_{1}| − (√m_{1} − 1) > 0,

i.e.

ϕ_{a,G}(g + (−1)^{i})|_{β_{n}^{i}} = a_{r(−g−(−1)^{i}+β_{n}^{i})} = a_{0} for n < n′.

If n ≥ n′, β_{n}^{1} = β_{n}^{2} − 2, i.e.

ϕ_{a,G}(g − 1)|_{β_{n}^{1}} = a_{r(−g+1+β_{n}^{1})} = a_{r(−g−1+β_{n}^{2})} = ϕ_{a,G}(g + 1)|_{β_{n}^{2}}.

Thus for all n,

ϕ_{a,G}(g − 1)|_{β_{n}^{1}} = ϕ_{a,G}(g + 1)|_{β_{n}^{2}}.

and so we have demonstrated that

D_{∞} (ρϕ_{a,G}(g − 1), ρϕ_{a,G}(g + 1)) < Prob(n′ > √m_{1} − 1)

and by recurrence Prob(n′ > √m_{1} − 1) → 0 as m_{1} → ∞.

Let w, w′ be any two infinite words in A^{ℤ}. We know that a joining of the simple random walk with itself induces a joining of ρ(w) and ρ(w′). The following simple technical lemma is rather standard, and shows that all joinings of ρ(w) and ρ(w′) can be constructed in this way. Denote by ω the standard measure on the space Ω of simple random walks. Ω is a compact space that can be identified with {−1, 1}^{ℕ}: indeed to every (ϵ_{n})_{n=1}^{∞} ∈ {−1, 1}^{ℕ} there corresponds the random walk α_{0} = 0, α_{1} = ϵ_{1}, α_{2} = ϵ_{1} + ϵ_{2}, etc. Given a scenery w ∈ A^{ℤ}, we recall the definition of Ψ_{w}: Ω → A^{ℕ}

Ψ_{w}: ((α_{n})_{n=0}^{∞}) ↦ (w_{α_{0}}, w_{α_{1}}, …).

Ψ_{w} × Ψ_{w′} clearly maps J(ω, ω) to J(ρ(w), ρ(w′)).

Lemma 4.2. Ψ_{w} × Ψ_{w′} maps J(ω, ω) onto J(ρ(w), ρ(w′)).

Proof: As Ψ_{w} × Ψ_{w′} is continuous, Ω compact, C(Ψ_{w}(Ω) × Ψ_{w′}(Ω)) can be viewed as a closed subspace of C(Ω × Ω). A joining in J(ω, ω) is a positive linear functional with norm 1 on C(Ω × Ω) that gives the value zero to any function in the closed set

A = {f(α, β) : ∀α, β f(α, β) = g(α) or ∀α, β f(α, β) = g(β)
with g(α) ∈ C(Ω), and ∫ g(α)dω(α) = 0}

INDISTINGUISHABLE SCENERIES 11

Take any element ν ∈ J(ρ(w), ρ(w′)). we must show there is some ν̃ ∈ J(ω, ω) such that Ψ_{w} × Ψ_{w′}(ν̃) = ν.

An elements ν of J(ρ(w), ρ(w′)) can be viewed as a positive functional with norm one on C(Ψ_{w}(Ω) × Ψ_{w′}(Ω)), which is zero on A ∩ C(Ψ_{w}(Ω) × Ψ_{w′}(Ω)). By the Hahn-Banach theorem, this functional can be extended to a positive functional ν̃ that acts on the full space C(Ω × Ω) with norm one, so that for any f ∈ A, ν̃(f) = 0. By construction

Ψ_{w} × Ψ_{w′}(ν̃) = ν.

Definition 4.1. Let G = G(m_{1}, m_{2}, …), G̃ = G(m_{2}, m_{3}, …). Define T: G → G̃ by

γ_{k−1}(T g) = γ_{k}(g) for all k ≥ 1.

Thus Γ(T g) = (γ_{2}, γ_{3}, …) is the sequence Γ(g) = (γ_{1}, γ_{2}, …) shifted once to the left. Let α_{n} be a simple random walk along a scenery w = ϕ_{a,G}(g) for g ∈ G with π_{1}(G) = 0, and we consider the times t during which α_{t} ∈ m_{1}ℤ — i.e. the times where the symbol recorded on the film is not a_{0}. The symbols we record at these times are a result of a slightly different random walk (there is now a positive probability of staying at exactly the same place the next step of the random walk), along a modified scenery. The modified scenery is the scenery we get from ϕ_{a,G}(g) by erasing all symbols except those at places in m_{1}ℤ. This modified scenery is exactly the scenery that corresponds to T (g) via ϕ_{σa,G̃}, where G̃ = G(m_{2}, m_{3}, …) and σa is the sequence a shifted to the left. If we consider the symbols of ϕ_{a,G}(g) recorded on the film not for all t such that α_{t} ∈ m_{1}ℤ, but only only for those times t_{k} such that α_{t_{k}} ∈ m_{1}ℤ but the last α_{t} ∈ m_{1}ℤ for t < t_{k} is not equal to α_{t_{k}}, then the distribution of these symbols is exactly the distribution we see when we walk by a simple random walk on ϕ_{σa,G̃}(T (g)).

The next lemma allows us to use inductive type arguments for estimating how well ρ(ϕ_{a,G}(g)) and ρ(ϕ_{a,G}(h)) can be coupled by showing that if we have a good coupling of ρ(ϕ_{σa,G̃}(T g)) and ρ(ϕ_{σa,G̃}(T h)) (for g, h ∈ G which are zero in their γ_{1} coordinate), we can use this to obtain a good coupling of ρ(ϕ_{a,G}(g)) and ρ(ϕ_{a,G}(h)). The idea is to use the inverse of the procedure described above for deriving a simple random walk on ϕ_{σa,G̃}(T g) from a random walk on ϕ_{a,G}(g) to get, from a pair of coupled random walks on ϕ_{σa,G̃}(T g) and ϕ_{σa,G̃}(T h), a pair of random walks on ϕ_{a,G}(g) and ϕ_{a,G}(h).

Lemma 4.3. Again let G = G(m_{1}, m_{2}, …), G̃ = G(m_{2}, m_{3}, …). If g, h ∈ G, such that π_{1}(g) = π_{1}(h) = 0 then

D_{∞}(ρ(ϕ_{a,G}(g)), ρ(ϕ_{a,G}(h))) ≤ D_{∞}(ρ(ϕ_{σa,G̃}(T g)), ρ(ϕ_{σa,G̃}(T h))).

12 ELON LINDENSTRAUSS

Proof:

Let ϵ > 0,

ν ∈ J(ρ(ϕ_{σa,G̃}(T g)), ρ(ϕ_{σa,G̃}(T h)))

such that

ν(Δ_{∞}) > 1 − D_{∞}(ρ(ϕ_{σa,G̃}(T g)), ρ(ϕ_{σa,G̃}(T h))) − ϵ.

By Lemma 4.2, there is some joining ν̃ of the simple random walk with itself that induces the joining ν.

We will now define a joining μ̃ that will induce a joining μ ∈ J(ρ(ϕ_{a,G}(g)), ρ(ϕ_{a,G}(h))) such that μ(Δ_{∞}) will be high.

In order to define μ̃ we will give an algorithm how to generate a μ̃-random pair of (non independent) simple random walks (β_{n}^{1})_{n=0}^{∞}, (β_{n}^{2})_{n=0}^{∞} from a triplet of random walks: A simple random walk (s_{n})_{n=0}^{∞}, chosen independently of the pair (α_{n}^{1})_{n=0}^{∞} and (α_{n}^{2})_{n=0}^{∞}, which we chose according to ν̃.

Define the sequence 0 = t_{0} < t_{1} < t_{2} < … inductively by

t_{n} := min{t > t_{n−1} : π_{1}(s_{t}) = 0, s_{t} ≠ s_{t_{n−1}}}.

Thus, t_{n} is the least t such that s_{t} = s_{t_{n−1}} ±m_{1}. Define β_{0}^{1} = β_{0}^{2} = 0, and for all t_{k} < t ≤ t_{k+1}, i = 1, 2

β_{t}^{i} = β_{t_{k}}^{i} + (s_{t} − s_{t_{k}}) sgn(s_{t_{k+1}} − s_{t_{k}})(α_{k+1}^{i} − α_{k}^{i}).

Notice that since s_{t_{k+1}} − s_{t_{k}} = ±m_{1}, β_{t_{k+1}}^{i} − β_{t_{k}}^{i} is also ±m_{1} — in fact, β_{t_{k+1}}^{i} − β_{t_{k}}^{i} = m_{1}(α_{k+1}^{i} − α_{k}^{i}), and so β_{t_{n}}^{i} = m_{1}α_{n}^{i}.

We must first convince ourself that β_{t}^{1} by itself is distributed like a simple random walk, and the same for β_{t}^{2}. But β_{t}^{1} depends only on s_{n} and α_{n}^{1}, two independent simple random walks. Essentially what happens is that as {α_{k+1}^{1} − α_{k}^{1}}_{k=0}^{∞} are ±1 with equal probability i.i.d. irrespective of s_{t}, the same is true for {sgn(s_{t_{k+1}} − s_{t_{k}})(α_{k+1}^{1} − α_{k}^{1})}_{k=0}^{∞}. And so β_{n}^{1} is obtained by reflecting the simple random walk s_{k} at times chosen randomly in a way that depends only on past history. By the Strong Markov Property of simple random walks this does not change the distribution - i.e. β_{n}^{1} is distributed as a simple random walk. The same argument is valid for β_{n}^{2}. Thus μ̃ ∈ J(ω, ω).

We would like now to show

μ(Δ_{∞}) ≥ ν(Δ_{∞}).  (3)

So let s_{n} be arbitrary, α_{n}^{1}, α_{n}^{2} a pair such that

ϕ_{σa,G̃}(T g)|_{α_{n}^{1}} = ϕ_{σa,G̃}(T h)|_{α_{n}^{2}}  for all n.  (4)

The probability of this event happening is exactly ν(Δ_{∞}). We claim that if (4) holds, then

ϕ_{a,G}(g)|_{β_{t}^{1}} = ϕ_{a,G}(h)|_{β_{t}^{2}} for all t.

We first prove that for all k,

ϕ_{a,G}(g)|_{β_{t_{k}}^{1}} = ϕ_{a,G}(h)|_{β_{t_{k}}^{2}}

We recall that the definition of r in equation (2) depends on the group G. This has not caused any confusion up to now since the group G was fixed; now, however, since we have two groups we are working with, we will use the notation r_{G} and rG̃ to designate the function r on G and G̃ respectively. If t = t_{k} then by construction β_{t_{k}}^{i} = m_{1}α_{k}^{i}, i.e.

ϕ_{a,G}(g)|_{β_{t_{k}}^{1}} = a_{r_{G}(−g+m_{1}α_{k}^{1})} = a_{rG̃(−T g+α_{k}^{1})+1} = ϕ_{σa,G̃}(T g)|_{α_{k}^{1}}
= ϕ_{σa,G̃}(T h)|_{α_{k}^{2}} = a_{rG̃(−T h+α_{k}^{2})+1} = ϕ_{a,G}(h)|_{β_{t_{k}}^{2}} .

where r_{G}(−g + m_{1}α_{k}^{i}) = rG̃(−T g + α_{k}^{1}) + 1 since

π_{i, in G}(g − m_{1}α_{k}^{1}) = m_{1}π_{i−1, in G̃} (T g − α_{k}^{1}),

thus π_{i, in G}(g − m_{1}α_{k}^{1}) ≡ 0 (mod m_{1} · m_{2} ⋯ m_{i}) — and hence r_{G}(−g + m_{1}α_{k}^{1}) ≥ i — if and only if π_{i−1, in G̃}(T g − α_{k}^{1}) ≡ 0 (mod m_{2} ⋯ m_{i}).

Now suppose t ∉ {t_{0}, t_{1}, … }. Then either π_{1}(β_{t}^{1}) ≠ 0, which implies π_{1}(β_{t}^{2}) ≠ 0 and so

ϕ_{a,G}(g)|_{β_{t}^{1}} = a_{r_{G}(−g+β_{t}^{1})} = a_{0} = a_{r_{G}(−h+β_{t}^{2})} = ϕ_{a,G}(h)|_{β_{t}^{2}},

or t_{k} < t < t_{k+1} for some k, and s_{t_{k}} = s_{t}. If this is the case then β^{i}|_{t} = β^{i}|_{t_{k}} for both i = 1 and 2 — and ϕ_{a,G}(g)|_{β_{t}^{1}} = ϕ_{a,G}(h)|_{β_{t}^{2}} follows from ϕ_{a,G}(g)|_{β_{t_{k}}^{1}} = ϕ_{a,G}(h)|_{β_{t_{k}}^{2}} .

Thus

μ̃ {β_{n}^{1}, β_{n}^{2} : ϕ_{a,G}(g)|_{β_{n}^{1}} = ϕ_{a,G}(h)|_{β_{n}^{2}} for all n}
≥ ν̃ {α_{n}^{1}, α_{n}^{2} : ϕ_{σa,G̃}(T g)|_{α_{n}^{1}} = ϕ_{σa,G̃}(T h)|_{α_{n}^{2}} for all n}

proving (3).

Lemma 4.4. Let m_{i}, G = g(m_{1}, m_{2}, …) be as above, g and f elements of G, with π_{1}(g) = π_{1}(f) = p. p is an element of ℤ/m_{1}ℤ, but with slight abuse of notation we can view it as an

14 ELON LINDENSTRAUSS

element of ℤ between 0 and m_{1} − 1. Using this notation we claim that

D_{∞}(ρϕ_{a,G}(g), ρϕ_{a,G}(f)) ≤ max (D_{∞}(ρϕ_{a,G}(g − p), ρϕ_{a,G}(f − p)),
D_{∞}(ρϕ_{a,G}(g + m_{1} − p), ρϕ_{a,G}(f + m_{1} − p))).

Proof. since the proof of this lemma is very similar to the proofs of the preceding lemmas, we omit the details.

Assume ν^{1} ∈ J(ρ(ϕ_{a,G}(g − p)), ρ(ϕ_{a,G}(f − p))) and ν^{2} ∈ J(ρ(ϕ_{a,G}(g + m_{1} − p)), ρ(ϕ_{a,G}(f + m_{1}−p))) having an almost maximal measure for Δ_{∞}, and use Lemma 4.2 to find ν̃^{i} ∈ J(ω, ω) joinings of simple random walks that induce ν^{i}. We will use a simple random walk α_{n}^{1}, two random walks (α_{n}^{2} and α_{n}^{3}) chosen according to ν̃^{1}, and two chosen according to ν̃^{2} (α_{n}^{4} and α_{n}^{5}). We will use all these α_{n}^{i}’s to construct a pair of random walks β_{n}^{1} and β_{n}^{2}. This will give us a measure μ̃ on pairs of random walks which will easily seen to be a joining of two simple random walks, which will induce a measure μ ∈ J(ρϕ_{a,G}(g), ρϕ_{a,G}(f)) with high μ(Δ_{∞}).

Indeed, we take β_{n}^{1} = β_{n}^{2} = α_{n}^{1} up to the first n′ such that π_{1}(g − α_{n}^{1}) = 0 (this will also mean that π_{1}(f − α_{n′}^{1}) = 0). There are two possibilities: α_{n′}^{1} = p or α_{n′}^{1} = p − m_{1}. In the first case we will take for n > n′, and i = 1,2, β_{n}^{i} = α_{n−n′}^{1+i} + p, in the second case we take for n > n′, and i = 1,2, β_{n}^{i} = α_{n−n′}^{3+i} + p − m_{1}. The rest of the details are omitted.

Theorem 4.5. Let c_{i} > 0 be a sequence of positive real numbers, {m_{1}, m_{2}, …, } a sequence of integers such that m_{i} > F (c_{i}) (where F is as in Lemma 4.1). Let G = G(m_{1}, m_{2}, …),

with g ∈ G satisfying √m_{1} < γ_{1}(g) < m_{1} − √m_{1} and √m_{k} + 1 < γ_{k}(g) < m_{k} − √m_{k} for

k > 1. Then for any ξ^{1}, ξ^{2} ∈ Λ,

D_{∞}(ρ(ϕ_{a,G}(g + ξ^{1})), ρ(ϕ_{a,G}(g + ξ^{2}))) ≤ ∑_{i=1}^{∞} c_{i},

and hence if ∑ c_{i} < 1, ϕ_{a,G}(g + ξ^{1}) and ϕ_{a,G}(g + ξ^{2}) are indistinguishable (in the sense explained in the introduction)

Proof:

Step 1: First we show by induction on k that for any k and any m_{i}, ξ^{1}, ξ^{2} and g as in the statement of the Theorem,

D_{∞}(ρ(ϕ_{a,G}(g + π_{k}(ξ^{1}))), ρ(ϕ_{a,G}(g + π_{k}(ξ^{2})))) ≤ ∑_{i=1}^{k} c_{k}  (5)

(again we treat π_{k}(·) as an element of ℤ between 0 and M_{k} − 1). Let ξ(k, r) ∈ G be defined by γ_{i}(ξ(k, r)) = γ_{i}(ξ^{1}) for i ≤ r, γ_{i}(ξ(k, r)) = γ_{i}(ξ^{2}) for r < i ≤ k, and γ_{i}(ξ(k, r)) = 0 for i > k. Note that ξ(k, 0) = π_{k}(ξ^{2}), ξ(k, k) = π_{k}(ξ^{1}).

INDISTINGUISHABLE SCENERIES 15

To show (5) holds, we will use induction on k: we assume that (5) holds for k − 1 and all m_{1}, m_{2}, …, g, and ξ^{i} satisfying the above conditions, and use this to prove the same for k. For k = 0 the result is trivial. Now assume (5) holds for k − 1. Use Lemma 4.1 to see that

D_{∞}(ρϕ_{a,G}(g + ξ(k, k)),ρϕ_{a,G}(g + ξ(k, 0)))
≤ D_{∞}(ρϕ_{a,G}(g + ξ(k, k)), ρϕ_{a,G}(g + ξ(k, 1)))
+ D_{∞}(ρϕ_{a,G}(g + ξ(k, 1)), ρϕ_{a,G}(g + ξ(k, 0)))
≤ D_{∞}(ρϕ_{a,G}(g + ξ(k, k)), ρϕ_{a,G}(g + ξ(k, 1))) + c_{1}

(6)

But π_{1}(g + ξ(k, k)) = π_{1}(g + ξ(k, 1)) and so Applying Lemma 4.4, we have

D_{∞}(ρϕ_{a,G}(g + ξ(k, k)), ρϕ_{a,G}(g + ξ(k, 1)))
≤ max(D_{∞}(ρϕ_{a,G}(g − π_{1}(g + ξ^{1}) + ξ(k, k)), ρϕ_{a,G}(g − π_{1}(g + ξ^{1}) + ξ(k, 1))),
D_{∞}(ρϕ_{a,G}(g + m_{1} − π_{1}(g + ξ^{1}) + ξ(k, k)),
ρϕ_{a,G}(g + m_{1} − π_{1}(g + ξ^{1}) + ξ(k, 1)))) = (∗).

We then apply Lemma 4.3 twice, to get

(∗) ≤ max(D_{∞}(ρϕ_{σa,G̃}(T (g − π_{1}(g)) + T (ξ(k, k) − π_{1}(ξ^{1}))),
ρϕ_{σa,G̃}(T (g − π_{1}(g)) + T (ξ(k, 1) − π_{1}(ξ^{1})))),
D_{∞}(ρϕ_{σa,G̃}(T (g + m_{1} − π_{1}(g)) + T (ξ(k, k) − π_{1}(ξ^{1}))),
ρϕ_{σa,G̃}(T (g + m_{1} − π_{1}(g)) + T (ξ(k, 1) − π_{1}(ξ^{1}))))) = (∗∗).

We now note that for i > 1

\begin{aligned}γ_{i, in G̃}(T (g − π_{1}(g))) & = γ_{i, in G̃}(T (g + m_{1} − π_{1}(g))) \\ & = γ_{i+1, in G}(g) ∈ [√m_{i+1} + 1, m_{i+1} − √m_{i+1}]. \end{aligned}

For i = 1,

\begin{aligned}γ_{1, in G̃}(T (g − π_{1}(g))) & = γ_{1, in G̃}(T (g + m_{1} − π_{1}(g))) − 1 \\ & = γ_{2, in G}(g) ∈ [√m_{2} + 1, m_{2} − √m_{2}], \end{aligned}

hence both the first and second term are in [√m_{2}, m_{2} − √m_{2}]. Finally using the induction hypothesis twice, once for for T (g − π_{1}(g)) and once for T (g + m_{1} − π_{1}(g)), we see that

D_{∞}(ρϕ_{a,G}(g + ξ(k, k)), ρϕ_{a,G}(g + ξ(k, 1))) ≤ (∗∗) ≤ max(∑_{i=2}^{k} c_{i}, ∑_{i=2}^{k} c_{i}) = ∑_{i=2}^{k} c_{i} (7)

Combining (6) and (7) we get (5).

16 ELON LINDENSTRAUSS

step 2:

We only need to pass to the limit as k → ∞. But this is easy, since clearly if N is smaller than M_{k−1}√m_{k}, the sceneries ϕ_{a,G}(g + π_{k}(ξ^{i})) and ϕ_{a,G}(g + ξ^{i}) are identical in the first N coordinates in both directions from the origin. This clearly implies

D_{N}(ρϕ_{a,G}(g + ξ^{1}), ρϕ_{a,G}(g + ξ^{2})) = D_{N}(ρϕ_{a,G}(g + π_{k}(ξ^{1})), ρϕ_{a,G}(g + π_{k}(ξ^{2})))

since the distribution of the first N symbols in the film cannot depend on the scenery at places of distance greater than N from the origin. The latter expression is less than ∑_{i=1}^{∞} c_{i} by step 1. We now use Lemma 3.2 to pass to the limit.

It is, perhaps, interesting to note that for all finite k, ϕ_{a,G}(g + π_{k}(ξ^{1})) is a translate of ϕ_{a,G}(g + π_{k}(ξ^{2})). Only by passing to the limit do we obtain a counter example for the conjecture.

5. Concluding Remarks

X_{a,G} is shift invariant and uniquely ergodic, its invariant measure m being the image of the Haar measure on the compact group G(m_{1}, m_{2}, …). If the m_{i} increases fast enough, the set

{g ∈ G : ∀k √m_{k} + 1 < γ_{k}(g) < m_{k} − √m_{k}}

has positive measure, and from this using ergodicity one easily concludes that m-a.e. x ∈ X_{a,G} there are uncountable number of points of X_{a,G} that are not distinguishable by suffixes from x.

One can try to weaken the conjecture that every two points (except for the trivial case of points that can be derived one from the other by reflection and/or translation) be distinguishable, by asking whether there is an ergodic shift invariant measure on A^{ℤ} such that according to this measure a.e. two points are indistinguishable.

From the results in Benjamini and Kesten (1996) or Matzinger (1997) it follows that if one takes the Bernoulli measure on k ≥ 2 symbols then a.e. two points can be distinguished. The analogous question for the measure m is not clear. It is not hard to see that if the symbols in the sequence a are all distinct then almost every pair of elements in X_{a,G} are distinguishable. It might be true however that for some a if m_{i} → ∞ fast enough m × m-almost every two points are indistinguishable.

INDISTINGUISHABLE SCENERIES 17

The measure m we have considered is rather rigid. It is conceivable that if we take a shift invariant measure μ with “enough mixing” (e.g. K-systems) a.e. pair of points can be distinguished.

References

[1] I. Benjamini and H. Kesten, Distinguishing Sceneries by Observing the Scenery along a Random Walk Path, J. d’Anal. Math. (69), pp 97–135.

[2] Howard, C. D., Detecting defects in periodic scenery by random walks on ℤ, Random Structures and Algorithms (1996, vol 8), pp 59–74.

[3] Howard, C. D., Distinguishing certain random sceneries on ℤ via random walks, Statistics and Probability Letters (1997).

[4] Kesten, H., Detecting a single defect in a scenery by observing the scenery along a random walk path, Itô’s Stochastic Calculus and Probability Theory (editors N. Ikeda, S. Watanabe, M. Fukushima and H. Kunita), Springer-Verlag (1996), pp 171-183.

[5] H. Kesten, Distinguishing and reconstructing sceneries from observations along random walk paths, in preparation (1997).

[6] Matzinger, H. Ph.D. Thesis Cornell University, in preparation (1997).

Institute of Mathematics, The Hebrew University, Jerusalem 91904, Israel

   E-mail address: elon@math.huji.ac.il