View source for 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<sup>''n''</sup>&nbsp;&minus;&nbsp;1 nonempty subsets of ''S''.

Let ''S'' = {''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub>} and <math>  x_1< x_2< \dots < x_n </math>.

The [[identity (mathematics)|identity]] states that 

: <math> \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} ) </math>

where <math>0<\lambda<\infty</math> and the inner sum is over all possible samples of <math>k</math> elements of <math>n</math>, or conversely

: <math> \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} ) </math>

provided that <math>x_1> x_2> \dots > x_n</math>. 

Sorting identity automatically arranges its left-hand side in ascending order of <math>x_i</math> for the given right-hand side.

Sorting identity generalizes the [[maximum-minimums identity]] reduces to it in the limit <math>\lambda\rightarrow\infty</math>.

== References ==
* {{cite arXiv |last=Zaskulnikov |first=V. M. |authorlink= |eprint=1205.6546 |title=Statistical mechanics of fluids in a step potential |class= |year=2012 |version=v1 |accessdate=June 1, 2012 }}

[[Category:Mathematical identities]]