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 o 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} e {X_{i}}_{1}; j e i_{1}, i_{2}, ..., i_{r}

; and, last but not least, the multivariate vector

Z_{A B} = (Y_{A}, Y_{A + 1}, ..., Y_{B})

. We provide Poisson approximations for the distributions of

W

,

Y_{r}

and

Z_{A B}

under some general conditions. New results on the joint distribution of cell counts in the occupancy problem are derived as a corollary.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: Competition between discrete random variables, with applications to occupancy problems