Integer Sequences for Diversity Statistics

Bradley K. Moon and Noah A. Rosenberg Department of Biology Stanford University Stanford, CA 94305 USA

                     bradmoon@stanford.edu
                      noahr@stanford.edu

Abstract

Consider a discrete set of objects and a sample of size N taken with replacement from the set, producing a list of counts of the objects that corresponds to a partition of N. Two statistics that are commonly used for measuring the “diversity” of the sample are the Gini–Simpson index and the Shannon index. We study the number of possible values that these indices can take across all possible partitions of the sample size N as N increases. The two statistics are highly correlated over the set of partitions of N. However, the number of possible values that the Shannon index can take (\underline{A383683}) far exceeds the number of possible values of the Gini–Simpson index (\underline{A069999}), with the latter growing quadratically and the former growing faster than every polynomial.

1 Introduction

How does one measure the “diversity” of a set of objects drawn from a finite set of classes? The question arises in many contexts, including ecology [?], genetics [?], health services research [?], and the social sciences [?]. Consider a discrete set D of objects {1, 2, …, I}, with I ≥ 1, and N draws from D with replacement, producing counts (n_{1}, n_{2}, …, n_{I}) with ∑_{i=1}^{I} n_{i} = N. The ordered vector of counts is a sample. A diversity index is a real-valued function that is computed from a sample and that seeks to capture the “diversity” of the sample. Typically, a diversity index has its lowest value if n_{i} = N for some value of i (each draw is the same as all the others), and its highest value if n_{i} = 1 for N distinct values of i (each draw is distinct from all the others).

Two frequently used indices of diversity are the Gini–Simpson index H = 1−∑_{i=1}^{I}(n_{i}/N)^{2}, and the Shannon index S = − ∑_{i=1}^{I}(n_{i}/N) log(n_{i}/N) [?, pp. 39, 94]. The Gini–Simpson index measures the probability that two objects randomly drawn with replacement from a probability distribution with frequencies n_{i}/N are distinct. In population genetics, it is known as heterozygosity, as it computes the probability that a genotype is heterozygous— that it contains two distinct alleles—if the allele frequencies in an allele frequency distribution have values n_{1}/N, n_{2}/N, …, n_{I}/N. The Shannon index is the information-theoretic measure of the entropy of the probability distribution specified by (n_{1}/N, n_{2}/N, …, n_{I}/N). Across all possible samples of size N, the Gini–Simpson index has the property that its lowest value is 0 if n_{i} = N for some i, and if I ≥ N, its highest value is 1 − \frac{1}{N} if n_{i} = 1 for N distinct values of i. The Shannon index also has its lowest value of 0 if n_{i} = N for some i. If I ≥ N, its highest value is log N if n_{i} = 1 for N distinct values of i.

Considering only the counts in a sample and not the object labels 1, 2, …, I—that is, disregarding the order of entries in its vector—a sample is simply a partition of N. Provided that the number of distinct objects I satisfies I ≥ N, the set of all possible samples of size N corresponds to the partitions of N, where we understand each partition of N to be a non-decreasing sequence of positive integers summing to N [?, Chapter 1] (appending zeroes to extend partitions to possess length I where necessary).

Multiple partitions of N can potentially produce the same value of the Gini–Simpson index. For example, for N = 6, partitions (4, 1, 1) and (3, 3) both produce H = \frac{1}{2}. Similarly, multiple partitions can produce the same value of the Shannon index. With N = 8, partitions (4, 1, 1, 1, 1) and (2, 2, 2, 2) both produce S = 2 log 2. Because distinct partitions map to the same value of a diversity statistic, the value of the statistic does not necessarily indicate that the underlying sample possesses a specific feature, such as a specific value of its largest entry, or a specific number of nonzero entries.

In analyses of discrete data, the Gini–Simpson and Shannon indices are used in similar ways, and they are seen to have high empirical correlation coefficients. Considering all 627 partitions of N = 20, the Pearson correlation coefficient [?, p. 117] of the Gini–Simpson and Shannon indices is approximately 0.927. As we will see here, however, despite their conceptual similarity, as N grows, the number of possible values of the Shannon index far exceeds the number of possible values of the Gini–Simpson index. We study the sequences describing the number of possible values of the Gini–Simpson index and the number of possible values of the Shannon index. In particular, we review results concerning the sequence for the Gini–Simpson index and discuss new results for the sequence for the Shannon index. We also briefly discuss implications for the use of diversity statistics.

2 Relationship between the Gini–Simpson and Shannon indices

We first illustrate that the Gini–Simpson and Shannon indices have a close relationship. In particular, we show that it is possible to find bounds on the Shannon index given knowledge of only the Gini–Simpson index and the number of distinct objects I in the set D. For this computation, we work with a vector of nonnegative real numbers p_{i} with ∑_{i=1}^{I} p_{i} = 1. The Gini–Simpson index is 1 − ∑_{i=1}^{I} p_{i}^{2}, and the Shannon index is − ∑_{i=1}^{I} p_{i} log p_{i}. The analysis generalizes beyond the case in which the nonnegative real numbers (p_{1}, p_{2}, …, p_{I}) can be written (n_{1}/N, n_{2}/N, …, n_{I}/N) for integers n_{1}, n_{2}, …, n_{I} and N, with N ≤ I.

Proposition 1 (Theorem 2.7 of [?]). Let I ≥ 2. For all length-I vectors p = (p_{1}, p_{2}, …, p_{I}) of nonnegative real numbers with ∑_{i=1}^{I} p_{i} = 1 and at least two nonzero entries, writing J = ∑_{i=1}^{I} p_{i}^{2} and M = max(p_{1}, p_{2}, …, p_{I}), the following inequality holds:

\frac{1}{⌈J^{−1}⌉}(1 + \sqrt{\frac{⌈J^{−1}⌉J − 1}{⌈J^{−1}⌉ − 1}}) ≤ M ≤ \frac{1}{I}(1 + \sqrt{(IJ − 1)(I − 1)}).

It is convenient to define functions

M_{min}(J) = \frac{1}{⌈J^{−1}⌉}(1 + \sqrt{\frac{⌈J^{−1}⌉J − 1}{⌈J^{−1}⌉ − 1}}),  (1)
M_{max}(J) = \frac{1}{I}(1 + \sqrt{(IJ − 1)(I − 1)}).  (2)

These functions are monotonically increasing on [\frac{1}{I}, 1) (Lemma 2.9 of [?]).

Proposition 2 (Corollary 3.16 of [?]). Let I ≥ 2. For all length-I vectors p = (p_{1}, p_{2}, …, p_{I}) of nonnegative real numbers with ∑_{i=1}^{I} p_{i} = 1 and at least two nonzero entries, writing S = − ∑_{i=1}^{I} p_{i} log p_{i} and M = max(p_{1}, p_{2}, …, p_{I}), the following inequality holds:

⌊M^{−1}⌋M log \frac{1}{M} +(1−⌊M^{−1}⌋M) log (\frac{1}{1 − ⌊M^{−1}⌋M} ) ≤ S ≤ M log \frac{1}{M} +(1−M) log (\frac{I − 1}{1 − M} ).

Next, note that the functions in the lower and upper bounds in Proposition 2 are monotonically decreasing functions of M on the permissible domain M ∈ [\frac{1}{I}, 1). To do so, write

S_{min}(M) = ⌊M^{−1}⌋M log \frac{1}{M} + (1 − ⌊M^{−1}⌋M) log (\frac{1}{1 − ⌊M^{−1}} M⌋),  (3)
S_{max}(M) = M log \frac{1}{M} + (1 − M) log (\frac{I − 1}{1 − M} ).  (4)

For the monotonicity of the upper bound, we have dS_{max}(M)/dM = − log (\frac{M(I−1)}{1−M}). Because M ≥ \frac{1}{I}, I ≥ 2, and M < 1, we have \frac{M(I−1)}{1−M} ≥ 1, and dS_{max}(M)/dM ≤ 0 with equality if and only if M = \frac{1}{I}, so that S_{max}(M) is monotonically decreasing on [\frac{1}{I}, 1).

For the lower bound, it suffices to verify that S_{min}(M) is decreasing on intervals E_{k} = (\frac{1}{k+1}, \frac{1}{k}) for 1 ≤ k ≤ I − 1, where ⌊M^{−1}⌋ has the fixed value k, as S_{min}(M) is continuous at the interval boundaries M = \frac{1}{2}, \frac{1}{3}, …, \frac{1}{I−1} (and at M = \frac{1}{I}). On intervals E_{k}, we have that dS_{min}(M)/dM = −k log(\frac{M}{1−kM}), a negative quantity as kM < 1 and \frac{M}{1−kM} > 1 on E_{k}.

Theorem 3. Let I ≥ 2. For all length-I vectors p = (p_{1}, p_{2}, …, p_{I}) of nonnegative real numbers with ∑_{i=1}^{I} p_{i} = 1 and at least two nonzero entries, if the Gini–Simpson index