Логарифм и количество информации

[purser]

Теорема: Единственной монотонной функцией, удовлетворяющей условию $\varphi(nk)=n\varphi(k), n,k \in \mathbb{Z}$ является функция $\varphi(k)=C\log{k}, C=const$
Док-во: Пусть $a,b \in \mathbb{N}, a \ge 2, b \ge 2. \forall {N>0} \exists m: b^{m} \le a^{N} \le b^{m+1}$ (1.1)
Отсюда, пользуясь свойствами функции $\varphi$ имеем
$m\varphi(b) \le N\varphi(a) \le(m+1)\varphi(b)$ (1.2)
Для логарифмической функции справедливо такое же неравенство:
$m\log{b} \le N\log{a} \le (m+1)\log{b}$ (1.3)
Из (1.2) и (1.3) вытекает, что $|\frac{\varphi(a)}{\varphi(b)}-\frac{\log{a}}{\log{b}}| \le \frac{1}{N}$ (1.4)
Переходя к пределу имеем $\frac{\varphi(a)}{\varphi(b)}=\frac{\log{a}}{\log{b}}$ и значит $\frac{\varphi(a)}{\log{a}}=\frac{\varphi(b)}{\log{b}}=const=C$, что и требовалось доказать.
Мне непонятно, как получено неравенство (1.2) и (1.4)

[Xaositect]

У Вас явно опечатка в условии, потому что $C\log k$ не удовлетворяет условию.

[purser]

Я так понимаю, тут nk просто переобозначили как k. Теорема из книжки "Сжатие и поиск информации" Кричевский, стр.15

[Xaositect]

purser в сообщении #900892 писал(а):

Я так понимаю, тут nk просто переобозначили как k. Теорема из книжки "Сжатие и поиск информации" Кричевский, стр.15

Я имею в виду, что теорема неверная. Функция $\varphi(k) = C\log k$ не удовлетворяет соотношению $\varphi(nk) = n\varphi(k)$.

-- Ср авг 27, 2014 20:36:08 --

Скорее всего имелось в виду $\varphi(k^n) = n\varphi(k)$. Тогда (1.2) получается применением в (1.1) функции $\varphi$ ко всем частям неравенства, с учетом монотонности $\varphi$. Нужно рассмотреть еще случай, когда $\varphi$ монотонно убывает, но там только знаки поменяются, а так все то же самое.
Дальше, поделив (1.2) на $N\varphi(b)$, можно получить, что $\frac{m}{N}\leqslant \frac{\varphi(a)}{\varphi(b)} \leqslant \frac{m+1}{N}$, аналогично для логарифмов. Отсюда неравенство (1.4) - оба отношения под модулем лежат на отрезке $[\frac{m}{N}, \frac{m+1}{N}]$
(из (1.2) следует, что $\varphi(b) \geqslant 0$, так как $m\varphi(b)\leqslant (m+1)\varphi(b)$. Если $\varphi(b) = 0$, то делить на него нельзя, но $\varphi$ тогда будет тождественно равно 0).

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

[purser]

Спасибо...Действительно, в самом условии ошибка. Вот цитирую абзац перед теоремой.
"Конечным комбинаторным источником называется произвольное конечное множество S. В качестве таких источников как правило будем рассматривать множества слов некоторого алфавита A. Основной характеристикой источника является его энтропия. Она формализует интуитивное понятие "количество информации, несомое одним элементом S". Чтобы отвечать нашим интуитивным представлениям, это количество должно, во-первых, зависеть только от мощности |S|, и во-вторых, возрастать с ростом |S|. Далее, количество нформации, несомое n элементами S, должно быть в n раз больше количества, несомого одним элементом, n>1. Если энтропию источника обозначить H(S), то можем записать, что H(S)=$\varphi(|S|)$, где $\varphi(|S|)$ - некоторая монотонная функция, удовлетворяющая условию$\varphi(n|S|)=n\varphi(|S|)$". И дальше следует теорема. Поэтому, скорее в виду имеется $\varphi(nk)=n\varphi(k)$

[Xaositect]

Ну тут тоже должно быть $\varphi(|S|^n) = n\varphi(|S|)$, потому что множество $n$-ок элементов $S$ имеет мощность $|S|^n$.

[purser]

Сорри...А можно поподробней, я совсем запутался)

[Xaositect]

Мы хотим определить количество информации, несомое элементом множества. При этом мы хотим, чтобы $n$ элементов множества несли в $n$ раз больше информации, чем $1$ элемент.
$n$ элементов из множества можно выбрать $|S|^n$ способами - $|S|$ способов для первого элемента, $|S|$ способов для второго и т.д.
Например, если элемент множества $S = \{0,1\}$ несет некоторое количество информации $b = \varphi(2)$, то $3$ элемента должны нести $3b$. Эти три элемента составляют элемнт множества $S^3 = \{(000, 001, 010, 011, 100, 101, 110, 111\}$, в нем $8 = 2^3$ элементов. Значит, мы хотим, чтобы $\varphi(8) = 3\varphi(2)$. Так же и для всех $k$ и $n$ если множество $S$ содержит $k$ элементов, то множество наборов $n$ элементов $S$ имеет мощность $k^n$ и для количества информации мы получаем соотношение $\varphi(k^n) = n\varphi(k)$.

[purser]

Спасибо большое, теперь всё ясно