Subadditivity

(Redirected fromSubadditive function)

Inmathematics,subadditivity is a property of a function that states, roughly, that evaluating the function for the sum of twoelements of thedomain always returns something less than or equal to the sum of the function's values at each element. There are numerous examples of subadditive functions in various areas of mathematics, particularlynorms andsquare roots.Additive maps are special cases of subadditive functions.

Definitions

edit

A subadditive function is afunction $f\colon A\to B$ , having adomainA and anordered codomainB that are bothclosed under addition, with the following property: $\forall x,y\in A,f(x+y)\leq f(x)+f(y).$

An example is thesquare root function, having thenon-negative real numbers as domain and codomain:since $\forall x,y\geq 0$ we have: ${\sqrt {x+y}}\leq {\sqrt {x}}+{\sqrt {y}}.$

Asequence $\left\{a_{n}\right\}_{n\geq 1}$ is calledsubadditive if it satisfies theinequality $a_{n+m}\leq a_{n}+a_{m}$ for allm andn. 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.

Properties

edit

Sequences

edit

A useful result pertaining to subadditive sequences is the followinglemma due toMichael Fekete.^[1]

Fekete's Subadditive Lemma—For every subadditive sequence ${\left\{a_{n}\right\}}_{n=1}^{\infty }$ , thelimit $\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}$ is equal to theinfimum $\inf {\frac {a_{n}}{n}}$ . (The limit may be $-\infty$ .)

Proof

Let $s^{*}:=\inf _{n}{\frac {a_{n}}{n}}$ .

By definition, $\liminf _{n}{\frac {a_{n}}{n}}\geq s^{*}$ . So it suffices to show $\limsup _{n}{\frac {a_{n}}{n}}\leq s^{*}$ .

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

Since $s^{*}:=\inf _{n}{\frac {a_{n}}{n}}$ , there exists an $a_{m}$ such that ${\frac {a_{m}}{m}}<s^{*}+\epsilon$ .

Byinfinitary pigeonhole principle, there exists a sub-subsequence of $(a_{n_{k}})_{k}$ , whose indices all belong to the sameresidue class modulo $m {\displaystyle m}$ , and so they advance by multiples of $m {\displaystyle m}$ . This sequence, continued for long enough, would be forced by subadditivity to dip below the $s^{*}+\epsilon$ slope line, a contradiction.

In more detail, by subadditivity, we have

${\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 \\a_{n_{k}}&\leq a_{n_{1}}+a_{m}(n_{k}-n_{1})/m\end{aligned}}}$

which implies $\limsup _{k}a_{n_{k}}/n_{k}\leq a_{m}/m<s^{*}+\epsilon$ , a contradiction.

The analogue of Fekete's lemma holds for superadditive sequences as well, that is: $a_{n+m}\geq a_{n}+a_{m}.$ (The limit then may be positive infinity: consider the sequence $a_{n}=\log n!$ .)

There are extensions of Fekete's lemma that do not require the inequality $a_{n+m}\leq a_{n}+a_{m}$ to hold for allm andn, but only form andn such that ${\textstyle {\frac {1}{2}}\leq {\frac {m}{n}}\leq 2.}$

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}\leq 2a_{m}$ . Similarly, we have $a_{3m}\leq a_{2m}+a_{m}\leq 3a_{m}$ , etc.

By the assumption, for any $s,t\in \mathbb {N}$ , we can use subadditivity on them if

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

If we were dealing with continuous variables, then we can use subadditivity to go from $a_{n_{k}}$ to $a_{n_{k}}+[\ln 1.5,\ln 3]$ , then to $a_{n_{k}}+\ln 1.5+[\ln 1.5,\ln 3]$ , and so on, which covers the entire interval $a_{n_{k}}+[\ln 1.5,+\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

$\ln(2)>\ln(1.5)+\ln \left({\frac {1.5n_{k}+m}{1.5n_{k}}}\right)$ then let $n^{'} {\displaystyle n'}$ be the smallest number in the intersection $(n_{k}+m\mathbb {Z} )\cap (\ln n_{k}+[\ln(1.5),\ln(3)])$ . By the assumption on $n_{k}$ , it's easy to see (draw a picture) that the intervals $\ln n_{k}+[\ln(1.5),\ln(3)]$ and $\ln n'+[\ln(1.5),\ln(3)]$ touch in the middle. Thus, by repeating this process, we cover the entirety of $(n_{k}+m\mathbb {Z} )\cap (\ln n_{k}+[\ln(1.5),\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}\leq a_{n}+a_{m}$ may be weakened as follows: $a_{n+m}\leq a_{n}+a_{m}+\phi (n+m)$ provided that $\phi$ is an increasing function such that the integral ${\textstyle \int \phi (t)t^{-2}\,dt}$ converges (near the infinity).^[2]

There are also results that allow one to deduce therate of convergence to the limit whose existence is stated in Fekete's lemma if some kind of bothsuperadditivity and subadditivity is present.^[3]^[4]

Besides, analogues of Fekete's lemma have been proved for subadditive real maps (with additional assumptions) from finite subsets of an amenable group^[5]^[6],^[7]and further, of a cancellative left-amenable semigroup.^[8]

Functions

edit

Theorem:^[9]—For everymeasurable subadditive function $f:(0,\infty )\to \mathbb {R} ,$ the limit $\lim _{t\to \infty }{\frac {f(t)}{t}}$ exists and is equal to $\inf _{t>0}{\frac {f(t)}{t}}.$ (The limit may be $-\infty .$ )

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

Aconcave function $f:[0,\infty )\to \mathbb {R}$ with $f(0)\geq 0$ is also subadditive.To see this, one first observes that $f(x)\geq \textstyle {\frac {y}{x+y}}f(0)+\textstyle {\frac {x}{x+y}}f(x+y)$ .Then looking at the sum of this bound for $f(x)$ and $f(y)$ , will finally verify thatf is subadditive.^[10]

The negative of a subadditive function issuperadditive.

Examples in various domains

edit

Entropy

edit

Entropy plays a fundamental role ininformation theory andstatistical physics, as well as inquantum mechanics in a generalized formulation due tovon 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 itsquantum analog.

Economics

edit

Subadditivity is an essential property of some particularcost functions. It is, generally, anecessary and sufficient condition for the verification of anatural 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 subadditiveaverage 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]}

Finance

edit

Subadditivity is one of the desirable properties ofcoherent risk measures inrisk management.^[11] 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 ofVaR models which do not rely on the assumption ofnormality of risk factors. The Gaussian VaR ensures subadditivity: for example, the Gaussian VaR of a two unitary long positions portfolio $V {\displaystyle 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, ${\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}}}$ where $z_{p}$ is the inverse of the normalcumulative distribution function at probability level $p {\displaystyle p}$ , $\sigma _{x}^{2},\sigma _{y}^{2}$ are the individual positions returns variances and $\rho _{xy}$ is thelinear correlation measure between the two individual positions returns. Sincevariance is always positive, ${\sqrt {\sigma _{x}^{2}+\sigma _{y}^{2}+2\rho _{xy}\sigma _{x}\sigma _{y}}}\leq \sigma _{x}+\sigma _{y}$ Thus the Gaussian VaR is subadditive for any value of $\rho _{xy}\in [-1,1]$ and, in particular, it equals the sum of the individual risk exposures when $\rho _{xy}=1$ which is the case of no diversification effects on portfolio risk.

Thermodynamics

edit

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

Combinatorics on words

edit

A factoriallanguage $L {\displaystyle L}$ is one where if aword is in $L {\displaystyle L}$ , then allfactors of that word are also in $L {\displaystyle L}$ . Incombinatorics on words, a common problem is to determine the number $A(n)$ of length- $n {\displaystyle n}$ words in a factorial language. Clearly $A(m+n)\leq A(m)A(n)$ , so $\log A(n)$ is subadditive, and hence Fekete's lemma can be used to estimate the growth of $A(n)$ .^[12]

For every $k\geq 1$ , sample two strings of length $n {\displaystyle n}$ uniformly at random on the alphabet $1,2,...,k$ . The expected length of thelongest common subsequence is asuper-additive function of $n {\displaystyle n}$ , and thus there exists a number $\gamma _{k}\geq 0$ , such that the expected length grows as $\sim \gamma _{k}n$ . By checking the case with $n=1$ , we easily have ${\frac {1}{k}}<\gamma _{k}\leq 1$ . The exact value of even $\gamma _{2}$ , however, is only known to be between 0.788 and 0.827.^[13]

Notes

edit

^Fekete, M. (1923). "Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten".Mathematische Zeitschrift.17 (1):228–249.doi:10.1007/BF01504345.S2CID 186223729.
^de Bruijn, N.G.; Erdös, P. (1952). "Some linear and some quadratic recursion formulas. II".Nederl. Akad. Wetensch. Proc. Ser. A.55:152–163.doi:10.1016/S1385-7258(52)50021-0. (The same asIndagationes Math.14.) See also Steele 1997, Theorem 1.9.2.
^Michael J. Steele. "Probability theory and combinatorial optimization". SIAM, Philadelphia (1997).ISBN 0-89871-380-3.
^Michael J. Steele (2011).CBMS Lectures on Probability Theory and Combinatorial Optimization. University of Cambridge.
^Lindenstrauss, Elon;Weiss, Benjamin (2000)."Mean topological dimension".Israel Journal of Mathematics.115 (1):1–24.CiteSeerX 10.1.1.30.3552.doi:10.1007/BF02810577.ISSN 0021-2172. Theorem 6.1
^Ornstein, Donald S.;Weiss, Benjamin (1987)."Entropy and isomorphism theorems for actions of amenable groups".Journal d'Analyse Mathématique.48 (1):1–141.doi:10.1007/BF02790325.ISSN 0021-7670.
^Gromov, Misha (1999). "Topological Invariants of Dynamical Systems and Spaces of Holomorphic Maps: I".Mathematical Physics, Analysis and Geometry.2 (4):323–415.Bibcode:1999MPAG....2..323G.doi:10.1023/A:1009841100168.ISSN 1385-0172.S2CID 117100302.
^Ceccherini-Silberstein, Tullio; Krieger, Fabrice; Coornaert, Michel (2014)."An analogue of Fekete's lemma for subadditive functions on cancellative amenable semigroups".Journal d'Analyse Mathématique.124:59–81.arXiv:1209.6179.doi:10.1007/s11854-014-0027-4. Theorem 1.1
^Hille 1948, Theorem 6.6.1. (Measurability is stipulated in Sect. 6.2 "Preliminaries".)
^Schechter, Eric (1997).Handbook of Analysis and its Foundations. San Diego: Academic Press.ISBN 978-0-12-622760-4., p.314,12.25
^Rau-Bredow, H. (2019)."Bigger Is Not Always Safer: A Critical Analysis of the Subadditivity Assumption for Coherent Risk Measures".Risks.7 (3): 91.doi:10.3390/risks7030091.hdl:10419/257929.
^Shur, Arseny (2012). "Growth properties of power-free languages".Computer Science Review.6 (5–6):187–208.doi:10.1016/j.cosrev.2012.09.001.
^Lueker, George S. (May 2009)."Improved bounds on the average length of longest common subsequences".Journal of the ACM.56 (3):1–38.doi:10.1145/1516512.1516519.ISSN 0004-5411.S2CID 7232681.

References

edit

György Pólya andGábor Szegő.Problems and Theorems in Analysis, vol. 1. Springer-Verlag, New York (1976).ISBN 0-387-05672-6.
Einar Hille. "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.