Premium
Detecting defects in periodic scenery by random walks on Z
Author(s) -
Howard C. Douglas
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199601)8:1<59::aid-rsa3>3.0.co;2-q
Subject(s) - random walk , conjecture , combinatorics , mathematics , reflection (computer programming) , generating function , function (biology) , simple (philosophy) , discrete mathematics , computer science , statistics , philosophy , epistemology , evolutionary biology , biology , programming language
Thinking of a deterministic function s : Z → N as “scenery” on the integers, a random walk ( Z 0 , Z 1 , Z 2 ,…) on Z generates a random record of scenery “observed” along the walk: s ( Z ) = ( s ( Z 0 ), s ( Z 1 ),…). 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, +1}. If both sceneries are purely periodic and the walk is asymmetric (with steps restricted to {−1, 0, +1}), we get a somewhat stronger result. © 1996 John Wiley & Sons, Inc.