Consecutive covering arrays and a new randomness test

A k×nk×n array with entries from an “alphabet” A={0,1,…,q−1}A={0,1,…,q−1} of size q is said to form a t  -covering array (resp. orthogonal array) if each t×nt×n submatrix of the array contains, among its columns, at least one (resp. exactly one) occurrence of each t  -letter word from AA (we must thus have n=qtn=qt for an orthogonal array to exist and n≥qtn≥qt for a t-coveringt-covering array). In this paper, we continue the agenda laid down in Godbole et al. (2009) in which the notion of consecutive covering arrays   was defined and motivated; a detailed study of these arrays for the special case q=2q=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=Wk,n,tW=Wk,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 ( Arratia et al., 1989 and Arratia et al., 1990) to provide upper bounds on the total variation error incurred while approximating L(W)L(W) by a Poisson distribution Po(λ)Po(λ) 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.