# Inverse Sampling according to Haldane (1945)

According to the inverse-sampling method (Haldane 1945) you continue sampling until m of the rare items have been found. Let p be the frequency of the rare item and q = 1-p. m is the number of rare items observed. n is the number of observations

What is now the probability that exactly n observations have been made before m rare items are observed? According to Haldane (1945) this probability is

$w_{n} = \binom{n-1}{m-1}p^{m}q^{n-m}$

Haldane then concludes that "this is the coefficient of $t^n$ in $(\dfrac{qt}{1-qt})^m$ " (Haldane 1945: 222)

He does not go more into detail here and just continues with his proof on inverse sampling. However, I have no idea to what coefficient he refers to here. Did he refer to permutations? Any ideas?

• The coefficient is perfectly well-defined: expand $(qt/(1-qt))^m$ into a power series in $t$. (The Binomial Theorem applied to $(1-qt)^{-m}$ does it immediately.)
– whuber
Commented May 9, 2016 at 20:56
• @whuber, thanks! If I expand $(qt/(1-qt))^{m}$ I get $\sum_i\binom{m+i-1}{i}qt^{i+m}$, right? I just do not see how this relates to the probability $w_n$ as defined above. Any other hints?
– DomB
Commented May 11, 2016 at 5:02
• That's not what the Binomial Theorem says. It asserts $$(1+x)^n=\sum_{i=0}^\infty\binom{n}{i}x^i.$$ You need to substitute $-qt$ for $x$ and $-m$ for $n$.
– whuber
Commented May 11, 2016 at 15:58
• @whuber! thanks. I am still not seeing it. Amongst others, I just do not see where $t^n$ pops up. I also do not really see the connection to w(n). However, I will still continue my research.
– DomB
Commented May 11, 2016 at 20:39
• The numerator $(qt)^n$ contributes a factor of $t^n$.
– whuber
Commented May 11, 2016 at 20:41

Let's do this from scratch, using only basic principles, rules of arithmetic and probability, and the (generalized) Binomial Theorem (developed first in the Seventeenth century by James Gregory and Isaac Newton).

The chance of observing one rare observation is called $p=1-q$ (and $q$ is the chance of making a "non-rare" observation).

Since all observations are assumed independent, the chance of making a sequence of $i \ge 0$ non-rare observations followed by a rare observation is $a(i+1)=pq^i$. Note that the index $i+1$ counts the rare observation along with the $i$ preceding non-rare ones.

The probability generating function for the number of observations made in order to see one rare observation matches each $a(i+1)$ with the corresponding power of an "abstract variable" $t$, thus:

$$f(t) = a(0) + a(1) t + a(2)t^2 + \cdots + a(i)t^i + \cdots = p t + pq t^2 + pq^2 t^3 + \cdots.$$

The right hand side sums a geometric series with starting value $pt$ and common ratio $qt$. In closed form this is

$$f(t) = \frac{pt}{1-qt}.$$

The probability generating function for the number of observations made in order to see $m\ge 0$ rare observations is

$$f(t)^m = \left(\frac{pt}{1-qt}\right)^m = p^m t^m \left(1-qt\right)^{-m}$$

because, according to the rules of addition and multiplication, the coefficient of $t^n$ in that power is a sum over all the possible ways to make the first, second, ..., $m^\text{th}$ rare observation. For each such way it takes the products of the chances. But that's precisely what the axioms of probability tell us to do when cases are disjoint (and no two ways are exactly the same)--you sum the chances--and independent (as assumed)--you multiply the chances.

The Binomial Theorem asserts

$$(1 + x)^k = \binom{k}{0} + \binom{k}{1}x + \binom{k}{2}x^2 + \cdots + \binom{k}{i}x^i + \cdots.$$

The sum continues until the coefficients vanish (when $k$ is a natural number) or forever (in all other cases, assuming $|x| \lt 1$). Plugging $-qt$ in for $x$ and $-m$ for $k$ expands $f(t)^m$ automatically:

$$f(t)^m = p^m t^m (1-qt)^{-m} = p^m t^m \sum_{i=0}^\infty\binom{-m}{i}(-qt)^i = \sum_{i=0}^\infty (-1)^i\binom{-m}{i}p^m q^{i}\, t^{m+i}.$$

By construction, for any $n$ the coefficient of $t^n$ in this sum is the chance of making $n$ observations before seeing $m$ rare ones, including the last observation (when the $m^\text{th}$ rare one is seen). Therefore we must inspect the term where $m+i=n$, which (since obviously $i=n-m$) is

$$w_n = (-1)^{n-m}\binom{-m}{n-m}p^m q^{n-m}.\tag{1}$$

That's a perfectly fine answer, (and explains why such distributions are often termed "negative binomial") but it doesn't exactly match Haldane's expression. It's easy to see why the answers give the same values, though. The Binomial coefficients are computed as fractions. The denominator is just $(n-m)! = 1(2)(3)\cdots(n-m)$. The numerator starts with $-m$, then counts down $n-m$ places $-m-1, -m-2, \ldots, -m-(n-m)+1 = 1-n$ and multiplies them all. Since all these terms are non-positive, it is tempting to absorb the factor of $(-1)^{n-m}$ simply by negating each of these $n-m$ values. Thus, provided $m\ge 1$,

$$(-1)^{n-m}\binom{-m}{n-m} = \frac{(m)(m+1)(m+2)\cdots(n-1)}{(n-m)!} = \binom{n-1}{n-m} = \binom{n-1}{m-1}.$$

Substituting this into $(1)$ yields

$$w_n = \binom{n-1}{m-1}p^m q^{n-m},$$

QED.