• Detecting Defects in Periodic Scenery by Random Walks on Z C. Douglas Howard* Department of Mathematics, Polytechnic University, Six Metrotech Center, Brooklyn, NY 7 1207 ABSTRACT Thinking of a deterministic function s : Z+ N as “scenery” on the integers, a random walk (Z,,, Z,, Z , , . . .) on Z generates a random record of scenery ‘‘observed’’ along the walk: s ( Z ) = (s(Z,) , s(Z,), . . .). Suppose t : Z + N is another scenery on the integers that is neither a translate of s nor a translate of the reflection of s. It has been conjectured that, under these circumstances, with a simple symmetric walk Z the distributions of s ( Z ) and t ( Z ) are orthogonal. The conjecture is generally known to hold for periodic s and t . In this paper we show that the conjecture continues to hold for periodic sceneries that have been altered at finitely many locations with any symmetric walk whose steps are restricted to {-1, 0, +l}. If both sceneries are purely periodic and the walk is asymmetric (with steps restricted to { -1, 0, +l}), we get a somewhat stronger result. 0 1996 John Wiley & Sons, Inc. 1. INTRODUCTION If we think of a deterministic function s : Z- N as describing “scenery” on the integers, a random walk Z = ( Z o , Z , , Z , , . . .) on Z induces a random record of scenery “observed” along the walk: s ( Z ) = (s(Z,) , s (Z , ) , . . .). A conjecture of Benjamini and, independently, of den Hollander and Keane (BHK) concerns the following question: If t : Z- N is another scenery on the integers and we are handed a random scenery record induced by either s or t in this fashion, under what circumstances can the source be correctly identified (with probability l)? * Based on research supported by a New York University Dean’s Dissertation Fellowship. Random Structures and Algorithms, Vol. 8, No. 1 (1996) 0 1996 John Wiley & Sons, Inc. CCC 1042-9832/96/010059-16 59
  • 60 HOWARD Stated formally, the issue is to identify conditions on s and f ensuring that the distributions of s ( Z ) and t ( Z ) are orthogonal. If this obtains, we say that s and t are distinguishable. Let s - t denote the equivalence relation that s is either a translate of t or a translate of the reflection of t , i.e., s(n)=t(an + b ) , where a = 2 1 and b E Z . BHK have conjectured that, for simple symmetric walks, s / t is sufficient to ensure that they are distinguishable. In [3] it is shown that the BHK conjecture is true if some item of scenery appears in only finitely many locations in at least one of the sceneries, e.g.. s- ’ (6 ) is finite (nonempty) for some 6 E N . The conjecture is also generally known to be true if s and t are periodic [BHK, unpublished]. In [l] it is shown that if s is any 0-1 valued scenery and { t (n) : n E Z} are iid with P { t ( n ) = 0} = P{r(n) = l } = .5. then, almost surely with respect to the choice of t , s and t will be distinguishable. Note that under these circumstances it is true, almost surely, that s / r . The nature of the - equivalence plays no role in [l]. In this paper, we prove two generalizations of the periodic case. In particular, BHK continues to hold (1) for periodic sceneries with any (nonconstant) random walk whose steps are restricted to { -1, 0, +1} (if the walk is asymmetric we get a stronger result) and (2) for periodic sceneries that have been altered at finitely many locations (we think of such locations as “defects”) with any (nonconstant) symmetric walk whose steps are restricted to { - 1, 0, + l } . In the remainder of this paper, all random walks 2 satisfy: Z,, = 0; and 2, - Z k - , E { -1, 0, l}. Example 1 . 1 . Let s(n) = 1 if 41n, 0 otherwise; and t(n) = 1 if 3(n , 0 otherwise. Suppose the walk is simple symmetric. In a scenery record coming from s, there will always be an odd number of 0’s between occurrences of 1’s. On the other hand, a scenery record coming from t will have regular (but randomly located) occurrences of the sequence (1, 0, 0, 1) embedded within it. Example 1.2. Let the walk and s be as in Example 1.1; and set t(n) =s(n) if n # 2, and 42) = 1. This case is much more subtle: A scenery record coming from either source will always have an odd number of 0’s between 1’s. However, since a simple symmetric walk on Z is recurrent, the random walk returns infinitely often to n = 2-the only location where s and t differ. In fact, this happens often enough to be detected. 2. PRELIMINARY IDEAS The basic technique is similar to that used in (31. Set gI = { (do , . . . , d,) : di E N}, GI = Urns, 9Im, and 9 = U, $3,. Any d E 9 may be thought of as a finite sequence of observable scenery. We denote the length of d by ldl, i.e., d E gIdl. For d ’ , d 2 E 9, we say that d’ = d’ if Id’[ = Id2[ and all of their respective components agree. Put r = NN, so r is the space of all possible scenery records. By equipping r with the standard a-field 92 generated by the finite dimensional cylinder sets, (r, 3 ) becomes a measurable space. Any sequence d € 9 may, or may not, appear in a particular scenery record y E r. The idea is to define some notion of the frequency f (d , y ) with which the finite sequence d appears in y. The precise definition of f ( d , y ) will depend on the application, but we wish it to have two
  • DETECTING DEFECTS BY RANDOM WALKS 61 properties. First, for any choice of d and x = s or t, we wish Ad, x , Z ) = f ( d , x ( Z ) ) to be constant almost surely with respect ,to the random walk Z. With some abuse of notation, we denote this constant by f(d, x ) . Second, we want f ( d * , s) #f(d*, t), for some d* E 9. Iff meets both these conditions and we are handed a scenery record y = s(2) or t ( Z ) , we may determine the source of y simply by calculating f ( d * , y ). Establishing the first condition for f requires a probabilistic argument while establishing the second condition for s& t requires a combinatoric argu- ment. Establishing both conditions shows that the distributions of (s (Z , ) , s(Z,),. . .) and ( t (Zo) , t(Z,), . . .) are supported by the disjoint sets {y E r : f ( d * , y) = f ( d * , s)}, and {y E r : f(d*, y) = A d * , t)}, respectively, formally showing that s and c are distinguishable. For 1 2 0, let W, denote all walks starting at the origin and taking 1 steps: W, = { (w,,, . . . , w,) : wo = 0; Iwi+, - wil = 0 or 1 for O I i < r } . For w E W,, let R(w) denote the number of steps to the “right” in w, L(w) the number of steps to the “left”, and P(w) the number of “pauses”; so R(w) + L(w) + P(w) = 1. If p( p , w) = p4‘;Y)p;‘w’pf‘w’ is the probability that any 1 steps of the random walk follow the pattern in w. For a E Z, d = (do, . . . , d,) E 9,, and scenery x , define W(d, x , a) = { w E W, : (x (a + W”), . . . , x ( a + w,)) = d } , and T ( P , 4 x ; a) = 2 P ( P ? w). W € W ( d . X , Q ) Then ~ ( p , d , x ; a ) is the probability of observing (do, . . . , d,) in a scenery record induced by scenery x beginning at a specific point in the record where the random walk is at a. We will need to distinguish the “straight” walks w: = (0, 1, . . . , I) and w,- = (0, -1, . . . , - 1 ) from the “crooked” walks in W,, where, for W C W,, the crooked walks in W are W = W - {w,‘} - {wy}. Set (2.3) p- l if (x (a - 0), . . . , x ( a - I ) ) = d , otherwise, and put
  • 62 HOWARD 4(p, d , x ; a) = q ( p , d , x ; a) - f d p , d , x ; a) (2.5) = c P ( P 9 W ) wE@(d.x .o ) with the final equality holding with Id1 z- 1. Note that, by this convention, when d E Bo we have q + ( p , d , x; a) = T - ( P , d , x ; a) = q ( p , d , x ; a ) . Finally, for any finite set A C Z, define (where # denotes cardinality) with analogous definitions of q + ( p , d , x; A ) , q - ( p , d , x ; A ) , ? ( p , d , x; A ) , and 6 ( p , d , x ; A ) . 3. THE PERIODIC CASE WITH SYMMETRIC WALK In this section we consider periodic scenery with an underlying random walk with transition probabilities of the form (2.1) with O < p - , = p , . (3.1) Let Zper denote the collection of all periodic sceneries on Z. Presently we prove; Theorem 3.1. transition probabilities p of the form (3.1), then s and t are dktinguishable. Let s, tEZ.,,, with s&t. If the underlying random walk has Proof. (yo, y , , . . .) be any scenery record and suppose d E 9/. Then define In this case, the appropriate choice of f is the natural one. Let y = and put n - 1 assuming, of course, that this limit exists. [If the limit does not exist, set f p e r (d , y ) =0.] G,(d, y ) detects the occurrence of the sequence ( d o , . . . , d,) embedded in y starting at the kth location and fp,,(d, y ) is precisely the limiting density of these occurrences. Analogously, set and put
  • DETECTING DEFECTS BY RANDOM WALKS 63 (assuming the limit exists) so fper(d, x(Z)) =Aer(d, x , Z). Let x E-Xper have period c and put 2, = 2, (mod c) and I, = (0, 1, . . . , c - l } . Then x(Z,) =x(Z,); also, 2 = (&, 2,, . . .) is a finite-state irreducible Markov process with invariant measure equal to the uniform distribution on I, (since the transition matrix is doubly stochastic). Under these circumstances, the ergodic theorem (see 6, p. 511) ensures that the limit in (3.5) exists and, almost surely, Aer(d, x , 2) = v ( p , d , x ; Z,). Benjamini and Kesten [l] observe that [5] contains a result that also yields the existence of these limits. It remains, then, to establish the second condition for our choice off = fper. The following lemma ensures the existence of the requisite d*. Lemma 3.2. q(p , d , s; I , )=q(p , d, t; I,) for all d €9, then S - t . Let s, t E Zper with common period c. If p is of the form (3.1) and Proof. Using only information in def A = (qd = q(p , 4 s ; 1,) =V(P, 4 t; 1,) : d E 9) we shall construct h E Zper with s - h and, by symmetry, t - h. Since - is an equivalence relation, s - t. As observed earlier, for each d E 9, qd has contributions arising from crooked walks and contributions arising from straight walks. As in (2 .5) , denote this split by qd = 7 j d + i j d . Suppose we know this split (i.e., we know 7 j d and 77,) for all d E 9. For any d E 9,-,, i j , > 0 if and only if the sequence d is observed along some c consecutive sites on s (either from left to right or from right to left). Choose one such d and define h E Zper by h(m) = d,,,, where [m] = m (mod c). Since c is a period of s, h satisfies s - h. We note that different choices of d € 9,-, with ijd > 0 will, in general, yield different h's-but they must all be in s's - equivalence class. We proceed by induction to prove that this split may be calculated for d E 9, for all n. Suppose we know ;id for all sequences d with [dl < n. Crooked walks in W, touch at most n - 1 contiguous integers. Therefore, based on the afore- mentioned knowledge, we should be able to calculate the frequency
  • 64 HOWARD reach is the d: component of d‘ and whose rightmost reach is d ” s last component. The index a in (3.6) represents the location within d‘ of the start of these walks. For example, if d‘ = (3 , 5 , 3, 0 ) E g3 and d = (3, 3, 5 , 3, 5 , 3, 0) E g 6 , then -2, -1, 0, l)}, and W:,d, = 0. If p = (.25, .5, .25), then P(d, d’) = 3(.5)(.25)5. The 6 analogue of (2.6) partitions the crooked walks contributing to ?jd according to their starting location a € I , . If, instead, we partition according to the walk’s leftmost reach (mod c) [indexed in (3.7) by a ] and the length of the interval supporting the walk (indexed by m), and exploit the periodicity of s, we see that w: ,da = ((0, 0, 1, 2, 1, 2, 3), (0, 0, 1, 0, 1, 27 3)}7 w:,d* = 0, w i , d ’ = ((O, O, -l? (3.7) 1 = - I n - l C u = o m=O i d =- P(d, d’ (s, m)) 7 where d’(s, a, m ) = (s(a), (s(a + l), . . . , s(a + m)) E gnI. If, for d ’ , d 2 E 9, we put A(d’, d 2 ) = 1 if d ’ = d’; 0 otherwise, then (3.7) yields For any d E gin, let - d E 9,1 denote the same sequence written backwards, i.e. ( - d ) k = d n - k for 0 5 k ~ n . When the walk is symmetric, q:. =qIdt and P(d , d ’ ) = ~ ( d , -d ’ ) . AISO, -d’ ranges over all of G,l-l as d‘ ranges over all of gin-,. From these observations and (3.8), we have also that and, by adding (3.8) and (3.9), Thus we can deduce i jd = qd - 6, for d E 9,! using only information in A. rn Example 3.3. With s and t as in Example 1 . 1 , we have common period c = 12 and may take 1, = (0, 1,. . . , 11). Taking d = (1, 0, 0, 1) E g3 and p = (.5, 0, . 5 ) gives q( p , d , s ; I , ) = 0 and q ( p , d , t ; I , ) = f X 2 X 2-3. Remark 3.4. to calculate f d for d E g,!. We observe for future reference that we only need vd for all d E 5?Jn
  • DETECTING DEFECTS BY RANDOM WALKS 65 4. THE PERIODIC CASE WITH ASYMMETRIC WALK In this case the random walk’s transition probabilities are of the form (2.1) with p - l Z p , . (4.1) The probabilistic component of the argument is unchanged: We take f = f,,, as in (3.3), and, for precisely the same reasons, the ergodic theorem yields that, almost surely, fper(d , x , Z) = q ( p , d , x ; Z,). The combinatoric argument must be handled somewhat differently to account for orientation. We have: Lemma 4.1. Let s, t E ZPer with common period c. If p is of the form (4.1) and ~ ( p , d , s ; I,) = q ( p , d , t ; I,) for all d € 9, then s - t ; in fact, s is a translate oft . Proof. As in Lemma 3.2, using only information in we shall construct h E Zper with s a translate of h. By symmetry again, we have that t is also a translate of h and hence s is a translate of t. Suppose, w.l.o.g., that O s p - , < p l . This time our breakdown of qd must take orientation into account. Suppose we know that (2.4, 2.5) breakdown qd = 6, + 77; + 77; (i.e., we know ijd, qd, and 7:) for all d E 9. Then choose any d E 9c-l with 77: > O and put h ( m ) = d[,,,!. Since > O if and only if the sequence d appears in s along c consecutive sites proceeding from left to right, we have that s is a translate of h. Again we proceed by induction to prove that this breakdown may be calculated for d E9,, for all n. If n = 0, then qd+ = q d =qd. Suppose we know this breakdown for all d ’ E G n - l , where n 2 l . Using (3.8) (this formula did not depend on the walk’s symmetry) we may calculate i jd for all d E 9,,. This gives us f d =qd - i j d for all d €9~~. If p - l = O then qd+ = ijd and qd = O . Suppose, then, that O
  • 66 HOWARD 5. DEFECTIVE PERIODIC SCENERY In this section we consider the case of periodic scenery that has been altered at finitely many locations. Throughout this section the underlying random walk is assumed to have transition probabilities of the form (3.1). The combinatoric Lemma 5.3 will ensure that portions of the scenery record coming from the defective region are in some sense drawn from a different distribution than those coming from the unaltered portion of the scenery. The idea is that after k steps the walk is in the defective region with probability of order k-”*. This is sufficient to detect its existence. The following simple model illustrates the idea and motivates the proof of our main result. Let X , and Yk be mutually independent 0-1 valued random variables with P{Xk = 1) = k-”’ and P{Y, = l } = A . Set Tk = max(X,, Y , ) so that Tk is usually drawn from an iid sequence of 0 s and 1’s (Y,) with an occasional “bogus” 1 thrown in (Xk). Now suppose we wish to determine if a given sequence of 0’s and 1’s is generated by the T process or the Y process. Consider the following averaging scheme for any random sequence V = (V , , V,, . . .): Let (n) = ( n ; ) = ( n , , n,, . . .) be a fixed sequence of increasing positive integers and define 1 A:’[V] = - N,,,[V] . m If we apply this to V, = Y, - A , then Nni[V] converges in distribution to a normal with mean 0 and variance A( 1 - A) as ni+ 30. The sequence ( n i ) may be chosen to make the N,, asymptotically independent in a sense that ensures that lim A i ’ [ Y - A ] = O m-x a s . (5.3) On the other hand, if we apply this scheme to vk = Tk - A , then, since max(X,, Y k ) = X, + Y, - X,Y, , we have 1 ”; EN,, [ V ] =- ( k - ” 2 + A - Ak-”2 - A) ‘ f i ’ k = l +2(1-A) a s n i + = , and, since the variance of N, [V] is bounded, it is not hard to see that for some sequence (n,) we have lim AL’[T - A ] = 2(1 - A) a s . m+x (5.4) Furthermore, by passing to a subsequence if necessary, (n , ) may be chosen so that (5.3) and (5.4) simultaneously hold, thus proving orthogonality of the dis- tributions of T and Y assuming, of course, that A < 1. This general idea works in our setting as well. Let Zdef denote all sceneries s
  • DETECTING DEFECTS BY RANDOM WALKS 67 with s(n) = s ' (n) except at finitely many locations n for some s' E Xper. Note that, for each s, s ' is unique-we shall reserve the prime notation to denote this mapping from Zdef to Zper.. Note also that Xper C Zdef. If c is any period of s ' and Z is a set of c consecutive integers such that s = s ' off I , then, we refer to I as a defective interval of s. (This definition is somewhat of a misnomer--e.g., if s is purely periodic, then every interval whose length is a period is a defective interval .) Note that if s, t E Xdef and s ' f t ' , then the symmetric periodic calculation (3.3) will work to distinguish s and t. This works since the random walk spends asymptotically none of its time in a defective interval so fper(d , x , 2) =&,,(d, X I , Z ) for x E Zdef. Note also that if s ' - t' and I is any interval whose length is a period of either (hence of both), then ~ ( p , d , s'; I ) = q ( p , d , t ' ; I ) and is independent of I for all observable scenery patterns d . In this case the choice f = f,,, defined in (3.3) and (3.5) will not work. The remainder of this section shows that the more refined notion defined in (5.6) does work. Our main result is the following: Theorem 5.1. transition probabilities p of the form (3.1), then s and t are dktinguishable. Let s, t EX,,, with s f t . If the underlying random walk has This result is an immediate consequence of the previous remark (concerning the case s ' / t ' ) , and Lemmas 5.2 and 5.3 as stated below. Lemma 5.3 is the combinatoric lemma analogous to Lemmas 3.2 and 4.1. We remark that the condition p - , = p , is, in general, essential. If the walk were transient, the defective interval would be visited only finitely often (possibly never) and insufficient information may be garnered to distinguish s from t. Lemma 5.2. Let s, t EX:,,, with s ' - t ' and with defective intervals I, and I,, respectively, of length c. Let d* = (d:, . . . , d;"..) be some finite sequence of observable scenery. Suppose that W ( d * , s, a ) = W ( d * , s', a ) and W ( d * , t , b ) = W ( d * , t', b ) for all a$Z, and b jZI , , b u t q ( p , d * , s; I,) # q ( p , d * , t ; Z,). Then s and t are distinguishable. Lemma 5.3. Let s, t EX,,, with s ' - t ' but s / t . Then there exists defective intervals Z, and I,, respectively, of common length c and some finite sequence of observable scenery d* = (d; , . . . , d;".) such that ( i ) W ( d * , s, a ) = W ( d * , s', a ) and W ( d * , I , b ) = W ( d * , t', b ) for all a$Z, and b g I , and (ii) ~ ( p , d * , s; I,) # q ( p , d * , t ; I,). Remark 5.4. We note that, since p - , = p , , the conclusion of Lemma 5.3 holds for the pair s, t E Zdef if and only if it holds for the pair s, -t [where ( - t ) (n) = t(-n)l . Proof of Lemma 5.2. Fix any d E 9,. x E Xdef. Let x = s or t and put I = I s or I, as appropriate. Set q(x) = ~ ( p , d , x ; I ) and ~ ( x ' ) = q ( p , d , x ' ; Z). Most of the time the walk is off I, and d occurs in an induced scenery record y with likelihood q ( x ' ) . Occasionally, however, the walk is in I and the likelihood of spotting d in the scenery record y changes to q(x) . To define f ( d , y) in this case, we apply the
  • 68 HOWARD averaging scheme of (5.1) and (5.2) to the sequence V, = G,(d, y ) - v ( x ' ) , where G, is defined as in (3.2). We claim that, for some sequence ( n , ) , 2 A:: '[6(d.x, Z ) - T & X ~ ) ] % ~ ( ~ ( x ) - ~ ( x ' ) ) as m+ M (5.5) ( 1 - P " b where 5 denotes convergence in probability and 6, is defined as in (3.4). (We recall that c is the common length of 1, and l , .) For some sequence (m,), therefore, the limit in (5.5) occurs almost surely with respect to the walk. Assuming (5.5). set f d , @ Y 1 =ti? A!:,)[G(d. 7 ) - v(x')l so that f;,,(d, x, Z ) =lim A ! : : ' [ E ( ~ . x , Z ) - v ( x ' ) l ,-= I = c fT ( 1 - P O h (v(x) - v(x')) a.s. ( 5 . 6 ) The lemma follows from (5.6) since, with d = d*, we have ~ ( s ' ) =v(f') and v(s) +v(t) , yielding that L e l ( d * . s, Z ) Z&el(d*, t,Z). To see (5 .5 ) . we decompose 6A into indicator functions that are easier to analyze. Let u = {(a, w) E I x "u., : (x(a + w,,), . . * , x(a + W / ) ) = d } , U' = {(a, w) E I x w; : (x'(a + W " ) , . . . , x' (a + W / ) ) = d } , and, for (a, w) E I x W;, let if (Z,, . . . , Zk+,) = (a + w", . . . , a + w,) , otherwise. Y:" " ' ( Z ) = {; Then we have 6 , ( d . x, Z ) = Ek(d' xf, Z ) - c Y:" " ' ( Z ) + 2 YIp "'(Z) . (5.7) ( < I W)EU ( a M ) E U Using 1 1 C ( a ~ ) E U - c P(P7 w) =v(x) and - c P ( P , w) =v(x') C ( a w)EU and the linearity of the averaging scheme, it suffices to show that P A!,"'[E(d, X I , Z ) - 77(~')]+0 and as m - x . To see ( 5 . 8 ) , note that x ' is periodic and, with 2 as in Theorem 3.1, 2 is a finite state Markov chain. By an application of the appropriate central limit
  • DETECTING DEFECTS BY RANDOM WALKS 69 theorem (see, e.g., [2, pp. 375-3581) we have that N, ’!Zf N,[G(d, x’ , Z ) - ~ ( x ’ ) ] converges in distribution to a mean 0, finite variance normal distribution as n - , ~ . It is also easy to establish that cov(Nno, N n , ) + O for any fixed no as n + m. This covariance condition, together with the fact that var(N,) is bounded, yields (5.8) and follows for an appropriate (n,) (see [2, p. 291). To establish (5.9), we use [7, Theorem 2.81 to get, when po = 0, that P { Z , = a } = { k-’12 + O(k-’ / ’ ) when k = a 0 otherwise. (mod 2) , If pO > 0, let B, denote the number of true steps (nonpause steps) that the walk has taken by time k . Then B, is binomially distributed with parameters k and 1 -pO and k P { Z , = a } = x P { Z k = a l B , = j } P { B , = j ) j = O j - a even Note that EB, = (1 - p( , )k . With gk = (B, - (1 - p O ) k ) / v w , we note also that E exp(g,) and E exp(-E,) converge to fi as k + = . Using (5.10) and Chebyshev’s inequality applied to exp(lI?,’,l) to control the tails of B,, it is not hard to see that, when po > 0, Combining the cases po > 0 and p( , = 0, we have k - u even (5.11) yields that (5.12) where N , now denotes N,[Y‘”.”’]. A similar analysis, based on a conditional version of (5.11), establishes that var(N,) is bounded in n and cov(N,,,, N , , , ) + O for fixed no as n , + 00. These variance/covariance conditions together with (5.12)
  • 70 HOWARD suffice to establish (5.9) for some sequence ( n i ) . Clearly, by passing to sub- sequences if necessary, we may establish (5.8) or (5.9), as appropriate, simul- taneously for each summand in (5.7) for some sequence (n;). Proofof Lemma 5.3. By Remark 5.4, we may assume without loss of generality that s’ is a translate of t ’ . Set P = (s‘( l ) , . . . , s’(cmln)), where cmln is the minimal period of s‘ . If D denotes any finite sequence of n natural numbers, we write = n. (Note that this is smaller by one than the 1 . 1 notion defined in Section 2.) If we think of sceneries on Z as two-sided infinite sequences, then we may concatenate finite sequences to form such sceneries, e.g., (. . . PPPDPPP. . .). (To to be precise, we must also know where along Z the sequence D is found.) In this manner, we may represent and where these representations are unique if we assume that the defective sequences D , and D, are minimal, i.e., they neither begin nor end with the sequence P. We observe that 11D,11 and 11D,11 are (possibly different) multiples of c,,, . We assume without loss of generality that llD,ll 5 l(D,II and note that D, may be the empty sequence, i.e., t may be periodic. We say that a sequence of observable scenery S = (S,,, . . . ,a,) E 9/ occurs on a straight walk in the scenery x on Z if for w = w,’ or w; and some a E Z we have s = (. . . PPPD,PPP. . .) t = (. . . P P P D , P P P . . .) , s = (x(a + w o ) . . . . , x (a + W / ) ) . We claim that for some 8 E gi 6 occurs on a straight walk in s but not in t . (5.13) This fact may seem an obvious consequence of s J t , but some care must be taken in constructing &-we leave this detail for later. Assume, then, that 8 has the property (5.13). Choose m such that IlP”’II = mc,,, > 1 , where P” denotes m copies of P strung together. Also, fix k 2 0 such that (ID,(I = IID,P’II. Define - fir = P”’D,P”‘ and fir = P“‘D,Ph’“ so that 11fi;,11 = 116,11 and s = (. . . P P P f i ; , P P P . . .) and Let Z, and Z, denote the intervals in Z that respectively support the scenery sequences 6, and 6,. Then, by construction, 1, and I, have a common length c which is some period of s’ (and t’) and represent defective intervals for s and t respectively. We note also that each end of Z, and I, is “padded” with sufficiently many copies of P so that conclusion (i) in the Lemma holds provided we choose d* so that I * 5 r. To see that conclusion (ii) holds for this choice of Z, and Z, and some choice of d’ E Gi = U,sT 9/, define the following periodic sceneries: t = (. . . P P P 6 , P P P . . .) . - - - s* = (. . . 6@,fiS.. .) and t* = (. . . D,D,D, . . .) ,
  • DETECTING DEFECTS BY RANDOM WALKS 71 where, simply to be specific, we may assume that one of the sequences of f i s coincides with 1, and one of the sequences of fi, coincides with Z,. We note that, again because of the padding, we have 7 7 ( p I d , s ; ~ , ) = 7 7 ( p , d , s * ; ~ , ) , ~ ( p , d , t ; I , ) = d p , d , t * ; I , ) f o r a l I d E G j . (5.14) If 7 7 ( P , d , s ; I , ) = r ) ( p , d , t ; I , ) f o r a l I d E g j (5.15) it would follow from (5.14) and the proof of Lemma 3.2 (see Remark 3.4) that (5.16) If (5.16) were true, afortiori, any d E gi that occurs on a straight walk in s* must also occur on a straight walk in t*. We note also that, because of the padding, for any d E Gi, d occurs on a straight walk in s if and only if d occurs on a straight walk in s*, with an analogous statement true for t and t*. Therefore, if (5.16) were true, we would have that any d E !2& that occurs on a straight walk in s must also occur on a straight walk in t. This contradicts the existence of d as defined above. Hence (5.16) and therefore (5.15) must be false, establishing conclusion (ii). This brings us back to the detail of establishing 6's existence. Clearly we may assume that s is not periodic. One is tempted to assert that the sequence D, cannot occur as straight walk in t . To see that this is, in general, false, take P = (1, 2), D, = (2, l ) , and let D, be the empty sequence so that f is periodic. To remedy this problem, choose r so that llP'll> 11D,11. If t' happens to be a translate of - ( t ' ) = ( - ? ) I , then we may, as above, represent + ( p , d , s*; I,) = + ( p , d, t* ; 1,) for all d E Gi . - t = (. . . PPPD-,PPP . . .) , where D-, is minimal. In this event increase r , if necessary, so that we also have llP'll > l(D-,ll. [Note that ((D,ll is not necessarily equal to 11D-,!; e.g., take P = (0, 0 , l), D, = (0 , 2, 2), then D-, = (0, 0, 2, 2, 0, l).] Now set 6 equal to the sequence of scenery obtained by traversing P'D,P' from left to right. If d appears occurs on a straight walk from left to right in t , then along this straight walk the initial P' portion of 8 must terminate exactly where D, begins. This is due to the minimality of P, D,, D, and the fact that at least cmin consecutive elements of the sequence P' must occur outside of D,. Similarly, the final P' portion of d must begin exactly where D, ends. But this means that D, = D,, contradicting s / t . If 8 occurs on a straight walk from right to left in t , then t' must be a translate of - t ' . This holds since at least one of the blocks of P in the 6 sequence is found occurring from right to left in t fully outside of D,. But then, by reasoning identical to the "left to right" case, we must have D, = D-,, again contradicting s / t . I We give two examples. In each case, s t = t', 1, =I,, and the random walk has transition probabilities p = ( S , 0, S) . Example 5.5. Let s and t be defined as in Examples 1.2. Take Z, =I, = (0 , 1, 2,
  • 72 HOWARD 3) and d * = (1) E 9(). In this case we have q ( s ’ ) = q(t’) = .25, ~ ( s ) = .25, and q(t) = . 5 , and the averaging scheme will detect the single extra 1 in the t scenery. Example 5.6. s(n) = 1 if n E L,, s(n) = 0 otherwise with t similarly defined: Let L = { 2 n : n E Z } , L , = L U { l , 5 } , and L , = L U { l , 7). Set n ... -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 s‘(n) = t ‘ (n) . . . 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . a . s(n) . . . 0 1 0 1 1 1 0 l l 1 0 1 0 1 0 1 - e - t(n> . . . 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 l . . ’ With a simple symmetric walk, if we take I, = I, = [ - 1, 81 and d* = (1, 1, 0, 1, 1) E g4, then q(s’) = q(t‘) = 0, q(s) = 2 - 4 X 6/10, and q(t) = 2 - 4 X 4/10. (This, in fact, is the shortest sequence that works.) We conclude this section with a corollary to the proof of Lemma 5.2. Corollary 5.7. Let s, t E Z, d E 9,. and suppose p has the form (3.1 ). I f c q( p , d , s; a) < c T ( P , d , t ; a ) , U E Z O E Z then s and t are distinguishable. Proof. Note that part of the hypothesis is that COEZ q ( p , d , s; a) < x . Hence, for some I = {-m,. . . , m}, q(p, d , s; a) = O for a$I while q ( p , d , s; I ) < q ( p , d , t ; I ) . Set r= { -m - I , . . . , m + I}. Letting 6 E N be outside of the ranges of s and t (without loss of generality we may assume such a 6 exists), define {(n) i f n E J , S(n) = otherwise, and r similarly. Notice, then, that S’(n) = ?(n) = 6 and that f is a defective interval for S and r. To apply Lemma 5.2 to S and f, we note that def q’ = q(p. d , S ’ ; I ) = q ( p , d , f’; r ) = 0 , q(S) E f q ( p , d , S; I ) = q(p , d , s ; I ) X # I / # [ , q(F )%‘q (p ,d , t ; I ) ~ q ( p , d , t ; I ) x # ] / # I so that q ( S ) < q ( t ) . In the proof of Lemma 5.2, sequences ( n , ) and (m,) are constructed such that drf . u = Iim A;,”[G(~, S, z ) ]
  • DETECTING DEFECTS BY R A N D O M WALKS 73 6. STRICT DISTINGUISHABILITY Thus far, our notion of distinguishability has been pairwise. In this final section we introduce a notion that is stronger in the sense that it implies (pairwise) distinguishability. It will follow easily that the scenery class Cdef satisfies this stronger notion. Recalling that (r, 9) is the measurable space of observable scenery records, corresponding to any scenery s : Z+ N, define the probability measure P, on (r, 9 ) by P,A = P{s(Z) E A}. Then, according to our definition, sceneries s and t are distinguishable if and only if for some A E '3 we have P,A = P,A' = 1. The set A may depend on both s and t , as it clearly does in the proof of Theorem 5.1. We say that a collection of sceneries C that is closed under the - equivalence is strictly distinguishable if associated with each s E C there is an E, E 9 such that (i) P,E, = 1 and (ii) for any t E C with t f s we have E, fl E, = 0. The key idea is that the set E,s supporting the P, measure can be constructed without reference to another scenery. This notion of strict distinguishability is equivalent to the existence of a "decoder" function g : rg+m-, whose domain is a (not necessarily measurable) subset of r and whose range is the set of - equivalence classes in C that satisfies for all s E C: (i) g - ' ( [ s ] ) E 3 and (ii) P,g-'([s]) = 1. Here we use [s] to denote the - equivalence class of s. To see this, note that if such a g exists, then we may take E, =g-l([s]). On the other hand, if I: is strictly distinguishable, take rg = UsEX E, and put g ( y ) = [s] for The strict distinguishability of Zdef when the walk is symmetric follows from: y E u;-, E;. Theorem 6.1. distinguishable, then it is strictly distinguishable. If a countable collection of sceneries 2 is closed under - and Proof. Now put For each pair s, t E C with s / t construct A,, E 9 with P,A,, = P,AJ:, = 1. E,= n A,!- u A , , . l € Z : r p l € Z : I j S It is straightforward to verify that the sets E, satisfy the conditions of strict distinguishability specified above. H Loosely speaking, this says that if we know that the scenery is in Cdef, then its - equivalence class can be deduced via the decoder function from a single observed scenery record. See [4] for more results on strict distinguishability. ACKNOWLEDGMENTS The author wishes to thank Chuck Newman, Itai Benjamini, and a very thorough referee for helpful discussion and comments.
  • 74 HOWARD REFERENCES [ l ] I. Benjamini and H, Kesten, Distinguishing sceneries by observing the scenery along a [2] R. Durrett, Probability: Theory and Examples, Brooks/Cole, Belmont, CA, 1991. [3] C. D. Howard, Orthogonality of measures induced by random walks with scenery, Combinat. Probab. Comput., to appear. [4] C. D. Howard, The orthogonality of measures induced by random walks with scenery, Ph.D. dissertation. Courant Institute of Mathematical Sciences, New York, 1995. [5] J.-P. Kahane, J. Peyriere, Z.-Y. Wen, and L.-M. Wu, Moyennes uniforrnes et moyennes suivant une marche alCatoire, Probab. Theory Related Fields, 79, 625-628 (1988). random walk path, preprint, 1995. [6] K. Petersen. Ergodic Theory, Cambridge University Press. Cambridge, 1983. [7] P. RivCsz, Random Walk in Random and Non-Random Environments, World Sci- entific, Singapore. 1990. Received March 23. 1995 Accepted June 2. 1995
Please download to view
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
...

Detecting defects in periodic scenery by random walks on Z

by c-douglas-howard

on

Report

Category:

Documents

Download: 0

Comment: 0

212

views

Comments

Description

Download Detecting defects in periodic scenery by random walks on Z

Transcript

  • Detecting Defects in Periodic Scenery by Random Walks on Z C. Douglas Howard* Department of Mathematics, Polytechnic University, Six Metrotech Center, Brooklyn, NY 7 1207 ABSTRACT Thinking of a deterministic function s : Z+ N as “scenery” on the integers, a random walk (Z,,, Z,, Z , , . . .) on Z generates a random record of scenery ‘‘observed’’ along the walk: s ( Z ) = (s(Z,) , s(Z,), . . .). Suppose t : Z + N is another scenery on the integers that is neither a translate of s nor a translate of the reflection of s. It has been conjectured that, under these circumstances, with a simple symmetric walk Z the distributions of s ( Z ) and t ( Z ) are orthogonal. The conjecture is generally known to hold for periodic s and t . In this paper we show that the conjecture continues to hold for periodic sceneries that have been altered at finitely many locations with any symmetric walk whose steps are restricted to {-1, 0, +l}. If both sceneries are purely periodic and the walk is asymmetric (with steps restricted to { -1, 0, +l}), we get a somewhat stronger result. 0 1996 John Wiley & Sons, Inc. 1. INTRODUCTION If we think of a deterministic function s : Z- N as describing “scenery” on the integers, a random walk Z = ( Z o , Z , , Z , , . . .) on Z induces a random record of scenery “observed” along the walk: s ( Z ) = (s(Z,) , s (Z , ) , . . .). A conjecture of Benjamini and, independently, of den Hollander and Keane (BHK) concerns the following question: If t : Z- N is another scenery on the integers and we are handed a random scenery record induced by either s or t in this fashion, under what circumstances can the source be correctly identified (with probability l)? * Based on research supported by a New York University Dean’s Dissertation Fellowship. Random Structures and Algorithms, Vol. 8, No. 1 (1996) 0 1996 John Wiley & Sons, Inc. CCC 1042-9832/96/010059-16 59
  • 60 HOWARD Stated formally, the issue is to identify conditions on s and f ensuring that the distributions of s ( Z ) and t ( Z ) are orthogonal. If this obtains, we say that s and t are distinguishable. Let s - t denote the equivalence relation that s is either a translate of t or a translate of the reflection of t , i.e., s(n)=t(an + b ) , where a = 2 1 and b E Z . BHK have conjectured that, for simple symmetric walks, s / t is sufficient to ensure that they are distinguishable. In [3] it is shown that the BHK conjecture is true if some item of scenery appears in only finitely many locations in at least one of the sceneries, e.g.. s- ’ (6 ) is finite (nonempty) for some 6 E N . The conjecture is also generally known to be true if s and t are periodic [BHK, unpublished]. In [l] it is shown that if s is any 0-1 valued scenery and { t (n) : n E Z} are iid with P { t ( n ) = 0} = P{r(n) = l } = .5. then, almost surely with respect to the choice of t , s and t will be distinguishable. Note that under these circumstances it is true, almost surely, that s / r . The nature of the - equivalence plays no role in [l]. In this paper, we prove two generalizations of the periodic case. In particular, BHK continues to hold (1) for periodic sceneries with any (nonconstant) random walk whose steps are restricted to { -1, 0, +1} (if the walk is asymmetric we get a stronger result) and (2) for periodic sceneries that have been altered at finitely many locations (we think of such locations as “defects”) with any (nonconstant) symmetric walk whose steps are restricted to { - 1, 0, + l } . In the remainder of this paper, all random walks 2 satisfy: Z,, = 0; and 2, - Z k - , E { -1, 0, l}. Example 1 . 1 . Let s(n) = 1 if 41n, 0 otherwise; and t(n) = 1 if 3(n , 0 otherwise. Suppose the walk is simple symmetric. In a scenery record coming from s, there will always be an odd number of 0’s between occurrences of 1’s. On the other hand, a scenery record coming from t will have regular (but randomly located) occurrences of the sequence (1, 0, 0, 1) embedded within it. Example 1.2. Let the walk and s be as in Example 1.1; and set t(n) =s(n) if n # 2, and 42) = 1. This case is much more subtle: A scenery record coming from either source will always have an odd number of 0’s between 1’s. However, since a simple symmetric walk on Z is recurrent, the random walk returns infinitely often to n = 2-the only location where s and t differ. In fact, this happens often enough to be detected. 2. PRELIMINARY IDEAS The basic technique is similar to that used in (31. Set gI = { (do , . . . , d,) : di E N}, GI = Urns, 9Im, and 9 = U, $3,. Any d E 9 may be thought of as a finite sequence of observable scenery. We denote the length of d by ldl, i.e., d E gIdl. For d ’ , d 2 E 9, we say that d’ = d’ if Id’[ = Id2[ and all of their respective components agree. Put r = NN, so r is the space of all possible scenery records. By equipping r with the standard a-field 92 generated by the finite dimensional cylinder sets, (r, 3 ) becomes a measurable space. Any sequence d € 9 may, or may not, appear in a particular scenery record y E r. The idea is to define some notion of the frequency f (d , y ) with which the finite sequence d appears in y. The precise definition of f ( d , y ) will depend on the application, but we wish it to have two
  • DETECTING DEFECTS BY RANDOM WALKS 61 properties. First, for any choice of d and x = s or t, we wish Ad, x , Z ) = f ( d , x ( Z ) ) to be constant almost surely with respect ,to the random walk Z. With some abuse of notation, we denote this constant by f(d, x ) . Second, we want f ( d * , s) #f(d*, t), for some d* E 9. Iff meets both these conditions and we are handed a scenery record y = s(2) or t ( Z ) , we may determine the source of y simply by calculating f ( d * , y ). Establishing the first condition for f requires a probabilistic argument while establishing the second condition for s& t requires a combinatoric argu- ment. Establishing both conditions shows that the distributions of (s (Z , ) , s(Z,),. . .) and ( t (Zo) , t(Z,), . . .) are supported by the disjoint sets {y E r : f ( d * , y) = f ( d * , s)}, and {y E r : f(d*, y) = A d * , t)}, respectively, formally showing that s and c are distinguishable. For 1 2 0, let W, denote all walks starting at the origin and taking 1 steps: W, = { (w,,, . . . , w,) : wo = 0; Iwi+, - wil = 0 or 1 for O I i < r } . For w E W,, let R(w) denote the number of steps to the “right” in w, L(w) the number of steps to the “left”, and P(w) the number of “pauses”; so R(w) + L(w) + P(w) = 1. If p( p , w) = p4‘;Y)p;‘w’pf‘w’ is the probability that any 1 steps of the random walk follow the pattern in w. For a E Z, d = (do, . . . , d,) E 9,, and scenery x , define W(d, x , a) = { w E W, : (x (a + W”), . . . , x ( a + w,)) = d } , and T ( P , 4 x ; a) = 2 P ( P ? w). W € W ( d . X , Q ) Then ~ ( p , d , x ; a ) is the probability of observing (do, . . . , d,) in a scenery record induced by scenery x beginning at a specific point in the record where the random walk is at a. We will need to distinguish the “straight” walks w: = (0, 1, . . . , I) and w,- = (0, -1, . . . , - 1 ) from the “crooked” walks in W,, where, for W C W,, the crooked walks in W are W = W - {w,‘} - {wy}. Set (2.3) p- l if (x (a - 0), . . . , x ( a - I ) ) = d , otherwise, and put
  • 62 HOWARD 4(p, d , x ; a) = q ( p , d , x ; a) - f d p , d , x ; a) (2.5) = c P ( P 9 W ) wE@(d.x .o ) with the final equality holding with Id1 z- 1. Note that, by this convention, when d E Bo we have q + ( p , d , x; a) = T - ( P , d , x ; a) = q ( p , d , x ; a ) . Finally, for any finite set A C Z, define (where # denotes cardinality) with analogous definitions of q + ( p , d , x; A ) , q - ( p , d , x ; A ) , ? ( p , d , x; A ) , and 6 ( p , d , x ; A ) . 3. THE PERIODIC CASE WITH SYMMETRIC WALK In this section we consider periodic scenery with an underlying random walk with transition probabilities of the form (2.1) with O < p - , = p , . (3.1) Let Zper denote the collection of all periodic sceneries on Z. Presently we prove; Theorem 3.1. transition probabilities p of the form (3.1), then s and t are dktinguishable. Let s, tEZ.,,, with s&t. If the underlying random walk has Proof. (yo, y , , . . .) be any scenery record and suppose d E 9/. Then define In this case, the appropriate choice of f is the natural one. Let y = and put n - 1 assuming, of course, that this limit exists. [If the limit does not exist, set f p e r (d , y ) =0.] G,(d, y ) detects the occurrence of the sequence ( d o , . . . , d,) embedded in y starting at the kth location and fp,,(d, y ) is precisely the limiting density of these occurrences. Analogously, set and put
  • DETECTING DEFECTS BY RANDOM WALKS 63 (assuming the limit exists) so fper(d, x(Z)) =Aer(d, x , Z). Let x E-Xper have period c and put 2, = 2, (mod c) and I, = (0, 1, . . . , c - l } . Then x(Z,) =x(Z,); also, 2 = (&, 2,, . . .) is a finite-state irreducible Markov process with invariant measure equal to the uniform distribution on I, (since the transition matrix is doubly stochastic). Under these circumstances, the ergodic theorem (see 6, p. 511) ensures that the limit in (3.5) exists and, almost surely, Aer(d, x , 2) = v ( p , d , x ; Z,). Benjamini and Kesten [l] observe that [5] contains a result that also yields the existence of these limits. It remains, then, to establish the second condition for our choice off = fper. The following lemma ensures the existence of the requisite d*. Lemma 3.2. q(p , d , s; I , )=q(p , d, t; I,) for all d €9, then S - t . Let s, t E Zper with common period c. If p is of the form (3.1) and Proof. Using only information in def A = (qd = q(p , 4 s ; 1,) =V(P, 4 t; 1,) : d E 9) we shall construct h E Zper with s - h and, by symmetry, t - h. Since - is an equivalence relation, s - t. As observed earlier, for each d E 9, qd has contributions arising from crooked walks and contributions arising from straight walks. As in (2 .5) , denote this split by qd = 7 j d + i j d . Suppose we know this split (i.e., we know 7 j d and 77,) for all d E 9. For any d E 9,-,, i j , > 0 if and only if the sequence d is observed along some c consecutive sites on s (either from left to right or from right to left). Choose one such d and define h E Zper by h(m) = d,,,, where [m] = m (mod c). Since c is a period of s, h satisfies s - h. We note that different choices of d € 9,-, with ijd > 0 will, in general, yield different h's-but they must all be in s's - equivalence class. We proceed by induction to prove that this split may be calculated for d E 9, for all n. Suppose we know ;id for all sequences d with [dl < n. Crooked walks in W, touch at most n - 1 contiguous integers. Therefore, based on the afore- mentioned knowledge, we should be able to calculate the frequency
  • 64 HOWARD reach is the d: component of d‘ and whose rightmost reach is d ” s last component. The index a in (3.6) represents the location within d‘ of the start of these walks. For example, if d‘ = (3 , 5 , 3, 0 ) E g3 and d = (3, 3, 5 , 3, 5 , 3, 0) E g 6 , then -2, -1, 0, l)}, and W:,d, = 0. If p = (.25, .5, .25), then P(d, d’) = 3(.5)(.25)5. The 6 analogue of (2.6) partitions the crooked walks contributing to ?jd according to their starting location a € I , . If, instead, we partition according to the walk’s leftmost reach (mod c) [indexed in (3.7) by a ] and the length of the interval supporting the walk (indexed by m), and exploit the periodicity of s, we see that w: ,da = ((0, 0, 1, 2, 1, 2, 3), (0, 0, 1, 0, 1, 27 3)}7 w:,d* = 0, w i , d ’ = ((O, O, -l? (3.7) 1 = - I n - l C u = o m=O i d =- P(d, d’ (s, m)) 7 where d’(s, a, m ) = (s(a), (s(a + l), . . . , s(a + m)) E gnI. If, for d ’ , d 2 E 9, we put A(d’, d 2 ) = 1 if d ’ = d’; 0 otherwise, then (3.7) yields For any d E gin, let - d E 9,1 denote the same sequence written backwards, i.e. ( - d ) k = d n - k for 0 5 k ~ n . When the walk is symmetric, q:. =qIdt and P(d , d ’ ) = ~ ( d , -d ’ ) . AISO, -d’ ranges over all of G,l-l as d‘ ranges over all of gin-,. From these observations and (3.8), we have also that and, by adding (3.8) and (3.9), Thus we can deduce i jd = qd - 6, for d E 9,! using only information in A. rn Example 3.3. With s and t as in Example 1 . 1 , we have common period c = 12 and may take 1, = (0, 1,. . . , 11). Taking d = (1, 0, 0, 1) E g3 and p = (.5, 0, . 5 ) gives q( p , d , s ; I , ) = 0 and q ( p , d , t ; I , ) = f X 2 X 2-3. Remark 3.4. to calculate f d for d E g,!. We observe for future reference that we only need vd for all d E 5?Jn
  • DETECTING DEFECTS BY RANDOM WALKS 65 4. THE PERIODIC CASE WITH ASYMMETRIC WALK In this case the random walk’s transition probabilities are of the form (2.1) with p - l Z p , . (4.1) The probabilistic component of the argument is unchanged: We take f = f,,, as in (3.3), and, for precisely the same reasons, the ergodic theorem yields that, almost surely, fper(d , x , Z) = q ( p , d , x ; Z,). The combinatoric argument must be handled somewhat differently to account for orientation. We have: Lemma 4.1. Let s, t E ZPer with common period c. If p is of the form (4.1) and ~ ( p , d , s ; I,) = q ( p , d , t ; I,) for all d € 9, then s - t ; in fact, s is a translate oft . Proof. As in Lemma 3.2, using only information in we shall construct h E Zper with s a translate of h. By symmetry again, we have that t is also a translate of h and hence s is a translate of t. Suppose, w.l.o.g., that O s p - , < p l . This time our breakdown of qd must take orientation into account. Suppose we know that (2.4, 2.5) breakdown qd = 6, + 77; + 77; (i.e., we know ijd, qd, and 7:) for all d E 9. Then choose any d E 9c-l with 77: > O and put h ( m ) = d[,,,!. Since > O if and only if the sequence d appears in s along c consecutive sites proceeding from left to right, we have that s is a translate of h. Again we proceed by induction to prove that this breakdown may be calculated for d E9,, for all n. If n = 0, then qd+ = q d =qd. Suppose we know this breakdown for all d ’ E G n - l , where n 2 l . Using (3.8) (this formula did not depend on the walk’s symmetry) we may calculate i jd for all d E 9,,. This gives us f d =qd - i j d for all d €9~~. If p - l = O then qd+ = ijd and qd = O . Suppose, then, that O
  • 66 HOWARD 5. DEFECTIVE PERIODIC SCENERY In this section we consider the case of periodic scenery that has been altered at finitely many locations. Throughout this section the underlying random walk is assumed to have transition probabilities of the form (3.1). The combinatoric Lemma 5.3 will ensure that portions of the scenery record coming from the defective region are in some sense drawn from a different distribution than those coming from the unaltered portion of the scenery. The idea is that after k steps the walk is in the defective region with probability of order k-”*. This is sufficient to detect its existence. The following simple model illustrates the idea and motivates the proof of our main result. Let X , and Yk be mutually independent 0-1 valued random variables with P{Xk = 1) = k-”’ and P{Y, = l } = A . Set Tk = max(X,, Y , ) so that Tk is usually drawn from an iid sequence of 0 s and 1’s (Y,) with an occasional “bogus” 1 thrown in (Xk). Now suppose we wish to determine if a given sequence of 0’s and 1’s is generated by the T process or the Y process. Consider the following averaging scheme for any random sequence V = (V , , V,, . . .): Let (n) = ( n ; ) = ( n , , n,, . . .) be a fixed sequence of increasing positive integers and define 1 A:’[V] = - N,,,[V] . m If we apply this to V, = Y, - A , then Nni[V] converges in distribution to a normal with mean 0 and variance A( 1 - A) as ni+ 30. The sequence ( n i ) may be chosen to make the N,, asymptotically independent in a sense that ensures that lim A i ’ [ Y - A ] = O m-x a s . (5.3) On the other hand, if we apply this scheme to vk = Tk - A , then, since max(X,, Y k ) = X, + Y, - X,Y, , we have 1 ”; EN,, [ V ] =- ( k - ” 2 + A - Ak-”2 - A) ‘ f i ’ k = l +2(1-A) a s n i + = , and, since the variance of N, [V] is bounded, it is not hard to see that for some sequence (n,) we have lim AL’[T - A ] = 2(1 - A) a s . m+x (5.4) Furthermore, by passing to a subsequence if necessary, (n , ) may be chosen so that (5.3) and (5.4) simultaneously hold, thus proving orthogonality of the dis- tributions of T and Y assuming, of course, that A < 1. This general idea works in our setting as well. Let Zdef denote all sceneries s
  • DETECTING DEFECTS BY RANDOM WALKS 67 with s(n) = s ' (n) except at finitely many locations n for some s' E Xper. Note that, for each s, s ' is unique-we shall reserve the prime notation to denote this mapping from Zdef to Zper.. Note also that Xper C Zdef. If c is any period of s ' and Z is a set of c consecutive integers such that s = s ' off I , then, we refer to I as a defective interval of s. (This definition is somewhat of a misnomer--e.g., if s is purely periodic, then every interval whose length is a period is a defective interval .) Note that if s, t E Xdef and s ' f t ' , then the symmetric periodic calculation (3.3) will work to distinguish s and t. This works since the random walk spends asymptotically none of its time in a defective interval so fper(d , x , 2) =&,,(d, X I , Z ) for x E Zdef. Note also that if s ' - t' and I is any interval whose length is a period of either (hence of both), then ~ ( p , d , s'; I ) = q ( p , d , t ' ; I ) and is independent of I for all observable scenery patterns d . In this case the choice f = f,,, defined in (3.3) and (3.5) will not work. The remainder of this section shows that the more refined notion defined in (5.6) does work. Our main result is the following: Theorem 5.1. transition probabilities p of the form (3.1), then s and t are dktinguishable. Let s, t EX,,, with s f t . If the underlying random walk has This result is an immediate consequence of the previous remark (concerning the case s ' / t ' ) , and Lemmas 5.2 and 5.3 as stated below. Lemma 5.3 is the combinatoric lemma analogous to Lemmas 3.2 and 4.1. We remark that the condition p - , = p , is, in general, essential. If the walk were transient, the defective interval would be visited only finitely often (possibly never) and insufficient information may be garnered to distinguish s from t. Lemma 5.2. Let s, t EX:,,, with s ' - t ' and with defective intervals I, and I,, respectively, of length c. Let d* = (d:, . . . , d;"..) be some finite sequence of observable scenery. Suppose that W ( d * , s, a ) = W ( d * , s', a ) and W ( d * , t , b ) = W ( d * , t', b ) for all a$Z, and b jZI , , b u t q ( p , d * , s; I,) # q ( p , d * , t ; Z,). Then s and t are distinguishable. Lemma 5.3. Let s, t EX,,, with s ' - t ' but s / t . Then there exists defective intervals Z, and I,, respectively, of common length c and some finite sequence of observable scenery d* = (d; , . . . , d;".) such that ( i ) W ( d * , s, a ) = W ( d * , s', a ) and W ( d * , I , b ) = W ( d * , t', b ) for all a$Z, and b g I , and (ii) ~ ( p , d * , s; I,) # q ( p , d * , t ; I,). Remark 5.4. We note that, since p - , = p , , the conclusion of Lemma 5.3 holds for the pair s, t E Zdef if and only if it holds for the pair s, -t [where ( - t ) (n) = t(-n)l . Proof of Lemma 5.2. Fix any d E 9,. x E Xdef. Let x = s or t and put I = I s or I, as appropriate. Set q(x) = ~ ( p , d , x ; I ) and ~ ( x ' ) = q ( p , d , x ' ; Z). Most of the time the walk is off I, and d occurs in an induced scenery record y with likelihood q ( x ' ) . Occasionally, however, the walk is in I and the likelihood of spotting d in the scenery record y changes to q(x) . To define f ( d , y) in this case, we apply the
  • 68 HOWARD averaging scheme of (5.1) and (5.2) to the sequence V, = G,(d, y ) - v ( x ' ) , where G, is defined as in (3.2). We claim that, for some sequence ( n , ) , 2 A:: '[6(d.x, Z ) - T & X ~ ) ] % ~ ( ~ ( x ) - ~ ( x ' ) ) as m+ M (5.5) ( 1 - P " b where 5 denotes convergence in probability and 6, is defined as in (3.4). (We recall that c is the common length of 1, and l , .) For some sequence (m,), therefore, the limit in (5.5) occurs almost surely with respect to the walk. Assuming (5.5). set f d , @ Y 1 =ti? A!:,)[G(d. 7 ) - v(x')l so that f;,,(d, x, Z ) =lim A ! : : ' [ E ( ~ . x , Z ) - v ( x ' ) l ,-= I = c fT ( 1 - P O h (v(x) - v(x')) a.s. ( 5 . 6 ) The lemma follows from (5.6) since, with d = d*, we have ~ ( s ' ) =v(f') and v(s) +v(t) , yielding that L e l ( d * . s, Z ) Z&el(d*, t,Z). To see (5 .5 ) . we decompose 6A into indicator functions that are easier to analyze. Let u = {(a, w) E I x "u., : (x(a + w,,), . . * , x(a + W / ) ) = d } , U' = {(a, w) E I x w; : (x'(a + W " ) , . . . , x' (a + W / ) ) = d } , and, for (a, w) E I x W;, let if (Z,, . . . , Zk+,) = (a + w", . . . , a + w,) , otherwise. Y:" " ' ( Z ) = {; Then we have 6 , ( d . x, Z ) = Ek(d' xf, Z ) - c Y:" " ' ( Z ) + 2 YIp "'(Z) . (5.7) ( < I W)EU ( a M ) E U Using 1 1 C ( a ~ ) E U - c P(P7 w) =v(x) and - c P ( P , w) =v(x') C ( a w)EU and the linearity of the averaging scheme, it suffices to show that P A!,"'[E(d, X I , Z ) - 77(~')]+0 and as m - x . To see ( 5 . 8 ) , note that x ' is periodic and, with 2 as in Theorem 3.1, 2 is a finite state Markov chain. By an application of the appropriate central limit
  • DETECTING DEFECTS BY RANDOM WALKS 69 theorem (see, e.g., [2, pp. 375-3581) we have that N, ’!Zf N,[G(d, x’ , Z ) - ~ ( x ’ ) ] converges in distribution to a mean 0, finite variance normal distribution as n - , ~ . It is also easy to establish that cov(Nno, N n , ) + O for any fixed no as n + m. This covariance condition, together with the fact that var(N,) is bounded, yields (5.8) and follows for an appropriate (n,) (see [2, p. 291). To establish (5.9), we use [7, Theorem 2.81 to get, when po = 0, that P { Z , = a } = { k-’12 + O(k-’ / ’ ) when k = a 0 otherwise. (mod 2) , If pO > 0, let B, denote the number of true steps (nonpause steps) that the walk has taken by time k . Then B, is binomially distributed with parameters k and 1 -pO and k P { Z , = a } = x P { Z k = a l B , = j } P { B , = j ) j = O j - a even Note that EB, = (1 - p( , )k . With gk = (B, - (1 - p O ) k ) / v w , we note also that E exp(g,) and E exp(-E,) converge to fi as k + = . Using (5.10) and Chebyshev’s inequality applied to exp(lI?,’,l) to control the tails of B,, it is not hard to see that, when po > 0, Combining the cases po > 0 and p( , = 0, we have k - u even (5.11) yields that (5.12) where N , now denotes N,[Y‘”.”’]. A similar analysis, based on a conditional version of (5.11), establishes that var(N,) is bounded in n and cov(N,,,, N , , , ) + O for fixed no as n , + 00. These variance/covariance conditions together with (5.12)
  • 70 HOWARD suffice to establish (5.9) for some sequence ( n i ) . Clearly, by passing to sub- sequences if necessary, we may establish (5.8) or (5.9), as appropriate, simul- taneously for each summand in (5.7) for some sequence (n;). Proofof Lemma 5.3. By Remark 5.4, we may assume without loss of generality that s’ is a translate of t ’ . Set P = (s‘( l ) , . . . , s’(cmln)), where cmln is the minimal period of s‘ . If D denotes any finite sequence of n natural numbers, we write = n. (Note that this is smaller by one than the 1 . 1 notion defined in Section 2.) If we think of sceneries on Z as two-sided infinite sequences, then we may concatenate finite sequences to form such sceneries, e.g., (. . . PPPDPPP. . .). (To to be precise, we must also know where along Z the sequence D is found.) In this manner, we may represent and where these representations are unique if we assume that the defective sequences D , and D, are minimal, i.e., they neither begin nor end with the sequence P. We observe that 11D,11 and 11D,11 are (possibly different) multiples of c,,, . We assume without loss of generality that llD,ll 5 l(D,II and note that D, may be the empty sequence, i.e., t may be periodic. We say that a sequence of observable scenery S = (S,,, . . . ,a,) E 9/ occurs on a straight walk in the scenery x on Z if for w = w,’ or w; and some a E Z we have s = (. . . PPPD,PPP. . .) t = (. . . P P P D , P P P . . .) , s = (x(a + w o ) . . . . , x (a + W / ) ) . We claim that for some 8 E gi 6 occurs on a straight walk in s but not in t . (5.13) This fact may seem an obvious consequence of s J t , but some care must be taken in constructing &-we leave this detail for later. Assume, then, that 8 has the property (5.13). Choose m such that IlP”’II = mc,,, > 1 , where P” denotes m copies of P strung together. Also, fix k 2 0 such that (ID,(I = IID,P’II. Define - fir = P”’D,P”‘ and fir = P“‘D,Ph’“ so that 11fi;,11 = 116,11 and s = (. . . P P P f i ; , P P P . . .) and Let Z, and Z, denote the intervals in Z that respectively support the scenery sequences 6, and 6,. Then, by construction, 1, and I, have a common length c which is some period of s’ (and t’) and represent defective intervals for s and t respectively. We note also that each end of Z, and I, is “padded” with sufficiently many copies of P so that conclusion (i) in the Lemma holds provided we choose d* so that I * 5 r. To see that conclusion (ii) holds for this choice of Z, and Z, and some choice of d’ E Gi = U,sT 9/, define the following periodic sceneries: t = (. . . P P P 6 , P P P . . .) . - - - s* = (. . . 6@,fiS.. .) and t* = (. . . D,D,D, . . .) ,
  • DETECTING DEFECTS BY RANDOM WALKS 71 where, simply to be specific, we may assume that one of the sequences of f i s coincides with 1, and one of the sequences of fi, coincides with Z,. We note that, again because of the padding, we have 7 7 ( p I d , s ; ~ , ) = 7 7 ( p , d , s * ; ~ , ) , ~ ( p , d , t ; I , ) = d p , d , t * ; I , ) f o r a l I d E G j . (5.14) If 7 7 ( P , d , s ; I , ) = r ) ( p , d , t ; I , ) f o r a l I d E g j (5.15) it would follow from (5.14) and the proof of Lemma 3.2 (see Remark 3.4) that (5.16) If (5.16) were true, afortiori, any d E gi that occurs on a straight walk in s* must also occur on a straight walk in t*. We note also that, because of the padding, for any d E Gi, d occurs on a straight walk in s if and only if d occurs on a straight walk in s*, with an analogous statement true for t and t*. Therefore, if (5.16) were true, we would have that any d E !2& that occurs on a straight walk in s must also occur on a straight walk in t. This contradicts the existence of d as defined above. Hence (5.16) and therefore (5.15) must be false, establishing conclusion (ii). This brings us back to the detail of establishing 6's existence. Clearly we may assume that s is not periodic. One is tempted to assert that the sequence D, cannot occur as straight walk in t . To see that this is, in general, false, take P = (1, 2), D, = (2, l ) , and let D, be the empty sequence so that f is periodic. To remedy this problem, choose r so that llP'll> 11D,11. If t' happens to be a translate of - ( t ' ) = ( - ? ) I , then we may, as above, represent + ( p , d , s*; I,) = + ( p , d, t* ; 1,) for all d E Gi . - t = (. . . PPPD-,PPP . . .) , where D-, is minimal. In this event increase r , if necessary, so that we also have llP'll > l(D-,ll. [Note that ((D,ll is not necessarily equal to 11D-,!; e.g., take P = (0, 0 , l), D, = (0 , 2, 2), then D-, = (0, 0, 2, 2, 0, l).] Now set 6 equal to the sequence of scenery obtained by traversing P'D,P' from left to right. If d appears occurs on a straight walk from left to right in t , then along this straight walk the initial P' portion of 8 must terminate exactly where D, begins. This is due to the minimality of P, D,, D, and the fact that at least cmin consecutive elements of the sequence P' must occur outside of D,. Similarly, the final P' portion of d must begin exactly where D, ends. But this means that D, = D,, contradicting s / t . If 8 occurs on a straight walk from right to left in t , then t' must be a translate of - t ' . This holds since at least one of the blocks of P in the 6 sequence is found occurring from right to left in t fully outside of D,. But then, by reasoning identical to the "left to right" case, we must have D, = D-,, again contradicting s / t . I We give two examples. In each case, s t = t', 1, =I,, and the random walk has transition probabilities p = ( S , 0, S) . Example 5.5. Let s and t be defined as in Examples 1.2. Take Z, =I, = (0 , 1, 2,
  • 72 HOWARD 3) and d * = (1) E 9(). In this case we have q ( s ’ ) = q(t’) = .25, ~ ( s ) = .25, and q(t) = . 5 , and the averaging scheme will detect the single extra 1 in the t scenery. Example 5.6. s(n) = 1 if n E L,, s(n) = 0 otherwise with t similarly defined: Let L = { 2 n : n E Z } , L , = L U { l , 5 } , and L , = L U { l , 7). Set n ... -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 s‘(n) = t ‘ (n) . . . 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . a . s(n) . . . 0 1 0 1 1 1 0 l l 1 0 1 0 1 0 1 - e - t(n> . . . 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 l . . ’ With a simple symmetric walk, if we take I, = I, = [ - 1, 81 and d* = (1, 1, 0, 1, 1) E g4, then q(s’) = q(t‘) = 0, q(s) = 2 - 4 X 6/10, and q(t) = 2 - 4 X 4/10. (This, in fact, is the shortest sequence that works.) We conclude this section with a corollary to the proof of Lemma 5.2. Corollary 5.7. Let s, t E Z, d E 9,. and suppose p has the form (3.1 ). I f c q( p , d , s; a) < c T ( P , d , t ; a ) , U E Z O E Z then s and t are distinguishable. Proof. Note that part of the hypothesis is that COEZ q ( p , d , s; a) < x . Hence, for some I = {-m,. . . , m}, q(p, d , s; a) = O for a$I while q ( p , d , s; I ) < q ( p , d , t ; I ) . Set r= { -m - I , . . . , m + I}. Letting 6 E N be outside of the ranges of s and t (without loss of generality we may assume such a 6 exists), define {(n) i f n E J , S(n) = otherwise, and r similarly. Notice, then, that S’(n) = ?(n) = 6 and that f is a defective interval for S and r. To apply Lemma 5.2 to S and f, we note that def q’ = q(p. d , S ’ ; I ) = q ( p , d , f’; r ) = 0 , q(S) E f q ( p , d , S; I ) = q(p , d , s ; I ) X # I / # [ , q(F )%‘q (p ,d , t ; I ) ~ q ( p , d , t ; I ) x # ] / # I so that q ( S ) < q ( t ) . In the proof of Lemma 5.2, sequences ( n , ) and (m,) are constructed such that drf . u = Iim A;,”[G(~, S, z ) ]
  • DETECTING DEFECTS BY R A N D O M WALKS 73 6. STRICT DISTINGUISHABILITY Thus far, our notion of distinguishability has been pairwise. In this final section we introduce a notion that is stronger in the sense that it implies (pairwise) distinguishability. It will follow easily that the scenery class Cdef satisfies this stronger notion. Recalling that (r, 9) is the measurable space of observable scenery records, corresponding to any scenery s : Z+ N, define the probability measure P, on (r, 9 ) by P,A = P{s(Z) E A}. Then, according to our definition, sceneries s and t are distinguishable if and only if for some A E '3 we have P,A = P,A' = 1. The set A may depend on both s and t , as it clearly does in the proof of Theorem 5.1. We say that a collection of sceneries C that is closed under the - equivalence is strictly distinguishable if associated with each s E C there is an E, E 9 such that (i) P,E, = 1 and (ii) for any t E C with t f s we have E, fl E, = 0. The key idea is that the set E,s supporting the P, measure can be constructed without reference to another scenery. This notion of strict distinguishability is equivalent to the existence of a "decoder" function g : rg+m-, whose domain is a (not necessarily measurable) subset of r and whose range is the set of - equivalence classes in C that satisfies for all s E C: (i) g - ' ( [ s ] ) E 3 and (ii) P,g-'([s]) = 1. Here we use [s] to denote the - equivalence class of s. To see this, note that if such a g exists, then we may take E, =g-l([s]). On the other hand, if I: is strictly distinguishable, take rg = UsEX E, and put g ( y ) = [s] for The strict distinguishability of Zdef when the walk is symmetric follows from: y E u;-, E;. Theorem 6.1. distinguishable, then it is strictly distinguishable. If a countable collection of sceneries 2 is closed under - and Proof. Now put For each pair s, t E C with s / t construct A,, E 9 with P,A,, = P,AJ:, = 1. E,= n A,!- u A , , . l € Z : r p l € Z : I j S It is straightforward to verify that the sets E, satisfy the conditions of strict distinguishability specified above. H Loosely speaking, this says that if we know that the scenery is in Cdef, then its - equivalence class can be deduced via the decoder function from a single observed scenery record. See [4] for more results on strict distinguishability. ACKNOWLEDGMENTS The author wishes to thank Chuck Newman, Itai Benjamini, and a very thorough referee for helpful discussion and comments.
  • 74 HOWARD REFERENCES [ l ] I. Benjamini and H, Kesten, Distinguishing sceneries by observing the scenery along a [2] R. Durrett, Probability: Theory and Examples, Brooks/Cole, Belmont, CA, 1991. [3] C. D. Howard, Orthogonality of measures induced by random walks with scenery, Combinat. Probab. Comput., to appear. [4] C. D. Howard, The orthogonality of measures induced by random walks with scenery, Ph.D. dissertation. Courant Institute of Mathematical Sciences, New York, 1995. [5] J.-P. Kahane, J. Peyriere, Z.-Y. Wen, and L.-M. Wu, Moyennes uniforrnes et moyennes suivant une marche alCatoire, Probab. Theory Related Fields, 79, 625-628 (1988). random walk path, preprint, 1995. [6] K. Petersen. Ergodic Theory, Cambridge University Press. Cambridge, 1983. [7] P. RivCsz, Random Walk in Random and Non-Random Environments, World Sci- entific, Singapore. 1990. Received March 23. 1995 Accepted June 2. 1995
Fly UP