ENBIS-8 in Athens

21 – 25 September 2008 Abstract submission: 14 March – 11 August 2008

Poisson approximation for Consecutive Covering Arrays

22 September 2008, 11:47 – 11:51


Submitted by
Fotios Milienos
F.S. Milienos, M.V. Koutras,A.P. Godbole
Department of Statistics and Actuarial Science,University of Piraeus, Greece; Department of Mathematics, East Tennessee State University, USA
A k×n array with entries from a q−letter alphabet is called a t−covering array if each
t×n submatrix contains amongst its columns each one of the qt different words of length
t that can be produced by the q letters (see e.g. Colbourn (2004), Godbole et al. (1996)
and Dalal and Mallows (1998)). In the present article we study a t-covering problem
where, instead of looking at all possible t × n submatrices, we consider only submatrices
of dimension t×n with its rows being consecutive rows of the original k ×n array. In the
present work, exploiting the celebrated Stein-Chen method (Barbour et al. (1992)), we
establish a Poisson approximation result for an enumerating random variable, that counts
the number of submatrices consisting of consecutive rows of the original k × n array, in
which, at least one word is missing. Finally, a potential application in the field of factorial
designs is also included.
Keywords. t-covering arrays, consecutive covering arrays, Markov chains, random matrices,
factorial designs
[1] Barbour, A.D., Holst, L. and Janson, S. (1992). Poisson Aproximation. Oxford Univ. Press.
[2] Colbourn C.J. (2004). Combinatorial aspects of covering arrays, Le Matematiche (Catania),
58, 121-167.
[3] Dalal S.R. and Mallows C.L. (1998). Factor-covering designs for testing software. Technometrics,
40, 234-243.
[4] Godbole A.P., Skipper D.E. and R.A. Sunley (1996). t-covering arrays: upper bounds and
Poisson approximations. Combinatorics, Probability and Computing, 5, 105-118.
View paper

Return to programme