From: toms@fcs260c2.ncifcrf.gov (Tom Schneider)
Subject: Re: entropy estimates from a finite sample
Organization: Frederick Cancer Research and Development Center
Date: Thu, 5 Nov 1992 23:50:30 GMT

In article <1992Oct30.002041.16123@rp.CSIRO.AU> awoolf@rp.CSIRO.AU () writes:

> Given a finite number of independant samples from an
>unknown (assumed stationary) distribution, are there well-known methods for
>estimating the entropy of the source ? 

Hunh?  Won't Shannon's H function do that?

>i.e. Given a finite set of samples {x(i)} from a stationary source with
>probability distribution p(x), are there methods for forming an estimate
>of the entropy  \int p(x) log(p(x)) dx 
>(where the integral is taken over the entire space of x, which may be
>multidimensional in general).

For continuous functions there is a problem about how to put the data into
bins.  One size of bin will give different results from another, and it is not
clear to me which how to deal with this.  Should one just try various bin sizes
and maximize the uncertainty?  (It is easy to minimize - just have 1 bin!)
Maybe there is a way to avoid the bins altogether.  Anybody know methods?

> One way would be to estimate the distribution p(x)
>and then calculate the entropy on that basis.
>(There are known methods for estimating unknown distributions from
>finite samples). 

Such as...

> It would also be good to have some idea of the confidence
>limits of the entropy estimate. 

Some references on these:

@inproceedings{Miller1955,
author = "G. A. Miller",
title = "Note on the Bias of Information Estimates",
editor = "H. Quastler",
booktitle = "Information Theory in Psychology",
publisher = "Free Press",
address = "Glencoe, IL",
location = "Norlen",
pages = "95-100",
year = "1955"}

@article{Basharin1959,
author = "G. P. Basharin",
title = "On a Statistical Estimate for the Entropy
of a Sequence of Independent Random Variables",
journal = "Theory Probability Appl.",
comment = "Theory of Probability and its Applications",
volume = "4",
number = "3",
pages = "333-336",
year = "1959"}

and from yours truely:

@article{Schneider1986,
author = "T. D. Schneider
 and G. D. Stormo
 and L. Gold
 and A. Ehrenfeucht",
title = "Information content of binding sites on nucleotide sequences",
journal = "J. Mol. Biol.",
volume = "188",
pages = "415-431",
year = "1986"}

(See the appendix.)  Also:

@article{Engelbrecht1992,
author = "J. Engelbrecht
 and S. Knudsen
 and S. Brunak",
title = "{G + C}-rich Tract in $5'$ End of Human Introns",
journal = "J. Mol. Biol.",
volume = "227",
pages = "108-113",
year = "1992"}
 
They give two new papers, the first of which may not be relevant,
and the second which I have not seen:

@article{Grassberger1988,
author = "P. Grassberger", 
title = "Finite sample corrections to entropy and dimension estimates",
journal = "Phys. Letters, ser. A",
volume = "128",
pages = "369-373",
year = "1988"}

@article{Herzel1988,
author = "H. Herzel",
title = "Complexity of symbol sequences",
journal = "Anal. Model. Simul.",    
volume = "5",  
pages = "435-444",
year = "1988"}

  Tom Schneider
  National Cancer Institute
  Laboratory of Mathematical Biology
  Frederick, Maryland  21702-1201
  toms@ncifcrf.gov