Determining Bounds on Integrals with Applications to Cataloging Problems

Assume that a random sample of size N has been drawn from a multinomial population with an unknown and perhaps countably infinite number of classes. Hence, if Xⱼ is the jth observation, and Mᵢ the ith class, then P\Xⱼ Mᵢ\ = pᵢ 0 i = 1, 2, ; for all j, and ^₁ pᵢ = 1. If the number of classes is finite, then pᵢ = 0, for all i > S, where S is the number of classes. We do not suppose the classes to have a natural ordering, since the classes may be species of insects, or chess openings. Let nᵣ be the number of classes which occur exactly r times in the sample. Then ⁱnftyₑ = ₀ rnᵣ = N d = Nₑ = ₁ nᵣ where d is the number of distinct classes observed in the sample. It is the purpose of this paper to present some techniques to aid the experimenter in answering the following kinds of questions. 1) Prediction of the number of distinct classes that will be observed in a second sample of size N, 1. 2) Prediction of the number of additional classes that will be observed when the sample size is increased by (- 1) N additional observations. 3) Estimation of the coverage of the sample, where coverage, denoted by C, is defined as follows: equation*1C = ⱼ pⱼ. equation* The sum is to be taken over those classes for which at least one representative has been observed. 4) Prediction of the coverage of a second sample of size N. 5) Prediction of the increased coverage to be obtained when the sample size is augmented by (- 1) N additional observations. Let d () and C () denote the number of classes and coverage obtained from N observations, either in the case of a second sample, or an augmented sample. Subsequently, we will show that equation*2 Ed () d + n₁ E\1 - e^{- (-1) xx\}equation* and equation*3EC () 1 - n₁N + n₁N E\1 - e^{- (-1) x\}equation* where the expectations on the right hand side of (2) and (3) are taken with respect to F (x), a constructed cumulative distribution function on 0, ), which is unknown to the experimenter, but estimates of the moments of this distribution are available. It will be shown that equation*4ᵣ (r + 1) ! (nₑ+₁) n₁equation* where ᵣ = ^₀ xʳ dF (x). Hence, a reasonable procedure is to compute upper (lower) predictors for d () and C () by computing the supremum (infimum) of (2) and (3) respectively, where the supremum (infimum) is taken over all cumulative distribution functions whose first k moments are specified by (4). It will be shown that (x) = 1 - e^- (-1) xx (x) = 1 - e^- (-1) x may be treated identically in the computation of extrema with the observation that the computation of the supremum of E\ (x) \ will be identical with the computation of the infimum of E\ (x) \; and similarly for the computation of the infimum of E\ (x) \. Thus, we will restrict the discussion to (x). The solution will be of the form equation*5 () E\ (x) \ = ʳ₈ = ₁ ᵢ (xᵢ) equation* where ᵢ 0, ʳ₈ = ₁ ᵢ = 1 and xᵢ belongs to the extended non-negative real numbers. To determine the xᵢ and ᵢ, the following system of equations must be solved. equation*6split₁x₁ + ₂x₂ + + ᵣxᵣ = ₁\\ ₁x²₁ + ₂x²₂ + + ᵣx²ᵣ = ₂\\. . . . . . . . . . . . . . . . . . . . . . . . . . . \\ ₁xᵏ₁ + ₂xᵏ₂ + + ᵣxᵏᵣ = ₖsplitequation* where x₁ x₂ xᵣ. If k = 2c, c an integer, the supremum will be obtained by solving (6), with x₁ = 0, r (k + 2) /2, and x₂, , xᵣ interior points of 0, ). If k = 2c + 1, the solution of (6) will coincide with that for k - 1 with the addition of a mass point at infinity, with mass tending to zero at a rate which will satisfy the kth moment constraint. Since () = 0, no change in (5) is obtained by the addition of the kth moment constraint. If k = 2c + 1, the infimum is obtained by solving (6) with r (k + 1) /2 and the xᵢ are all interior points of 0, ). If k = 2c, c > 0, the solution of (6) is obtained from that for k - 1 by the addition of a mass point at infinity with mass tending to zero at a rate which will satisfy the last moment constraint. Explicit solutions are computed for k 3, and applied to several examples. In addition, the low order moments of d, nᵣ, and C are computed, and the asymptotic sampling error of C (1) = 1 - (n₁/N) as an estimate of sample coverage is given. It will be convenient before proceeding to the general problem to compute the low order moments of d, nᵣ, C.