Reconstructing a two-color scenery by observing it along a simple random walk path (Q1774198)

A scenery is a function \(\xi \) from \(\mathbb{Z=}\left\{ \dots ,-1,0,1,\dots \right\} \) to \(\left\{ 0,1\right\} \). Two sceneries \(\xi \) and \(\widetilde{\xi }\) are said to be equivalent if and only if there exist \( \alpha \in \mathbb{Z}\) and \(b\in \left\{ -1,1\right\} \) such that \(\xi \left( x\right) =\widetilde{\xi }\left\{ a+bx\right\} \) for any \(x\in \mathbb{Z}\). Let \((S(k))_{k\in \mathbb{N}},\;\mathbb{N}=\left\{ 0,1,\dots \right\} \), be a simple random walk starting at the origin and \((\xi \left( \ell \right) )_{\ell \in \mathbb{Z}}\;\)a doubly infinite sequence of i.i.d. Bernoulli variables with parameter \(\frac{1}{2}\). Assume that these processes are independent. Write \(\xi :\ell \rightarrow \xi \left( \ell \right) ,\;\mathbb{Z\rightarrow }\left\{ 0,1\right\} .\) It is proved that a.s. \(\chi :=(\xi \left( S\left( k\right) \right) )_{k\in \mathbb{N}}\) determines \(\xi\) up to equivalence, to mean that there exists a measurable function \(A:\left\{ 0,1\right\} ^{\mathbb{N}}\rightarrow \left\{ 0,1\right\} ^{\mathbb{Z}}\) such that \(P(A\left( \chi \right) \) is equivalent to \(\xi )=1\) . This result solves in the affirmative the question, raised by H. Kesten, of whether one can a.s. detect a single defect in almost every two-color random scenery by only observing it along a random walk path.