Субаддитивность

Свойство некоторых математических функций

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

Определения

Субаддитивная функция — это функция , имеющая область определения A и упорядоченную область значений B , которые обе замкнуты относительно сложения, со следующим свойством: ${\displaystyle f\colon A\to B}$ $${\displaystyle \forall x,y\in A,f(x+y)\leq f(x)+f(y).}$$

Примером может служить функция квадратного корня , имеющая в качестве области определения и кодомена неотрицательные действительные числа : поскольку мы имеем: ${\displaystyle \forall x,y\geq 0}$ $${\displaystyle {\sqrt {x+y}}\leq {\sqrt {x}}+{\sqrt {y}}.}$$

Последовательность называется субаддитивной , если она удовлетворяет неравенству для всех m и n . Это частный случай субаддитивной функции, если последовательность интерпретируется как функция на множестве натуральных чисел. ${\displaystyle \left\{a_{n}\right\}_{n\geq 1}}$ $${\displaystyle a_{n+m}\leq a_{n}+a_{m}}$$

Обратите внимание, что хотя вогнутая последовательность является субаддитивной, обратное утверждение неверно. Например, случайным образом назначьте значения в ; тогда последовательность будет субаддитивной, но не вогнутой. ${\displaystyle a_{1},a_{2},...}$ ${\displaystyle [0.5,1]}$

Характеристики

Последовательности

Полезным результатом, относящимся к субаддитивным последовательностям, является следующая лемма , принадлежащая Майклу Фекете . ^[1]

Лемма Фекете о субаддитивности  —  Для каждой субаддитивной последовательности предел равен инфимуму . (Предел может быть равен . ) ${\displaystyle {\left\{a_{n}\right\}}_{n=1}^{\infty }}$ ${\displaystyle \displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}}$ ${\displaystyle \inf {\frac {a_{n}}{n}}}$ ${\displaystyle -\infty }$

Доказательство

Позволять . ${\displaystyle s^{*}:=\inf _{n}{\frac {a_{n}}{n}}}$

По определению, . Поэтому достаточно показать . ${\displaystyle \liminf _{n}{\frac {a_{n}}{n}}\geq s^{*}}$ ${\displaystyle \limsup _{n}{\frac {a_{n}}{n}}\leq s^{*}}$

Если нет, то существует подпоследовательность и , такие, что для всех . ${\displaystyle (a_{n_{k}})_{k}}$ ${\displaystyle \epsilon >0}$ ${\displaystyle {\frac {a_{n_{k}}}{n_{k}}}>s^{*}+\epsilon }$ ${\displaystyle k}$

Так как , то существует такое, что . ${\displaystyle s^{*}:=\inf _{n}{\frac {a_{n}}{n}}}$ ${\displaystyle a_{m}}$ ${\displaystyle {\frac {a_{m}}{m}}<s^{*}+\epsilon /2}$

По принципу бесконечной ячейки существует подподпоследовательность , все индексы которой принадлежат одному и тому же классу остатков по модулю , и поэтому они увеличиваются на кратные . Эта последовательность, продолжающаяся достаточно долго, была бы вынуждена из-за субаддитивности опуститься ниже линии наклона, противоречие. ${\displaystyle (a_{n_{k}})_{k}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle s^{*}+\epsilon }$

Более подробно, по субаддитивности, имеем

${\textstyle {\begin{aligned}a_{n_{2}}&\leq a_{n_{1}}+a_{m}(n_{2}-n_{1})/m\\a_{n_{3}}&\leq a_{n_{2}}+a_{m}(n_{3}-n_{2})/m\leq a_{n_{1}}+a_{m}(n_{3}-n_{1})/m\\\cdots &\cdots \end{aligned}}}$

что подразумевает ${\displaystyle \limsup _{k}a_{n_{k}}/n_{k}\leq a_{m}/m<s^{*}+\epsilon }$

Аналог леммы Фекете справедлив и для супераддитивных последовательностей, а именно: (Тогда пределом может быть положительная бесконечность: рассмотрим последовательность .) ${\displaystyle a_{n+m}\geq a_{n}+a_{m}.}$ ${\displaystyle a_{n}=\log n!}$

Существуют расширения леммы Фекете, которые не требуют, чтобы неравенство выполнялось для всех m и n , а только для m и n, таких что ${\displaystyle a_{n+m}\leq a_{n}+a_{m}}$ ${\textstyle {\frac {1}{2}}\leq {\frac {m}{n}}\leq 2.}$

Доказательство

Продолжайте доказательство, как и прежде, пока не воспользуемся принципом бесконечной ячейки.

Рассмотрим последовательность . Так как , то имеем . Аналогично имеем , и т.д. ${\displaystyle a_{m},a_{2m},a_{3m},...}$ ${\displaystyle 2m/m=2}$ ${\displaystyle a_{2m}\leq 2a_{m}}$ ${\displaystyle a_{3m}\leq a_{2m}+a_{m}\leq 3a_{m}}$

По предположению, для любого мы можем использовать субаддитивность на них, если ${\displaystyle s,t\in \mathbb {N} }$

$${\displaystyle \ln(s+t)\in [\ln(1.5s),\ln(3s)]=\ln s+[\ln 1.5,\ln 3]}$$

Если бы мы имели дело с непрерывными переменными, то мы могли бы использовать субаддитивность, чтобы перейти от к , затем к и т. д., что охватывает весь интервал . ${\displaystyle a_{n_{k}}}$ ${\displaystyle a_{n_{k}}+[\ln 1.5,\ln 3]}$ ${\displaystyle a_{n_{k}}+\ln 1.5+[\ln 1.5,\ln 3]}$ ${\displaystyle a_{n_{k}}+[\ln 1.5,+\infty )}$

Хотя у нас нет непрерывных переменных, мы все еще можем охватить достаточно целых чисел, чтобы завершить доказательство. Пусть будет достаточно большим, таким, что ${\displaystyle n_{k}}$

$${\displaystyle \ln(2)>\ln(1.5)+\ln \left({\frac {1.5n_{k}+m}{1.5n_{k}}}\right)}$$тогда пусть будет наименьшим числом в пересечении . По предположению о , легко увидеть (нарисовать рисунок), что интервалы и соприкасаются в середине. Таким образом, повторяя этот процесс, мы покрываем всю . ${\displaystyle n'}$ ${\displaystyle (n_{k}+m\mathbb {Z} )\cap (\ln n_{k}+[\ln(1.5),\ln(3)])}$ ${\displaystyle n_{k}}$ ${\displaystyle \ln n_{k}+[\ln(1.5),\ln(3)]}$ ${\displaystyle \ln n'+[\ln(1.5),\ln(3)]}$ ${\displaystyle (n_{k}+m\mathbb {Z} )\cap (\ln n_{k}+[\ln(1.5),\infty ])}$

При этом все прижимается вниз, как и в предыдущем доказательстве. ${\displaystyle a_{n_{k}},a_{n_{k+1}},...}$

Более того, условие можно ослабить следующим образом: при условии, что — возрастающая функция, такая, что интеграл сходится (вблизи бесконечности). ^[2] ${\displaystyle a_{n+m}\leq a_{n}+a_{m}}$ ${\displaystyle a_{n+m}\leq a_{n}+a_{m}+\phi (n+m)}$ ${\displaystyle \phi }$ ${\textstyle \int \phi (t)t^{-2}\,dt}$

Существуют также результаты, которые позволяют вывести скорость сходимости к пределу, существование которого утверждается в лемме Фекете, если присутствует некоторая разновидность как супераддитивности , так и субаддитивности. ^{[3] [4]}

Кроме того, аналоги леммы Фекете были доказаны для субаддитивных вещественных отображений (с дополнительными предположениями) из конечных подмножеств аменабельной группы ^{[5] [6]} , ^[7] и далее, сокращаемой левоаменабельной полугруппы. ^[8]

Функции

Теорема: ^[9]  —  Для каждой измеримой субаддитивной функциипределсуществует и равен(предел может быть) ${\displaystyle f:(0,\infty )\to \mathbb {R} ,}$ ${\displaystyle \lim _{t\to \infty }{\frac {f(t)}{t}}}$ ${\displaystyle \inf _{t>0}{\frac {f(t)}{t}}.}$ ${\displaystyle -\infty .}$

Если f — субаддитивная функция, и если 0 находится в ее области определения, то f (0) ≥ 0. Чтобы увидеть это, возьмем неравенство вверху. . Следовательно ${\displaystyle f(x)\geq f(x+y)-f(y)}$ ${\displaystyle f(0)\geq f(0+y)-f(y)=0}$

Вогнутая функция с также является субаддитивной. Чтобы увидеть это, сначала следует заметить, что . Затем, рассматривая сумму этой границы для и , окончательно убедимся, что f является субаддитивной. ^[10] ${\displaystyle f:[0,\infty )\to \mathbb {R} }$ ${\displaystyle f(0)\geq 0}$ ${\displaystyle f(x)\geq \textstyle {\frac {y}{x+y}}f(0)+\textstyle {\frac {x}{x+y}}f(x+y)}$ ${\displaystyle f(x)}$ ${\displaystyle f(y)}$

Отрицательная часть субаддитивной функции является супераддитивной .

Примеры в различных областях

Энтропия

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

Экономика

Субаддитивность является существенным свойством некоторых конкретных функций затрат . Это, как правило, необходимое и достаточное условие для проверки естественной монополии . Это подразумевает, что производство только одной фирмы является социально менее затратным (с точки зрения средних затрат), чем производство части исходного количества равным числом фирм.

Экономия за счет масштаба представлена ​​субаддитивными функциями средних затрат .

За исключением случаев дополнительных товаров, цена товаров (как функция количества) должна быть субаддитивной. В противном случае, если сумма стоимости двух товаров дешевле, чем стоимость набора из двух из них вместе, то никто никогда не купит этот набор, фактически заставляя цену набора «стать» суммой цен двух отдельных товаров. Таким образом, доказывая, что это не является достаточным условием для естественной монополии; поскольку единица обмена может не быть фактической стоимостью товара. Эта ситуация знакома каждому на политической арене, где некоторое меньшинство утверждает, что потеря некоторой конкретной свободы на некотором конкретном уровне правительства означает, что многие правительства лучше; тогда как большинство утверждает, что есть некоторая другая правильная единица стоимости. ^{[ необходима цитата ]}

Финансы

Субаддитивность является одним из желательных свойств последовательных мер риска в управлении рисками . ^[11] Экономическая интуиция, лежащая в основе субаддитивности меры риска, заключается в том, что подверженность риску портфеля должна, в худшем случае, просто равняться сумме подверженностей риску отдельных позиций, составляющих портфель. Отсутствие субаддитивности является одним из основных критических замечаний к моделям VaR , которые не полагаются на предположение о нормальности факторов риска. Гауссовская VaR обеспечивает субаддитивность: например, гауссовская VaR портфеля из двух унитарных длинных позиций на уровне доверия равна, предполагая, что средняя вариация стоимости портфеля равна нулю, а VaR определяется как отрицательный убыток, где — обратная функция нормального кумулятивного распределения на уровне вероятности , — дисперсии доходностей отдельных позиций, а — мера линейной корреляции между доходностями двух отдельных позиций. Поскольку дисперсия всегда положительна, то гауссовская VaR является субаддитивной для любого значения и, в частности, она равна сумме индивидуальных рисков, когда , что соответствует случаю отсутствия эффектов диверсификации на риск портфеля. ${\displaystyle V}$ ${\displaystyle 1-p}$ $${\displaystyle {\text{VaR}}_{p}\equiv z_{p}\sigma _{\Delta V}=z_{p}{\sqrt {\sigma _{x}^{2}+\sigma _{y}^{2}+2\rho _{xy}\sigma _{x}\sigma _{y}}}}$$ ${\displaystyle z_{p}}$ ${\displaystyle p}$ ${\displaystyle \sigma _{x}^{2},\sigma _{y}^{2}}$ ${\displaystyle \rho _{xy}}$ $${\displaystyle {\sqrt {\sigma _{x}^{2}+\sigma _{y}^{2}+2\rho _{xy}\sigma _{x}\sigma _{y}}}\leq \sigma _{x}+\sigma _{y}}$$ ${\displaystyle \rho _{xy}\in [-1,1]}$ ${\displaystyle \rho _{xy}=1}$

Термодинамика

Субаддитивность проявляется в термодинамических свойствах неидеальных растворов и смесей, таких как избыточный молярный объем и теплота смешения или избыточная энтальпия.

Комбинаторика слов

Факториальный язык — это язык, в котором если слово находится в , то все факторы этого слова также находятся в . В комбинаторике слов распространенной проблемой является определение количества слов длины в факториальном языке. Очевидно , что , так же как и субаддитивный, и, следовательно, лемма Фекете может быть использована для оценки роста . ^[12] ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle A(n)}$ ${\displaystyle n}$ ${\displaystyle A(m+n)\leq A(m)A(n)}$ ${\displaystyle \log A(n)}$ ${\displaystyle A(n)}$

Для каждого , выборка двух строк длины равномерно случайным образом в алфавите . Ожидаемая длина самой длинной общей подпоследовательности является супераддитивной функцией , и, таким образом, существует число , такое, что ожидаемая длина растет как . Проверяя случай с , мы легко получаем . Точное значение даже , однако, известно только как находящееся между 0,788 и 0,827. ^[13] ${\displaystyle k\geq 1}$ ${\displaystyle n}$ ${\displaystyle 1,2,...,k}$ ${\displaystyle n}$ ${\displaystyle \gamma _{k}\geq 0}$ ${\displaystyle \sim \gamma _{k}n}$ ${\displaystyle n=1}$ ${\displaystyle {\frac {1}{k}}<\gamma _{k}\leq 1}$ ${\displaystyle \gamma _{2}}$

Смотрите также

• Кажущаяся молярная характеристика  – разница в свойствах одного моля вещества в смеси по сравнению с идеальным раствором.
• Интеграл Шоке
• Супераддитивность  – свойство функции
• Неравенство треугольника  – свойство геометрии, также используемое для обобщения понятия «расстояние» в метрических пространствах.

Примечания

1. Фекете, М. (1923). «Über die Verteilung der Wurzeln bei gewissen алгебраишен Gleichungen mit ganzzahligen Koeffizienten». Mathematische Zeitschrift . 17 (1): 228–249. дои : 10.1007/BF01504345. S2CID  186223729.
2. де Брёйн, НГ; Эрдеш, П. (1952). «Некоторые формулы линейной и квадратичной рекурсии. II». Недерл. Акад. Ветенш. Учеб. Сер. А.​ 55 : 152–163. дои : 10.1016/S1385-7258(52)50021-0.(То же самое, что Indagationes Math. 14 .) См. также Steele 1997, теорема 1.9.2.
3. Майкл Дж. Стил. «Теория вероятностей и комбинаторная оптимизация». SIAM, Филадельфия (1997). ISBN 0-89871-380-3 . 
4. Майкл Дж. Стил (2011). Лекции CBMS по теории вероятностей и комбинаторной оптимизации. Кембриджский университет.
5. Линденштраусс, Элон ; Вайс, Бенджамин (2000). «Средняя топологическая размерность». Israel Journal of Mathematics . 115 (1): 1–24. CiteSeerX 10.1.1.30.3552 . doi : 10.1007/BF02810577 . ISSN  0021-2172. Теорема 6.1
6. Орнштейн, Дональд С.; Вайс , Бенджамин (1987). «Теоремы об энтропии и изоморфизме для действий аменабельных групп». Journal d'Analyse Mathématique . 48 (1): 1–141. doi : 10.1007/BF02790325 . ISSN  0021-7670.
7. Громов, Миша (1999). «Топологические инварианты динамических систем и пространств голоморфных отображений: I». Математическая физика, анализ и геометрия . 2 (4): 323–415. doi :10.1023/A:1009841100168. ISSN  1385-0172. S2CID  117100302.
8. Чеккерини-Зильберштейн, Туллио; Кригер, Фабрис; Курнарт, Мишель (2014). «Аналог леммы Фекете для субаддитивных функций на сокращающихся аменабельных полугруппах». Журнал Математического Анализа . 124 : 59–81. arXiv : 1209.6179 . дои : 10.1007/s11854-014-0027-4 .Теорема 1.1
9. Хилле 1948, Теорема 6.6.1. (Измеримость оговорена в разделе 6.2 «Предварительные сведения».)
10. Шехтер, Эрик (1997). Справочник по анализу и его основам . Сан-Диего: Academic Press. ISBN 978-0-12-622760-4., стр.314,12.25
11. Рау-Бредов, Х. (2019). «Больше не всегда безопаснее: критический анализ предположения о субаддитивности для когерентных мер риска». Риски . 7 (3): 91. doi : 10.3390/risks7030091 . hdl : 10419/257929 .
12. Шур, Арсений (2012). «Свойства роста языков без мощности». Computer Science Review . 6 (5–6): 187–208. doi :10.1016/j.cosrev.2012.09.001.
13. Люкер, Джордж С. (май 2009 г.). «Улучшенные границы средней длины самых длинных общих подпоследовательностей». Журнал ACM . 56 (3): 1–38. doi :10.1145/1516512.1516519. ISSN  0004-5411. S2CID  7232681.

Ссылки

• Дьёрдь Полья и Габор Сегё . Проблемы и теоремы анализа , вып. 1. Спрингер-Верлаг, Нью-Йорк (1976). ISBN 0-387-05672-6 . 
• Эйнар Хилле . «Функциональный анализ и полугруппы». Американское математическое общество, Нью-Йорк (1948).
• NH Bingham, AJ Ostaszewski. «Общие субаддитивные функции». Труды Американского математического общества, т. 136, № 12 (2008), стр. 4257–4266.

Внешние ссылки

В данной статье использованы материалы из раздела «Субаддитивность» на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .