Мажоризация

Материал из Википедии — свободной энциклопедии

Мажориза́ция — математический термин из теории множеств.

[править] Определение

Пусть $X=\{x_1; x_2; \ldots; x_n\}, Y=\{y_1; y_2; \ldots; y_n\}$ , где $x_1 \ge x_2 \ge \ldots \ge x_n, y_1 \ge y_2 \ge \ldots \ge y_n$ .

Говорят, что множество $X$ мажори́рует множество $Y$ (обозначается $X\succ Y$ ), если верно следующее:

для любого $k=1\ldots n-1$ , $\sum_{i=1}^k x_i \ge \sum_{i=1}^k y_i$ ; и $\sum_{i=1}^n x_i = \sum_{i=1}^n y_i$

Если последнее равенство заменить менее сильным условием $\sum_{i=1}^n x_i \ge \sum_{i=1}^n y_i$ , то $X$ нестрого мажорирует $Y$ .

Мажоризацию можно обобщить на случай неупорядоченных наборов чисел. Множество $X$ мажорирует множество $Y$ , если невозрастающая перестановка $X$ мажорирует невозрастающую перестановку $Y$ .

[править] Примеры

$\{8; 7; 1\} \succ \{6; 5; 5\}$ , так как $8 \ge 6,\ 8+7\ge6+5,\ 8+7+1=6+5+5$

$\{3; 2\} \succ \{3; 2\}$ , так как $3 \ge 3,\ 3+2=3+2$

Вообще, для любых $x_1 \ge x_2 \ge \ldots \ge x_n$ выполняется следующее:

$\{x_1+x_2+\ldots +x_n;\underbrace{0; 0;\ldots ;0}_{n-1} \} \succ \{x_1;x_2;\ldots ;x_n\} \succ \{\underbrace{\frac{x_1+\ldots +x_n}{n}; \frac{x_1+\ldots +x_n}{n}; \ldots ;\frac{x_1+\ldots +x_n}{n}}_{n}\}$