Teoria Informacji - zadanie

Question

Nie jestem pewien czy zamieszczam to pytanie w odpowiedniej kategorii ani nawet czy na prawidłowym forum ale nie mam pojęcia gdzie powinienem zapytać. Czy ktoś mógłby naprowadzić mnie na rozwiązanie zadania o treści:

Wykaż, że entropia źródła rozszerzonego do "k" wyjść jest równa entropii tego źródła bez rozszerzenia razy "k".

W skrócie: Wykaż, że H(S^k) = k * H(S)

Answer 1

Aby wykazać, że entropia źródła rozszerzonego do "k" wyjść jest równa krotności entropii tego źródła bez rozszerzenia, użyjemy definicji entropii.

Entropia informacyjna źródła informacji dyskretnej S jest określona jako:

\[ H(S) = - \sum_{i=1}^{n} P(x_i) \log_{2} P(x_i) \]

gdzie \( P(x_i) \) to prawdopodobieństwo wystąpienia symbolu \( x_i \) w źródle S.

Teraz, rozważ źródło rozszerzone do "k" wyjść, oznaczone jako \( S^k \). Prawdopodobieństwo wystąpienia konkretnego ciągu \( s_1, s_2, \ldots, s_k \) z \( S^k \) można zapisać jako iloczyn prawdopodobieństw symboli w tym ciągu:

\[ P(s_1, s_2, \ldots, s_k) = P(s_1) \cdot P(s_2) \cdot \ldots \cdot P(s_k) \]

Entropia tego źródła rozszerzonego do "k" wyjść jest zdefiniowana jako:

\[ H(S^k) = - \sum_{s_1} \sum_{s_2} \ldos \sum_{s_k} P(s_1, s_2, \ldots, s_k) \log_{2} P(s_1, s_2, \ldos, s_k) \]

Teraz, użyjmy definicji entropii źródła S w powyższym wyrażeniu:

\[ H(S^k) = - \sum_{s_1} \sum_{s_2} \ldos \sum_{s_k} P(s_1, s_2, \ldos, s_k) \log_{2} \left( P(s_1) \cdot P(s_2) \cdot \ldos \cdot P(s_k) \right) \]

Zasada logarytmu mnożenia pozwala nam przekształcić to wyrażenie:

\[ H(S^k) = - \sum_{s_1} \sum_{s_2} \ldos \sum_{s_k} P(s_1, s_2, \ldos, s_k) \left( \log_{2} P(s_1) + \log_{2} P(s_2) + \ldos + \log_{2} P(s_k) \right) \]

Teraz, zsumujmy te logarytmy:

\[ H(S^k) = - \sum_{s_1} \sum_{s_2} \ldos \sum_{s_k} P(s_1, s_2, \ldos, s_k) \log_{2} P(s_1) - \sum_{s_1} \sum_{s_2} \ldos \sum_{s_k} P(s_1, s_2, \ldos, s_k) \log_{2} P(s_2) - \ldos - \sum_{s_1} \sum_{s_2} \ldos \sum_{s_k} P(s_1, s_2, \ldos, s_k) \log_{2} P(s_k) \]

Teraz zauważmy, że każdy z tych składników to po prostu entropia źródła S:

\[ H(S^k) = k \cdot H(S) \]

Stąd udowodniliśmy, że entropia źródła rozszerzonego do "k" wyjść jest równa krotności entropii tego źródła bez rozszerzenia, czyli \( H(S^k) = k \cdot H(S) \).

Comments

Sam bym tego lepiej nie udowodnił! Brawo!