ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 46
Скачиваний: 0
ется, скупой хочет включить фальшивую монету в сумму долга, но, к сожалению, не может ее распознать. Какое наименьшее число взвешиваний на рычажных весах без гирь должен произвести скупой, чтобы обнаружить фаль шивую монету?
Р е ш е н и е . .Каждая из .12 монет, взятая наугад, мо жет оказаться фальшивой. Поэтому количество инфор мации от сообщения «взятая наугад монета фальшивая»
Л = — log log 12 = 3,58 (бит).
Так как произвольное взвешивание имеет три равноверо ятных исхода (перевесила правая чашка, перевесила ле вая чашка, чашки весов остались в равновесии), коли чество информации от такого взвешивания
h = — lo g ^ -= lo g 3 = |
1,58 (бит). |
Следовательно, минимальное число взвешиваний равно |
|
целой части |
|
■[^1/^2] =.[2.3] |
1 = 3. |
Каким же образом «отнять» у фальшивой монеты .за пасенную в ней информацию о своем отличии от других монет? Очевидно, необходимо так организовать взвеши
вание, чтобы всякий раз получать |
в результате опыта |
|||
1,58 |
бит: |
разбить 12монет на три равновероятные под |
||
группы |
(по 4 |
штуки в каждой), сравнить веса любых |
||
двух |
подгрупп, |
взять более легкую |
подгруппу и снова |
|
разбить ее на три подгруппы (1 + 14-2), снова сравнить веса первых двух подгрупп (по одной монете); если чаш ки весов остались в равновесии, взять оставшуюся под группу, содержащую 2 монеты, и сравнить их веса. Та ким образом, последнее, третье взвешивание однозначно
определит |
фальшивую |
монету. |
исхода Х\, Х2, х3 с соот |
|||||
Задача 4. Опыт X имеет три |
||||||||
ветственными |
вероятностями: |
Р(х\) = |
0,2, |
Р(х2) = 0,5, |
||||
Р(хЗ)= 0 ,3 . |
Найти точные и средние количества инфор |
|||||||
мации, несомые исходами |
х\, х2, х3. |
|
|
|||||
Р е ш е н и е . Точные количества информации, несомые |
||||||||
исходами Х[, |
х% х3, равны: |
|
|
|
||||
І(х\) = |
— log |
Р(х\) = |
— log 0,2 = |
2,32 |
(бит); |
|||
І(х2) = |
— log Р(х2) |
= |
— log 0,5 = |
1,00 |
(бит); |
|||
I(x3) = |
- |
log |
P(x3) |
= |
- log 0,3 = |
1,74 |
(бит). . |
|
10
Так как числа І(х\) = 2,32; І(х2) = 1; І(х3) = 1,74 появ ляются с соответственными вероятностями 0,2; 0,5; 0,3, среднее количество информации
— 2,32*0,2+1 • 0,5+ 4,74 -0,3= 1,49 (бит).
После усреднения количество информации, несомое исхо дом X], стало равным 1,49 бит, исходом х2 1,49 бит, исхо дом Xz 1,49 бит. Иными словами, операцией усреднения мы уничтожили индивидуальное различие исходов по их информативности.
FP)
0,5-
I |
г |
о |
4 ^ |
Рис. 1
Задача 5. В условиях предыдущей задачи вычислить дисперсию случайной величины / = —Іоg P ( x i ) и по строить функцию распределения.
Р е ш е н и е : По определению дисперсии
|
D[I] = |
І |
В Д - |
< І(хд > } 2Р(Х;) = |
|
|
|
*=1 |
|
|
|
= |
(2,32 — 1,49)2 *0,2 + |
(1 — 1,49)2-0,5 + |
|||
|
+ |
(1,74— 1,49)2-0,3 = 0,277. |
|||
Таким образом, |
случайная |
величина 1(хі) отклоняется |
|||
от своего |
среднего |
< С І ( х і ) ^ > |
в среднеквадратичном на |
||
величину |
а7 = \/D[I] = 0,525 . |
Так как случайная вели |
|||
чина 1(х{) = — log Р(х-і) дискретна, ее распределением вероятностей является интегральная функция распреде ления F (I) (рис. 1).
Очевидно., что:
F= 0 для |
1; |
/7= 0 ,5 для 1</<Л ,74;
П
F = |
0,8 |
для |
l,7 4 < /< 2 ,3 2 ; |
. |
F = |
1,0 |
для |
/>'2,32. |
|
Задача 6. Пусть некоторый опыт имеет два возмож ных исхода Х\ и х2 с вероятностями появления Р(х\) —0Л II Р(х2) = 0,9. Производится большое число N независи мых опытов. Найти среднее количество информации,' при ходящееся на один исход опыта.
Р е ш е н и е. Обозначим конкретную последователь ность исходов, получаемую в результате N опытов, бук вой с. Тогда при достаточно большом N, согласно теоре ме Бернулли, вероятности исходов можно определить по формулам:
Р(XI) = «1 W, Р(Хг) = «2;N,
где п\ и по соответственно число исходов х\ и х2 в после
довательности с. |
|
вероятность последова |
Ввиду независимости опытов |
||
тельности с по |
теореме умножения |
|
■Р(с) = Р(х1) |
-Р{х1) ... Р{Х\)- Р{Хо)Р{хг) ... Р(хг) = |
|
------------ —------------^-------------.-------------" |
||
|
раз |
па раз |
Отсюда видно, что вероятность конкретной последова тельности не зависит от ее вида, а зависит только от ве роятности исходов х.\ и х2 и N. Поэтому всевозможные по следовательности с могут рассматриваться как равнове роятные и число их будет п = \/[Р(с)].
В этом случае для определения количества информа ции, несомого последовательностью с, можно воспользо ваться формулой (1.2):
. /д,
= Jog« = — lo g Р(с) = log ([Я(Л.-1)]Л/5(Г,) [Р(х2)\АР{х,) } =
= — N[P(xt) log Р(хі) + Р{хг) log Р(х2)]> |
|
|||
где через ІіУ обозначено |
|
количество |
информации, |
несо |
мое N исходами опыта. А количество |
информации, |
при- |
||
. ходящееся на один исход, |
в N раз меньше: |
|
||
|
|
2 |
|
|
/ = |
- |
2 Я(л7) log Р(х,). |
|
|
|
|
/=*1 |
|
|
Подставив сюда Р(х\) — 0,1 и Р(Хч)^ 0,9, получим
/ = —0,1 log 0,1—0,9 log 0,9 = 0,469 (бит)..
12
Задача 7. Показать, что при равной вероятности исхо дов опыта количество информации, определяемое форму лой (1.2), является неслучайной величиной.
Формула (1.2а) при равной вероятности исходов опы та примет вид
п
< і (хі) > |
= |
l og4 " * - іо£ ~7г= lo g п =*7> |
|
/«= 1 |
|
т. е. 1 не случайно, так как оно оказалось равным неслу чайной величине < / ( * / ) > .
В заключение заметим, что мера количества инфор мации в виде (1.2) была впервые предложена в 1928 г. американским инженером Р. Хартли. Ясно, что формула- p. Хартли относится к весьма частному случаю, когда по сле опыта неопределенности в исходе опыта нет и все ис ходы равновероятны. Однако заслуга Р. Хартли велика, ибо введенная им мера применима к информации любоговида и содержания и, что наиболее ценно, объективна и независима от психологических, факторов, так как опре деляется через объективно существующую статистику со бытий.
• |
» |
§ 2. Энтропия и ее свойства |
|
Если после опыта остается |
некоторая неопределен |
ность. исхода, то формула |
|
Н(Х) = - S Р(х{) log Р(х,) |
(■! Л |
і= { |
|
уже не выражает среднее количество информации, несо мое одним исходом опыта. Однако величина Н(Х) сохра няет за собой другой, фундаментальный для теории ин формации смысл (см. § 1), а именно: Н (X) выражает среднее количество неопределенности до опыта в наступ лении того или иного исхода и называется энтропией.
Рассмотрим основные свойства энтропии.
\.. Н(Х)'^> 0, причем знак равенства имеет место только в том случае, когда- у опыта имеется один-единст- венный исход с вероятностью «единица».
Положительность Н(Х) видна из (1.7): вероятности положительны и заключены между нулем и единицей, ло гарифмы таких чисел отрицательны, а равенство нулю
13;
возможно только для такого опыта, у которого один ис ход достоверен, а остальные равны нулю. Например:
Х и Х^> |
Х ^ |
Хп |
О1 О о ...о
|
Тогда |
его энтропия |
|
|
|
|
|
|
Н(Х) |
— 0 -log 0 + 1 - log 1 |
+ |
••• |
+ 0 - log0 = О, |
||
так |
как log 1 = 0, . а |
|
|
|
іоg |
1 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
lim [— P[xt) log P (л’/)] = |
lim |
Ң*д |
||||
|
|
|
|||||
|
|
|
|
|
|
Ң*д |
|
|
|
= lim —— - - = lim - |
} л |
— О, |
|
||
|
|
а-*-9о |
K-J- оо а ІП2 |
|
|
||
где |
а = 1 IP(xt). |
|
|
|
|
|
|
|
Равенство нулю Н(Х) |
заложено |
нами в постулате 2 |
||||
'§ I-
2.При заданном п энтропия максимальна и равна
log п, когда все исходы, составляющие опыт, равноверо
ятны. |
{ |
|
Д о к а з а т е л ь с т в о . Необходимо найти максимум |
||
функции |
п |
|
Н( РЬ.Р2, |
||
.... Рп) = - 2 P , i o g P i |
||
/=1
а
при одном, очевидном, дополнительном условии
/=1
=1. Для этого * составим функцию
|
Рп) = Н { Р ѵ Рг% |
PJ + X (£ p t- - l ) , |
|||
где |
X— неопределенный |
множитель Лагранжа, |
и при |
||
равняем к нулю частные |
производные |
Ф (Р ь Ръ |
Р„) |
||
по |
Рі : |
|
|
|
|
|
-ЗБГ lH(Pu Р*’ - - W ( i |
P i - |
D] = 0. |
(1.8) |
|
|
|
i=\ |
|
|
|
Подставляя в последнее равенство значение энтропии н выполняя дифференцирование, получаем
(ln Pi + 1) + X= 0,
* См. В. И. С м и р н о в. Курс высшей математики, т. 1. М., 1967г
14