ПРИЛОЖЕНИЕ А. НЕРАВЕНСТВА, ВКЛЮЧАЮЩИЕ БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ

В этом приложении приводятся некоторые неравенства, полезные при оценке выражений, содержащих биномиальные коэффициенты. Материал взят из записей, сделанных на семинаре К. 3. Шеннона по теории информации в Массачусетсом технологическом институте. Пусть

тогда

и

где отличны от нуля.

Эти два неравенства можно доказать, используя приближение Стирлинга:

Известно (см. [90]), что если все члены ряда заменить нулями, получится нижняя оценка для если оставить только один член ряда то получится верхняя оценка для . Оценка сверху для выражения получается, если использовать разложение с выписанными двумя членами как оценки снизу и и взять оценку сверху для числителя, получаемую из того же самого разложения отбрасыванием всех членов ряда, начиная со слагаемого . В результате получается, что

Это выражение симметрично относительно Предположим, что Тогда

и

Таким образом,

Так находится верхняя граница, даваемая неравенством Нижняя граница вычисляется аналогично на основе разложения в котором для оценки сверху числителя оставляют только первый член ряда, а при оценке снизу знаменателя отбрасывают все слагаемые ряда.

Вторая оценка снизу — неравенство следует из неравенства если хотя бы одно из произведений не меньше 3, так как в этом случае меньше, чем

В четвертом случае, когда одновременно меньше трех, искомый результат получить совсем легко. Если то неравенство переходит в равенство.

Двост биномиального распределения можно оценить следующим образом:

где Кроме того,

Положим, что и умножим обе части неравенства на Получим

и

Нижняя граница в неравенстве очевидна. Верхняя граница получается как оценка сверху при помощи суммы геометрической прогрессии (см. [90]). Оценка - это частный случай

неравенства Чернова (см. [115]). Более точные и более общие результаты приведены в работе [89]. Сумму вида

можно оценить, если положить и заметить, что

В каждом из неравенств содержится некоторый множитель, лишь слабо зависящий от и множитель или Биномиальный коэффициент можно оценить, используя выражение и неравенства и и главным членом в этих оценках будет произведение Для вычислений при больших значениях полезны следующие формулы:

где

и

Но

и

и, следовательно,

где

Как показано на рис. А. 1, этому выражению может быть дана интересная геометрическая интерпретация.

Соотношения —(А. 13) верны при любом выборе основания логарифмов, конечно, при условии, что во всех соотношениях используется одно и то же основание. В приложении Б приводится краткая таблица для случая обычных логарифмов (по основанию 10).

Рис. A.1. Геометрическая интерпретация функции

Более полные таблицы, использующие логарифмы по основанию 2, приведены в работах [31] и [87].