Scenery reconstruction on finite abelian groups. (English) Zbl 1341.60033
Summary: 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. In 2006, H. Matzinger and J. Lember [ibid. 116, No. 11, 1584–1599 (2006; Zbl 1111.60081)] gave 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.
Citations:
Zbl 1111.60081References:
| [1] | Benjamini, I.; Kesten, H., Distinguishing sceneries by observing the scenery along a random walk path, J. Anal. Math., 69, 1, 97-135 (1996) · Zbl 0868.60059 |
| [2] | Howard, C., Detecting defects in periodic scenery by random walks on \(Z\), Random Struct. Algorithms, 8, 1, 59-74 (1996) · Zbl 0840.60064 |
| [3] | Howard, C. D., Orthogonality of measures induced by random walks with scenery, Combin. Probab. Comput., 5, 247-256 (1996) · Zbl 0865.60057 |
| [4] | Howard, C. D., Distinguishing certain random sceneries on \(Z\) via random walks, Statist. Probab. Lett., 34, 2, 123-132 (1997) · Zbl 0894.60066 |
| [5] | Kesten, H., Distinguishing and reconstructing sceneries from observations along random walk paths, (Microsurveys in Discrete Probability (Princeton, NJ, 1997) (1998)), 75-83 · Zbl 0908.60069 |
| [6] | Lindenstrauss, E., Indistinguishable sceneries, Random Struct. Algorithms, 14, 71-86 (1999) · Zbl 0963.60042 |
| [7] | Löwe, M.; Matzinger, H.; Merkl, F., Reconstructing a multicolor random scenery seen along a random walk path with bounded jumps, Electron. J. Probab. (electronic only), 9, 436-507 (2004) · Zbl 1064.60201 |
| [8] | Matzinger, H.; Lember, J., Reconstruction of periodic sceneries seen along a random walk, Stochastic Process. Appl., 116, 11, 1584-1599 (2006) · Zbl 1111.60081 |
| [9] | Matzinger, H.; Rolles, S. W.W., Reconstructing a piece of scenery with polynomially many observations, Stochastic Process. Appl., 107, 2, 289-300 (2003) · Zbl 1075.60521 |
| [10] | Mendel, J. M., Tutorial on higher-order statistics (spectra) in signal processing and system theory: theoretical results and some applications, Proc. IEEE, 79, 3, 278-305 (1991) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
