Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications (Q502868)

Suppose \(U_1, U_2, \ldots, U_n\) are i.i.d. observations from a fixed but unknown distribution \((p_j)^\infty_{j=1}\) over the positive integers, let \(X_{n,j} = \sum^n_{i=1} \mathbb{I}_{\{U_i=j\}}\) be the number of times that the symbol \(j\) occurs in a sample of size \(n\). The occupancy counts \(K_{n,r}=\sum^\infty_{j=1} \mathbb{I}_{\{X_{n,j}=r\}}\) are the number of symbols that appear exactly \(r\) times in a sample of size \(n\). This paper shows that, occupancy counts and several related random quantities satisfy Bernstein-type concentration inequalities.