Мажоризация

В математике , мажорирование является предзаказ на векторах из действительных чисел . Для вектора мы обозначаем вектор с такими же компонентами, но отсортированный по убыванию. Учитывая , мы говорим, что слабо мажоритарно (или доминирует) снизу записывается как iff${\ 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 {a} }$ ${\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 {a} }$ ${\displaystyle \mathbf {b} \prec _{w}\mathbf {a} }$

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

Обратите внимание, что порядок мажорирования не зависит от порядка компонентов векторов или . Мажоризация не является частичным порядком , поскольку и не подразумевает , это только означает, что компоненты каждого вектора равны, но не обязательно в одном и том же порядке.${\displaystyle \mathbf {a} }$${\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 f(\mathbf {a} )\geq f(\mathbf {b} )}$${\displaystyle f(\mathbf {a} )}$${\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)}$

(Сильный) мажорирование: . Для векторов с n компонентами${\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).}$

(Слабый) мажорирование: . Для векторов с n компонентами:${\displaystyle (1,2,3)\prec _{w}(1,3,3)\prec _{w}(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 {x} \prec \mathbf {y} }$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {y} }$

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

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

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

Эквивалентные условия [ править ]

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

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

В линейной алгебре [ править ]

• Предположим , что для двух действительных векторов , мажорирующая . Тогда можно показать, что существует такой набор вероятностей и набор перестановок , что . ^{[2] В} качестве альтернативы можно показать, что существует двустохастическая матрица такая, что${\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}$ ${\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 f(x)\geq g(x)}$${\displaystyle n}$${\displaystyle f(x)\geq g(x)}$${\displaystyle x>n}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f(x)>g(x)}$${\displaystyle f(x)\geq g(x)}$

Обобщения [ править ]

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Дж. Карамата. "Sur une inegalite относительные вспомогательные выпуклости". Publ. Математика. Univ. Белград  1, 145–158, 1932.
• Харди, Дж. Литтлвуд и Г. Полиа, Неравенства , 2-е издание, 1952, Издательство Кембриджского университета, Лондон.
• Неравенства: теория мажоризации и ее приложения Альберт В. Маршалл, Ингрэм Олкин , Барри Арнольд, второе издание. Серии Спрингера в статистике. Спрингер, Нью-Йорк, 2011. ISBN 978-0-387-40087-7 
• Неравенства: теория мажоризации и ее приложения (1980) Альберт В. Маршалл, Инграм Олкин , Academic Press, ISBN 978-0-12-473750-1 
• Посвящение книге Маршалла и Олкина «Неравенства: теория мажоризации и ее приложения».
• Матричный анализ (1996) Раджендра Бхатиа, Springer, ISBN 978-0-387-94846-1 
• Темы матричного анализа (1994) Роджер А. Хорн и Чарльз Р. Джонсон, Cambridge University Press, ISBN 978-0-521-46713-1 
• Мажоризация и матричные монотонные функции в беспроводной связи (2007) Эдуард Йорсвик и Хольгер Бош, Now Publishers, ISBN 978-1-60198-040-3 
• Мастер-класс Коши Шварца (2004) Дж. Майкл Стил, Cambridge University Press, ISBN 978-0-521-54677-5 

Внешние ссылки [ править ]

• Мажоризация в MathWorld
• Мажоризация в PlanetMath

Программное обеспечение [ править ]

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