2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Логарифм и количество информации
Сообщение27.08.2014, 19:06 
Теорема: Единственной монотонной функцией, удовлетворяющей условию $\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)

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 19:10 
Аватара пользователя
У Вас явно опечатка в условии, потому что $C\log k$ не удовлетворяет условию.

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 19:20 
Я так понимаю, тут nk просто переобозначили как k. Теорема из книжки "Сжатие и поиск информации" Кричевский, стр.15

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 19:27 
Аватара пользователя
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).

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

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 20:06 
Спасибо...Действительно, в самом условии ошибка. Вот цитирую абзац перед теоремой.
"Конечным комбинаторным источником называется произвольное конечное множество 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)$

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 20:12 
Аватара пользователя
Ну тут тоже должно быть $\varphi(|S|^n) = n\varphi(|S|)$, потому что множество $n$-ок элементов $S$ имеет мощность $|S|^n$.

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 20:20 
Сорри...А можно поподробней, я совсем запутался)

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 20:32 
Аватара пользователя
Мы хотим определить количество информации, несомое элементом множества. При этом мы хотим, чтобы $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)$.

 
 
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 21:44 
Спасибо большое, теперь всё ясно

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group