3
$\begingroup$

I have a question about the following statement about entropy:

If a source provides us with a sequence chosen from 4 symbols (say A, C, G, T), then the maximum average information per symbol is 2 bits. If the source provides blocks of 3 of these symbols, then the maximum average information is 6 bits per block.

In the first case, each symbol has probability 1/4 therefore the entropy is 2 bits on average -(4*1/4*log(1/4)). The second case where we are sending blocks of 3 symbols is unclear. What is the meaning of sending block of 3 symbols? Are the symbols always different or could be the same? How do we calculate the entropy of group of symbols from a set?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

By block, I assume they mean something like [AAA] or [ATC]: a set of several concatenated symbols.

We know, from the definition of joint entropy, that: $$H(X,Y,Z) = - \sum_x \sum_y \sum_z P(x,y,z) \log_2(P(x,y,z))$$ so you could calculate it directly, assuming you knew the joint distributions for $X$, $Y$, and $Z$.

Entropy is "subadditive", that is $$\begin{align} H(X) + H(Y) \lt H(X,Y) \hspace{0.1in} \textrm{if }& X \textrm{ and $Y$ are dependent} \\ H(X) + H(Y) = H(X,Y) \hspace{0.1in} \textrm{if }& X \textrm{ and } Y \textrm{ are independent} \end{align}$$ If you're willing to assume independence, the the entropy of a block is easy to calculate: it's the block length * the entropy of one element, so 3 symbols/block * 2 bits/symbol = 6 bits/block. If they are not independent or you do not know the joint distribution, then all you can say is that the entropy must be six bits or less.

Improve this answer
$\endgroup$
3
  • $\begingroup$ you wouldnt have the proof on the subadditivity of entropy would you ? I've been stuck on this for a while and your post here is the only lead I could find on the topic $\endgroup$
    – zython
    May 2, 2018 at 20:16
  • 1
    $\begingroup$ These notes from Cosma Shalizi may help: stat.cmu.edu/~cshalizi/350/2008/lectures/06a/lecture-06a.pdf (note that this sorta falls out of axiom #4 on page 2). $\endgroup$
    – Matt Krause
    May 3, 2018 at 16:06
  • $\begingroup$ thanks for replying, I had (or am still having) troubles proving it ofr thecase of dependant random variables. what you linked makes sense, but I cant understand the case for dependant variables. if you find the time and energy I'd appreciate it if you could leave me a hint at this question: stats.stackexchange.com/questions/344210/… $\endgroup$
    – zython
    May 3, 2018 at 16:19
0
$\begingroup$

The symbols could be both different and the same (any of the 64 triplets: AAA, AAC, ..., TTT). If the MAI (maximal average information) of one symbol is 2 bits, the MAI of 3 symbols is 3*2=6 bits. Another way to calculate the information is $ -(64*1/64*log_2(1/64))=6 $

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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