Distinguishing sceneries by observing the scenery along a random walk path (Q2565376)

The authors study the question whether or not one can distinguish two random sceneries (in other texts also called colorings) of the vertices of a graph if one knows them along some simple random walk path. Let \(({\mathcal G},\nu)\) be an infinite connected graph whose vertices have finite degree. The random walk \((S_n)_{n\in\mathbb{N}_0}\) on \(\nu\) starts at some fixed point in \(\nu\) and chooses one of the adjacent vertices with equal probability at each step. Two sceneries \(\xi\), \(\eta\) (that is, elements of \(\{0,1\}^\nu\)) are called distinguishable if the distributions of the sequences \((\xi(S_n))_{n\geq l}\) and \((\eta(S_n))_{n\geq l}\) are mutually singular for each \(l\in\mathbb{N}_0\). The first result states that, for \({\mathcal G}=\mathbb{Z}\) or \(\mathbb{Z}^2\), each fixed \(\xi\in\{0,1\}^\nu\) is distinguishable from \(\varrho\)-a.a. \(\eta\in\{0,1\}^\nu\) where \(\varrho=({1\over 2}(\delta_0+ \delta_1))^{\otimes\nu}\). For \({\mathcal G}=\mathbb{Z}^d\) with \(d\) large, the authors conjecture that two independent random sceneries with distribution \(\varrho\) each are not distinguishable, a.s. They prove this conjecture for the walk \((S_n)_{n\in\mathbb{N}_0}\) on \(\mathbb{Z}^d\) replaced by the oriented simple random walk on \(\mathbb{N}^d_0\) which starts at \(0\) and increases one of its \(d\) components (uniformly chosen) by one at each step. A similar result for unoriented simple random walk on trees is formulated. The last main result is for \({\mathcal G}=\mathbb{Z}^d\), \((S_n)_{n\in\mathbb{N}_0}=\) simple random walk, \(\xi\in\{0,1\}^\nu\) fixed and \(\eta\in\{0,1\}^\nu\) random with distribution \(\varrho\): For large \(k\in\mathbb{N}\), \(\xi\) and \(\eta\) are \(k\)-distinguishable, a.s., where \(\xi\) and \(\eta\) are called \(k\)-distinguishable if for all \(l\in\mathbb{N}_0\), the distributions of the set-valued sequences \((\xi(S_n+B_k))_{n\geq l}\) and \((\eta(S_n+B_k))_{n\geq l}\) are mutually singular, where \(B_k=\{w\in\mathbb{Z}^d: \sum^d_{i=1}|w_i|\leq k\}\) (i.e., a neighborhood of the walker's position is observed).