Мажоризация - Majorization

В математика, мажоризация это Предварительный заказ на векторов из действительные числа. Для вектора ${ displaystyle mathbf {a} in mathbb {R} ^ {d}}$ , обозначим через ${ displaystyle mathbf {a} ^ { downarrow} in mathbb {R} ^ {d}}$ вектор с такими же компонентами, но отсортированный по убыванию. Данный ${ displaystyle mathbf {a}, mathbf {b} in mathbb {R} ^ {d}}$ мы говорим, что ${ Displaystyle mathbf {а}}$ слабо мажоритарно (или доминирует) ${ displaystyle mathbf {b}}$ снизу написано как ${ displaystyle mathbf {a} succ _ {w} mathbf {b}}$ если только

{ displaystyle sum _ {i = 1} ^ {k} a_ {i} ^ { downarrow} geq sum _ {i = 1} ^ {k} b_ {i} ^ { downarrow} quad { text {for}} k = 1, dots, d,}

Эквивалентно мы говорим, что ${ displaystyle mathbf {b}}$ является слабо мажоритарный (или преобладают) ${ Displaystyle mathbf {а}}$ снизу, записанный как ${ Displaystyle mathbf {б} пре _ {ш} mathbf {а}}$ .

Если ${ displaystyle mathbf {a} succ _ {w} mathbf {b}}$ и вдобавок ${ displaystyle sum _ {i = 1} ^ {d} a_ {i} = sum _ {i = 1} ^ {d} b_ {i}}$ мы говорим, что ${ Displaystyle mathbf {а}}$ мажоритарный (или доминирует) ${ displaystyle mathbf {b}}$ , записанный как ${ displaystyle mathbf {a} succ mathbf {b}}$ . В равной степени мы говорим, что ${ displaystyle mathbf {b}}$ является мажоритарный (или преобладают) ${ Displaystyle mathbf {а}}$ , записанный как ${ Displaystyle mathbf {б} Pre mathbf {а}}$ .

Обратите внимание, что порядок мажорирования не зависит от порядка компонентов векторов. ${ Displaystyle mathbf {а}}$ или же ${ displaystyle mathbf {b}}$ . Мажоризация - это не частичный заказ, поскольку ${ displaystyle mathbf {a} succ mathbf {b}}$ и ${ displaystyle mathbf {b} succ mathbf {a}}$ не подразумевают ${ displaystyle mathbf {a} = mathbf {b}}$ , это только означает, что компоненты каждого вектора равны, но не обязательно в одном порядке.

Обратите внимание, что обозначения в математической литературе противоречивы: некоторые используют обратные обозначения, например, ${ Displaystyle succ}$ заменяется на ${ Displaystyle Prec}$ .

Функция ${ displaystyle f: mathbb {R} ^ {d} to mathbb {R}}$ как говорят Шур выпуклый когда ${ displaystyle mathbf {a} succ mathbf {b}}$ подразумевает ${ Displaystyle е ( mathbf {a}) geq f ( mathbf {b})}$ . По аналогии, ${ Displaystyle е ( mathbf {а})}$ является Шур вогнутый когда ${ displaystyle mathbf {a} succ mathbf {b}}$ подразумевает ${ displaystyle f ( mathbf {a}) leq f ( mathbf {b}).}$

Частичный порядок мажорирования на конечных множествах, описанный здесь, может быть обобщен на Лоренц заказывает, частичный заказ на функции распределения. Например, распределение богатства является Лоренц-большим, чем другой, если его Кривая Лоренца ложь ниже другой. Таким образом, распределение богатства по Лоренцу имеет более высокую Коэффициент Джини, и есть еще Дифференциация доходов.

Примеры

Порядок записей не влияет на мажорирование, например, утверждение ${ Displaystyle (1,2) Prec (0,3)}$ просто эквивалентно ${ Displaystyle (2,1) Prec (3,0)}$ .

(Сильная) мажоритарность: ${ Displaystyle (1,2,3) Prec (0,3,3) Prec (0,0,6)}$ . Для векторов с п составные части

{ displaystyle left ({ frac {1} {n}}, ldots, { frac {1} {n}} right) Prec left ({ frac {1} {n-1}} , ldots, { frac {1} {n-1}}, 0 right) prec cdots prec left ({ frac {1} {2}}, { frac {1} {2} }, 0, ldots, 0 right) prec left (1,0, ldots, 0 right).}

(Слабая) мажоритарность: ${ Displaystyle (1,2,3) Prec _ {ш} (1,3,3) Pre _ {ш} (1,3,4)}$ . Для векторов с п составные части:

{ displaystyle left ({ frac {1} {n}}, ldots, { frac {1} {n}} right) prec _ {w} left ({ frac {1} {n -1}}, ldots, { frac {1} {n-1}}, 1 right).}

Геометрия мажоризации

Рисунок 1. Пример 2D-мажоризации

За ${ displaystyle mathbf {x}, mathbf {y} in mathbb {R} ^ {n},}$ у нас есть ${ Displaystyle mathbf {х} Pre mathbf {y}}$ если и только если ${ displaystyle mathbf {x}}$ находится в выпуклой оболочке всех векторов, полученных перестановкой координат ${ displaystyle mathbf {y}}$ .

На рисунке 1 изображена выпуклая оболочка в 2D для вектора ${ Displaystyle mathbf {y} = (3, , 1)}$ . Обратите внимание, что центр выпуклой оболочки, который в данном случае является интервалом, является вектором ${ Displaystyle mathbf {x} = (2, , 2)}$ . Это «наименьший» вектор, удовлетворяющий ${ Displaystyle mathbf {х} Pre mathbf {y}}$ для данного вектора ${ displaystyle mathbf {y}}$ .

Рисунок 2. Пример 3D-мажоризации

На рисунке 2 изображена выпуклая оболочка в 3D. Центр выпуклой оболочки, которая в данном случае представляет собой двумерный многоугольник, является "наименьшим" вектором. ${ displaystyle mathbf {x}}$ удовлетворение ${ Displaystyle mathbf {х} Pre mathbf {y}}$ для данного вектора ${ displaystyle mathbf {y}}$ .

Эквивалентные условия

Каждое из следующих утверждений верно тогда и только тогда, когда ${ displaystyle mathbf {a} succ mathbf {b}}$ :

${ displaystyle mathbf {b} = D mathbf {a}}$ для некоторых дважды стохастическая матрица ${ displaystyle D}$ .^[1]^{:Thm. 2.1} Это эквивалентно высказыванию ${ displaystyle mathbf {b}}$ можно представить как выпуклое сочетание перестановок ${ Displaystyle mathbf {а}}$ ; можно проверить, что существует такое выпуклое представление, используя не более ${ displaystyle d}$ перестановки ${ Displaystyle mathbf {а}}$ .^[2]
Из ${ Displaystyle mathbf {а}}$ мы можем производить ${ displaystyle mathbf {b}}$ конечной последовательностью «операций Робин Гуда», где мы заменяем два элемента ${ displaystyle a_ {i}}$ и ${ displaystyle a_ {j}$ с ${ displaystyle a_ {i} - varepsilon}$ и ${ displaystyle a_ {j} + varepsilon}$ соответственно для некоторых ${ displaystyle varepsilon in (0, a_ {i} -a_ {j})}$ .^[1]^:11
Для каждой выпуклой функции ${ displaystyle h: mathbb {R} to mathbb {R}}$ $h: { mathbb {R}} to { mathbb {R}}$ , ${ Displaystyle сумма _ {я = 1} ^ {d} час (а_ {я}) geq сумма _ {я = 1} ^ {d} час (b_ {я})}$ $sum _ {{i = 1}} ^ {d} h (a_ {i}) geq sum _ {{i = 1}} ^ {d} h (b_ {i})$ .^[1]^{:Thm. 2,9}
- На самом деле достаточно частного случая: ${ Displaystyle сумма _ {я} {а_ {я}} = сумма _ {я} {Ь_ {я}}}$ и для каждого $т$ , ${ displaystyle sum _ {я = 1} ^ {d} { max {(0, a_ {i} -t)}} geq sum _ {i = 1} ^ {d} { max {( 0, b_ {i} -t)}}}$ .^[3]
${ displaystyle forall t in mathbb {R} quad sum _ {j = 1} ^ {d} | a_ {j} -t | geq sum _ {j = 1} ^ {d} | b_ {j} -t |}$ .^[4]^{:Упражнение 12.17}

В линейной алгебре

Предположим, что для двух реальных векторов ${ displaystyle v, v ' in mathbb {R} ^ {d}}$ , ${ displaystyle v}$ мажоритарный ${ displaystyle v '}$ . Тогда можно показать, что существует набор вероятностей ${ displaystyle (p_ {1}, p_ {2}, ldots, p_ {d}), sum _ {i = 1} ^ {d} p_ {i} = 1}$ и набор перестановки ${ displaystyle (P_ {1}, P_ {2}, ldots, P_ {d})}$ такой, что ${ displaystyle v '= sum _ {i = 1} ^ {d} p_ {i} P_ {i} v}$ .^[2] В качестве альтернативы можно показать, что существует дважды стохастическая матрица ${ displaystyle D}$ такой, что ${ Displaystyle vD = v '}$

Мы говорим, что Эрмитов оператор, ${ displaystyle H}$ , мажоритарный другой, ${ displaystyle H '}$ , если набор собственных значений ${ displaystyle H}$ мажоритарный ${ displaystyle H '}$ .

В теории рекурсии

Данный ${ displaystyle f, g: mathbb {N} to mathbb {N}}$ , тогда ${ displaystyle f}$ говорят мажорировать ${ displaystyle g}$ если для всех ${ displaystyle x}$ , ${ Displaystyle е (х) geq g (х)}$ . Если есть какие-то ${ displaystyle n}$ так что ${ Displaystyle е (х) geq g (х)}$ для всех ${ displaystyle x> n}$ , тогда ${ displaystyle f}$ говорят доминировать (или же в конечном итоге доминировать) ${ displaystyle g}$ . В качестве альтернативы, предыдущие термины часто определяются с учетом строгого неравенства ${ Displaystyle е (х)> г (х)}$ вместо ${ Displaystyle е (х) geq g (х)}$ в предыдущих определениях.

Обобщения

Различные обобщения мажоризации обсуждаются в главах 14 и 15 справочника. Неравенства: теория мажоризации и ее приложения. Альберт В. Маршалл, Инграм Олкин, Барри Арнольд. Второе издание. Серия Спрингера в статистике. Спрингер, Нью-Йорк, 2011. ISBN 978-0-387-40087-7

Смотрите также

Неравенство Мюрхеда
Неравенство Караматы
Выпуклая функция Шура
Теорема Шура – Хорна связывание диагональных элементов матрицы с ее собственными значениями.
Для положительного целые числа, слабое мажорирование называется Порядок доминирования.

Примечания

^ ^а ^б ^c Барри С. Арнольд. «Мажоризация и порядок Лоренца: краткое введение». Конспект лекций Springer-Verlag по статистике, т. 43, 1987.
^ ^а ^б Синчжи, Чжань (2003). «Точная теорема Радо для мажоритаций». Американский математический ежемесячник. 110 (2): 152–153. Дои:10.2307/3647776.
^ Сообщение от fleeting_guest от 3 июля 2005 г. Тема "Неравенство Караматы", AoPS форумы сообщества. В архиве 11 ноября, 2020.
^ Нильсен, Майкл А.; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3. OCLC 844974180.

внешняя ссылка

Программного обеспечения

Октава /MATLAB код для проверки мажоритарности

[Arnold-1] а ^б ^c Барри С. Арнольд. «Мажоризация и порядок Лоренца: краткое введение». Конспект лекций Springer-Verlag по статистике, т. 43, 1987.

[Zhan-2] а ^б Синчжи, Чжань (2003). «Точная теорема Радо для мажоритаций». Американский математический ежемесячник. 110 (2): 152–153. Дои:10.2307/3647776.

[3] Сообщение от fleeting_guest от 3 июля 2005 г. Тема "Неравенство Караматы", AoPS форумы сообщества. В архиве 11 ноября, 2020.

[NielsenChuang-4] Нильсен, Майкл А.; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3. OCLC 844974180.

[1]

[2]

[3]

[4]