Теория информации — страница 4

  • Просмотров 2357
  • Скачиваний 229
  • Размер файла 28
    Кб

достаточно ясно указывают на то, как нужно поставить первый вопрос. Разобьём множество всех возможных значений нашей переменной (то есть множество целых положительных чисел от 1 до 10) на две равные по численности группы (так как исходы опыта б1 должны быть равновероятны) и спросим, относится ли задуманное число к одной или другой из них (например, больше ли оно пяти). Далее нужно разбивать оставшееся множество чисел на две

возможно близкие по численности части, и тогда мы определим задуманное число с помощью четырёх вопросов. Нужно сказать, что с помощью тех же четырёх вопросов мы угадаем не только одно из 10 задуманных чисел, но даже одно из 16, так как после того как уже выяснено, что число имеет одно из Х значений, где Х нечётно, невозможно добиться строгой равновероятности исходов последующего опыта, следовательно, энтропия этого опыта будет

меньше 1. Это означает, что наш опыт не особенно выгоден с точки зрения полученной информации, то есть что с помощью того же числа вопросов можно найти загаданное число, имеющее не одно из 10, а одно из 24 = 16 возможных значений. Вообще, наименьшее число k вопросов, позволяющее найти заданное число Х, имеющее одно из n допустимых значений, определяется неравенствами k – 1< log n ≤ k или 2k - 1 < n ≤ 2k. Также можно заметить, что независимо

от значения n k ≥ log n; при этом k = log n только в том случае, когда число n является целой степенью числа 2.    Имеется 25 монет одного достоинства; 24 из них имеют одинаковый вес, а одна – фальшивая – несколько легче остальных. Спрашивается, сколькими взвешиваниями на чашечных весах без гирь можно обнаружить эту фальшивую монету. Опыт А, результат которого требуется определить, имеет в этом случае 25 возможных исходов, значит, так

как эти исходы равновероятны, Н(Б) = log 25. Опыт б1, состоящий в одном взвешивании, может иметь 3 исхода (либо перевесит левая чашка, либо правая, либо веса останутся в равновесии); поэтому Н (б1) = log 3 и информация I(б1, А), получаемая при проведении такого опыта, не превосходит log 3. Рассмотрим теперь сложный опыт Бк = б1б2…бк, заключающийся в k последовательных взвешиваниях; он даёт информацию, не превосходящую k log 3. Если опыт Бк позволяет

полностью определить исход опыта А, то должно выполняться Н (Бк) ≥ I (Бк, А) ≥ Н (А) или k log 3 ≥ log 25. Отсюда заключаем, что 3к ≥ 25, то есть K ≥ log3 25 = Или, так как k – целое число, k ≥ 3. Нетрудно показать, что с помощью трёх взвешиваний всегда можно определить фальшивую монету. Предположим, что на каждую чашку весов нами положено по n монет, не положены на весы будут 25 - 2n монет. Так как вероятность того, что фальшивая монета