Subadditivity

Template:Short description In mathematics, subadditivity is a property of a function that states, roughly, that evaluating the function for the sum of two elements of the domain 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, particularly norms and square roots. Additive maps are special cases of subadditive functions.

Definitions

A subadditive function is a function <math>f \colon A \to B</math>, having a domain A and an ordered codomain B that are both closed under addition, with the following property: <math display="block">\forall x, y \in A, f(x+y)\leq f(x)+f(y).</math>

An example is the square root function, having the non-negative real numbers as domain and codomain: since <math>\forall x, y \geq 0</math> we have: <math display="block">\sqrt{x+y}\leq \sqrt{x}+\sqrt{y}.</math>

A sequence <math>\left \{ a_n \right \}_{n \geq 1}</math> is called subadditive if it satisfies the inequality <math display="block"> a_{n+m}\leq a_n+a_m</math> 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 <math>a_1, a_2, ...</math> with values in <math>[0.5, 1]</math>; then the sequence is subadditive but not concave.

Properties

Sequences

Template:AnchorA useful result pertaining to subadditive sequences is the following lemma due to Michael Fekete.<ref>Template:Cite journal</ref>

Template:Math theorem_{n=1}^\infty</math>, the limit <math>\displaystyle \lim_{n \to \infty} \frac{a_n}{n}</math> is equal to the infimum <math>\inf \frac{a_n}{n}</math>. (The limit may be <math>-\infty</math>.)}}

Template:Math proof{n_k} > s^* + \epsilon</math> for all <math>k</math>.

Since <math>s^* := \inf_n \frac{a_n}n</math>, there exists an <math>a_m</math> such that <math>\frac{a_m}m < s^* + \epsilon</math>.

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

In more detail, by subadditivity, we have

<math display="inline">\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}</math>

which implies <math>\limsup_k a_{n_k}/n_k \leq a_m/m < s^* + \epsilon</math>, a contradiction. }}

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

There are extensions of Fekete's lemma that do not require the inequality <math>a_{n+m}\le a_n + a_m</math> to hold for all m and n, but only for m and n such that <math display="inline">\frac 1 2 \le \frac m n \le 2.</math>

Template:Math proof, ...</math> are forced down as in the previous proof. }}

Moreover, the condition <math>a_{n+m}\le a_n + a_m</math> may be weakened as follows: <math>a_{n+m}\le a_n + a_m + \phi(n+m)</math> provided that <math>\phi</math> is an increasing function such that the integral <math display="inline">\int \phi(t) t^{-2} \, dt</math> converges (near the infinity).<ref>Template:Cite journal (The same as Indagationes Math. 14.) See also Steele 1997, Theorem 1.9.2.</ref>

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.<ref>Michael J. Steele. "Probability theory and combinatorial optimization". SIAM, Philadelphia (1997). Template:Isbn.</ref><ref>Template:Cite video</ref>

Besides, analogues of Fekete's lemma have been proved for subadditive real maps (with additional assumptions) from finite subsets of an amenable group <ref>Template:Cite journal Theorem 6.1</ref> <ref>Template:Cite journal</ref> ,<ref>Template:Cite journal</ref> and further, of a cancellative left-amenable semigroup.<ref>Template:Cite journal Theorem 1.1</ref>

Functions

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. <math>f(x) \ge f(x+y) - f(y)</math>. Hence <math>f(0) \ge f(0+y) - f(y) = 0</math>

A concave function <math>f: [0,\infty) \to \mathbb{R}</math> with <math>f(0) \ge 0</math> is also subadditive. To see this, one first observes that <math>f(x) \ge \textstyle{\frac{y}{x+y}} f(0) + \textstyle{\frac{x}{x+y}} f(x+y)</math>. Then looking at the sum of this bound for <math>f(x)</math> and <math>f(y)</math>, will finally verify that f is subadditive.<ref>Template:Cite book, p.314,12.25</ref>

The negative of a subadditive function is superadditive.

Examples in various domains

Entropy

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.

Economics

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.Template:Citation needed

Finance

Subadditivity is one of the desirable properties of coherent risk measures in risk management.<ref name="Rau-Bredow">Template:Cite journal</ref> 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 <math> V </math> at the confidence level <math> 1-p </math> is, assuming that the mean portfolio value variation is zero and the VaR is defined as a negative loss, <math display="block"> \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} </math> where <math> z_p </math> is the inverse of the normal cumulative distribution function at probability level <math> p </math>, <math> \sigma_x^2,\sigma_y^2 </math> are the individual positions returns variances and <math> \rho_{xy} </math> is the linear correlation measure between the two individual positions returns. Since variance is always positive, <math display="block"> \sqrt{\sigma_x^2+\sigma_y^2+2\rho_{xy}\sigma_x \sigma_y} \leq \sigma_x + \sigma_y </math> Thus the Gaussian VaR is subadditive for any value of <math> \rho_{xy} \in [-1,1] </math> and, in particular, it equals the sum of the individual risk exposures when <math> \rho_{xy}=1 </math> which is the case of no diversification effects on portfolio risk.

Thermodynamics

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

Combinatorics on words

A factorial language <math>L</math> is one where if a word is in <math>L</math>, then all factors of that word are also in <math>L</math>. In combinatorics on words, a common problem is to determine the number <math>A(n)</math> of length-<math>n</math> words in a factorial language. Clearly <math>A(m+n) \leq A(m)A(n)</math>, so <math>\log A(n)</math> is subadditive, and hence Fekete's lemma can be used to estimate the growth of <math>A(n)</math>.<ref name=shur>Template:Cite journal</ref>

For every <math>k \geq 1</math>, sample two strings of length <math>n</math> uniformly at random on the alphabet <math>1, 2, ..., k</math>. The expected length of the longest common subsequence is a super-additive function of <math>n</math>, and thus there exists a number <math>\gamma_k \geq 0</math>, such that the expected length grows as <math>\sim \gamma_k n</math>. By checking the case with <math>n=1</math>, we easily have <math>\frac 1k < \gamma_k \leq 1</math>. The exact value of even <math>\gamma_2</math>, however, is only known to be between 0.788 and 0.827.<ref>Template:Cite journal</ref>

See also

• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link

Notes

<references />

References

• György Pólya and Gábor Szegő. Problems and Theorems in Analysis, vol. 1. Springer-Verlag, New York (1976). Template:Isbn.
• 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.

External links

{{#if: | This article incorporates material from the following PlanetMath articles, which are licensed under the Creative Commons Attribution/Share-Alike License: {{#if: | subadditivity | {{#if: 4615 | subadditivity | [{{{sourceurl}}} subadditivity] }} }}, {{#if: | {{{title2}}} | {{#if: | {{{title2}}} | [{{{sourceurl2}}} {{{title2}}}] }} }}{{#if: | , {{#if: | {{{title3}}} | {{#if: | {{{title3}}} | [{{{sourceurl3}}} {{{title3}}}] }} }} }}{{#if: | , {{#if: | {{{title4}}} | {{#if: | {{{title4}}} | [{{{sourceurl4}}} {{{title4}}}] }} }} }}{{#if: | , {{#if: | {{{title5}}} | {{#if: | {{{title5}}} | [{{{sourceurl5}}} {{{title5}}}] }} }} }}{{#if: | , {{#if: | {{{title6}}} | {{#if: | {{{title6}}} | [{{{sourceurl6}}} {{{title6}}}] }} }} }}{{#if: | , {{#if: | {{{title7}}} | {{#if: | {{{title7}}} | [{{{sourceurl7}}} {{{title7}}}] }} }} }}{{#if: | , {{#if: | {{{title8}}} | {{#if: | {{{title8}}} | [{{{sourceurl8}}} {{{title8}}}] }} }} }}{{#if: | , {{#if: | {{{title9}}} | {{#if: | {{{title9}}} | [{{{sourceurl9}}} {{{title9}}}] }} }} }}. | This article incorporates material from {{#if: | subadditivity | subadditivity}} on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. }}