Documentation

ThreeMajority.AnyStartRinott

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.

theorem ThreeMajority.majorizes_of_transfer {ι : Type u_1} [Fintype ι] {x y : ι → ℝ} {a b : ι} (hab : a ≠ b) (hc : ∀ (c : ι), c ≠ a → c ≠ b → y c = x c) (hs : y a + y b = x a + x b) (hba : x b ≤ y a) (hax : y a ≤ x a) :

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.

theorem ThreeMajority.majorizes_comp_perm {ι : Type u_1} [Fintype ι] (x : ι → ℝ) (π : Equiv.Perm ι) :
Majorizes x (x ∘ ⇑π)

A vector majorizes each of its rearrangements.

theorem ThreeMajority.pow_mul_pow_le_pow_mul_pow {u w : ℝ} (hw : 0 ≤ w) (hwu : w ≤ u) {K L : ℕ} (h : L ≤ K) :
w ^ K * u ^ L ≤ u ^ K * w ^ L

w ^ K * u ^ L ≤ u ^ K * w ^ L for 0 ≤ w ≤ u and L ≤ K.

theorem ThreeMajority.countVec_perm_comp {n : ℕ} {σ : Type u_1} [DecidableEq σ] (π : Equiv.Perm σ) (c : Fin n → σ) :
countVec (⇑π ∘ c) = countVec c ∘ ⇑(Equiv.symm π)

Relabelling the colours permutes the configuration vector.

theorem ThreeMajority.colourCount_update {n : ℕ} {σ : Type u_1} [DecidableEq σ] (x : Fin n → σ) (v : Fin n) (c d : σ) :
colourCount (Function.update x v c) d = {u ∈ Finset.univ.erase v | x u = d}.card + if c = d then 1 else 0

The number of agents of colour d after setting agent v to colour c.

noncomputable def ThreeMajority.transferWeight {σ : Type u_1} [DecidableEq σ] (w : σ → ℝ) (a b : σ) (θ : ℝ) (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
    def ThreeMajority.transferSlope {σ : Type u_1} [DecidableEq σ] (a b c : σ) :

    The derivative of transferWeight w a b θ c in θ.

    Equations
    Instances For
      theorem ThreeMajority.transferWeight_swap {σ : Type u_1} [DecidableEq σ] {w : σ → ℝ} {a b : σ} (hab : a ≠ b) (θ : ℝ) (c : σ) :
      transferWeight w a b θ ((Equiv.swap a b) c) = transferWeight w a b (w a + w b - θ) c

      Swapping the colours a and b exchanges θ and w a + w b - θ.

      theorem ThreeMajority.transferSlope_swap {σ : Type u_1} [DecidableEq σ] {a b : σ} (hab : a ≠ b) (c : σ) :

      Swapping the colours a and b reverses the slope.

      theorem ThreeMajority.hasDerivAt_transferWeight {σ : Type u_1} [DecidableEq σ] {w : σ → ℝ} {a b : σ} (c : σ) (θ : ℝ) :
      HasDerivAt (fun (t : ℝ) => transferWeight w a b t c) (transferSlope a b c) θ

      Each transfer weight is affine in θ, with slope transferSlope.

      theorem ThreeMajority.prod_transferWeight {n : ℕ} {σ : Type u_1} [DecidableEq σ] {w : σ → ℝ} {a b : σ} (hw : ∀ (c : σ), 0 ≤ w c) (hab : a ≠ b) (E : Finset (Fin n)) (x : Fin n → σ) :
      ∃ (R : ℝ), 0 ≤ R ∧ ∀ (θ : ℝ), ∏ u ∈ E, transferWeight w a b θ (x u) = θ ^ {u ∈ E | x u = a}.card * (w a + w b - θ) ^ {u ∈ E | x u = b}.card * R

      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 θ.

      theorem ThreeMajority.expect_independent_eq {n : ℕ} {σ : Type u_1} [Fintype σ] (r : Dynamics.Distribution σ) (g : σ → ℝ) (hg : ∀ (c : σ), r.weight c = g c) (φ : (Fin n → σ) → ℝ) :
      (Dynamics.Distribution.independent fun (x : Fin n) => r).expect φ = ∑ x : Fin n → σ, (∏ v : Fin n, g (x v)) * φ x

      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.

      theorem ThreeMajority.exists_equiv_antitone {σ : Type u_1} [Fintype σ] (f : σ → ℝ) :
      ∃ (e : Fin (Fintype.card σ) ≃ σ), Antitone (f ∘ ⇑e)

      Every weight function is antitone along some enumeration of the colours.

      theorem ThreeMajority.SchurConvex.apply_perm_comp {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] {φ : (Fin n → σ) → ℝ} (hφ : SchurConvex φ) (π : Equiv.Perm σ) (c : Fin n → σ) :
      φ (⇑π ∘ c) = φ c

      A Schur-convex observable is invariant under relabelling the colours.

      theorem ThreeMajority.expect_independent_perm {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] {φ : (Fin n → σ) → ℝ} (hφ : SchurConvex φ) (π : Equiv.Perm σ) (p r : Dynamics.Distribution σ) (hr : ∀ (c : σ), r.weight c = p.weight (π c)) :

      Relabelling the colours of the common law of the agents does not change the expectation of a Schur-convex observable.

      theorem ThreeMajority.majorizes_countVec_update {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] {a b : σ} (hab : a ≠ b) (x : Fin n → σ) (v : Fin n) (h : {u ∈ Finset.univ.erase v | x u = b}.card ≤ {u ∈ Finset.univ.erase v | x u = a}.card) :

      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.

      theorem ThreeMajority.transfer_term_nonneg {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] {w : σ → ℝ} {a b : σ} (hw : ∀ (c : σ), 0 ≤ w c) (hab : a ≠ b) {φ : (Fin n → σ) → ℝ} (hφ : SchurConvex φ) {θ : ℝ} (hθ : w a + w b - θ ≤ θ) (hθs : θ ≤ w a + w b) (x : Fin n → σ) (v : Fin n) :
      0 ≤ (∏ u ∈ Finset.univ.erase v, transferWeight w a b θ (x u) - ∏ u ∈ Finset.univ.erase v, transferWeight w a b (w a + w b - θ) (x u)) * (φ (Function.update x v a) - φ (Function.update x v 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.

      theorem ThreeMajority.sum_transferSlope_nonneg {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] {w : σ → ℝ} {a b : σ} (hw : ∀ (c : σ), 0 ≤ w c) (hab : a ≠ b) {φ : (Fin n → σ) → ℝ} (hφ : SchurConvex φ) {θ : ℝ} (hθ : w a + w b - θ ≤ θ) (hθs : θ ≤ w a + w b) (v : Fin n) :
      0 ≤ ∑ x : Fin n → σ, (∏ u ∈ Finset.univ.erase v, transferWeight w a b θ (x u)) * transferSlope a b (x v) * φ x

      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.

      theorem ThreeMajority.hasDerivAt_sum_transferWeight {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (w : σ → ℝ) (a b : σ) (φ : (Fin n → σ) → ℝ) (θ : ℝ) :
      HasDerivAt (fun (t : ℝ) => ∑ x : Fin n → σ, (∏ v : Fin n, transferWeight w a b t (x v)) * φ x) (∑ x : Fin n → σ, (∑ v : Fin n, (∏ u ∈ Finset.univ.erase v, transferWeight w a b θ (x u)) * transferSlope a b (x v)) * φ x) θ

      The derivative of the expectation along a transfer, as a function of the weight θ of a.

      theorem ThreeMajority.expect_le_of_transfer {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (p r : Dynamics.Distribution σ) {a b : σ} (hab : a ≠ b) (hc : ∀ (c : σ), c ≠ a → c ≠ b → r.weight c = p.weight c) (hs : r.weight a + r.weight b = p.weight a + p.weight b) (hba : r.weight b ≤ r.weight a) (hap : r.weight a ≤ p.weight a) {φ : (Fin n → σ) → ℝ} (hφ : SchurConvex φ) :

      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.

      theorem ThreeMajority.exists_transfer_step {m : ℕ} (x y : Fin m → ℝ) (hy : Antitone y) (hdom : ∀ (l : ℕ), ∑ i : Fin m with ↑i < l, y i ≤ ∑ i : Fin m with ↑i < l, x i) (hsum : ∑ i : Fin m, x i = ∑ i : Fin m, y i) (hne : ∃ (i : Fin m), x i ≠ y i) :
      ∃ (j : Fin m) (k : Fin m) (δ : ℝ), j ≠ k ∧ 0 ≤ δ ∧ y j ≤ x j - δ ∧ x k + δ ≤ y k ∧ y k ≤ y j ∧ (∀ (l : ℕ), ∑ i : Fin m with ↑i < l, y i ≤ ∑ i : Fin m with ↑i < l, ((x i - if i = j then δ else 0) + if i = k then δ else 0)) ∧ {i : Fin m | ((x i - if i = j then δ else 0) + if i = k then δ else 0) ≠ y i}.card < {i : Fin m | x i ≠ y i}.card

      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.

      theorem ThreeMajority.expect_le_of_partial_sums {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] {m : ℕ} (e : Fin m ≃ σ) (p q : Dynamics.Distribution σ) (hq : Antitone (q.weight ∘ ⇑e)) (hdom : ∀ (l : ℕ), ∑ i : Fin m with ↑i < l, q.weight (e i) ≤ ∑ i : Fin m with ↑i < l, p.weight (e i)) {φ : (Fin n → σ) → ℝ} (hφ : SchurConvex φ) :

      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.

      theorem ThreeMajority.sum_le_sum_of_card_eq {ι : Type u_2} {A B : Finset ι} (f : ι → ℝ) (hAB : A.card = B.card) (h : ∀ a ∈ A, ∀ b ∈ B, f a ≤ f b) :
      ∑ i ∈ A, f i ≤ ∑ i ∈ B, f i

      If #A = #B and every term over A is at most every term over B, the sum over A is at most the sum over B.

      theorem ThreeMajority.sum_le_sum_lt_of_antitone {m : ℕ} {g : Fin m → ℝ} (hg : Antitone g) (l : ℕ) (T : Finset (Fin m)) (hT : T.card = {i : Fin m | ↑i < l}.card) :
      ∑ i ∈ T, g i ≤ ∑ i : Fin m with ↑i < l, g i

      For an antitone g, the first l terms have the largest sum among sets of as many terms.

      theorem ThreeMajority.expect_le_of_majorizes {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (p q : Dynamics.Distribution σ) (hpq : Majorizes p.weight q.weight) (φ : (Fin n → σ) → ℝ) (hφ : SchurConvex φ) :

      Proposition 1 of BCEKMN17, proved in this file; multinomial_schurConvex restates it.