Количество комбинаций с ограничениями

[Mihaylo]

Мне интересно, кто-нибудь проникся идеей об измерении энтропии среднего значения? Пожалуйста, arseniiv, iancaple, ex-math, Евгений Машеров отпишитесь, что вы думаете по этому поводу. Выдвигаемая гипотеза - среднее значение чисел массива уменьшает энтропию массива значений $X_i$. Вычислена теоретическая величина этой энтропии, представленные результаты в целом укладываются в неформальное представление. Проблема в том, что данный подход "немного делает больно" шенноновской теории, а именно: обходится без нее.

[arseniiv]

Mihaylo в сообщении #1052856 писал(а):

Выдвигаемая гипотеза - среднее значение чисел массива уменьшает энтропию массива значений $X_i$.

Лично мне просто непонятно, что это значит.

Потом, как и со многими практическими срезами углов и подгонками «как-нибудь, лишь бы работало», тут, скорее всего, неверное толкование причин работы, если вообще что-то работает (я сильно не вникал в ваши идеи, да и разброс у них по нескольким темам), и энтропия, к примеру, вообще ни при чём, а при чём что-нибудь другое.

[iancaple]

Mihaylo в сообщении #1043787 писал(а):

Ну, друзья, надо что-то однозначно делать с моим куполом...

Видите ли, полторы страницы, до процитированного места, мы занимались вероятностью модального значения, это точная и, видимо, сложная математическая задача. Даже найти моду ($S_1,S_2$, при которых для данных $m,n$ число разбиений максимально) я не знаю как. В предположении, что это близко к распределению Фишера, заметим, что у распределения Фишера мода не совпадает со средним значением. Я хотел, но так и не собрался, сделать прогу, выдающую число разбиений для указанных четырех аргументов, чтобы понять, что там на самом деле.
А то, что Вы сообщили потом -это известные и математически простые вещи.

[Mihaylo]

arseniiv писал(а):

Потом, как и со многими практическими срезами углов и подгонками «как-нибудь, лишь бы работало», тут, скорее всего, неверное толкование причин работы, если вообще что-то работает (я сильно не вникал в ваши идеи, да и разброс у них по нескольким темам), и энтропия, к примеру, вообще ни при чём, а при чём что-нибудь другое.

Да, действительно запутал всех почти одинаковыми темами "Количество комбинаций..." и "Количество размещений кактуса". Название обеих тем несколько устарело, ибо изначально ставились узкие вопросы.
arseniiv, обратите внимание, эти темы повествуют о разном. В текущей теме речь о "более высокодуховных проблемах общества" - об энтропии, о теории разбиений и т.п. А в соседней теме обсуждение перешло в разработку алгоритмов сортировки, также с привлечением понятия энтропии.

iancaple писал(а):

$S_1,S_2$, при которых для данных $m,n$ число разбиений максимально

Это вторая задача с двумя условиями $S_1$, $S_2$. Она не решена.
А первая задача о среднем (с одним условием $S_1$) решена и получены следствия. И математические выкладки действительно простые, но из них можно делать некоторые важные выводы. Например, когда распределение вероятностей неизвестно и теория Шеннона напрямую не применима, прекрасно работает "теория Хартли".
Аналогично можно сделать выкладки для второй задачи ...если решить ее.

[arseniiv]

(Оффтоп)

Mihaylo в сообщении #1052936 писал(а):

обратите внимание, эти темы повествуют о разном

Спасибо, я заметил.

[Mihaylo]

Можно также получить энтропию экстремума (максимума или минимума) массива из $n$ чисел $x_i$. Экстремум - это также интегральная характеристика массива.

Пусть имеется массив из $n$ чисел, принимающих натуральные значения от 1 до $M$. Стало известно, что максимум чисел равен $X_m$.
Это означает, что:
1) одно из чисел равно $X_m$;
2) остальные числа принимают значения от 1 до $X_m$.

Существует $n$ вариантов массивов, когда одно из значений $x_i=X_m$. Дополнительно к этому существует ${X_m}^{n-1}$ комбинаций остальных $(n-1)$ чисел.

В итоге получаем энтропию максимума натуральных чисел
$H=\log(n\cdot {X_m}^{n-1})=\log n + (n-1)\log X_m$

Для интегральных характеристик интерес представляет удельная энтропия
$h=\frac{H}{n}=\frac{1}{n}\log n + \frac{n-1}{n}\log X_m=\log X_m - \frac{1}{n}\log \frac{X_m}{n}$

При $n\to\infty$ вторая составляющая бесконечно мала
$h=\log X_m$,
что очевидно.

-- 19.09.2015, 15:57 --

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

Задача третья. Имеется массив из $n$ чисел: $x_1, x_2, ..., x_n$. Все числа принимают натуральные значения от 1 до $m$. Необходимо пересчитать количество всевозможных комбинаций чисел при условии, что их произведение равно некоторому числу $P$, где $1 \leqslant P \leqslant m^ n$.

[Mihaylo]

В принципе тут же нашел решение. Необходимо разбить число $P$ на простые множители и извлечь степени $\alpha_1, \alpha_2, ..., \alpha_k$ при этих простых числах.
Тогда можно воспользоваться формулой при $M\to\infty$

Mihaylo в сообщении #1042906 писал(а):

$N = \frac{(n+S-1)!}{S!\cdot(n-1)!}$

где принять $S = \alpha_i$

Тогда количество комбинаций равно
$N=\prod\limits_{i=1}^{k}\frac{(n+\alpha_i-1)!}{\alpha_i!(n-1)!}$

Удельная энтропия
$h=\frac{\log N}{n}=\frac{1}{n}\sum\limits_{i=1}^{k}\log \frac{(n+\alpha_i-1)!}{\alpha_i!(n-1)!}$

Применяем формулу Муавра-Стирлинга, помня, что $\alpha_i$ должны принимать значения 0 или достаточно большие.
$h=\sum\limits_{i=1}^{k}[(\frac{\alpha_i}{n}+1)\log(\frac{\alpha_i}{n}+1)-\frac{\alpha_i}{n}\log\frac{\alpha_i}{n}]=\sum\limits_{i=1}^{k}[\frac{\alpha_i}{n}\log(1+(\frac{\alpha_i}{n})^{-1})+\log(\frac{\alpha_i}{n}+1)]$

Очень интересно, как ведут себя отношения $\frac{\alpha_i}{n}$ при росте $n$ и значениях $P$ вблизи $m^n$.

[Mihaylo]

Рассчитаем энтропию медианы натуральных чисел.

Пусть имеется массив из $n$ чисел, принимающих натуральные значения от 1 до $M$. Стало известно, что медиана уникальна и равна $X_m$. При этом будем считать, что число $n$ - четное.
Тогда ровно $\frac{n}{2}$ чисел меньше или равно $X_m$, другие $\frac{n}{2}$ чисел больше $X_m$.
Энтропия
$H=\log({X_m}^{\frac{n}{2}}(M-X_m)^{\frac{n}{2}})=\frac{n}{2}\log X_m+\frac{n}{2}\log(M-X_m)$
Удельная энтропия не зависит от $n$
$h=\frac{H}{n}=\frac{1}{2}\log X_m+\frac{1}{2}\log(M-X_m)$

Получим аналогичные формулы для конечного множества действительных чисел. Множество $[X_1;X_2]$ разобьем на $M$ элементов длины $\Delta=\frac{X_2-X_1}{M}$, M$\to\infty$.
Энтропия таких множеств бесконечна
$h=\frac{1}{2}\log \frac{X_m-X_1}{\Delta}+\frac{1}{2}\log(\frac{X_2-X_m}{\Delta})$
Рассмотрим количество информации, приходящейся на один элемент массива
$i=\lim\limits_{M\to\infty}(\frac{H_0}{n}-\frac{H}{n})=\lim\limits_{M\to\infty}(\frac{\log M^n}{n}-h)=$
$=\lim\limits_{M\to\infty}[\log \frac{X_2-X_1}{\Delta}-\frac{1}{2}\log\frac{X_m-X_1}{\Delta}-\frac{1}{2}\log\frac{X_2-X_m}{\Delta}]=$
$=\lim\limits_{M\to\infty}[\log (X_2-X_1)-\frac{1}{2}\log(X_m-X_1)-\frac{1}{2}\log(X_2-X_m)]$

В итоге получаем величину информативности (количество информации) медианы конечного множества действительных чисел
$i=\log(\frac{X_2-X_1}{\sqrt{X_m-X_1}\sqrt{X_2-X_m}})$

[Mihaylo]

Информативность (количество информации) распределения вероятности непрерывной величины

В учебниках по теории информации принято рассматривать распределение вероятности неограниченной непрерывной величины. Это неправильный подход, который приводит лишь к понятию дифференциальной энтропии, которое является искусственным. Дифференциальная энтропия не является энтропией распределения вероятности непрерывной величины.

Непрерывная величина должна быть ограничена, иначе априорная и апостериорная энтропии, а также количество информации будут равны бесконечности. Рассмотрим случайную величину $x$ на отрезке $[X_1;X_2]$.
Используем меру Шеннона для дискретной случайной величины
$h(x)=-\sum\limits_{x}p(x)\log p(x)$
Разобьем отрезок $[X_1;X_2]$ на малые отрезки $\Delta=\frac{X_2-X_1}{M}$, где $M\to\infty$. Тогда $p(x)=F(x)\cdot \Delta$, где $F(x)$ - распределение плотности вероятности величины $x$.
$h(x)=-\sum\limits_{x}F(x)\cdot \Delta\cdot\log [F(x)\cdot \Delta]=$
$=-\sum\limits_{x}F(x)\cdot \Delta\cdot\log F(x)-\sum\limits_{x}F(x)\cdot \Delta\cdot\log\Delta=$
$=-\sum\limits_{x}F(x)\cdot\log F(x)\cdot\Delta-\log\Delta\sum\limits_{x}F(x)\cdot \Delta=$
$=-\int\limits_{X_1}^{X_2}F(x)\cdot\log F(x)\cdot dx-\lim\limits_{M\to\infty}(\log\Delta)\cdot\int\limits_{X_1}^{X_2}F(x)\cdot dx=$
$=-\int\limits_{X_1}^{X_2}F(x)\cdot\log F(x)\cdot dx-\lim\limits_{M\to\infty}(\log\Delta)$,
где по условию нормировки $\int\limits_{X_1}^{X_2}F(x)\cdot dx = 1$.

Компоненту $-\int\limits_{x}F(x)\cdot\log F(x)\cdot dx$ при неограниченном $x$ называют дифференциальной энтропией.

Вернемся к ограниченной величине $x$ и рассмотрим количество информации, а не энтропию
$i(x)=h_0(x)-h(x)=\lim\limits_{M\to\infty}(\log M) - [-\int\limits_{X_1}^{X_2}F(x)\cdot\log F(x)\cdot dx-\lim\limits_{M\to\infty}(\log\Delta)]=$
$=\lim\limits_{M\to\infty}\log (M\cdot\Delta) + \int\limits_{X_1}^{X_2}F(x)\cdot\log F(x)\cdot dx=$
$=\log (X_2-X_1) + \int\limits_{X_1}^{X_2}F(x)\cdot\log F(x)\cdot dx$

Полученное выражение является количеством информации распределения непрерывной величины. Можно рассчитать количество информации для различных законов распределений $F(x)$, но только не для нормального, экспоненциального и др., т.к. в этих случаях величина не является ограниченной.

Практически можно выбрать такие значения $X_1$ и $X_2$, при которых вероятности $p(x<X_1)$ и $p(x>X_2)$ будут практически равны нулю. Данный факт можно считать вероятностной ограниченностью величины $x$, при таких значениях $x$ интеграл $\int\limits_{X_1}^{X_2}F(x)\cdot\log F(x)\cdot dx$ также практически равен нулю.