Subadditive function
   HOME

TheInfoList



OR:

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 In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . E ...
.
Additive map In algebra, an additive map, Z-linear map or additive function is a function f that preserves the addition operation: f(x + y) = f(x) + f(y) for every pair of elements x and y in the domain of f. For example, any linear map is additive. When the ...
s are special cases of subadditive functions.


Definitions

A subadditive function is a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
f \colon A \to B, having a domain ''A'' and an ordered
codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either th ...
''B'' that are both closed under addition, with the following property: \forall x, y \in A, f(x+y)\leq f(x)+f(y). An example is the
square root In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . ...
function, having the
non-negative In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s as domain and codomain, since \forall x, y \geq 0 we have: \sqrt\leq \sqrt+\sqrt. A
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
\left \, n \geq 1, is called subadditive if it satisfies the
inequality Inequality may refer to: Economics * Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy * Economic inequality, difference in economic well-being between population groups * ...
a_\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, randomly assign a_1, a_2, ... with values in 0.5, 1, then the sequence is subadditive but not concave.


Properties


Sequences

A useful result pertaining to subadditive sequences is the following lemma due to
Michael Fekete Michael (Mihály) Fekete ( he, מיכאל פקטה; 19 July 1886 – 13 May 1957) was a Hungarian- Israeli mathematician. Biography Fekete was born in 1886 in Zenta, Austria-Hungary (today Senta, Serbia). He received his PhD in 1909 from ...
. The analogue of Fekete's lemma holds for superadditive sequences as well, that is: a_\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_\le a_n + a_m to hold for all ''m'' and ''n'', but only for ''m'' and ''n'' such that \frac 1 2 \le \frac m n \le 2. Moreover, the condition a_\le a_n + a_m may be weakened as follows: a_\le a_n + a_m + \phi(n+m) provided that \phi is an increasing function such that the integral \int \phi(t) t^ \, dt converges (near the infinity). 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 In mathematics, a function f is superadditive if f(x+y) \geq f(x) + f(y) for all x and y in the domain of f. Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality a_ \geq a_n + a_m for all m and n. The t ...
and subadditivity is present. Besides, analogues of Fekete's lemma have been proved for subadditive real maps (with additional assumptions) from finite subsets of an amenable group , and further, of a cancellative left-amenable semigroup.


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. f(x) \ge f(x+y) - f(y). Hence f(0) \ge f(0+y) - f(y) = 0 A concave function f: 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, 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 In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
for the verification of a
natural monopoly A natural monopoly is a monopoly in an industry in which high infrastructural costs and other barriers to entry relative to the size of the market give the largest supplier in an industry, often the first supplier in a market, an overwhelming adv ...
. 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 In microeconomics, economies of scale are the cost advantages that enterprises obtain due to their scale of operation, and are typically measured by the amount of output produced per unit of time. A decrease in cost per unit of output enables ...
are represented by subadditive
average cost In economics, average cost or unit cost is equal to total cost (TC) divided by the number of units of a good produced (the output Q): AC=\frac. Average cost has strong implication to how firms will choose to price their commodities. Firms’ sale ...
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.


Finance

Subadditivity is one of the desirable properties of
coherent risk measure In the fields of actuarial science and financial economics there are a number of ways that risk can be defined; to clarify the concept theoreticians have described a number of properties that a risk measure might or might not have. A coherent ris ...
s in risk management. 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. In any other case the effects of diversification would result in a portfolio exposure that is lower than the sum of the individual risk exposures. The lack of subadditivity is one of the main critiques of
VaR Var or VAR may refer to: Places * Var (department), a department of France * Var (river), France * Vār, Iran, village in West Azerbaijan Province, Iran * Var, Iran (disambiguation), other places in Iran * Vár, a village in Obreja commune, Ca ...
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, \text_p \equiv z_\sigma_ = z_\sqrt where z_p is the inverse of the normal cumulative distribution function at probability level p , \sigma_x^2,\sigma_y^2 are the individual positions returns variances and \rho_ is the linear correlation measure between the two individual positions returns. Since
variance In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbe ...
is always positive, \sqrt \leq \sigma_x + \sigma_y Thus the Gaussian VaR is subadditive for any value of \rho_ \in 1,1 and, in particular, it equals the sum of the individual risk exposures when \rho_=1 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 Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
L is one where if a
word A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...
is in L, then all
factors Factor, a Latin word meaning "who/which acts", may refer to: Commerce * Factor (agent), a person who acts for, notably a mercantile and colonial agent * Factor (Scotland), a person or firm managing a Scottish estate * Factors of production, su ...
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) \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). For every k \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 A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring: unlike substrings, subsequences are not required to occupy conse ...
is a ''super''-additive function of 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 1k < \gamma_k \leq 1. The exact value of even \gamma_2, however, is only known to be between 0.788 and 0.827.


See also

* * * *


Notes


References

* György Pólya and Gábor Szegő. "Problems and theorems in analysis, volume 1". Springer-Verlag, New York (1976). . * 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

{{PlanetMath attribution, id=4615, title=subadditivity Mathematical analysis Sequences and series