This is an old revision of the document!
Estimate entropy of a finite discrete system using limited samples
Following idea of:
Consider a system with a state space of the size $|\mathbb{X}| = \Gamma$ with equal probability. The entropy is given by \begin{align} H & = - \sum_{x\in\mathbb{X}} \frac{1}{\Gamma} \ln\frac{1}{\Gamma} \\ & = \ln \Gamma . \end{align} The objective is to estimate $\Gamma$ by sampling the space $\mathbb{X}$. The only information we have is whether a sampled point is the same as the other: $\delta_{x_i,x_j}$.
The consideration of Ma is that the number of repeats or the number of coincident pairs in the sequence of length $N$ is dependent on the space size $\Gamma$. If the sequence has zero correlation time and the element are drawn independently from the space, the chance of finding a pair to be coincident ($x_i=x_j$) is estimated by $P_\mathrm{c} = \Gamma^{-1}$. Since there are $N(N-1)/2$ pairs in a sequence of length $N$, the expected number of coincident pairs is given by \begin{equation} N_\mathrm{c} = \frac{N(N-1)}{2\Gamma}. \end{equation}