Abstract
Waiting time random variables and related scan statistics have a wide variety of interesting and useful applications. In this paper, exact distribution of discrete scan statistics for the cases of homogeneous two-state Markov dependent trials as well as i.i.d. Bernoulli trials are discussed by utilizing probability generating functions. A simple algorithm has been developed to calculate the distributions. Numerical results show that the algorithm is very efficient and is capable of handling large problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Balakrishnan and M. V. Koutras, Runs and Scans with Applications, Wiley: New York, 2002.
N. Balakrishnan, S. G. Mohanty, and S. Aki, “Start-up demonstration tests under Markov dependence model with corrective actions,” Annals of the Institute of Statistical Mathematics vol. 49 pp. 155–169, 1997.
M. V. Boutsikas and M. V. Koutras, “Reliability approximation for Markov chain imbeddable systems,” Methodology and Computing in Applied Probability vol. 2 pp. 393–411, 2000.
M. Ebneshahrashoob and M. Sobel, “Sooner and later waiting time problems for Bernoulli trials: Frequency and run quotas,” Statistics & Probability Letters vol. 9 pp. 5–11, 1990.
M. Ebneshahrashoob, T. Gao, and M. Sobel, “Sequential window problems,” Sequential Analysis vol. 24 pp. 159–175, 2005.
M. J. Evans and J. S. Rosenthal, Probability and Statistics, The Science of Uncertainty, W. H. Freeman and Company: New York, 2004.
W. Feller, An Introduction to Probability Theory and Its Applications, Wiley: New York, 1957.
J. C. Fu, “Distribution of the scan statistics for a sequence of bistate trials,” Journal of Applied Probability vol. 38 pp. 908–916, 2001.
J. C. Fu and W. Y. Lou, Distribution Theory of Runs and Patterns and Its Applications, World Scientific Publisher: Singapore, 2003.
J. C. Fu, L. Q. Wang, and W. Y. Lou, “On exact and large deviation approximation for the distribution of the longest run in a sequence of two-state Markov dependent trials,” Journal of Applied Probability vol. 40 pp. 346–360, 2003.
J. Glaz and N. Balakrishnan (eds.), Scan Statistics and Applications, Birkhäuser: Boston, 1999.
J. Glaz, J. I. Naus, and S. Wallenstein, Scan Statistics, Springer-Verlag: New York, 2001.
P. Lancaster and M. Tismenetsky, The Theory of Matrices: With Applications, Academic Press: Orlando, 2nd edition, 1985.
J. I. Naus, “Probabilities for a generalized birthday problem,” Journal of the American Statistical Association vol. 69 pp. 810–815, 1974.
Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM: Philadelphia, 2003.
Author information
Authors and Affiliations
Corresponding author
Additional information
AMS 2000 Subject Classification
60J22, 60E05, 60J10
Rights and permissions
About this article
Cite this article
Ebneshahrashoob, M., Gao, T. & Wu, M. An Efficient Algorithm for Exact Distribution of Discrete Scan Statistics. Methodol Comput Appl Probab 7, 459–471 (2005). https://doi.org/10.1007/s11009-005-5003-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11009-005-5003-0