2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Логарифм и количество информации
Сообщение27.08.2014, 19:06 


26/01/11
66
Теорема: Единственной монотонной функцией, удовлетворяющей условию $\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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Прошу пояснить док-во теоремы
Сообщение27.08.2014, 19:20 


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

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


06/10/08
6422
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 


26/01/11
66
Спасибо...Действительно, в самом условии ошибка. Вот цитирую абзац перед теоремой.
"Конечным комбинаторным источником называется произвольное конечное множество 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 
Заслуженный участник
Аватара пользователя


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

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


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

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


06/10/08
6422
Мы хотим определить количество информации, несомое элементом множества. При этом мы хотим, чтобы $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 


26/01/11
66
Спасибо большое, теперь всё ясно

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group