0
$\begingroup$

Taking into account the Shannon entropy, I was wondering that, if we have a String like $1122344444455$ , is this possible to find out the entropy of digit $4$ in this String? In other words, I would like to know if we can find a way to measure the degree of uncertainty of occurrence of digit $4$ in this String. Is this the responsibility of Relative entropy?

$\endgroup$
0
$\begingroup$

Entropy is a measure of how much information there is in one source with one probability distribution. Relative entropy is a measure how close or distant one probability distribution is to another. If you have one probability distribution you wish to test against your string then you could calculate a relative entropy.

Entropy can be defined as $$E(k) = \sum_{\forall i} -p_i\log_k(p_i)$$, which is the expected value of the logarithm of the probabilities. What is interesting here is that each $p_i$ occurs only in one term of this sum. So each outcome contributes with an own addition to the entropy.

It seems I need to clarify some words. If we consider (1,2,3,4,5) to be the "alphabet" ( in language of probability : the set of possible outcomes ). Each element (like "4") can be called a "symbol". Using these words instead of probability words are common to do in information theory. Which could be one of the tags the bot wanted us to add to the question.

The entropy of "4" is the expected number of bits on average we would need to store "4". 6 out of 13 symbols are "4". Let us for simplicity guess that 6 out of 12 or 7 out of 14 are "4". Then 4 would occur almost half of the symbols. The entropy (in binary digits) would then be $-\frac{1}{2} \log_2\left(\frac{1}{2}\right) = \frac{1}{2}$ which means that on average we would need 1/2 bits per symbol to consider if it was a "4" or not.

Having an entropy of 1/2 means that if "4" occurs on average 1 in 2 symbols we should need on average 1/2 bit per symbol to tell if it was a 4.


The thing with Relative Entropy or Kullback-Leibler Divergence is that it requires two distributions, we got to have some second distribution to compare against. Once we have that it's just to follow the formula on the wikipedia page. It's very straight forward.

$\endgroup$
  • $\begingroup$ What do you mean half bits per symbol? what is the symbol in here? the whole stream of digits? $\endgroup$ – lonesome Dec 13 '15 at 15:59
  • $\begingroup$ I would also like to point out that in here, these digits are a symbol of a system response. Consider there is a relevancy feedback system that returns an answer to a query. So my aim is to show that how unexpected are the results of this system. In other words, the system should make as diverse response as possible to the different queries. So if we get the idea that this system is giving quite similar answers for different queries, then we conclude this system might has a low throughput. As a result, my question here is that if I am using right way of using entropy here? $\endgroup$ – lonesome Dec 13 '15 at 16:04
  • $\begingroup$ Yes relative entropy could be a useful measure for how unexpected or deviating something is in the strings. $\endgroup$ – mathreadler Dec 13 '15 at 16:15
  • $\begingroup$ Alright, then why did you not explain anything about how to compute the relative entropy of 4 in this String? Because I have a little bit of hard time getting it into my head. After reading your edited answer, I got some more clues of entropy but what about the relative one? Can you also explain it with the digit 4 in here? $\endgroup$ – lonesome Dec 13 '15 at 16:27
  • $\begingroup$ Because relative entropy needs two distributions and we only have one. $\endgroup$ – mathreadler Dec 13 '15 at 16:56

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.