Distinguishing sceneries by observing the scenery along a random walk path
Distinguishing sceneries by observing the scenery along a random walk path
复制标题
通过沿着随机步行路径观察风景来辨别风景
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
H. Kesten
中科院分区：
文献类型：
--
作者：
I. Benjamini;H. Kesten
设G是一个顶点集为V的无限连通图. G上的风景是一个映射V：V → 0，1（等价于G的顶点的0和1的赋值）。设Snn ≥0是G上的一个简单随机游动，起始于某个特殊顶点v0.设n和η是两个已知的场景，假设我们观测到两个序列中的一个，但我们不知道这两个序列中的哪一个被观测到。我们能否在零错误概率的情况下，确定观察到的是两个序列中的哪一个？我们证明了，如果G = Z或G = Z ~ 2，则对每个固定的ε和“几乎所有”的η，答案都是“是”。我们也给出了一些例子的graphsG，几乎所有的对（ε，η）是不可区分的，并讨论了这个问题的一些变种。
LetG be an infinite connected graph with vertex setV. Ascenery onG is a map ξ :V → 0, 1 (equivalently, an assignment of zeroes and ones to the vertices ofG). LetSnn≥0 be a simple random walk onG, starting at some distinguished vertex v0. Now let ξ and η be twoknown sceneries and assume that we observe one of the two sequences ξ(Sn)n≥0 or {η(Sn)}n≥0 but we do not know which of the two sequences is observed. Can we decide, with a zero probability of error, which of the two sequences is observed? We show that ifG = Z orG = Z2, then the answer is “yes” for each fixed ξ and “almost all” η. We also give some examples of graphsG for which almost all pairs (ξ, η) are not distinguishable, and discuss some variants of this problem.