Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-06T16:10:23.757Z Has data issue: false hasContentIssue false
  • English
  • Français

Almost-sure waiting time results for weak and very weak Bernoulli processes

Published online by Cambridge University Press:  14 October 2010

Katalin Marton  and
Paul C. Shields
Katalin Marton
Affiliation:
Mathematics Institute, Hungarian Academy of Sciences, Hungary
Paul C. Shields
Affiliation:
University of Toledo§, Toledo, OH 43606, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

Almost-sure convergence of (l/k) log Wk(x, y) to entropy for weak Bernoulli processes is proved, where Wk (x, y) is the waiting time until an initial segment of length k of a sample path x is seen in an independently chosen sample path y. Analogous almost-sure results are obtained in the approximate match case for very weak Bernoulli processes. The weak Bernoulli proof uses recent results obtained by the authors about the estimation of joint distributions, while the very weak Bernoulli result utilizes a new characterization of such processes in terms of a blowing-up property.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 15 , Issue 5 , October 1995 , pp. 951 - 960
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Ledrappier, F.. Sur la condition de Bernoulli faible et ses applications. Théorie Ergodique, Proceedings 1973/1974. Conze, J. P. and Keane, M. S., eds. Springer Lecture Notes in Mathematics 532. pp. 152–159. Springer, Berlin, 1976.CrossRefGoogle Scholar
[2] Marton, K. and Shields, P.. Entropy and the consistent estimation of joint distributions. Ann. Probab. 22 (1994), 960–977.CrossRefGoogle Scholar
[3] Marton, K. and Shields, P.. The positive-divergence and blowing-up properties. Israel J. Math. 86 (1994), 331–348.CrossRefGoogle Scholar
[4] Nobel, A. and Wyner, A.. A recurrence theorem for dependent processes with applications to data compresssion. IEEE Trans. Inform. Th. IT-38 (1992), 1561–1563.Google Scholar
[5] Ornstein, D.. Ergodic Theory, Randomness, and Dynamical Systems. Yale University Press, New Haven, 1974.Google Scholar
[6] Ornstein, D. and Weiss, B.. How sampling reveals a process. Ann. Probab. 18 (1990), 905–930.CrossRefGoogle Scholar
[7] Pollard, D.. Convergence of Stochastic Processes. Springer, New York, 1984.CrossRefGoogle Scholar
[8] Shields, P.. Waiting times: positive and negative results on the Wyner-Ziv problem. The Journal of Theoret. Probab. 6 (1993), 499–519.CrossRefGoogle Scholar
[9] Wyner, A. and Ziv, J.. Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression. IEEE Trans. Inform. Th. IT-35 (1989), 125–1258.CrossRefGoogle Scholar
[10] Marton, K. and Shields, P.. Correction of ‘Entropy and the consistent estimation of joint distributions.’ Ann. Probab. Submitted.Google Scholar