×

Consecutive covering arrays and a new randomness test. (M25.) (English) Zbl 1279.62044

Summary: A \(k\times n\) array with entries from an “alphabet” \(\mathcal A = \{0,1,\dots,q-1\}\) of size \(q\) is said to form a \(t\)-covering array (resp. orthogonal array) if each \(t\times n\) submatrix of the array contains, among its columns, at least one (resp. exactly one) occurrence of each \(t\)-letter word from \(\mathcal A\) (we must thus have \(n=qt\) for an orthogonal array to exist and \(n\geq q^t\) for a \(t\)-covering array). In this paper, we continue the agenda laid down in [A. P. Godbole et al., “Binary consecutive covering arrays”, to appear in Ann. Inst. Statist. Math.] in which the notion of consecutive covering arrays was defined and motivated; a detailed study of these arrays for the special case \(q=2\), has also carried out by the same authors. In the present article we use first a Markov chain embedding method to exhibit, for general values of \(q\), the probability distribution function of the random variable \(W=W_{k,n,t}\) defined as the number of sets of \(t\) consecutive rows for which the submatrix in question is missing at least one word. We then use the Chen-Stein method [R. Arratia et al., Ann. Probab. 17, No. 1, 9–25 (1989; Zbl 0675.60017); Stat. Sci. 5, No. 4, 403–434 (1990; Zbl 0955.62542)] to provide upper bounds on the total variation error incurred while approximating \(\mathcal L(W)\) by a Poisson distribution \(Po(\lambda )\) with the same mean as \(W\). Last but not least, the Poisson approximation is used as the basis of a new statistical test to detect run-based discrepancies in an array of \(q\)-ary data.

MSC:

62F03 Parametric hypothesis testing
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
05B15 Orthogonal arrays, Latin squares, Room squares
62E17 Approximations to statistical distributions (nonasymptotic)
62H10 Multivariate distribution of statistics
Full Text: DOI

References:

[1] Agin, M.; Godbole, A., A new exact runs test for randomness, (Page, C.; LePage, R., Computing Science and Statistics (1992), Springer: Springer New York), 281-285
[2] Aki, S.; Hirano, K., Waiting time problems for a two-dimensional pattern, Annals of the Institute of Statistical Mathematics, 56, 169-182 (2004) · Zbl 1057.60013
[3] Arratia, R. L.; Goldstein, L.; Gordon, L., Two moments suffice for Poisson approximations: the Chen-Stein method, Annals of Probability, 17, 9-25 (1989) · Zbl 0675.60017
[4] Arratia, R. L.; Goldstein, L.; Gordon, L., Poisson approximation and the Chen-Stein method, Statistical Science, 5, 403-423 (1990) · Zbl 0955.62542
[5] Balakrishnan, N.; Koutras, M. V., Runs, scans and applications (2002), Wiley: Wiley New York · Zbl 0991.62087
[6] Barbour, A. D.; Holst, L.; Janson, S., Poisson Approximation (1992), Clarendon Press: Clarendon Press Oxford · Zbl 0746.60002
[7] Campbell, S.; Godbole, A.; Schaller, S., Discriminating between sequences of Bernoulli and Markov-Bernoulli trials, Communications in Statistics—Theory and Methods, 23, 2787-2814 (1994) · Zbl 0850.62102
[8] Charalambides, Ch. A., Enumerative Combinatorics (2002), Chapman & Hall, CRC Press: Chapman & Hall, CRC Press Boca Raton, FL · Zbl 1001.05001
[9] Colbourn, C. J., Combinatorial aspects of covering arrays, Le Matematiche (Catania), 58, 121-167 (2004)
[10] Dalal, S. R.; Mallows, C. L., Factor-covering designs for testing software, Technometrics, 40, 234-243 (1998)
[11] Feller, W., 1968. An Introduction to Probability Theory and its Applications, vol. I, third ed. Wiley, New York.; Feller, W., 1968. An Introduction to Probability Theory and its Applications, vol. I, third ed. Wiley, New York. · Zbl 0155.23101
[12] Fu, J. C.; Koutras, M. V., Distribution theory of runs: a Markov chain approach, Journal of the American Statistical Association, 89, 1050-1058 (1994) · Zbl 0806.60011
[13] Fu, J. C.; Lou, W. Y.W., Distribution Theory of Runs and Patterns and its Applications: A Finite Markov Chain Imbedding Approach (2003), World Scientific: World Scientific Singapore · Zbl 1030.60063
[14] Godbole, A. P., Applications of the Stein-Chen method to the theory of patterns and runs: an annotated bibliography, (Godbole, A. P.; Papastavridis, S. G., Runs and Patterns in Probability (1994), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 253-261 · Zbl 0832.60015
[15] Godbole, A.P., Koutras, M.V., Milienos, F.S., 2009. Binary consecutive covering arrays. Annals of the Institute of Statistical Mathematics, available online; Godbole, A.P., Koutras, M.V., Milienos, F.S., 2009. Binary consecutive covering arrays. Annals of the Institute of Statistical Mathematics, available online · Zbl 1333.62189
[16] Godbole, A. P.; Skipper, D. E.; Sunley, R. A., \(t\)-covering arrays: upper bounds and Poisson approximations, Combinatorics, Probability & Computing, 5, 105-118 (1996) · Zbl 0865.60008
[17] Hartman, A., Software and hardware testing using combinatorial covering suites, (Golumbic, M.; Hartman, A., Interdisciplinary Applications of Graph Theory, Combinatorics and Algorithms (2006), Springer: Springer Berlin), 237-266 · Zbl 1089.68023
[18] Hedayat, A. S.; Sloane, N. J.A.; Stufken, J., Orthogonal Arrays (1999), Springer: Springer New York · Zbl 0935.05001
[19] Katona, G., Two applications (for search theory and truth functions) of Sperner type theorems, Periodica Mathematica Hungarica, 3, 19-26 (1973) · Zbl 0266.05001
[20] Kleitman, D.; Spencer, J., Families of \(k\)-independent sets, Discrete Mathematics, 6, 255-262 (1973) · Zbl 0269.05002
[21] Koutras, M. V., Applications of Markov chains to the distribution theory of runs and patterns, (Shanbhag, D. N.; Rao, C. R., Handbook of Statistics, Stochastic Processes, Modeling and Simulation (2003), Elsevier: Elsevier Netherlands) · Zbl 1023.60010
[22] Koutras, M. V.; Alexandrou, V. A., Runs, scans and urn model distributions: a unified Markov chain approach, Annals of the Institute of Statistical Mathematics, 47, 743-766 (1995) · Zbl 0848.60021
[23] Renyi, A., Foundations of Probability (1971), Wiley: Wiley New York · Zbl 0203.49801
[24] Sloane, N. J.A., Covering arrays and intersecting codes, Journal of Combinatorial Designs, 1, 51-63 (1993) · Zbl 0828.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.