Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 15 open journal systems 


Information recovery from randomly mixed-up message text

Jüri Lember, University of Tartu, Estonia
Heinrich Matzinger, University of Bielefeld, Germany


Abstract
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.


Full text: PDF

Pages: 396-466

Published on: March 20, 2008
Bibliography
  1. Benjamini, Itai; Kesten, Harry. Distinguishing sceneries by observing the scenery along a random walk path. J. Anal. Math. 69 (1996), 97--135. MR1428097 (98f:60134)
  2. den Hollander, W. Th. F. Mixing properties for random walk in random scenery. Ann. Probab. 16 (1988), no. 4, 1788--1802. MR0958216 (89i:60199)
  3. den Hollander, Frank; Steif, Jeffrey E. Mixing properties of the generalized $T,Tsp {-1}$-process. J. Anal. Math. 72 (1997), 165--202. MR1482994 (98m:28034)
  4. den Hollander, Frank; Steif, Jeffrey E. Random walk in random scenery: a survey of some recent results. Dynamics & stochastics, 53--65, IMS Lecture Notes Monogr. Ser., 48, Inst. Math. Statist., Beachwood, OH, 2006. MR2306188
  5. Heicklen, Deborah; Hoffman, Christopher; Rudolph, Daniel J. Entropy and dyadic equivalence of random walks on a random scenery. Adv. Math. 156 (2000), no. 2, 157--179. MR1808244 (2002g:37003)
  6. Harris, Matthew; Keane, Michael. Random coin tossing. Probab. Theory Related Fields 109 (1997), no. 1, 27--37. MR1469918 (99c:60086)
  7. Hart, Andrew; Matzinger, Heinrich. Markers for error-corrupted observations. Stochastic Process. Appl. 116 (2006), no. 5, 807--829. MR2218337 (2007i:60138)
  8. Howard, C. Douglas. Detecting defects in periodic scenery by random walks on $ Z$. Random Structures Algorithms 8 (1996), no. 1, 59--74. MR1368850 (97f:60087)
  9. Howard, C. Douglas. Distinguishing certain random sceneries on $Z$ via random walks. Statist. Probab. Lett. 34 (1997), no. 2, 123--132. MR1457504 (98h:60106)
  10. Kalikow, Steven Arthur. $T,,Tsp{-1}$ transformation is not loosely Bernoulli. Ann. of Math. (2) 115 (1982), no. 2, 393--409. MR0647812 (85j:28019)
  11. Keane, M.; den Hollander, W. Th. F. Ergodic properties of color records. Phys. A 138 (1986), no. 1-2, 183--193. MR0865242 (88g:60170)
  12. Kesten, Harry. Detecting a single defect in a scenery by observing the scenery along a random walk path. Itô's stochastic calculus and probability theory, 171--183, Springer, Tokyo, 1996. MR1439524 (98i:60066)
  13. Kesten, Harry. Distinguishing and reconstructing sceneries from observations along random walk paths. Microsurveys in discrete probability (Princeton, NJ, 1997), 75--83, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Amer. Math. Soc., Providence, RI, 1998. MR1630410 (99i:60141)
  14. Lindenstrauss, Elon. Indistinguishable sceneries. Random Structures Algorithms 14 (1999), no. 1, 71--86. MR1662199 (99m:60106)
  15. Juri Lember and Heinrich Matzinger. Reconstructing a piece of $2$-color scenery. Eurandom http://www.eurandom.nl/EURANDOMreports.htm, 2002. Submitted.
  16. Löwe, Matthias; Matzinger, Heinrich, III. Scenery reconstruction in two dimensions with many colors. Ann. Appl. Probab. 12 (2002), no. 4, 1322--1347. MR1936595 (2004a:60167)
  17. Löwe, Matthias; Matzinger, Heinrich, III. Reconstruction of sceneries with correlated colors. Stochastic Process. Appl. 105 (2003), no. 2, 175--210. MR1978654 (2004d:60262)
  18. Matzinger, Heinrich; Lember, Jüri. Reconstruction of periodic sceneries seen along a random walk. Stochastic Process. Appl. 116 (2006), no. 11, 1584--1599. MR2269217 (2007m:60310)
  19. Löwe, Matthias; Matzinger, Heinrich; Merkl, Franz. Reconstructing a multicolor random scenery seen along a random walk path with bounded jumps. Electron. J. Probab. 9 (2004), no. 15, 436--507 (electronic). MR2080606 (2005h:60309)
  20. D. A. Levin and Y. Peres. Identifying several biased coins encountered by a hidden random walk. Random Structures Algorithms, 25(1):91--114, 2004.
  21. Levin, David A.; Pemantle, Robin; Peres, Yuval. A phase transition in random coin tossing. Ann. Probab. 29 (2001), no. 4, 1637--1669. MR1880236 (2002m:60071)
  22. bibitem [Mat99a]Heinrich Matzinger.newblock {em Reconstructing a 2-color scenery by observing it along a simple random walk path with holding}.newblock PhD thesis, Cornell University, 1999.
  23. Matzinger, Heinrich. Reconstructing a three-color scenery by observing it along a simple random walk path. Random Structures Algorithms 15 (1999), no. 2, 196--207. MR1704344 (2000m:60048)
  24. Heinrich Matzinger. Reconstructing a 2-color scenery by observing it along a simple random walk path. Ann. Appl. Prob, 15(1):778--819, 2005.
  25. Heinrich Matzinger and Juri Lember. Scenery reconstruction: an overview. In Information and Randomness (Maass, Martinez, San Martin (Eds)), volume 66, pages 76--125. Hermann, Travaux en cours, 2006.
  26. Matzinger, Heinrich; Popov, Serguei. Detecting a local perturbation in a continuous scenery. Electron. J. Probab. 12 (2007), no. 22, 637--660 (electronic). MR2318405
  27. Matzinger, Heinrich; Rolles, Silke W. W. Reconstructing a piece of scenery with polynomially many observations. Stochastic Process. Appl. 107 (2003), no. 2, 289--300. MR1999792 (2004i:60152)
  28. Matzinger, Heinrich; Rolles, Silke W. W. Reconstructing a random scenery observed with random errors along a random walk path. Probab. Theory Related Fields 125 (2003), no. 4, 539--577. MR1974414 (2004b:60231)
  29. Matzinger, Heinrich; Rolles, Silke W. W. Retrieving random media. Probab. Theory Related Fields 136 (2006), no. 3, 469--507. MR2257132 (2007m:60309)
  30. Petrov, Valentin V. Limit theorems of probability theory.Sequences of independent random variables.Oxford Studies in Probability, 4. Oxford Science Publications.The Clarendon Press, Oxford University Press, New York, 1995. xii+292 pp. ISBN: 0-19-853499-X MR1353441 (96h:60048)













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489