Ky Fan inequality
Encyclopedia
In mathematics
, there are two different results that share the common name of the Ky Fan inequality. One is an inequality involving the geometric mean
and arithmetic mean
of two sets of real number
s of the unit interval
. The result was published on page 5 of the book Inequalities by Beckenbach and Bellman (1961), who refer to an unpublished result of Ky Fan
. They mention the result in connection with the inequality of arithmetic and geometric means
and Augustin Louis Cauchy
's proof of this inequality by forward-backward-induction; a method which can also be used to prove the Ky Fan inequality.
The Ky Fan inequality is a special case of Levinson's inequality and also the starting point for several generalizations and refinements, some of them are given in the references below.
with equality if and only if x1 = x2 = . . . = xn.
denote the arithmetic and geometric mean, respectively, of x1, . . ., xn, and let
denote the arithmetic and geometric mean, respectively, of 1 − x1, . . ., 1 − xn. Then the Ky Fan inequality can be written as
which shows the similarity to the inequality of arithmetic and geometric means
given by Gn ≤ An.
with the convention 00 := 0. Equality holds if and only if either
The classical version corresponds to γi = 1/n for all i = 1, . . ., n.
to the strictly concave function
Detailed proof: (a) If at least one xi is zero, then the left-hand side of the Ky Fan inequality is zero and the inequality is proved. Equality holds if and only if the right-hand side is also zero, which is the case when γixi = 0 for all i = 1, . . ., n.
(b) Assume now that all xi > 0. If there is an i with γi = 0, then the corresponding xi > 0 has no effect on either side of the inequality, hence the ith term can be omitted. Therefore, we may assume that γi > 0 for all i in the following. If x1 = x2 = . . . = xn, then equality holds. It remains to show strict inequality if not all xi are equal.
The function f is strictly concave on (0,½], because we have for its second derivative
Using the functional equation
for the natural logarithm
and Jensen's inequality for the strictly concave f, we obtain that
where we used in the last step that the γi sum to one. Taking the exponential of both sides gives the Ky Fan inequality.
This second inequality is equivalent to the Brouwer Fixed Point Theorem
, but is often more convenient. Let S be a compact
convex
subset of a finite dimensional vector space
V, and let f(x,y) be a continuous function from S × S to the real numbers
that is lower semicontinuous in x, concave
in y and has f(z,z) ≤ 0 for all z in S.
Then there exists x* ∈ S such that for all y ∈ S, f( x* , y ) ≤ 0 . This Ky Fan Inequality is used to establish the existence of
equilibria in various games studied in economics.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, there are two different results that share the common name of the Ky Fan inequality. One is an inequality involving the geometric mean
Geometric mean
The geometric mean, in mathematics, is a type of mean or average, which indicates the central tendency or typical value of a set of numbers. It is similar to the arithmetic mean, except that the numbers are multiplied and then the nth root of the resulting product is taken.For instance, the...
and arithmetic mean
Arithmetic mean
In mathematics and statistics, the arithmetic mean, often referred to as simply the mean or average when the context is clear, is a method to derive the central tendency of a sample space...
of two sets of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s of the unit interval
Unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...
. The result was published on page 5 of the book Inequalities by Beckenbach and Bellman (1961), who refer to an unpublished result of Ky Fan
Ky Fan
Ky Fan was an American mathematician and Emeritus Professor of Mathematics at the University of California, Santa Barbara .-Biography:...
. They mention the result in connection with the inequality of arithmetic and geometric means
Inequality of arithmetic and geometric means
In mathematics, the inequality of arithmetic and geometric means, or more briefly the AM–GM inequality, states that the arithmetic mean of a list of non-negative real numbers is greater than or equal to the geometric mean of the same list; and further, that the two means are equal if and only if...
and Augustin Louis Cauchy
Augustin Louis Cauchy
Baron Augustin-Louis Cauchy was a French mathematician who was an early pioneer of analysis. He started the project of formulating and proving the theorems of infinitesimal calculus in a rigorous manner, rejecting the heuristic principle of the generality of algebra exploited by earlier authors...
's proof of this inequality by forward-backward-induction; a method which can also be used to prove the Ky Fan inequality.
The Ky Fan inequality is a special case of Levinson's inequality and also the starting point for several generalizations and refinements, some of them are given in the references below.
Statement of the classical version
If xi with 0 ≤ xi ≤ ½ for i = 1, ..., n are real numbers, thenwith equality if and only if x1 = x2 = . . . = xn.
Remark
Letdenote the arithmetic and geometric mean, respectively, of x1, . . ., xn, and let
denote the arithmetic and geometric mean, respectively, of 1 − x1, . . ., 1 − xn. Then the Ky Fan inequality can be written as
which shows the similarity to the inequality of arithmetic and geometric means
Inequality of arithmetic and geometric means
In mathematics, the inequality of arithmetic and geometric means, or more briefly the AM–GM inequality, states that the arithmetic mean of a list of non-negative real numbers is greater than or equal to the geometric mean of the same list; and further, that the two means are equal if and only if...
given by Gn ≤ An.
Generalization with weights
If xi ∈ [0,½] and γi ∈ [0,1] for i = 1, . . ., n are real numbers satisfying γ1 + . . . + γn = 1, thenwith the convention 00 := 0. Equality holds if and only if either
- γixi = 0 for all i = 1, . . ., n or
- all xi > 0 and there exists x ∈ (0,½] such that x = xi for all i = 1, . . ., n with γi > 0.
The classical version corresponds to γi = 1/n for all i = 1, . . ., n.
Proof of the generalization
Idea: Apply Jensen's inequalityJensen's inequality
In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context,...
to the strictly concave function
Detailed proof: (a) If at least one xi is zero, then the left-hand side of the Ky Fan inequality is zero and the inequality is proved. Equality holds if and only if the right-hand side is also zero, which is the case when γixi = 0 for all i = 1, . . ., n.
(b) Assume now that all xi > 0. If there is an i with γi = 0, then the corresponding xi > 0 has no effect on either side of the inequality, hence the ith term can be omitted. Therefore, we may assume that γi > 0 for all i in the following. If x1 = x2 = . . . = xn, then equality holds. It remains to show strict inequality if not all xi are equal.
The function f is strictly concave on (0,½], because we have for its second derivative
Using the functional equation
Functional equation
In mathematics, a functional equation is any equation that specifies a function in implicit form.Often, the equation relates the value of a function at some point with its values at other points. For instance, properties of functions can be determined by considering the types of functional...
for the natural logarithm
Natural logarithm
The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...
and Jensen's inequality for the strictly concave f, we obtain that
where we used in the last step that the γi sum to one. Taking the exponential of both sides gives the Ky Fan inequality.
The Ky Fan Inequality in Game Theory
A second inequality is also called the Ky Fan Inequality, because of a 1972 paper, "A minimax inequality and its applications".This second inequality is equivalent to the Brouwer Fixed Point Theorem
Brouwer fixed point theorem
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after Luitzen Brouwer. It states that for any continuous function f with certain properties there is a point x0 such that f = x0. The simplest form of Brouwer's theorem is for continuous functions f from a disk D to...
, but is often more convenient. Let S be a compact
Compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:* Interstate compact* Compact government, a type of colonial rule utilized in British North America...
convex
Convex
'The word convex means curving out or bulging outward, as opposed to concave. Convex or convexity may refer to:Mathematics:* Convex set, a set of points containing all line segments between each pair of its points...
subset of a finite dimensional vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
V, and let f(x,y) be a continuous function from S × S to the real numbers
that is lower semicontinuous in x, concave
Concave
The word concave means curving in or hollowed inward, as opposed to convex. The former may be used in reference to:* Concave lens, a lens with inward-curving surfaces.* Concave polygon, a polygon which is not convex....
in y and has f(z,z) ≤ 0 for all z in S.
Then there exists x* ∈ S such that for all y ∈ S, f( x* , y ) ≤ 0 . This Ky Fan Inequality is used to establish the existence of
equilibria in various games studied in economics.