×

Information recovery from randomly mixed-up message text. (English) Zbl 1189.60025

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.

MSC:

60C05 Combinatorial probability
60G50 Sums of independent random variables; random walks
60K37 Processes in random environments
PDFBibTeX XMLCite
Full Text: DOI EuDML EMIS