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 {samp} }\min(x_{\alpha _{1}},x_{\alpha _{2}},\dots ,x_{\alpha _{k}})$

where $0<\lambda <\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 {samp} }\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 \rightarrow \infty$.

References

• Template:Cite arXiv