Из мешка наугад вынимают один... - вопрос №536479

Для этого надо воспользоваться формулой Шеннона H(a)=−∑(i=1 до N)Pi*log(Pi), где N — количество  состояний системы, Pi — вероятность нахождения системы в i-ом состоянии 

Мне не очень понятно что есть 5*2, поэтому рассмотрим несколько случаев.

1. 10 — пронумерованных шаров от 0 до 9. В этом случае после наша система после вынимания любого из шаров имеет 10 возможнзых состояний, соотвественно:

вынули шар 0 — в мешке шары от 1 до 9

вынули шар 1 — в мешке шары 0, от 2 до 9

вынули шар 2 — в мешке шары 0,1, от 3 до 9

и т.д. 

Таким образом количество состояний системы 10, вероятность нахождения системы в каждом из состоянии просто соответствует частоте появления данного состояний 1/N = 1/10. Таким образом по формуле:

-0,1*log(0,1)-0,1*log(0,1)-… ещё 8 раз, итого получаем -10*0,1*-3,3=~3,3бит (логарифм берём по основанию 2, т.к. считаем информацию в битах).

Собственно если переходить к двоичной арифметике, точнее к прикладным задачам то можно сказать — для того чтобы варазить 10 различных состояний нам необходимо использовать 4бита, т.к. 3 битное число может выразить 8 возможных состояний 2^3. А 4 бита 16 состояний 2^4.

2. Вариант второй у нас 10 шаров номера на которых повторяются каждый по два раза, т.е. два шара 0, два шара 1, и т.д. В этом случае количество состояний нашей системы всего 5:

вынули шар 0 — в мешке шары 0 и от 1 до 4 два раза

вынули шар 1 — в мешке шары 0 два раза, 1 и от 2 до 4 два раза  

вынули шар 2 — в мешке шары от 0 до 1 два раза, 2 и от 3 до 4 два раза   

вынули шар 3  -  в мешке шары от 0 до 2 два раза, 3 и 4 два раза    

вынули шар 4  — от 0 до 3 два раза и 4

Но т.к. достать мы можем 10 шаров, вероятность (частота) каждого состояния 2/10 таким образом

-5*0,2*log(0,2)=~2,3бит

Отличие от первого варианта только в подсчёте количества состояний, т.е. фактически для варианта доставания одного шара из мешка у нас всегда меняется состояние системы, поэтому мы получаем сразу много (полную) информацию о системе.

Дальше мы достаём ещё один шар. Для первого случая.

1. Количество состояний системы:

Первый шар был 0, достали 1, остались 2,3,4,5,6,7,8,9

Первый шар был 0, достали 2, остались 1,3,4,5,6,7,8,9

...

Первый шар был 1, достали 0, остались 2,3,4,5,6,7,8,9

и т.д. Видно что каждое состояние повторяется 2 раза, т.к. мы не делаем разницу между вариантами 1 и 0, или 0 и 1, таким образом по тем шарам которые достали:

01,02,03,04,05,06,07,08,09 — 9 состояний по два раза

12,13,14,15,16,17,18,19 — 8 состояний по два раза

23,24,25,26,27,28,29  - 7 состояний по два раза

и т.д. всего 9+8+7+6+5+4+3+2+1=45 уникальных состояний 

вероятность(частота) каждого 2/90 (т.к. 01 и 10 для нас одно и тоже)/90(всего возможных состояний по 9 состояний для каждого случая: сначала вытащили 0, сначала вытащили 1, и т.д.)=2/90. Применяем формулу:

-45*2/90*log(2/90)=~5,5бит. Добавили 5,5-3,3=2,2 бит. Сложность системы выросла, но новый шар принёс меньше полезной информации, т.к. появлется больше предсказуемости в том какой шар появится дальше. Вынув 9 шаров из 10, мы на 100% будем знать какой шар будет следующим и ценность 10-ого шара будет 0бит.

2. Для второго случая

00

01,02,03,04 — по два раза

11

12,13,14 — по два раза

22

23,24 — по два раза

33

34 — по два раза

44

Всего (1+1+1+1+1)+(4+3+2+1)=15 уникальных состояний и 25 всего. Вероятность каждого состояния не одинакова. Двойные шары имеют вероятность 1/25, а остальные 2/25 (т.к. см. предыдущий пункт у 34 и 43 для нас одинаковы). Применяем формулу:

5*1/25*log(1/25)+ 10*2/25*log(2/25)=~3,8бит. Добавили 3,8-2,3=1,5бит