8
$\begingroup$

Information entropy, $IE$, is defined as:

$$IE = \sum_{i} p_i log\frac{1}{p_i}$$

Where $p_i$ is the probability of event $i$ (and we are summing over all possible events).

Let's say I have data only, and estimate $p_i$, with $\hat{p_i}$, where:

$$\hat{p_i} = \frac{n_i}{N}$$

Where $n_i$ is the number of occurances of event $i$ in the data, and $N$ is the total number of observations. Then I can estimate $IE$ with $\hat{IE}$ as:

$$ \hat{IE} = \sum_{i} \hat{p_i} log\frac{1}{\hat{p_i}}$$

Is there a way to analytically find, say, a 95% confidence interval on $\hat{IE}$?

$\endgroup$
  • $\begingroup$ The problem is, the "plug-in" estimate, i.e., first estimate the distribution, and then compute the entropy is not always the best estimate for the entropy. This will very much depend on the distribution of your data. Do you have a class of probability distributions that you want to consider as possibilities? $\endgroup$ – kodlu Apr 30 '15 at 23:56
  • $\begingroup$ @kodlu I had a multinomial distribution in mind: The data is $i.i.d. Multinomial(p_1, p_2, ..., p_k)$. So $\hat{p_i}$ is the maximum likelihood estimate of $p_i$. I guess the distribution of $\hat{p_i}$ first needs to be determined? $\endgroup$ – applecider May 1 '15 at 0:06
  • $\begingroup$ The general question is not so well posed, since the minimum probability event contributes $\log(1/p_{min}),$ so it becomes significant as $p_{min}$ gets smaller and smaller. Under the assumption of a lower bound on $p_{min}$ something better can be done. Also if $n$ is very large, a lot of samples are required before all events are seen. $\endgroup$ – kodlu Jun 7 '15 at 10:06
  • $\begingroup$ I have a similar problem, only it is against a stream of data. I can know the random chance of each event, but I need to know how to calculate my confidence for a given number of sampled events to make a statement about the entropy of the stream. $\endgroup$ – Pete Mancini Oct 28 '15 at 15:20
  • $\begingroup$ $\exp(-N S)$ where $S = -\sum_i p_1 \log\left(\frac{p_i}{q_i}\right)$ and $q_i$ are the true probabilities, is the conditional probability of observing your data given the true probability distribution. So, you can get to reasonable estimates of the true probability distribution and its entropy given your observations using Bayes' theorem and other information you may have about the true probability distribution. $\endgroup$ – Count Iblis Mar 29 '17 at 1:55
1
$\begingroup$

Let the total number of events be $K$ and let $X_1, X_2, \ldots X_N$ be a random sample of events where $X_i = j$ means that the sample $X_i$ corresponds to event $j$ and the probability of happening of event $j$ be $p_j$ (note that $j\leq K$). The estimated value of $p_j$ be $\hat{p_j}$ which is given by,

$\hat{p_j} = \frac{\sum\limits_{i=1}^{N}\mathbb{I}(X_i=j)}{N}$, where $\mathbb{I}$ is the indicator function.

Let us denote $\vec{T}=(\hat{p_1}, \hat{p_2}, \ldots, \hat{p_K})$, $\vec{\theta} = (p_1, p_2, \ldots, p_K)$ and $g(\vec{x}) = \sum\limits_{i=1}^{K}x_i\log\frac{1}{x_i}$, then using the first order taylor approximation, we get,

$g(\vec{T}) \approx g(\vec{\theta}) + \sum\limits_{i=1}^{K}g^{'}_{i}(\vec{\theta})(T_i-\theta_i)$

and therefore,

$E(g(\vec{T})) \approx g(\vec{\theta})$, because $E(T_i) = \theta_i$

$Var(g(\vec{T})) \approx E((g(\vec{T})-g(\vec{\theta}))^2) \\ \approx E((\sum\limits_{i=1}^{K}g^{'}_{i}(\vec{\theta})(T_i-\theta_i))^2)\\ = \sum\limits_{i=1}^{K}(g^{'}_{i}(\theta))^2Var(T_i) + 2\sum\limits_{i>j}g^{'}_{i}(\theta)g^{'}_{j}(\theta)Cov(T_i,T_j)$

Assuming zero covariance between $T_i$ and $T_j$, we get,

$Var(g(\vec{T})) \approx \sum\limits_{i=1}^{K}(g^{'}_{i}(\theta))^2Var(T_i) \\ = \sum\limits_{i=1}^{K}(\log(\frac{1}{p_i})-1)^2.\frac{p_{i}(1-p_{i})}{N} \\ = \sum\limits_{i=1}^{K}(\log(p_i)+1)^2.\frac{p_{i}(1-p_{i})}{N}$

Now, to get an estimate of above variance, substitute $\hat{p_i}$ with $p_i$. Note that the above method gives an approximate value of the variance of estimate of information entropy. To compute the confidence interval, one needs to know the distribution of $g(\vec{T})$. If the sample size is very large i.e. $N \rightarrow \infty$, then by using the multivariate extension of transformation based central limit theorem, one can show in our case that,

$\sqrt{N}(g(\vec{T}) - g(\vec{\theta})) \rightarrow \mathcal{N}(0,\sum\limits_{i=1}^{K}(\log(p_i)+1)^2.\frac{p_{i}(1-p_{i})}{N})$

and thereafter it is easy to compute any confidence interval for $g(\vec{T})$.

Let me know if something is not clear.

$\endgroup$
  • $\begingroup$ Correct me if I'm wrong but $Cov(T_i,T_j) = - \frac{p_i p_j}{N} \neq 0$, and $Cov(T_i,T_j)$ and $Var(T_i)$ have roughly the same order of magnitude. So I think you cannot neglect the second term but not the first when calculating $Var(g(\vec{T}))$. $\endgroup$ – zaphodef Jun 29 '18 at 14:55
0
$\begingroup$

Basharin answered this (implicitly) in "On a Statistical Estimate for the Entropy of a Sequence of Independent Random Variables". Teor Veroyatnost i Primenen. 1959;4(3):361–364. English version at https://epubs.siam.org/doi/10.1137/1104033.

He calculated bias and variance for the estimator of Shannon entropy given above, and showed that the estimator is consistent and asymptotically normal estimate. Thus for a large enough data set, one should be able to use approximate Gaussian confidence intervals. Basharin's variance estimator is $${\mbox{Var}}\left[\hat{H}\right] = \frac{1}{N} \left[ \sum_{i=1}^s p_i \big( \log_2 p_i \big)^2 - H^2 \right] + O\left( \frac{1}{N^2} \right). $$

Basharin also calculates the bias though, which is important for smaller samples, however in these cases Gaussianity may be a poor approximation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.