Good–Turing frequency estimation is a statistical technique for estimating the probability of encountering an object of a hitherto unseen species, given a set of past observations of objects from different species. In drawing balls from an urn, the 'objects' would be balls and the 'species' would be the distinct colours of the balls (finite but unknown in number). After drawing R red {\displaystyle R_{\text{red}}} red balls, R black {\displaystyle R_{\text{black}}} black balls and R green {\displaystyle R_{\text{green}}} green balls, we would ask what is the probability of drawing a red ball, a black ball, a green ball or one of a previously unseen colour.
Historical background Good–Turing frequency estimation was developed by Alan Turing and his assistant I. J. Good as part of their methods used at Bletchley Park for cracking German ciphers for the Enigma machine during World War II. Turing at first modelled the frequencies as a multinomial distribution, but found it inaccurate. Good developed smoothing algorithms to improve the estimator's accuracy. The discovery was recognised as significant when published by Good in 1953, but the calculations were difficult so it was not used as widely as it might have been. The method even gained some literary fame due to the Robert Harris novel Enigma. In the 1990s, Geoffrey Sampson worked with William A. Gale of AT&T to create and implement a simplified and easier-to-use variant of the Good–Turing method described below. Various heuristic justifications and a simple combinatorial derivation have been provided.
The method The Good–Turing estimator is largely independent of the distribution of species frequencies.
Notation Suppose that X {\displaystyle X} distinct species have been observed, enumerated 1 , … , X {\displaystyle 1,\dots ,X} . Then the frequency vector, R ¯ {\displaystyle {\bar {R}}} , has elements R x {\displaystyle R_{x}} that give the number of individuals that have been observed for species x {\displaystyle x} . The frequency of frequencies vector, ( N r ) r = 0 , 1 , … {\displaystyle (N_{r})_{r=0,1,\ldots }} , shows how many times the frequency r {\displaystyle r} occurs in the vector R ¯ {\displaystyle {\bar {R}}} (i.e., among the elements R x {\displaystyle R_{x}} ):
N r = | { x ∣ R x = r } | . {\displaystyle N_{r}={\Bigl |}\left\{x\mid R_{x}=r\right\}{\Bigr |}.}
For example, N 1 {\displaystyle N_{1}} is the number of species for which only one individual was observed. Note that the total number of objects observed, N {\displaystyle N} , can be found from
N = ∑ r = 1 ∞ r N r = ∑ x = 1 X R x . {\displaystyle N=\sum _{r=1}^{\infty }rN_{r}=\sum _{x=1}^{X}R_{x}.}
Calculation The first step in the calculation is to estimate the probability that a future observed individual (or the next observed individual) is a member of a thus far unseen species. This estimate is
p 0 = N 1 N . {\displaystyle p_{0}={\frac {N_{1}}{N}}.}
The next step is to estimate the probability that the next observed individual is from a species which has been seen r {\displaystyle r} times. For a single species this estimate is
p r = ( r + 1 ) S ( N r + 1 ) N S ( N r ) . {\displaystyle p_{r}={\frac {(r+1)S(N_{r+1})}{NS(N_{r})}}.}
… excerpt ends here. Continue reading the full article.
