In mathematics, the rearrangement inequality [1] states that for every choice of real numbers
and every permutation of the numbers we have
. |
| (1) |
Informally, this means that in these types of sums, the largest sum is achieved by pairing large values with large values, and the smallest sum is achieved by pairing small values with large values. This can be formalised in the case that the are distinct, meaning that then:
Note that the rearrangement inequality ( 1 ) makes no assumptions on the signs of the real numbers, unlike inequalities such as the arithmetic-geometric mean inequality.
Many important inequalities can be proved by the rearrangement inequality, such as the arithmetic mean – geometric mean inequality, the Cauchy–Schwarz inequality, and Chebyshev's sum inequality.
As a simple example, consider real numbers : By applying ( 1 ) with for all it follows that
for every permutation of
The rearrangement inequality can be regarded as intuitive in the following way. Imagine there is a heap of $10 bills, a heap of $20 bills and one more heap of $100 bills. You are allowed to take 7 bills from a heap of your choice and then the heap disappears. In the second round you are allowed to take 5 bills from another heap and the heap disappears. In the last round you may take 3 bills from the last heap. In what order do you want to choose the heaps to maximize your profit? Obviously, the best you can do is to gain dollars. This is exactly what the upper bound of the rearrangement inequality ( 1 ) says for the sequences and In this sense, it can be considered as an example of a greedy algorithm.
Assume that and Consider a rectangle of width and height subdivided into columns of widths and the same number of rows of heights so there are small rectangles. You are supposed to take of these, one from each column and one from each row. The rearrangement inequality ( 1 ) says that you optimize the total area of your selection by taking the rectangles on the diagonal or the antidiagonal.
The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound to
Therefore, it suffices to prove the upper bound in ( 1 ) and discuss when equality holds. Since there are only finitely many permutations of there exists at least one for which the middle term in ( 1 )
is maximal. In case there are several permutations with this property, let σ denote one with the highest number of integers from satisfying
We will now prove by contradiction, that has to keep the order of (then we are done with the upper bound in ( 1 ), because the identity has that property). Assume that there exists a such that for all and Hence and there has to exist a with to fill the gap. Therefore,
| (2) |
which implies that
| (3) |
Expanding this product and rearranging gives
| (4) |
which is equivalent to ( 3 ). Hence the permutation
which arises from by exchanging the values and has at least one additional point which keeps the order compared to namely at satisfying and also attains the maximum in ( 1 ) due to ( 4 ). This contradicts the choice of
If then we have strict inequalities in ( 2 ), ( 3 ), and ( 4 ), hence the maximum can only be attained by permutations keeping the order of and every other permutation cannot be optimal.
As above, if suffices to treat the upper bound in ( 1 ). For a proof by mathematical induction, we start with Observe that
implies that
| (5) |
which is equivalent to
| (6) |
hence the upper bound in ( 1 ) is true for If then we get strict inequality in ( 5 ) and ( 6 ) if and only if Hence only the identity, which is the only permutation here keeping the order of gives the maximum.
As an induction hypothesis assume that the upper bound in the rearrangement inequality ( 1 ) is true for with and that in the case there is equality only when the permutation of keeps the order of
Consider now and Take a from the finite number of permutations of such that the rearrangement in the middle of ( 1 ) gives the maximal result. There are two cases:
A straightforward generalization takes into account more sequences. Assume we have finite ordered sequences of nonnegative real numbers
and a permutation of and another permutation of Then
Note that, unlike the standard rearrangement inequality ( 1 ), this statement requires the numbers to be nonnegative. A similar statement is true for any number of sequences with all numbers nonnegative.
Another generalization of the rearrangement inequality states that for all real numbers and every choice of continuously differentiable functions for such that their derivatives satisfy
the inequality
holds for every permutation of [2] Taking real numbers and the linear functions for real and the standard rearrangement inequality ( 1 ) is recovered.
Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable as a function of the time lag between them. The analysis of autocorrelation is a mathematical tool for finding repeating patterns, such as the presence of a periodic signal obscured by noise, or identifying the missing fundamental frequency in a signal implied by its harmonic frequencies. It is often used in signal processing for analyzing functions or series of values, such as time domain signals.
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.
In mathematics, when X is a finite set with at least two elements, the permutations of X (i.e. the bijective functions from X to X) fall into two classes of equal size: the even permutations and the odd permutations. If any total ordering of X is fixed, the parity (oddness or evenness) of a permutation of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that x < y and σ(x) > σ(y).
In mathematics, an infinite series of numbers is said to converge absolutely if the sum of the absolute values of the summands is finite. More precisely, a real or complex series is said to converge absolutely if for some real number Similarly, an improper integral of a function, is said to converge absolutely if the integral of the absolute value of the integrand is finite—that is, if
In theoretical physics, path-ordering is the procedure that orders a product of operators according to the value of a chosen parameter:
In mathematics, Muirhead's inequality, named after Robert Franklin Muirhead, also known as the "bunching" method, generalizes the inequality of arithmetic and geometric means.
In quantum field theory, the Wightman distributions can be analytically continued to analytic functions in Euclidean space with the domain restricted to the ordered set of points in Euclidean space with no coinciding points. These functions are called the Schwinger functions and they are real-analytic, symmetric under the permutation of arguments, Euclidean covariant and satisfy a property known as reflection positivity. Properties of Schwinger functions are known as Osterwalder–Schrader axioms. Schwinger functions are also referred to as Euclidean correlation functions.
In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an n × n-matrix B as a weighted sum of minors, which are the determinants of some (n − 1) × (n − 1)-submatrices of B. Specifically, for every i, the Laplace expansion along the ith row is the equality
In complex analysis, a branch of mathematics, a holomorphic function is said to be of exponential type C if its growth is bounded by the exponential function for some real-valued constant as . When a function is bounded in this way, it is then possible to express it as certain kinds of convergent summations over a series of other complex functions, as well as understanding when it is possible to apply techniques such as Borel summation, or, for example, to apply the Mellin transform, or to perform approximations using the Euler–Maclaurin formula. The general case is handled by Nachbin's theorem, which defines the analogous notion of -type for a general function as opposed to .
Toroidal coordinates are a three-dimensional orthogonal coordinate system that results from rotating the two-dimensional bipolar coordinate system about the axis that separates its two foci. Thus, the two foci and in bipolar coordinates become a ring of radius in the plane of the toroidal coordinate system; the -axis is the axis of rotation. The focal ring is also known as the reference circle.
In statistics, an exchangeable sequence of random variables is a sequence X1, X2, X3, ... whose joint probability distribution does not change when the positions in the sequence in which finitely many of them appear are altered. Thus, for example the sequences
In mathematics, the theory of optimal stopping or early stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance. A key example of an optimal stopping problem is the secretary problem. Optimal stopping problems can often be written in the form of a Bellman equation, and are therefore often solved using dynamic programming.
In probability theory and theoretical computer science, McDiarmid's inequality is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a bounded differences property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function.
In mathematics, particularly linear algebra, the Schur–Horn theorem, named after Issai Schur and Alfred Horn, characterizes the diagonal of a Hermitian matrix with given eigenvalues. It has inspired investigations and substantial generalizations in the setting of symplectic geometry. A few important generalizations are Kostant's convexity theorem, Atiyah–Guillemin–Sternberg convexity theorem, Kirwan convexity theorem.
In statistical mechanics, the Griffiths inequality, sometimes also called Griffiths–Kelly–Sherman inequality or GKS inequality, named after Robert B. Griffiths, is a correlation inequality for ferromagnetic spin systems. Informally, it says that in ferromagnetic spin systems, if the 'a-priori distribution' of the spin is invariant under spin flipping, the correlation of any monomial of the spins is non-negative; and the two point correlation of two monomial of the spins is non-negative.
For certain applications in linear algebra, it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices. Suppose is a finite sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter t:
In the mathematical field of group theory, an Artin transfer is a certain homomorphism from an arbitrary finite or infinite group to the commutator quotient group of a subgroup of finite index. Originally, such mappings arose as group theoretic counterparts of class extension homomorphisms of abelian extensions of algebraic number fields by applying Artin's reciprocity maps to ideal class groups and analyzing the resulting homomorphisms between quotients of Galois groups. However, independently of number theoretic applications, a partial order on the kernels and targets of Artin transfers has recently turned out to be compatible with parent-descendant relations between finite p-groups, which can be visualized in descendant trees. Therefore, Artin transfers provide a valuable tool for the classification of finite p-groups and for searching and identifying particular groups in descendant trees by looking for patterns defined by the kernels and targets of Artin transfers. These strategies of pattern recognition are useful in purely group theoretic context, as well as for applications in algebraic number theory concerning Galois groups of higher p-class fields and Hilbert p-class field towers.
The concept of angles between lines, between two planes or between a line and a plane can be generalized to arbitrary dimensions. This generalization was first discussed by Camille Jordan. For any pair of flats in a Euclidean space of arbitrary dimension one can define a set of mutual angles which are invariant under isometric transformation of the Euclidean space. If the flats do not intersect, their shortest distance is one more invariant. These angles are called canonical or principal. The concept of angles can be generalized to pairs of flats in a finite-dimensional inner product space over the complex numbers.
In mathematics, the injective tensor product of two topological vector spaces (TVSs) was introduced by Alexander Grothendieck and was used by him to define nuclear spaces. An injective tensor product is in general not necessarily complete, so its completion is called the completed injective tensor products. Injective tensor products have applications outside of nuclear spaces. In particular, as described below, up to TVS-isomorphism, many TVSs that are defined for real or complex valued functions, for instance, the Schwartz space or the space of continuously differentiable functions, can be immediately extended to functions valued in a Hausdorff locally convex TVS without any need to extend definitions from real/complex-valued functions to -valued functions.