Proposition 1 of BCEKMN17 (Rinott; Marshall–Olkin–Arnold, Proposition 11.E.11) #
If p ⪰ q, every Schur-convex observable of the configuration has a larger expectation when
the n agents draw their colours i.i.d. from p than from q.
The proof sorts neither configurations nor colour counts, and uses no multinomial sums.
expect_le_of_transfer: a single Robin Hood transfer of mass between two coloursaandb. Along the transfer the expectation is a polynomial in the weightθofa, nondecreasing past the midpoint: its derivative is a sum over agentsv, and pairing each configuration with its images under swappingaandb(for all agents, then for agentvonly) leaves terms that are nonnegative by Schur-convexity (sum_transferSlope_nonneg).expect_le_of_partial_sums: a chain of transfers (the Hardy–Littlewood–Pólya construction,exists_transfer_step) leads fromptoqwhenqis sorted along an enumeration of the colours and the partial sums ofpdominate those ofq.expect_le_of_majorizes: sortingqandpand relabelling the colours ofp(expect_independent_perm) reduces the sort-free majorization to that case.
A Robin Hood transfer between two coordinates a and b (with x b ≤ y a ≤ x a and the
same sum on {a, b}) produces a vector majorized by the original one.
A vector majorizes each of its rearrangements.
Relabelling the colours permutes the configuration vector.
The number of agents of colour d after setting agent v to colour c.
Colour weights along a transfer between the colours a and b: θ on a, the rest
w a + w b - θ of their mass on b, and w elsewhere.
Equations
Instances For
The derivative of transferWeight w a b θ c in θ.
Instances For
Swapping the colours a and b exchanges θ and w a + w b - θ.
Swapping the colours a and b reverses the slope.
Each transfer weight is affine in θ, with slope transferSlope.
Along a transfer, a product of colour weights is θ ^ K * (w a + w b - θ) ^ L * R, with
K, L the numbers of factors of colour a, b and R ≥ 0 not depending on θ.
The expectation of an observable under i.i.d. colours, as an explicit sum over the configurations, with the colour weights given by any function equal to them.
Every weight function is antitone along some enumeration of the colours.
A Schur-convex observable is invariant under relabelling the colours.
Relabelling the colours of the common law of the agents does not change the expectation of a Schur-convex observable.
Moving agent v from colour a to colour b is a Robin Hood transfer of the
configuration vector when the other agents have colour a at least as often as colour b.
The paired terms of the derivative along a transfer are nonnegative: the weight difference and the difference of the observable have the same sign.
The contribution of agent v to the derivative along a transfer is nonnegative past the
midpoint. Pair each configuration with its image under swapping a and b (for all agents,
then for agent v only), and apply transfer_term_nonneg.
The derivative of the expectation along a transfer, as a function of the weight θ of a.
Transfer lemma. Moving mass from a colour a to a colour b, without making b
heavier than a, does not increase the expectation of a Schur-convex observable under i.i.d.
colours. The expectation along the transfer is monotone past the midpoint, by
sum_transferSlope_nonneg.
One step of the Hardy–Littlewood–Pólya construction. If the partial sums of x dominate
those of an antitone y with the same total and x ≠ y, moving some δ ≥ 0 from an index j
to a later index k keeps the domination, keeps the entry at j above the one at k, and makes
x agree with y at one more index. Here k is the first index with x k < y k.
Chain of transfers. If the partial sums of p dominate those of q along an
enumeration of the colours on which q is antitone, then E_q φ ≤ E_p φ. By induction on the
number of colours where p and q differ, with exists_transfer_step and
expect_le_of_transfer.
Proposition 1 of BCEKMN17, proved in this file; multinomial_schurConvex restates it.