Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

9.4. Биномиальная оценка

Другой необходимый математический результат состоит в вычислении числа вершин единичного куба из разд. 3.6, лежащих на сфере радиуса Другими словами, нужна оценка суммы биномиальных коэффициентов

где (Предполагается, что целое число.)

Поскольку члены монотонно возрастают, так что наибольшим слагаемым является последнее:

Применяя к каждому факториалу формулу Стирлинга, получаем

После перегруппировки членов имеем

Выражения в первой и третьей скобках в точности равны 1, а выражения в остальных двух скобках дают

Логарифм по основанию 2 знаменателя в первых скобках равен

так что первый множитель в (9.4.3) есть

Второй множитель — константа, умноженная на

Перепишем теперь исходную сумму (9.4.1) в обратном порядке

и оценим ее суммой геометрической прогрессии. Для того чтобы получить знаменатель этой геометрической прогрессии, заметим, что, переходя. от одного слагаемого к другому при обычном порядке записи (9.4.1), можно найти каждый биномиальный коэффициент, умножая предыдущий последовательно на величины

Если начать с наибольшего члена и двигаться в обратном порядке, нужно умножать на величины, обратные приведенным выше и расположенным в обратном порядке:

Требуется оценить эти числа. Оценкой сверху этих чисел является так что оценка сверху суммы биномиальных коэффициентов получается умножением наибольшего слагаемого на

Подставляя все это в (9.4.1), используя (9.4.4) и (9.4.5), получаем

Для всех таких что (напомним, что произведение последних трех сомножителей меньше 1. Поэтому для достаточно больших

где значение энтропийной функции в точке Это неравенство потребуется нам позже.

<< Предыдущий параграф Следующий параграф >>
Оглавление