Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1156572 | Stochastic Processes and their Applications | 2014 | 17 Pages |
Abstract
We consider the question of when a random walk on a finite abelian group with a given step distribution can be used to reconstruct a binary labeling of the elements of the group, up to a shift. Matzinger and Lember (2006) give a sufficient condition for reconstructability on cycles. While, as we show, this condition is not in general necessary, our main result is that it is necessary when the length of the cycle is prime and larger than 5, and the step distribution has only rational probabilities. We extend this result to other abelian groups.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)
Authors
Hilary Finucane, Omer Tamuz, Yariv Yaari,