Generalized k-matches

Suppose that an urn contains m distinguishable balls, and that these balls are sampled (with replacement), thus generating a sequence of colors. Many questions can be asked about this sequence; the distribution of the time until a color is sampled twice within a memory window of size k (i.e., the waiting time till the first k-match) was derived by Arnold (1972). Next, Burghardt et al. (1994) proved that the limiting distribution of the number of k-matches in the first n draws is Poisson if k = o(m). An even more general question is discussed here: if, for every draw from the urn, a random k-sample is taken of the previous draws, what is the distribution of the number of generalized k-matches? Our solution resolves a question of Glen Meeden (see Arnold, 1972). Extensions to the case where the k-sample is drawn from the (union of the) past and the future are provided, and the case of non-uniform selection probabilities is treated. © 1998 Elsevier Science B.V. All rights reserved