Лабораторна робота №3-4

Тема: Безумовна ентропія.

Мета: навчатися визначати ентропію дискретного джерела повідомлень

Теоретичні відомості

Ентропія дискретного джерела повідомлень

Кількісну міру апріорної невизначеності про те, яке повідомлення буде породжене дискретним джерелом повідомлень (або середню кількість інформації в кожному повідомленні)  в теорії інформації називають ентропією  і позначають Н.

Точно ентропію Н (А) можна визначити як математичне сподівання питомої кількості інформації:

     

У випадку рівної ймовірності повідомлень р(a₁)= р(a₂)=… р(a_k)=1/k ентропія джерела обчислюється за формулою:

 

Ентропія як кількісна міра інформаційності джерела має такі властивості:

1)  ентропія дорівнює нулю, якщо хоча б одне з повідомлень достовірне;

2)  ентропія завжди більша або дорівнює нулю, є величиною дійсною і обмеженою;

3)  ентропія джерела з двома альтернативними подіями може змінюватися від 0 до 1;

4)  ентропія - величина адитивна: ентропія джерела, повідомлення якого складаються з повідомлень декількох статистично незалежних джерел, дорівнює сумі ентропій цих джерел;

5)  ентропія максимальна, якщо всі повідомлення мають однакову імовірність. Таким чином,

.

 

Приклади виконання завдань

Приклад_1.  Дискретні випадкові величини (д. в. в.) X₁ та X₂ визначаються підкиданням двох гральних кубиків. Д. в. в. Y=X₁+X₂. Знайти кількість інформації I(Y, X₁), I(X₁, X₁), I(Y, Y).

Розв'язання

      Побудуємо розподіл ймовірностей д. в. в. X₁ (або X₂)  (табл. 1):

  Таблиця 1

 

      Звідси знаходимо ентропію д. в. в X₁, що у даному випадку буде максимальною, оскільки значення рівноймовірні:

            HX₁=HX₂=log₂6=1+log₂3»1+1,585»2,585 (біт/сим).

      Оскільки X₁ та X₂ незалежні д. в. в., то їх сумісна ймовірність визначається так:

P(X₁=i, X₂=j)=P(X₁=i)×P(X₂=j)=1/36; i=1...6, j=1...6.

      Побудуємо допоміжною таблицю значень д. в. в. Y =X₁+X₂ (табл.2):

            Таблиця 2    

     

      Обчислимо ймовірності P(Y=j) (j=2, 3, …, 12):

P(Y=2)=1/36; P(Y=3)=2×1/36=1/18; P(Y =4)=3×1/36=1/12;

P(Y=5)=4×1/36=1/9; P(Y=6)=5×1/36=5/36; P(Y=7)=6×1/36=1/6; P(Y=8)=5×1/36=5/36;P(Y=9)=4×1/36=1/9; P(Y=10)=3×1/36=1/12; P(Y=11)=2×1/36=1/18; P(Y=12)=1/36;

      Скориставшись допоміжною таблицею (табл.2), запишемо безумовний закон розподілу д. в. в. Y (табл. 3):

Таблиця 3

 

      Звідси знаходимо ентропію д. в. в. Y так:

(біт/сим)

      Побудуємо таблицю розподілу ймовірностей системи д. в. в. (X₁, Y) p_ij=P(X₁=i, Y=j) (табл. 4).

Таблиця 4

           

      Тоді взаємна ентропія д. в. в. X₁, Y

=log₂36=2log₂6=2(1+log₂3)»2+

+2×1,585»5,17 (біт/сим).            

      Кількість інформації, що містить д. в. в. Y стосовно д. в. в. X₁, обчислимо за формулою . Отже,

(біт/сим).

      Кількість інформації I(Y, X₁) здебільшого зручніше знайти, скориставшись властивістю 4 кількості інформації і ентропії:

            .

      Оскільки Y=X₁+X₂, де X₁ та X₂ – незалежні д. в. в., то

.

(біт/сим).

Відповідь: (біт/сим);

(біт/сим);

(біт/сим).

 

Приклад_2.  Знайти ентропії дискретних випадкових величин (д. в. в.) X, Y, Z та кількість інформації, що містить д. в. в.   стосовно X та Y. X, Y – незалежні д. в. в., які задаються такими розподілами (табл. 1, табл. 2):

Таблиця 1                                                    Таблиця 2

 

Розв'язання

      Скориставшись відповідним рядом розподілу ймовірностей д. в. в. X та Y, знаходимо їх ентропії.

      Ентропія д. в. в. X

(біт/сим).

      Ентропія д. в. в. Y (біт/сим).

      Побудуємо допоміжну таблицю значень д. в. в. Z=½X-Y½ та їх ймовірностей (табл. 3). Оскільки X та Y – незалежні д. в. в., то сумісна ймовірність випадання пар значень (x_i, y_j) .

               Таблиця 3

Знайдемо ймовірності системи д. в. в. (Z=j, X=i, , ):

P(Z=0, X=1)=1/32, P(Z=1, X=1)=1/32, P(Z=2, X=1)=1/32, P(Z=3, X=1)=1/32; P(Z=0, X=2)=1/32, P(Z=1, X=2)=1/32+1/32=1/16, P(Z=2, X=2)=1/32, P(Z=3, X=2)=0; P(Z=0, X=3)=1/16, P(Z=1, X=3)=1/16+1/16=1/8, P(Z=2, X=3)=1/16, P(Z=3, X=3)=0; P(Z=0, X=4)=1/8, P(Z=1, X=4)=1/8, P(Z=2, X=4)=1/8, P(Z=3, X=4)=1/8.

      Побудуємо таблицю розподілу ймовірностей системи д. в. в.(X, Z) (табл. 4).

                  Таблиця 4

     

      Тоді взаємна ентропія д. в. в. Z та X

(біт/сим).

      Скориставшись табл. 3 або табл. 4, побудуємо розподіл ймовірностей д. в. в. Z (табл. 5).

                     Таблиця 5

     

      Звідси знаходимо ентропію д. в. в. Z:

 

 (біт/сим).

      Кількість інформації, що містить д. в. в. Z стосовно д. в. в. X, знаходимо, скориставшись властивістю 4 кількості інформації і ентропії:

(біт/сим).

      Побудуємо таблицю розподілу ймовірностей системи д. в. в.(Y, Z) (табл. 6). Для цього, скориставшись табл. 3, обчислимо ймовірності:

P(Z=0, Y=1)=1/32, P(Z=1, Y=1)=1/32, P(Z=2, Y=1)=1/16, P(Z=3, Y=1)=1/8; P(Z=0, Y=2)=1/32, P(Z=1, Y=2)=1/32+1/16=3/32, P(Z=2, Y=2)=1/8, P(Z=3, Y=2)=0; P(Z=0, Y=3)=1/16, P(Z=1, Y=3)=1/32+1/8=5/32, P(Z=2, Y=3)=1/32, P(Z=3, Y=3)=0; P(Z=0, Y=4)=1/8, P(Z=1, Y=4)=1/16, P(Z=2, Y=4)=1/32, P(Z=3, Y=4)=1/32.

                     Таблиця 6

 

      Тоді взаємна ентропія д. в. в. Z та Y

(біт/сим).

      Отже, кількість інформації, що містить д. в. в. Z стосовно  д. в. в. Y

     

     

(біт/сим).

Відповідь:   HX = 1,75 (біт/сим);  HY = 2  (біт/сим); (біт/сим);

(біт/сим);

(біт/сим).

Завдання до лабораторної роботи

Завдання 1.

Дискретні випадкові величини (д. в. в.) X₁ та X₂ визначаються підкиданням двох ідеальних тетраедрів, грані яких позначені числами від 1 до 4. Знайти, скільки інформації про д. в. в. X₁ містить д. в. в. Z=X₁*X₂, а також ентропію HZ.

Завдання 2.

Знайти ентропії дискретних випадкових величин (д. в. в.) X, Y, Z і кількість інформації, що містить д. в. в. Z=X+Y стосовно д. в. в. Y. X та Y незалежні д. в. в., задані такими розподілами:

Завдання 3.

Дискретні випадкові величини (д. в. в.) X₁ та X₂ визначаються підкиданням двох ідеальних тетраедрів, грані яких позначені числами від 1 до 4. Д. в. в. Y  дорівнює сумі чисел, що випали при підкиданні цих тетраедрів, тобто Y=X₁+X₂. Знайти кількість взаємної інформації I(X, Y), ентропії HX₁, HY.

Завдання 4.

Дискретна випадкова величина (д. в. в.) X визначається кількістю очок, які випадуть при підкиданні грального кубика, а д. в. в. Y=0, якщо кількість очок, що випали, непарна, і Y=1, якщо кількість очок парна. Знайти кількість інформації I(X, Y) та I(Y, Y).

Завдання 5.

Знайти ентропії д. в. в. X, Y, Z і кількість інформації, що містить д. в. в. Z=2X+Y стосовно X та Y. X, Y – незалежні д. в. в., задані такими розподілами ймовірностей:

Завдання 6.

Дискретна випадкова величина (д. в. в.) X₁ може набувати три значення: -1, 0 і 1 з однаковими ймовірностями. Д. в. в. X₂ з однаковими ймовірностями може набувати значення 0, 1 і 2. X₁ і X₂ – незалежні, Y=X₁²+X₂. Знайти кількість інформації I(X₁,Y), I(X₂,Y) і ентропії HX₁, HX₂, HY.

Завдання 7.

Дискретна випадкова величина (д. в. в.) X з різною ймовірністю може набувати значень від 1 до 8. Д. в. в. Y набуває значення 0, якщо X парне, і 1, якщо X непарне. Знайти кількість інформації I(Y, X) і ентропію HX, якщо д. в. в. X задана таким розподілом ймовірностей:

 

 

Після виконання завдань оформити та здати звіт викладачу