0
$\begingroup$

I'm puzzled by the measure $$E(S) = -\sum p(i) \lg p(i)$$ because I'm considering a source emitting $0, 1, 0, 1, 0, ...$ and having the maximum entropy as given by $E(S)$. Shouldn't $E(S)$ measure the quantity of information? The sequence that just repeats $1$ after $0$ seems to me to convey very little information --- contained in this very phrase.

Where am I wrong in my understanding of entropy and of $E(S)$?

$\endgroup$
  • 3
    $\begingroup$ What is the connection to cryptography? This appears to be a question that is better suited for the computer science stackexchange. $\endgroup$ – Ella Rose Feb 5 '19 at 1:40
  • 1
    $\begingroup$ there are different definitions for entropy, in this case, you can rewrite that is 0,1,repeat, so, for cryptographic definitions of entropy, 2 bytes maybe? $\endgroup$ – Richie Frame Feb 5 '19 at 1:51
  • 6
    $\begingroup$ Entropy (in the sense of the definition you give) is a property of probability distributions; it makes no sense to speak of the entropy of a sequence. $\endgroup$ – fkraiem Feb 5 '19 at 2:00
  • 1
    $\begingroup$ @yyyyyyy Why can it not be measures objectively? For example the size of the smallest algorithm (including data) on a given Turing Complete machine that can output the original data? (that would be a few bytes in this case) $\endgroup$ – RocketNuts Feb 5 '19 at 4:38
  • 4
    $\begingroup$ You are probably asking about the complexity of that sequence. The sequence itself has no entropy, and wouldn't even if it were perfectly random. The generation method, however, can exhibit entropy and that entropy is measured as the binary logarithm of the number of possible states the algorithm can be in. $\endgroup$ – forest Feb 5 '19 at 5:58
4
$\begingroup$

Let's just fill it in! Your generator has two possible outcomes, both with certain probabilities. For the every element of your sequence, you're certain about its outcome, thus:

\begin{align*} E(S)&=-p_0\log p_0 - p_1\log p_1\\ &=-p_0\log p_0 - (1-p_0)\log (1-p_0)\\ &\mathrel{\mathop{=}_{p_0\to1}} -1\log 1 - 0\\ &=-1\cdot0=0 \end{align*}

Seems like your source does not convey any information (zero bits), because indeed you already know what it will produce! Talking about entropy of a source only makes sense when the source has a stochastic behaviour; when it has an element of unpredictability.

$\endgroup$
  • 2
    $\begingroup$ @user45491 No, at any position in the produced stream one of the values has probablity 1 and the other has probability 0. $\endgroup$ – Maeher Feb 5 '19 at 11:11
  • 1
    $\begingroup$ @user45491: think of it this way. At any position in the stream, I ask you to guess the next symbol. The probability with which you will succeed is the probability we're talking about. We're not talking about "how many symbols on average". $\endgroup$ – Ruben De Smet Feb 5 '19 at 11:13
  • 1
    $\begingroup$ Interesting. I don't seem to agree. What's the probability of getting a zero given no other information? I say it's $1/2$. What's the probability of getting a zero given a one was just produced by the source? I say it's $1$. The formula $E(S)$ uses $p_i$ where $p_i$ is the proportion of symbol $i$ in the source. What do you say? $\endgroup$ – user45491 Feb 5 '19 at 11:20
  • 1
    $\begingroup$ @user45491 Welcome to entropy. It's pretty much an open question how to calculate it for a complex sequence. The Shannon log formula is pretty difficult to use as determining $i$ is well neigh impossible. That's why you're finding that $p("1") = \frac{1}{2}$, yet $p("01") = 1$ and that all the answers are different. $\endgroup$ – Paul Uszak Feb 5 '19 at 16:38
  • 2
    $\begingroup$ @user45491 Paul has been a problem on this website for a long time. We can't educate him and we can't ban him. I recommend ignoring him. $\endgroup$ – Future Security Feb 6 '19 at 13:49

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.