A Poisson approximation for the number of k-matches

Consider a sample of size n drawn with replacement from an urn with m different balls, and let Xn denote the number of k-matches, i.e. the number of times that a ball of the same color is drawn as on one of the previous k draws. This generalizes the situation studied by Arnold (1972), who investigated the waiting time until the first such duplication. We prove that the distribution of Xn can be well approximated by that of a Poisson random variable if k2 = o(m), and use the Stein-Chen method to obtain total variation bounds for this comparison. Conditions are also obtained for Poisson convergence when the balls are not equiprobable. Finally, it is shown that the variable Wn, defined as the number of k-matches when each draw is allotted a full memory window of size k, can be approximated by a Poisson random variable with the same mean provided only that k = o(m)