Lember, Jüri; Matzinger, Heinrich Information recovery from randomly mixed-up message text. (English) Zbl 1189.60025 Electron. J. Probab. 13, 396-466 (2008). Summary: This paper is concerned with finding a fingerprint of a sequence. As input data one uses the sequence which has been randomly mixed up by observing it along a random walk path. A sequence containing order \(\exp (n)\) bits receives a fingerprint with roughly n bits information. The fingerprint is characteristic for the original sequence. With high probability the fingerprint depends only on the initial sequence, but not on the random walk path. Cited in 4 Documents MSC: 60C05 Combinatorial probability 60G50 Sums of independent random variables; random walks 60K37 Processes in random environments Keywords:scenery reconstruction; random walk in random environment PDFBibTeX XMLCite \textit{J. Lember} and \textit{H. Matzinger}, Electron. J. Probab. 13, 396--466 (2008; Zbl 1189.60025) Full Text: DOI EuDML EMIS