Poisson Approximations for the Number of kl-Scans

Consider a lecture class with a population of N students. Suppose we keep track of the order of students called upon to answer a question. Each student on the roster has l friends before his/her name and l friends after his/her name; these may be considered to be students who are lexicographically close. A kl-match occurs when two students, who are in each other’s list of 2l friends or are themselves, are called upon within the k previous questions. A large number of such occurrences might indicate that the professor is not selecting students at random. Let Xn denote the number of kl-matches within the first n questions asked by the professor, where each student has a full window of 2l + 1 friends and a full window of k previous questions. This scenario is built off of Burkhardt et al. (Stat Probab Lett 21:1–8, 1994) paper about the distribution of k-matches. The distribution of Xn, in the uniform case, is approximated by a Poisson random variable if lk2 = o(N). In the nonuniform but i.i.d. case, the distribution is also approximately Poisson. There is a relation of this problem to two-dimensional scan statistics, where one is counting numbers of events that are close in time and space.