{'fraction_non_alphanumeric': 0.043508366993652625, 'fraction_numerical': 0.006578188113098673, 'mean_word_length': 3.686857760951866, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On random walks in random scenery

This paper considers 1-dimensional generalized random walks in random scenery. That is, the steps of the walk are generated by an arbitrary stationary process, and also the scenery is a priori arbitrary stationary. Under an ergodicity condition--which is satisfied in the classical case--a simple proof of the distinguishability of periodic sceneries is given.


Introduction
Random walks in random scenery have been studied by Mike Keane for quite some time (see [2] for his most recent work). In fact, he and Frank den Hollander were pioneers in this exciting area. Around 1985 they formulated a conjecture about "recovery of the scene" by a simple random walker. A weaker form of this: "distinguishability of two scenes", was proven by Benjamini and Kesten ( [1]). Since then there has been a lot of action in this field, especially by Matzinger and co-workers. We just mention the recent paper [5].
In the following we will introduce generalized random walks in random scenery, and analyse them from a dynamical point of view. This gives us in Section 2 a general scenery recovery result on the level of measures, from which we deduce in a simple way in Section 3 a proof for the distinguishability of periodic sceneries.
We consider a random walker on the integers. The integers are coloured by colours from an alphabet C. This is the scenery. At time n the walker records the scenery at his position, this yields r n from C. To formalize somewhat more, let the random walk be described by a measure µ on the Borel sets of Ω, where Ω = {ω = (ω n ) n∈Z : ω n ∈ J for all n}.
Here the set J of the possible steps of the walk will simply be {−1, +1}, or somewhat more general {−1, 0, +1}. Although often a single scenery x = (x k ) k∈Z is considered, it is useful to consider x as an element of the shift space X = C Z with shift map T : X → X, equipped with some ergodic T -invariant measure λ, which we will call the scenery measure. We then consider x picked according to the measure λ. The colour record ϕ x of x can be written as a map ϕ x : Ω → X: where in line with the description above, one has for n ≥ 1 This definition is completed by putting r 0 (ω, x) = x 0 , and for n < 0: The dynamics of the whole process is well described by a skew product transformation T Ω×X on the product space Ω × X defined by where σ denotes the shift map on Ω.
Let us now look at the colour records of all x; we define the global recording map Φ : Ω × X → X by Φ(ω, x) = (r n (ω, x)) n∈Z .
Proof. One way: The other way: Clearly product measure µ × λ is preserved by T Ω×X . We will be particularly interested in the image of µ×λ under the global recording map Φ, which we denote ρ: We call ρ the global record measure. It follows from Lemma 1 that ρ is invariant for T . Moreover, ρ will be ergodic when T Ω×X is ergodic for µ×λ. In the classical case were µ is product measure this is guaranteed by Kakutani's random ergodic theorem. In this case, when λ and λ ′ are two scenery measures, and ρ = (µ×λ)•Φ −1 and ρ ′ = (µ×λ ′ ) • Φ −1 are the corresponding global record measures, then either ρ = ρ ′ or ρ ⊥ ρ ′ . The colour record ϕ x of a scenery x induces the record measure ρ x defined by Following [4] we call the two sceneries x and y distinguishable if ρ x ⊥ρ y . The following lemma shows that global distinguishability carries over to local distinguishability.

Reconstructing the scenery measure
Here we consider the case of a generalized random walk with steps J = {−1, 0, +1} given by an ergodic stationary measure µ on Ω = J Z . For ease of notation we rename J to {l, h, r}. To simplify the exposition we will assume that there is no holding (µ([h]) = 0), and show at the appropriate moment that this restriction can trivially be removed.
There is a basic difference between symmetric walks and asymmetric walks in the reconstruction of the scenery. We call µ symmetric if for each word w Here w denote the mirror image of w, that is, the word obtained from w by replacing r by l and l by r. Since he does not know left from right, a symmetric walker can only reconstruct a scenery x up to a reflection. This will result in two theorems, one for the asymmetric, and one for the symmetric case.
Let λ be a scenery measure. We give a few examples of calculation of the ρprobabilities of cylinder sets. Let W n be the set of all words w = w 1 . . . w n of length n over the (colour)  In the sequel we shall denote the word r . . . r, N times repeated, as r N . Note how with each appearance of a word w on the right side also the reversed word ← w appears, defined by ← w = w n . . . w 1 if w = w 1 . . . w n . Words w that satisfy w = ← w are called palindromes. Now let us put all the words w from ∪ 1≤k≤n W k in some fixed order, taking care that their lengths are non-decreasing and that for a fixed k we first take all palindromes, and then all non-palindromes in pairs (w,  Here 'almost lower triangular' means that A n has the form , and (at nonpalindrome pairs) is a 2 × 2 matrix of the form With simple linear algebra we find that A n is non-singular if and only if Let us call a generalized random walk given by µ strongly asymmetric if all these inequalities hold. For instance, if µ is a stationary Markov chain given by a 2 × 2 transition matrix (p s,s ), then µ is strongly asymmetric if and only if p r,r = p l,l . Note that when µ[h] > 0, then only some sub-diagonal elements of A n will change from 0 to a positive value. We therefore obtained the following result.
Theorem 1. For strongly asymmetric generalized random walk with holding the scenery measure λ can be reconstructed from ρ.
What remains is the symmetric walker case. Then in general λ can not be reconstructed from ρ. However, often we can reconstruct the reversal symmetrized measureλ defined for each word w by In general, if w is a word of length N + 1, then ρ[w] is obtained as a sum of products , where the length of v is at most N + 1, and length N + 1 only occurs when u = r N or u = l N . Moreover, now there is for all words w one term 2µ[r N ]λ[w] for the v = w with maximal length. So this time we obtain the existence of a (2 n+1 − 2) × (2 n+1 − 2) lower triangular matrix A n such that Let us call µ straightforward if arbitrary long words of r's have positive probability to appear. Then the diagonal elements of A n are positive for each n, and we obtain the following.
Theorem 2. For straightforward symmetric generalized random walk with holding the reversal symmetrized scenery measureλ can be reconstructed from ρ.

Distinguishing periodic sceneries
In this section we shall derive more general results with more simple proofs than in [3]. It is shown there that for asymmetric simple random walk with holding any two periodic sceneries x and y which are not translates of each other can be distinguished by their scenery records, i.e., ρ x ⊥ρ y . Our result is Theorem 3. Any strongly asymmetric generalized random walk with holding can distinguish two periodic sceneries that are not translates of each other, provided that their global record measures are ergodic.
Proof. Let us write x t ∼ y if x and y are translates of each other, i.e., for some k one has y = T k x. Let Per(x) be the period of x, i.e. p =Per(x) is the smallest natural number such that T p x = x. Let λ be the scenery measure generated by x, i.e., denoting point measure in z by δ z , The scenery measure generated by y is denoted as λ ′ . Now suppose that ρ x is not orthogonal to ρ y . Then, since λ and λ ′ are discrete, it follows from Lemma 2 that also ρ and ρ ′ are not orthogonal. But since these measures are ergodic, they must be equal. From Theorem 1 it then follows that also λ = λ ′ . This implies that x t ∼ y, by the discreteness of λ and λ ′ . Indeed, equality of these measures yields that δ T k x = δ T j y for some k and j, and hence that x t ∼ y.
For a symmetric (generalized) random walk it is impossible to distinguish a sequence x from its reflection ← x , defined by ← x k = x −k . So let us call x and y equivalent, and we denote x ∼ y, if y can be obtained from x by translation and/or reflection.
Theorem 4. Any straightforward symmetric generalized random walk with holding can distinguish two periodic sceneries that are not equivalent, provided that their global record measures are ergodic.
Proof. The proof follows the same path as the proof of Theorem 3, using Theorem 2 instead of Theorem 1. The only other difference now is that the measureλ is a mixture of point measures in T k x and in T j ← x . But then equality ofλ andλ ′ implies that y must be a translate, or the reflection of a translate of x, i.e., x ∼ y.