Distribution algebra

In mathematics, the sorting identity is a relation between the ordered set of a set S of n numbers and the minima of the 2ⁿ − 1 nonempty subsets of S.

Let S = {x₁, x₂, ..., x_n} and $x_1<x_2<\dots <x_n$.

The identity states that

$\sum _{l=1}^n{\lambda }^l{x}_l=\sum _{k=1}^n(1-\lambda {)}^{k-1}{\lambda }^{n-k+1}\sum _{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}}min(x_{{\alpha }_1},x_{{\alpha }_2},\dots ,x_{{\alpha }_k})$

where $0<\lambda <\mathrm{\infty }$ and the inner sum is over all possible samples of $k$ elements of $n$, or conversely

$\sum _{l=1}^n{\lambda }^l{x}_l=\sum _{k=1}^n(1-\lambda {)}^{k-1}{\lambda }^{n-k+1}\sum _{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}}max(x_{{\alpha }_1},x_{{\alpha }_2},\dots ,x_{{\alpha }_k})$

provided that $x_1>x_2>\dots >x_n$.

Sorting identity automatically arranges its left-hand side in ascending order of $x_i$ for the given right-hand side.

Sorting identity generalizes the maximum-minimums identity reduces to it in the limit $\lambda \to \mathrm{\infty }$.

References

• Template:Cite arXiv