Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T09:33:07.634Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximum Waiting Times are Asymptotically Independent

Published online by Cambridge University Press:  12 September 2008

Tamás F. Móri
Tamás F. Móri
Affiliation:
Department of Probability Theory and Statistics, Eötvös Loránd University, H-1088 Budapest
Get access Rights & Permissions [Opens in a new window]

Abstract

For every n consider a subset Hn of the patterns of length n over a fixed finite alphabet. The limit distribution of the waiting time until each element of Hn appears in an infinite sequence of independent, uniformly distributed random letters was determined in an earlier paper. This time we prove that these waiting times are getting independent as n → ∞. Our result is used for applying the converse part of the Borel–Cantelli lemma to problems connected with such waiting times, yielding thus improvements on some known theorems.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 3 , September 1992 , pp. 251 - 264
Copyright
Copyright © Cambridge University Press 1992

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

[1]Benczür, A. (1986) On the expected time of the first occurrence of every k bit long patterns in the symmetric Bernoulli process. Ada Math. Hungar. 47 233–238.CrossRefGoogle Scholar
[2]Erdös, P. and Chen, R. W. (1988) Random walks on Z2n. J. Multivar. Anal. 25 111–118.CrossRefGoogle Scholar
[3]Erdöos, P. and Rényi, A. (1959) On Cantor's series with convergent Σl/qn. Annales Univ. Sci. Budapest. R. Eötvöos Norn., Sect. Math. 2 93–109.Google Scholar
[4]Li, S. R. (1980) A martingale approach to the study of occurrence of sequence patterns in repeated experiments. Ann. Probab. 8 1171–1176.CrossRefGoogle Scholar
[5]Móri, T. F. (1985) Large deviation results for waiting times in repeated experiments. Ada Math., Hungar. 45 213–221.CrossRefGoogle Scholar
[6]Móri, T. F. (1987) On the expectation of the maximum waiting time. Annales Univ. Sci. Budapest. R. Eötvös Norn., Sect. Comput. 7 111–115.Google Scholar
[7]Móri, T. F. (1987) Maximum waiting time when the size of the alphabet increases. In: Mathematical Statistics and Probability Theory, Vol. B (Bad Tatzmannsdorf, 1986), Reidel, Dordrecht, 169–178.CrossRefGoogle Scholar
[8]Móri, T. F. (1989) On the number of patterns preceding a given one. Studia Sci. Math. Hungar. 24 355–364.Google Scholar
[9]Móri, T. F. (1991) On the waiting time till each of some given patterns occurs as a run. Probab. Th. Rel. Fields 87 313–323.CrossRefGoogle Scholar
[10]Móri, T. F. (1990) More on the waiting time till each of some given patterns occurs as a run. Can. J. Math. 42 915–932.CrossRefGoogle Scholar
[11]Móri, T. F. (to appear). How homogeneous can the last appearing pattern be? Random Structures and Algorithms.Google Scholar
[12]Móri, T. F. (to appear). Asymptotic joint distribution of cover times. In: Godbole, A. P. and Papastavridis, S. G. (eds.), Runs and Patterns in Probability: Selected Papers, Marcel Dekker.Google Scholar