147
правок
Изменения
Нет описания правки
|statement = <tex>g(n) = H(\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}) = -k \log_2 \frac{1}{n}</tex>
|proof =
Будем рассматривать для <tex>k=1</tex> (1 бит).
Рассмотрим функцию <tex>g(mn)</tex>:
: <tex>g(mn)=g(m)+ \sum\limits_{i=1}^{m} \frac{1}{m} g(n) = g(m)+g(n)</tex>
Заметим, что:
: <tex>g(2)=1 \quad g(2^t)=t</tex>
Аналогично:: <tex>g(2n)=1 \log_2(n) \quad \quad g(2n^kt)=kt \cdot g(n)</tex>
: <tex>g(n) = 2^i \log_2(n) \quad \quad g(leq n^k)=k \cdot g(n)t < 2^{i+1}</tex>
По предыдущим рассуждениям: <tex>2^i \leq n^k < 2^i+1 \quad \quad g(2^i) \leq g(n^kt) < g(2^{i+1})</tex>
: <tex>i=\lfloor \log_2 n^k\rfloor \quad \quad i \leq k t \cdot g(n) <i+1\quad \quad i=\lfloor \log_2 n^t\rfloor </tex>
Разделив на <tex>t</tex> получаем: <tex>\frac{i}{kt} \leq g(n) < \frac{i+1}{kt}</tex>
Отсюда ясно, что если: <tex> kt\rightarrow \infty \quad \quad </tex> то получаем:<tex>g(n) = \log_2n = -k \log_2 \frac{1}{n}</tex>
}}
