Entropy of an information Source

Question

I'm reading 1.7 Entropy of an Information Source of Shannons paper "A Mathematical Theory of Communication"
I am kind of confused with the definition of Source entropy:
\begin{align*} H = \displaystyle\sum_{i}P_iH_i =\displaystyle\sum_{i,j}P_ip_i(j)log(p_i(j)) \end{align*} $H_i$ is the Entropy of each state i and $p_i(j)$ is the transition probability from state i to state j. As far as I understand it, it is basically the probability of state i times the Entropy of transitioning out of state i into state j ? Which for me would be the same as normal entropy which is defined as: \begin{align*} H = \displaystyle\sum_{i}p_ilog(p_i) \end{align*} Thus I would say source entropy is "just" the sum of entropy over every individual state.
Thanks for your help :)

Answer 1

The entropy (you missed a minus sign) of a source is

$$\begin{align*} H = -\displaystyle\sum_{i}p_ilog(p_i) \end{align*} $$

Now, if the source has "memory" (the succesive symbols have some dependence), what matters is not really the entropy of each emission, but the entropy rate, which is defined as

$$H_r = \lim_{n \to \infty} \frac{1}{n}H(X_1, X_2 ... X_n)$$

(here the subindices refer to the "time"). For a memory-less source (independent symbols) it's easy to see that $H_r = H$.

In the case of a stationary Markov chain, the entropy rate reduces to

$$H_r = H(X_k|X_{k-1}) = \sum_i P(X_{k-1}=i) \, H(X_k | X_{k-1}=i) = - \sum_i p_i \sum_j p_{j|i} \log p_{j|i}$$

where $p_{j|i}$ are the transition probabilities, and $p_i$ are the stationary probabilities.

For details, see any textbook (ej: Cover and Thomas, chapter 4).