Competition between discrete random variables, with applications to occupancy problems

Abstract Consider n players whose “scores” are independent and identically distributed values { X i } i = 1 n from some discrete distribution F . We pay special attention to the cases where (i) F is geometric with parameter p → 0 and (ii) F is uniform on { 1 , 2 , … , N } ; the latter case clearly corresponds to the classical occupancy problem. The quantities of interest to us are, first, the U -statistic W which counts the number of “ties” between pairs i , j ; second, the univariate statistic Y r , which counts the number of strict r -way ties between contestants, i.e., episodes of the form X i 1 = X i 2 = ⋯ = X i r ; X j ≠ X i 1 ; j ≠ i 1 , i 2 , … , i r ; and, last but not least, the multivariate vector Z AB =( Y A , Y A +1 ,…, Y B ). We provide Poisson approximations for the distributions of W , Y r and Z AB under some general conditions. New results on the joint distribution of cell counts in the occupancy problem are derived as a corollary.