Изменения
→Оценка минимальной и максимальной длины кода
L_{min} = \dfrac{1}{{\binom{l}{n+l-1}}l!} = \dfrac{1}{C_{n+l-1}^{l}l!}
</tex>
==== Докажем верхнюю границу: Верхняя граница ====
Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов <tex>k=1, 2, \dots, l</tex> вес символа будет равен k, а значение кода будет изменяться в <tex>\dfrac{k}{n+k-1}</tex> раз.
</tex>
}}
{{Утверждение
|id = th1.
|statement=При адаптивном арифметическом кодировании строки длины <tex>l</tex>, символы которой принадлежат алфавиту мощности <tex>n</tex>, количество бит, необходимых для кодирования сообщения будет лежать в диапазоне <tex>[-\sum_{i=1}^{l} log_2{\dfrac{1}{n+i-1}}, -\sum_{i=0}^{l-1}log_2\dfrac{i+1}{n+i}]</tex>
|proof=
Произведём оценку количества бит, необходимых для записи кода $L$ в общем случае:
<tex>
log_2 L = -\sum_{i=1}^{l} log_2 \frac{w_{\alpha_i}}{n+i-1}
</tex>
Все коды лежат в диапазоне <tex>[0, 1)</tex>.
Таким образом:
Максимальное количество бит будет затрачено при записи кода, являющегося минимальной дробью:
<tex>
log_2 L_{min} = -\sum_{i=1}^{l} log_2 \frac{1}{n+i-1}
</tex>
Минимальное число бит будет затрачено в случае записи кода максимального размера:
<tex>
log_2 L_{max} = -\sum_{i=0}^{l-1} log_2 \frac{i+1}{n+i}
</tex>
}}
