(번역) Subadditivity

Original article: w:Subadditivity

 

수학(mathematics)에서, 부분-덧셈성(subadditivity)은 도메인(domain)의 두 원소(elements)의 합에 대한 함수를 평가하면 항상 각 원소에서 함수의 값의 합보다 작거나 같은 값을 반환한다고, 대략적으로, 설명하는 함수의 속성입니다. 수학의 다양한 영역, 특히 노름(norms)과 제곱근(square roots)에서 부분-덧셈 함수의 수많은 예가 있습니다. 덧셈 맵(Additive maps)은 부분덧셈 함수의 특수한 경우입니다.

Definitions

부분-덧셈 함수는 다음 속성을 갖는 덧셈 아래에서 둘 다 닫혀(closed) 있는 도메인(domain) A와 순서화된(ordered) 코도메인(codomain) B를 가지는 함수(function) $f:A\to B$입니다:

$\mathrm{\forall }x,y\in A,f(x+y)\le f(x)+f(y).$

한 예제는 도메인과 코도메인으로 비-음의(non-negative) 실수(real numbers)를 가지는 제곱근(square root) 함수인데, 왜냐하면 $\mathrm{\forall }x,y\ge 0$에 대해 다음을 가지기 때문입니다:

$\sqrt{x+y}\le \sqrt{x}+\sqrt{y}.$

[[sequence|수열(sequence)]] $\left\{a_n\right\},n\ge 1$은, 만약 모든 m과 n에 대해 다음 부등식(inequality)을 만족시키면 부분-덧셈적(subadditive)이라고 불립니다:

$a_{n+m}\le a_n+a_m$

이것은 수열이 자연수의 집합 위에 함수로 해석되면 부분덧셈 함수의 특별한 경우입니다.

오목 수열은 부분덧셈적이지만, 그 전환은 거짓임을 주목하십시오. 예를 들어, $a_1,a_2,...$에 $0.5,1$의 값을 임의로 할당하면, 그 수열은 부분덧셈적이지만 오목하지 않습니다.

Properties

Sequences

부분덧셈 수열과 관련된 유용한 결과는 마이클 페케떼(Michael Fekete)에 기인한 다음 보조정리입니다.

 

Fekete's Subadditive Lemma — 모든 각 부분덧셈의 수열 ${\left\{a_n\right\}}_{n=1}^{\mathrm{\infty }}$에 대해, 극한(limit) ${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{n}}$이 존재하고 하한(infimum) $inf\frac{a_n}{n}$과 같습니다.  (그 극한은 $-\mathrm{\infty }$일 수 있습니다.)}}

Proof 

${\displaystyle s^{\ast }:=\underset{n}{inf}\frac{a_n}{n}}$라고 놓습니다.

정의에 의해, $\underset{n}{lim inf}\frac{a_n}{n}\ge s^{\ast }$입니다. 따라서 $\underset{n}{lim sup}\frac{a_n}{n}\le s^{\ast }$를 보이는 것으로 충분합니다.

만약 그것이 아니면, 모든  $k$에 대해 $\frac{a_{n_k}}{n_k}>s^{\ast }+ϵ$를 만족하는 수열 $(a_{n_k}{)}_k$과 $ϵ>0$이 존재합니다. $\frac{a_m}{m}<s^{\ast }+ϵ/2$을 만족하는 $a_m$을 취하십시오.

무한 비둘기집 원리(infinitary pigeonhole principle)에 의해, 우리는 부분수열 $(a_{n_k}{)}_k$을 얻으며, 그것의 인덱스는 같은 잔여 클래스 모듈로 $m$에 모두 속하고, 따라서 그것들은 $m$의 배수만큼 전진합니다. 이 수열은, 충분히 오랫동안 계속되며, $s^{\ast }+ϵ$ 기울기 직선 아래로 내려가는 것은 부분덧셈성에 의해 강제될 것입니다. 이는 모순입니다.$◼$

페케떼의 보조정리의 아날로그는 초월덧셈 수열에 대해 마찬가지로 유지됩니다, 즉: 
$a_{n+m}\ge a_n+a_m.$  (그 극한은 그때에 양의 무한대가 될 수 있습니다: 수열 $a_n=\log n!$을 생각해 보십시오.)

부등식 $a_{n+m}\le a_n+a_m$을 모든 m과 n에 대해 유지하는 것을 요구하지 않지만, 오직 m과 n에 대해 $\frac{1}{2}\le \frac{m}{n}\le 2$임을 만족하도록 요구하는 페케떼의 보조정리의 확장이 있습니다. 

Proof

무한 비둘기집 원리를 사용할 때까지 이전과 같이 증명을 계속하십시오.

수열 $a_m,a_{2m},a_{3m},...$을 생각해 보십시오. $2m/m=2$이기 때문에, $a_{2m}\le 2a_m$을 가집니다. 유사하게, $a_{3m}\le a_{2m}+a_m\le 3a_m$, 등을 가집니다.  

가정에 의해, 임의의 $s,t\in \mathbb{N}$에 대해, 만약 다음이면 그들 위에 덧셈가능성을 사용할 수 있습니다:

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

만약 연속 변수를 다루게 되면, $a_{n_k}$에서 $a_{n_k}+[\ln 1.5,\ln 3]$로, 그 다음에 $a_{n_k}+\ln 1.5+[\ln 1.5,\ln 3]$로, 등으로 가도록 덧셈가능성을 사용할 수 있으며, 이는 전체 구간 $a_{n_k}+[\ln 1.5,+\mathrm{\infty })$을 덮습니다.

비록 연속 변수를 가지지 않을지라도, 여전히 증명을 완료하기에 충분한 정수를 다룰 수 있습니다. $n_k$를 다음을 만족하게 충분하게 크게 놓습니다:

${\displaystyle \ln (2)>\ln (1.5)+\ln \left(\frac{1.5n_k+m}{1.5n_k}\right)}$

그런-다음 $n^{\prime }$을 교집합 $(n_k+m\mathbb{Z})\cap (\ln n_k+[\ln (1.5),\ln (3)])$에서 가장 작은 숫자로 놓습니다. $n_k$에 대한 가정에 의해, 구간 $\ln n_k+[\ln (1.5),\ln (3)]$와 $\ln n^{\prime }+[\ln (1.5),\ln (3)]$가 중간에서 접촉함을 (그림을 그려서) 쉽게 알 수 있습니다. 따라서, 이 과정을 반복함으로써, $(n_k+m\mathbb{Z})\cap (\ln n_k+[\ln (1.5),\mathrm{\infty }])$ 전체를 덮습니다.

이것과 함께, 모든 $a_{n_k},a_{n_{k+1}},...$는 이전 증명에서 처럼 아래로 강제됩니다.$◼$

 

더욱이, 조건 $a_{n+m}\le a_n+a_m$은 $a_{n+m}\le a_n+a_m+\varphi (n+m)$처럼 약화될 수 있습니다: $\varphi$는 적분 $\int \varphi (t)t^{-2}dt$가 (무한대 근처로) 수렴함을 만족하는 증가하는 함수라는 조건 아래에서 그렇습니다.

역시 어떤 종류의 초과덧셈성(superadditivity)과 부분덧셈성이 모두 존재하면 페케떼의 보조정리에서 그 존재가 명시된 극한까지 수렴의 율을 추론할 수 있는 결과가 있습니다.

게다가, 페케떼의 보조정리의 아날로그는 순응-가능 그룹의, 나아가서, 취소 왼쪽-순응가능 반그룹의 유한 부분집합에서 (추가적인 가정과 함께) 부분덧셈 실수 맵에 대해 증명되어 왔습니다.

Functions

Theorem: — 모든 각 측정가능(measurable) 부분덧셈 함수 $f:(0,\mathrm{\infty })\to \mathbb{R}$에 대해, 극한 ${\displaystyle \underset{t\to \mathrm{\infty }}{lim}\frac{f(t)}{t}}$이 존재하고 ${\displaystyle \underset{t>0}{inf}\frac{f(t)}{t}}$와 같습니다 (그 극한은 $-\mathrm{\infty }$가 될 수 있습니다)}}

만약 f가 부분덧셈 함수이고, 0이 그것의 도메인 내에 있으면, f(0) ≥ 0입니다. 이것을 보이기 위해, 꼭대기에서 부등식을 취하십시오. $f(x)\ge f(x+y)-f(y)$입니다. 따라서 $f(0)\ge f(0+y)-f(y)=0$입니다.

$f(0)\ge 0$을 갖는 오목 함수(concave function) $f:[0,\mathrm{\infty })\to \mathbb{R}$는 역시 부분덧셈적입니다. 이것을 보이기 위해, 먼저 $f(x)\ge \frac{y}{x+y}f(0)+\frac{x}{x+y}f(x+y)$임을 관찰하십시오. 그런-다음 $f(x)$와 $f(y)$에 대한 이 경계의 합을 바라보면, 마침내 f가 부분덧셈적임을 확인할 것입니다.

부분덧셈 함수의 부정은 초월덧셈적(superadditive)입니다.

Examples in various domains

Entropy

엔트로피(Entropy)는 폰 노이만(von Neumann)으로 인해 일반화된 공식의 양자 역학(quantum mechanics)뿐만 아니라 정보 이론(information theory)과 통계적 물리학(statistical physics)에서 기본적인 역할을 합니다. 엔트로피는 모든 그것의 공식에서 항상 부분덧셈 양으로 나타나며, 초월시스템의 엔트로피 또는 무작위 변수 집합의 합집합은 항상 개별 구성 요소의 엔트로피 합계보다 작거나 같아야 함을 의미합니다. 추가적으로, 물리학에서 엔트로피는 고전 통계적 역학과 그것의 양자 아날로그(quantum analog)에서 엔트로피의 강한 부분덧셈성과 같은 몇 가지 더 엄격한 부등식을 만족시킵니다.

Economics

부분덧셈성은 일부 특정 비용 함수(cost functions)의 필수 속성입니다. 그것은, 일반적으로, 자연 독점(natural monopoly)의 검증을 위한 필요충분(iff) 조건입니다. 이것은 한 기업의 생산이 같은 수의 기업에 의해 원래 수량의 일부를 생산하는 것보다 (평균 비용 측면에서) 사회적으로 덜 비싸다는 것을 의미합니다.

규모의 경제(Economies of scale)는 부분덧셈 평균 비용(average cost) 함수에 의해 표현됩니다.

보완재의 경우를 제외하고, (수량의 함수로서) 재화의 가격은 부분덧셈적이어야 합니다. 그렇지 않으면, 만약 두 항목의 비용의 합계가 두 항목을 함께 묶은 비용보다 저렴하다면, 아무도 그 묶음을 사지 않을 것이며, 묶음의 가격이 두 개의 개별 항목 가격의 합계가 "되도록" 효과적으로 발생합니다. 따라서 자연 독점에 대해 충분 조건이 아님을 증명합니다; 왜냐하면 교환 단위가 항목의 실제 비용이 아닐 수 있기 때문입니다. 이 상황은 일부 소수가 특정 정부 수준에서 특정 자유의 상실이 많은 정부가 더 낫다는 것을 의미한다고 주장하는 정치 분야의 모든 사람에게 친숙합니다; 대다수는 어떤 다른 정확한 비용 단위가 있다고 주장합니다.

Finance

부분덧셈성은 위험 관리(risk management)에서 일관된 위험 측정(coherent risk measures)의 바람직한 속성 중 하나입니다. 위험 측정 부분덧셈성 뒤에 있는 경제적 직관은, 최악의 경우에서, 포트폴리오 위험 노출이 포트폴리오를 구성하는 단순히 개별 위치의 위험 노출 합계와 같아야 한다는 것입니다. 임의의 다른 경우에서 다각화(diversification)의 효과는 개별 위험 노출의 합보다 낮은 포트폴리오 노출을 초래할 것입니다. 부분덧셈성의 부족은 위험 인수의 정규성(normality)의 가정에 의존하지 않는 VaR 모델의 주요 비판 중 하나입니다. 가우스 VaR은 부분덧셈성을 보장합니다; 예를 들어, 신뢰 수준 $1-p$에서 2개의 단일 긴 위치 포트폴리오 $V$의 가우스 VaR은,  평균 포트폴리오 가치 변동은 영이고 VaR은 음의 손실로 정의됨을 가정합니다:

${\text{VaR}}_p\equiv z_p{\sigma }_{\mathrm{\Delta }V}=z_p\sqrt{{\sigma }_x^2+{\sigma }_y^2+2{\rho }_{xy}{\sigma }_x{\sigma }_y}$

여기서 $z_p$는 확률 수준 $p$에서 정규 누적 분포 함수(cumulative distribution function)의 역, ${\sigma }_x^2,{\sigma }_y^2$는 개별 위치 반환 분산이고 ${\rho }_{xy}$는 두 개의 개별 위치 반환 사이의 선형 상관 측정(linear correlation measure)입니다. 분산(variance)이 항상 양수이기 때문에,

$\sqrt{{\sigma }_x^2+{\sigma }_y^2+2{\rho }_{xy}{\sigma }_x{\sigma }_y}\le {\sigma }_x+{\sigma }_y$

따라서 가우스 VaR은 ${\rho }_{xy}\in [-1,1]$의 임의의 값에 대해 부분덧셈적이고, 특히, ${\rho }_{xy}=1$일 때 개별 위험 노출의 합과 같으며 이는 포트폴리오 위험에 분산 효과가 없는 경우입니다.

Thermodynamics

부분덧셈성은 과잉 몰 부피와 혼합 열(heat of mixing) 또는 과잉 엔탈피와 같은 비-이상적 용액(ideal solutions)과 혼합물의 열역학적 속성에서 발생합니다.

Combinatorics on words

팩토리얼 언어(language) $L$은 만약 한 단어(word)가 $L$에 있으면, 해당 단어의 모든 인수(factors)도 $L$에 있는 언어입니다. 단어 조합론에서, 공통 문제는 팩토리얼 언어에서 길이-$n$ 단어의 수 $A(n)$을 결정하는 것입니다. 분명하게, $A(m+n)\le A(m)A(n)$이므로, $\log A(n)$은 부분덧셈적이고, 따라서 페케떼의 보조정리가 $A(n)$의 성장을 추정하기 위해 사용될 수 있습니다.

모든 각 $k\ge 1$에 대해, 알파벳 $1,2,...,k$에서 무작위로 균등하게 길이 $n$의 두 문자열을 표본으로 얻습니다. 가장 긴 공통 부분문자열(longest common subsequence)의 기대 길이는 $n$의 초월-덧셈 함수이고, 따라서 기대 길이가  $\sim {\gamma }_{k}n$으로 성장함을 만족하는 숫자 ${\gamma }_k\ge 0$가 존재합니다. $n=1$을 갖는 경우를 확인함으로써, $\frac{1}{k}<{\gamma }_k\le 1$를 쉽게 가집니다. 어쨌든, ${\gamma }_2$의 정확한 값 조차 오직 0.788와 0.827 사이에 있는 것으로 알려져 있습니다.

See also

• Superadditivity
• Triangle inequality – Property of geometry, also used to generalize the notion of "distance" in metric spaces – Property of geometry, also used to generalize the notion of "distance" in metric spaces

References

• György Pólya and Gábor Szegő. "Problems and theorems in analysis, volume 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.