Talk:Majorization

From Wikipedia, the free encyclopedia

Contents

[edit] Theoretical question

Can majorization be generalized to functions over a continuous space, where we use integrals instead of summations? It seems that, rather than ordering the vectors, we can say

u \geq_M v \iff \forall T\subseteq [0,d], \quad \exists S : |S|=|T|, \quad \sum_{i\in S} u_i \geq \sum_{i\in T} v_i

(with equality for |T|=d) I think this is equivalent in the finite case, since the best strategy is to put the indices of the largest elements of u and v in S and T respectively. But it also lets us replace sums with integrals, where |S| is now the area of S with respect to some base measure. If this is true, then one might ask whether theorems about convexity, doubly stochastic matrices, etc. continue to hold. A5 14:53, 16 March 2006 (UTC)

Yes, it can be generalized. The result is called the Lorenz ordering (this is mentioned on the Majorization page), and I believe the important theorems transfer. I've also heard it called the Increasing Convex (ICX) ordering. I'm not sure which term is more common. Nethgirb 00:15, 17 March 2006 (UTC)

I see, sorry I missed that. By the way, do you know if the Lorenz ordering is defined as I suggested above? I have a paper defining the Lorennz ordering in front of me but it's not obvious that it is analogous. I will keep reading. A5 14:56, 19 March 2006 (UTC)

One way to extend your definition to the continuous case would be to say that u and v, rather than being finite sets, are probability distributions over \Bbb{R}^+, and S and T are subsets of the outcome space of equal measure. If this is what you had in mind, I think your definition is equivalent.
However, that is not the way the Lorenz ordering is typically defined. You don't have to resort to your alternate definition of majorization in order to have a natural continuous analogy. In particular, while majorization compares the sums of the largest elements in two vectors, the Lorenz ordering compares the upper tails of two probability distributions. Intuitively, the probability distribution is already "sorted" for you if you look at the CDF of the distribution. The definition of the Lorenz ordering which I've seen uses the CDF. Nethgirb 06:36, 20 March 2006 (UTC)

[edit] Notation

The textbook I have uses "\prec" and "\succ" rather than "\leq_M" and "\geq_M" for majorization. I'm not sure which notation is better? Are we just using the latter because Wikipedia doesn't recognize the former? A5 14:53, 16 March 2006 (UTC)

Right, "\pred" or "\predeq" etc. is better but is not supported by Wikipedia's math mode. Nethgirb 00:15, 17 March 2006 (UTC)
Aha. Now it appears to work. \prec \succ \succeq \preceq. Will have to update the article. --Nethgirb 01:36, 23 July 2007 (UTC)

[edit] Not a partial order

(0,1) majorizes (1,0), and vice versa. They aren't equal. Therefore, this is not antisymmetric, and not a Partial order.--128.208.87.221 23:43, 24 September 2007 (UTC)

This is just a technicality, but since we're talking about math, you're absolutely right and it should be fixed. When people refer to the majorization partial order (in my limited experience), they treat the objects as sets rather than vectors...which is pretty much what the definition does anyway since the ordering of elements in the vector is irrelevant. So {0, 1} majorizes {1, 0} but these are equal so that doesn't violate antisymmetry. --Nethgirb 08:14, 25 September 2007 (UTC)

[edit] About the proposed merge

I think merging with Dominance order is a good idea.. looking briefly the definitions appear to be equivalent. --Nethgirb (talk) 05:43, 7 January 2008 (UTC)