Теорема (неравенство Макмиллана)

Пусть заданы кодируемый алфавит и кодирующий алфавит . Взаимно-однозначное кодирование задано набором кодовых слов с длинами . Тогда выполняется неравенство , где – количество букв в алфавите , – мощность алфавита .

Доказательство. Обозначим и рассмотрим , где – произвольное натуральное число.

(1)

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

Пример 6. Рассмотрим , где .

.

Обозначим и, приведя подобные в равенстве (1), получим

, (2)

где , – число наборов на которых . Если для какого-то не будет ни одного набора , на котором , соответствующее .

Оценим . Набору соответствует единственное слово ɱ . Так как упорядоченные наборы различны, то слова разные, кодирование взаимно-однозначное, их коды – слова в множестве ɱ также различны. Длина слова равна .

Таким образом, – число слов длины в алфавите , которые являются кодами слов длины в алфавите . Всех слов длины в алфавите , поэтому ,

.

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

,

от не зависит, поэтому , , следовательно, . Отсюда .