Subadditivity

A subadditive function is a function $f\; \backslash colon\; A\; \backslash to\; B$, having a domain A and an ordered codomain B that are both closed under addition, with the following property:

$$\backslash forall\; x,\; y\; \backslash in\; A,\; f(x+y)\backslash leq\; f(x)+f(y).$$

An example is the square root function, having the non-negative real numbers as domain and codomain:

since $\backslash forall\; x,\; y\; \backslash geq\; 0$ we have:

$$\backslash sqrt\{x+y\}\backslash leq\; \backslash sqrt\{x\}+\backslash sqrt\{y\}.$$

A sequence $\backslash left\; \backslash \{\; a\_n\; \backslash right\; \backslash \}\_\{n\; \backslash geq\; 1\}$ is called subadditive if it satisfies the inequality

$$a\_\{n+m\}\backslash leq\; a\_n+a\_m$$

for all m and n. This is a special case of subadditive function, if a sequence is interpreted as a function on the set of natural numbers.

Note that while a concave sequence is subadditive, the converse is false. For example, arbitrarily assign $a\_1,\; a\_2,\; ...$ with values in $[0.5,\; 1]$; then the sequence is subadditive but not concave.

{{Anchor|Fekete's Subadditive Lemma}}A useful result pertaining to subadditive sequences is the following lemma due to Michael Fekete.{{cite journal |last=Fekete |first=M. |title=Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten |journal=Mathematische Zeitschrift |volume=17 |issue=1 |year=1923 |pages=228–249 |doi=10.1007/BF01504345 |s2cid=186223729 }}

{{math theorem|name=Fekete's Subadditive Lemma|math_statement= For every subadditive sequence $\{\backslash left\; \backslash \{\; a\_n\; \backslash right\; \backslash \}\}\_\{n=1\}^\backslash infty$, the limit $\backslash displaystyle\; \backslash lim\_\{n\; \backslash to\; \backslash infty\}\; \backslash frac\{a\_n\}\{n\}$ is equal to the infimum $\backslash inf\; \backslash frac\{a\_n\}\{n\}$. (The limit may be $-\backslash infty$.)}}

{{Math proof|proof=

Let $s^*\; :=\; \backslash inf\_n\; \backslash frac\{a\_n\}n$.

By definition, $\backslash liminf\_n\; \backslash frac\{a\_n\}n\; \backslash geq\; s^*$. So it suffices to show $\backslash limsup\_n\; \backslash frac\{a\_n\}n\; \backslash leq\; s^*$.

If not, then there exists a subsequence $(a\_\{n\_k\})\_k$, and an $\backslash epsilon\; >\; 0$, such that $\backslash frac\{a\_\{n\_k\}\}\{n\_k\}\; >\; s^*\; +\; \backslash epsilon$ for all $k$.

Since $s^*\; :=\; \backslash inf\_n\; \backslash frac\{a\_n\}n$, there exists an $a\_m$ such that .

By infinitary pigeonhole principle, there exists a sub-subsequence of $(a\_\{n\_k\})\_k$, whose indices all belong to the same residue class modulo $m$, and so they advance by multiples of $m$. This sequence, continued for long enough, would be forced by subadditivity to dip below the $s^*\; +\; \backslash epsilon$ slope line, a contradiction.

In more detail, by subadditivity, we have

which implies , a contradiction.

}}

The analogue of Fekete's lemma holds for superadditive sequences as well, that is:

$a\_\{n+m\}\backslash geq\; a\_n\; +\; a\_m.$ (The limit then may be positive infinity: consider the sequence $a\_n\; =\; \backslash log\; n!$.)

There are extensions of Fekete's lemma that do not require the inequality $a\_\{n+m\}\backslash le\; a\_n\; +\; a\_m$ to hold for all m and n, but only for m and n such that $\backslash frac\; 1\; 2\; \backslash le\; \backslash frac\; m\; n\; \backslash le\; 2.$

{{Math proof|proof=

Continue the proof as before, until we have just used the infinite pigeonhole principle.

Consider the sequence $a\_m,\; a\_\{2m\},\; a\_\{3m\},\; ...$. Since $2m/m\; =\; 2$, we have $a\_\{2m\}\; \backslash leq\; 2a\_m$. Similarly, we have $a\_\{3m\}\; \backslash leq\; a\_\{2m\}+a\_m\; \backslash leq\; 3a\_m$, etc.

By the assumption, for any $s,\; t\; \backslash in\; \backslash N$, we can use subadditivity on them if

$$\backslash ln(s+t)\; \backslash in\; [\backslash ln(1.5\; s),\; \backslash ln\; (3s)]\; =\; \backslash ln\; s\; +\; [\backslash ln\; 1.5,\; \backslash ln\; 3]$$

If we were dealing with continuous variables, then we can use subadditivity to go from $a\_\{n\_k\}$ to $a\_\{n\_k\}\; +\; [\backslash ln\; 1.5,\; \backslash ln\; 3]$, then to $a\_\{n\_k\}\; +\; \backslash ln\; 1.5\; +\; [\backslash ln\; 1.5,\; \backslash ln\; 3]$, and so on, which covers the entire interval $a\_\{n\_k\}\; +\; [\backslash ln\; 1.5,\; +\backslash infty)$.

Though we don't have continuous variables, we can still cover enough integers to complete the proof. Let $n\_k$ be large enough, such that

$$\backslash ln\; (2)\; >\; \backslash ln(1.5)\; +\; \backslash ln\; \backslash left(\backslash frac\{1.5\; n\_k\; +\; m\}\{1.5\; n\_k\}\backslash right)$$

then let $n\text{'}$ be the smallest number in the intersection $(n\_k\; +\; m\backslash Z)\; \backslash cap\; (\backslash ln\; n\_k\; +\; [\backslash ln(1.5),\; \backslash ln\; (3)])$. By the assumption on $n\_k$, it's easy to see (draw a picture) that the intervals $\backslash ln\; n\_k\; +\; [\backslash ln(1.5),\; \backslash ln\; (3)]$ and $\backslash ln\; n\text{'}\; +\; [\backslash ln(1.5),\; \backslash ln\; (3)]$ touch in the middle. Thus, by repeating this process, we cover the entirety of $(n\_k\; +\; m\backslash Z)\; \backslash cap\; (\backslash ln\; n\_k\; +\; [\backslash ln(1.5),\; \backslash infty])$.

With that, all $a\_\{n\_k\},\; a\_\{n\_\{k+1\}\},\; ...$ are forced down as in the previous proof. }}

Moreover, the condition $a\_\{n+m\}\backslash le\; a\_n\; +\; a\_m$ may be weakened as follows: $a\_\{n+m\}\backslash le\; a\_n\; +\; a\_m\; +\; \backslash phi(n+m)$ provided that $\backslash phi$ is an increasing function such that the integral $\backslash int\; \backslash phi(t)\; t^\{-2\}\; \backslash ,\; dt$ converges (near the infinity).{{cite journal |last1=de Bruijn |first1=N.G. |last2=Erdös |first2=P. |title=Some linear and some quadratic recursion formulas. II |journal=Nederl. Akad. Wetensch. Proc. Ser. A |volume=55 |year=1952 |pages=152–163|doi=10.1016/S1385-7258(52)50021-0 }} (The same as Indagationes Math. 14.) See also Steele 1997, Theorem 1.9.2.

There are also results that allow one to deduce the rate of convergence to the limit whose existence is stated in Fekete's lemma if some kind of both superadditivity and subadditivity is present.Michael J. Steele. "Probability theory and combinatorial optimization". SIAM, Philadelphia (1997). {{isbn|0-89871-380-3}}.{{cite video|author=Michael J. Steele|title=CBMS Lectures on Probability Theory and Combinatorial Optimization|publisher=University of Cambridge|year=2011|url=http://sms.cam.ac.uk/collection/1189351}}

Besides, analogues of Fekete's lemma have been proved for subadditive real maps (with additional assumptions) from finite subsets of an amenable group {{Cite journal| doi = 10.1007/BF02810577 | doi-access=free | issn = 0021-2172| volume = 115| issue = 1| pages = 1–24| last1 = Lindenstrauss| first1 = Elon| authorlink1=Elon Lindenstrauss | last2 = Weiss| first2 = Benjamin| authorlink2=Benjamin Weiss| title = Mean topological dimension| journal = Israel Journal of Mathematics| year = 2000| citeseerx = 10.1.1.30.3552}} Theorem 6.1

{{Cite journal| doi = 10.1007/BF02790325| doi-access=free | issn = 0021-7670| volume = 48| issue = 1| pages = 1–141| last1 = Ornstein| first1 = Donald S.|authorlink1=Donald Samuel Ornstein| last2 = Weiss| first2 = Benjamin| authorlink2=Benjamin Weiss| title = Entropy and isomorphism theorems for actions of amenable groups| journal = Journal d'Analyse Mathématique| year = 1987}}

,{{Cite journal| doi = 10.1023/A:1009841100168| issn = 1385-0172| volume = 2| issue = 4| pages = 323–415| last = Gromov| first = Misha| title = Topological Invariants of Dynamical Systems and Spaces of Holomorphic Maps: I| journal = Mathematical Physics, Analysis and Geometry| year = 1999| bibcode = 1999MPAG....2..323G| s2cid = 117100302}}

and further, of a cancellative left-amenable semigroup.{{Cite journal | arxiv = 1209.6179| last1 = Ceccherini-Silberstein| first1 = Tullio| title = An analogue of Fekete's lemma for subadditive functions on cancellative amenable semigroups| journal = Journal d'Analyse Mathématique| volume = 124| pages = 59–81| last2 = Krieger| first2 = Fabrice| last3 = Coornaert| first3 = Michel| year = 2014| doi = 10.1007/s11854-014-0027-4 | doi-access=free}} Theorem 1.1

{{math theorem|name=Theorem:Hille 1948, Theorem 6.6.1. (Measurability is stipulated in Sect. 6.2 "Preliminaries".)|math_statement= For every measurable subadditive function $f\; :\; (0,\backslash infty)\; \backslash to\; \backslash R,$ the limit $\backslash lim\_\{t\backslash to\backslash infty\}\; \backslash frac\{f(t)\}\{t\}$ exists and is equal to $\backslash inf\_\{t>0\}\; \backslash frac\{f(t)\}\{t\}.$ (The limit may be $-\backslash infty.$)}}

If f is a subadditive function, and if 0 is in its domain, then f(0) ≥ 0. To see this, take the inequality at the top. $f(x)\; \backslash ge\; f(x+y)\; -\; f(y)$. Hence $f(0)\; \backslash ge\; f(0+y)\; -\; f(y)\; =\; 0$

A concave function $f:\; [0,\backslash infty)\; \backslash to\; \backslash mathbb\{R\}$ with $f(0)\; \backslash ge\; 0$ is also subadditive.

To see this, one first observes that $f(x)\; \backslash ge\; \backslash textstyle\{\backslash frac\{y\}\{x+y\}\}\; f(0)\; +\; \backslash textstyle\{\backslash frac\{x\}\{x+y\}\}\; f(x+y)$.

Then looking at the sum of this bound for $f(x)$ and $f(y)$, will finally verify that f is subadditive.{{cite book | last = Schechter | first=Eric | author-link=Eric Schechter| title=Handbook of Analysis and its Foundations | publisher=Academic Press | location = San Diego | year=1997 | isbn=978-0-12-622760-4}}, p.314,12.25

The negative of a subadditive function is superadditive.

Entropy plays a fundamental role in information theory and statistical physics, as well as in quantum mechanics in a generalized formulation due to von Neumann.

Entropy appears always as a subadditive quantity in all of its formulations, meaning the entropy of a supersystem or a set union of random variables is always less or equal than the sum of the entropies of its individual components.

Additionally, entropy in physics satisfies several more strict inequalities such as the Strong Subadditivity of Entropy in classical statistical mechanics and its quantum analog.

Subadditivity is an essential property of some particular cost functions. It is, generally, a necessary and sufficient condition for the verification of a natural monopoly. It implies that production from only one firm is socially less expensive (in terms of average costs) than production of a fraction of the original quantity by an equal number of firms.

Economies of scale are represented by subadditive average cost functions.

Except in the case of complementary goods, the price of goods (as a function of quantity) must be subadditive. Otherwise, if the sum of the cost of two items is cheaper than the cost of the bundle of two of them together, then nobody would ever buy the bundle, effectively causing the price of the bundle to "become" the sum of the prices of the two separate items. Thus proving that it is not a sufficient condition for a natural monopoly; since the unit of exchange may not be the actual cost of an item. This situation is familiar to everyone in the political arena where some minority asserts that the loss of some particular freedom at some particular level of government means that many governments are better; whereas the majority assert that there is some other correct unit of cost.{{citation needed|date=October 2015}}

Subadditivity is one of the desirable properties of coherent risk measures in risk management.{{Cite journal | doi = 10.3390/risks7030091| title = Bigger Is Not Always Safer: A Critical Analysis of the Subadditivity Assumption for Coherent Risk Measures| year = 2019| last1 = Rau-Bredow | first1 = H. | journal = Risks| volume = 7| issue = 3|pages = 91| doi-access = free| hdl = 10419/257929| hdl-access = free}} The economic intuition behind risk measure subadditivity is that a portfolio risk exposure should, at worst, simply equal the sum of the risk exposures of the individual positions that compose the portfolio. The lack of subadditivity is one of the main critiques of VaR models which do not rely on the assumption of normality of risk factors. The Gaussian VaR ensures subadditivity: for example, the Gaussian VaR of a two unitary long positions portfolio $V$ at the confidence level $1-p$ is, assuming that the mean portfolio value variation is zero and the VaR is defined as a negative loss,

$$\backslash text\{VaR\}\_p\; \backslash equiv\; z\_\{p\}\backslash sigma\_\{\backslash Delta\; V\}\; =\; z\_\{p\}\backslash sqrt\{\backslash sigma\_x^2+\backslash sigma\_y^2+2\backslash rho\_\{xy\}\backslash sigma\_x\; \backslash sigma\_y\}$$

where $z\_p$ is the inverse of the normal cumulative distribution function at probability level $p$, $\backslash sigma\_x^2,\backslash sigma\_y^2$ are the individual positions returns variances and $\backslash rho\_\{xy\}$ is the linear correlation measure between the two individual positions returns. Since variance is always positive,

$$\backslash sqrt\{\backslash sigma\_x^2+\backslash sigma\_y^2+2\backslash rho\_\{xy\}\backslash sigma\_x\; \backslash sigma\_y\}\; \backslash leq\; \backslash sigma\_x\; +\; \backslash sigma\_y$$

Thus the Gaussian VaR is subadditive for any value of $\backslash rho\_\{xy\}\; \backslash in\; [-1,1]$ and, in particular, it equals the sum of the individual risk exposures when $\backslash rho\_\{xy\}=1$ which is the case of no diversification effects on portfolio risk.

Subadditivity occurs in the thermodynamic properties of non-ideal solutions and mixtures like the excess molar volume and heat of mixing or excess enthalpy.

A factorial language $L$ is one where if a word is in $L$, then all factors of that word are also in $L$. In combinatorics on words, a common problem is to determine the number $A(n)$ of length-$n$ words in a factorial language. Clearly $A(m+n)\; \backslash leq\; A(m)A(n)$, so $\backslash log\; A(n)$ is subadditive, and hence Fekete's lemma can be used to estimate the growth of $A(n)$.{{cite journal|last=Shur|first=Arseny|title=Growth properties of power-free languages|journal=Computer Science Review|date=2012|volume=6|issue=5–6|pages=187–208|doi=10.1016/j.cosrev.2012.09.001}}

For every $k\; \backslash geq\; 1$, sample two strings of length $n$ uniformly at random on the alphabet $1,\; 2,\; ...,\; k$. The expected length of the longest common subsequence is a super-additive function of $n$, and thus there exists a number $\backslash gamma\_k\; \backslash geq\; 0$, such that the expected length grows as $\backslash sim\; \backslash gamma\_k\; n$. By checking the case with $n=1$, we easily have . The exact value of even $\backslash gamma\_2$, however, is only known to be between 0.788 and 0.827.{{Cite journal |last=Lueker |first=George S. |date=May 2009 |title=Improved bounds on the average length of longest common subsequences |url=https://dl.acm.org/doi/10.1145/1516512.1516519 |journal=Journal of the ACM |language=en |volume=56 |issue=3 |pages=1–38 |doi=10.1145/1516512.1516519 |s2cid=7232681 |issn=0004-5411}}

• {{annotated link|Apparent molar property}}
• {{annotated link|Choquet integral}}
• {{annotated link|Superadditivity}}
• {{annotated link|Triangle inequality}}

• György Pólya and Gábor Szegő. Problems and Theorems in Analysis, vol. 1. Springer-Verlag, New York (1976). {{isbn|0-387-05672-6}}.
• Einar Hille. "[https://archive.org/details/functionalanalys017173mbp Functional analysis and semi-groups]". American Mathematical Society, New York (1948).
• N.H. Bingham, A.J. Ostaszewski. "Generic subadditive functions." Proceedings of American Mathematical Society, vol. 136, no. 12 (2008), pp. 4257–4266.

{{PlanetMath attribution|id=4615|title=subadditivity}}

Category:Mathematical analysis

Category:Sequences and series

Category:Types of functions