Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-13T22:04:24.652Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximate probabilities for runs and patterns in i.i.d. and Markov-dependent multistate trials

Part of:Distribution theory - ProbabilityMarkov processes

Published online by Cambridge University Press:  01 July 2016

James C. Fu and
Brad C. Johnson
James C. Fu*
Affiliation:
University of Manitoba
Brad C. Johnson*
Affiliation:
University of Manitoba
*
∗ Postal address: Department of Statistics, University of Manitoba, Winnipeg, Canada R3T 2N2.
∗ Postal address: Department of Statistics, University of Manitoba, Winnipeg, Canada R3T 2N2.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let X n (Λ) be the number of nonoverlapping occurrences of a simple pattern Λ in a sequence of independent and identically distributed (i.i.d.) multistate trials. For fixed k, the exact tail probability P{Xn (∧) < k} is difficult to compute and tends to 0 exponentially as n → ∞. In this paper we use the finite Markov chain imbedding technique and standard matrix theory results to obtain an approximation for this tail probability. The result is extended to compound patterns, Markov-dependent multistate trials, and overlapping occurrences of Λ. Numerical comparisons with Poisson and normal approximations are provided. Results indicate that the proposed approximations perform very well and do significantly better than the Poisson and normal approximations in many cases.

Keywords

Finite Markov chain imbeddingrate functionsmultistate trial

MSC classification

Primary:60E05: Distributions
Secondary:60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 41 , Issue 1 , March 2009, pp. 292 - 308
Copyright
Copyright © Applied Probability Trust 2009 

Footnotes

This work was supported in part by the Natural Sciences and Engineering Research Council of Canada.

References

Arratia, R., Goldstein, L. and Gordon, L. (1990). Poisson approximation and the Chen–Stein method. Statist. Sci. 5, 403–434.Google Scholar
Barbour, A. D., Chryssaphinou, O. and Roos, M. (1996). Compound Poisson approximation in systems reliability. Naval Res. Logistics 43, 251–264.3.0.CO;2-9>CrossRefGoogle Scholar
Fu, J. C. and Koutras, M. V. (1994). Distribution theory of runs: a Markov chain approach. J. Amer. Statist. Assoc. 89, 1050–1058.CrossRefGoogle Scholar
Fu, J. C. and Lou, W. Y. W. (2003). Distribution Theory of Runs and Patterns and Its Applications. World Scientific, River Edge, NJ.CrossRefGoogle Scholar
Fu, J. C., Wang, L.and Lou, W. Y. W. (2003). On exact and large deviation approximation for the distribution of the longest run in a sequence of two-state Markov dependent trials. J. Appl. Prob. 40, 346–360.CrossRefGoogle Scholar
Godbole, A. P. (1991). Poisson approximations for runs and patterns of rare events. Adv. Appl. Prob. 23, 851–865.CrossRefGoogle Scholar
Godbole, A. P. and Schaffner, A. A. (1993). Improved Poisson approximations for word patterns. Adv. Appl. Prob. 25, 334–347.CrossRefGoogle Scholar
Mood, A. M. (1940). The distribution theory of runs. Ann. Math. Statist. 11, 367–392.CrossRefGoogle Scholar
Riordan, J. (1958). An Introduction to Combinatorial Analysis. John Wiley, New York.Google Scholar
Wald, J. and Wolfowitz, J. (1940). On a test whether two samples are from the same population. Ann. Math. Statist. 11, 147–162.CrossRefGoogle Scholar
Wishart, J. and Hirschfeld, H. O. (1936). A theorem concerning the distribution of Joins between line segments. J. London Math. Soc. 11, 227–235.CrossRefGoogle Scholar
Wolfowitz, J. (1943). On the theory of runs with some applications to quality control. Ann. Math. Statist. 14, 280–288.CrossRefGoogle Scholar