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

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

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

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

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

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

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

     

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

 

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

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

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

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

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

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

.

 

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

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

Розв'язання

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

  Таблиця 1

X1

1

2

3

4

5

6

pi

1/6

1/6

1/6

1/6

1/6

1/6

 

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

            HX1=HX2=log26=1+log23»1+1,585»2,585 (біт/сим).

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

P(X1=iX2=j)=P(X1=i)×P(X2=j)=1/36; i=1...6, j=1...6.

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

            Таблиця 2    

X2

 

X1

1

2

3

4

5

6

1

2

3

4

5

6

7

2

3

4

5

6

7

8

3

4

5

6

7

8

9

4

5

6

7

8

9

10

5

6

7

8

9

10

11

6

7

8

9

10

11

12

     

      Обчислимо ймовірності 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

Yj

2

3

4

5

6

7

8

9

10

11

12

qj

1/36

1/18

1/12

1/9

5/36

1/6

5/36

1/9

1/12

1/18

1/36

 

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

(біт/сим)

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

Таблиця 4

X1

Y

2

3

4

5

6

7

8

9

10

11

12

1

1/36

1/36

1/36

1/36

1/36

1/36

0

0

0

0

0

2

0

1/36

1/36

1/36

1/36

1/36

1/36

0

0

0

0

3

0

0

1/36

1/36

1/36

1/36

1/36

1/36

0

0

0

4

0

0

0

1/36

1/36

1/36

1/36

1/36

1/36

0

0

5

0

0

0

0

1/36

1/36

1/36

1/36

1/36

1/36

0

6

0

0

0

0

0

1/36

1/36

1/36

1/36

1/36

1/36

 

1/36

1/18

1/12

1/9

5/36

1/6

5/36

1/9

1/12

1/18

1/36

           

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

=log236=2log26=2(1+log23)»2+

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

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

(біт/сим).

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

            .

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

.

(біт/сим).

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

(біт/сим);

(біт/сим).

 

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

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

X

1

2

3

4

 

Y

1

2

3

4

p

1/8

1/8

1/4

1/2

q

1/4

 

Розв'язання

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

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

(біт/сим).

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

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

               Таблиця 3

X

Y

1

2

3

4

1

0

1

2

3

1/8

1/32

1/32

1/32

1/32

2

1

0

1

2

1/8

1/32

1/32

1/32

1/32

3

2

1

0

1

1/4

1/16

1/16

1/16

1/16

4

3

2

1

0

1/2

1/8

1/8

1/8

1/8

1/4

1/4

1/4

1/4

1

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

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

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

                  Таблиця 4

X

Z

0

1

2

3

1

1/32

1/32

1/32

1/32

1/8

2

1/32

1/16

1/32

0

1/8

3

1/16

1/8

1/16

0

1/4

4

1/8

1/8

1/8

1/8

1/2

1/4

11/32

1/4

5/32

1

     

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

(біт/сим).

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

                     Таблиця 5

Z

0

1

2

3

pi

1/4

11/32

1/4

5/32

     

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

 

 (біт/сим).

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

(біт/сим).

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

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

                     Таблиця 6

Y

Z

0

1

2

3

1

1/32

1/32

1/16

1/8

1/4

2

1/32

3/32

1/8

0

1/4

3

1/16

5/32

1/32

0

1/4

4

1/8

1/16

1/32

1/32

1/4

1/4

11/32

1/4

5/32

1

 

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

(біт/сим).

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

     

     

(біт/сим).

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

(біт/сим);

(біт/сим).

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

Завдання 1.

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

Завдання 2.

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

X

0

1

3

4

 

Y

-2

2

.

P

1/8

1/8

1/4

1/2

 

P

3/8

5/8

Завдання 3.

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

Завдання 4.

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

Завдання 5.

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

X

-1

0

1

 

Y

0

1

2

.

P

1/4

1/2

1/4

P

1/6

2/3

1/6

Завдання 6.

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

Завдання 7.

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

 

X

1

2

3

4

5

6

7

8

.

P

0,1

0,2

0,1

0,05

0,1

0,05

0,3

0,1

 

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