Documentation

Crn.GraphMajorityRandom

Approximate majority on a graph with a random initial placement (CRN-4) #

The 3-state approximate-majority protocol of Angluin, Aspnes and Eisenstat [AAE08] on an arbitrary graph G with the probabilistic scheduler [MNRS14, §2]: each step activates a uniformly random oriented edge (a uniform edge with a uniform orientation; Dynamics.EdgeRound), whose tail is the initiator and head the responder. The states are the species X, Y, B of Crn.ApproxMajority (CRN-1), and the transition is the one-way rule of [MNRS14, eq. (1)] (rule): the initiator never changes; an X/Y initiator turns an opposite responder blank and recruits a blank responder. Every effective transition is one of the four reactions of the approximate-majority CRN network (rule_mem_network, exists_rule_of_mem_network).

[MNRS14, Theorem 4]: if the m ≥ n − m majority agents (Y, the paper's green g) and the n − m minority agents (X, red r) are placed uniformly at random, the probability that the protocol converges to the minority is at most the probability that it converges to the majority.

Convergence is formalized in the finite probability layer of dynamics/: winProb G m s t is the probability (over the placement and the scheduler) that at time t every agent is in state s. Unanimous configurations are absorbing, so winProb is nondecreasing in t (winProb_monotone) and the convergence probability is its supremum, absorbProb G m s (the limit, tendsto_winProb), as for Dynamics.Kernel.iSup_event_of_invariant. We pin:

The proof follows [MNRS14, proof of Theorem 4]:

References #

The one-way rule of [AAE08] and its relation to the CRN network #

The 3-state protocol of [AAE08] as a population protocol: input true ↦ X, false ↦ Y, output true exactly in state X.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem Crn.ApproxMajority.rule_mem_network (p : Species × Species) (h : rule p ≠ p) :
    { reactants := s(p.1, p.2), products := s((rule p).1, (rule p).2) } ∈ network.reactions

    Every effective transition of rule is a reaction of the approximate-majority CRN network (CRN-1): reactants {x, y}, products δ(x, y).

    theorem Crn.ApproxMajority.exists_rule_of_mem_network (r : Reaction Species) (hr : r ∈ network.reactions) :
    ∃ (p : Species × Species), rule p ≠ p ∧ r = { reactants := s(p.1, p.2), products := s((rule p).1, (rule p).2) }

    Every reaction of the approximate-majority CRN network is an effective transition of rule for some (initiator, responder) pair.

    The chain on a graph #

    def Crn.ApproxMajority.graphStep {n : ℕ} (G : SimpleGraph (Fin n)) (c : Fin n → Species) (d : G.Dart) :
    Fin n → Species

    One step of the protocol on G: the endpoints of the oriented edge d interact (tail initiator, head responder) [MNRS14, §2].

    Equations
    Instances For

      The Markov chain of the protocol on G under the probabilistic scheduler [MNRS14, §2]: each step activates a uniformly random oriented edge (EdgeRound G), i.e. a uniform edge with a uniform orientation.

      Equations
      Instances For

        Every agent is in state s (for s = X, Y: the protocol has converged to s).

        Equations
        Instances For

          The initial placement with the majority type Y exactly on S and the minority type X elsewhere [MNRS14, proof of Theorem 4: (R₀, G₀) = (V − S, S)].

          Equations
          Instances For
            noncomputable def Crn.ApproxMajority.winProb {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (m : ℕ) (s : Species) (t : ℕ) :

            The probability that at time t every agent is in state s, when the m agents of type Y are placed uniformly at random (a uniform m-subset S, [MNRS14, eq. (18)]) and the protocol runs on G with the probabilistic scheduler.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              noncomputable def Crn.ApproxMajority.absorbProb {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (m : ℕ) (s : Species) :

              The probability that the protocol eventually converges to s from a uniformly random placement of m agents of type Y: the supremum (the limit, tendsto_winProb) of the finite-time probabilities winProb.

              Equations
              Instances For

                Monotonicity and symmetry #

                theorem Crn.ApproxMajority.rule_mono (p q : Species × Species) (h1 : rank p.1 ≤ rank q.1) (h2 : rank p.2 ≤ rank q.2) :
                rank (rule p).1 ≤ rank (rule q).1 ∧ rank (rule p).2 ≤ rank (rule q).2

                The rule is monotone in both states for the order Y < B < X (by inspection of the 3 × 3 table).

                The rule commutes with the exchange of X and Y (the protocol is symmetric for the two types [MNRS14, proof of Theorem 4]).

                theorem Crn.ApproxMajority.graphStep_mono {n : ℕ} (G : SimpleGraph (Fin n)) {c c' : Fin n → Species} (h : ∀ (v : Fin n), rank (c v) ≤ rank (c' v)) (d : G.Dart) (v : Fin n) :
                rank (graphStep G c d v) ≤ rank (graphStep G c' d v)

                Monotone coupling, one step. Two configurations ordered agentwise stay ordered when the same oriented edge is activated.

                theorem Crn.ApproxMajority.graphStep_swap {n : ℕ} (G : SimpleGraph (Fin n)) (c : Fin n → Species) (d : G.Dart) :

                The dynamics commutes with the exchange of X and Y.

                theorem Crn.ApproxMajority.graphKernel_apply {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (f : (Fin n → Species) → ℝ) (c : Fin n → Species) :
                (graphKernel G).apply f c = Dynamics.avg fun (d : G.Dart) => f (graphStep G c d)

                One step of the chain averages an observable over the uniformly random oriented edge.

                theorem Crn.ApproxMajority.iterate_graphKernel_mono {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (t : ℕ) {f : (Fin n → Species) → ℝ} (hf : ∀ (c c' : Fin n → Species), (∀ (v : Fin n), rank (c v) ≤ rank (c' v)) → f c ≤ f c') {c c' : Fin n → Species} (h : ∀ (v : Fin n), rank (c v) ≤ rank (c' v)) :

                Monotone coupling, t steps. If an observable is monotone for the agentwise order Y < B < X, so is its expectation after t steps.

                theorem Crn.ApproxMajority.iterate_graphKernel_swap {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (t : ℕ) (f : (Fin n → Species) → ℝ) (c : Fin n → Species) :
                (graphKernel G).iterate t (fun (c' : Fin n → Species) => f (swap ∘ c')) c = (graphKernel G).iterate t f (swap ∘ c)

                The dynamics commutes with the exchange of X and Y, at every time t.

                The exchanged configuration is unanimously Y exactly when the configuration is unanimously X.

                theorem Crn.ApproxMajority.event_allX_mono {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (t : ℕ) {c c' : Fin n → Species} (h : ∀ (v : Fin n), rank (c v) ≤ rank (c' v)) :

                Monotonicity [MNRS14, eq. (19)]: the probability that every agent is X at time t can only increase when the initial configuration increases agentwise in the order Y < B < X.

                Symmetry [MNRS14, eq. (20)]: the probability that every agent is X at time t from c is the probability that every agent is Y at time t from the exchanged configuration.

                A unanimous configuration is absorbing.

                Systems of distinct representatives #

                theorem Crn.ApproxMajority.exists_injective_of_regular {ι : Type u_1} {α : Type u_2} [Fintype ι] [Fintype α] [DecidableEq α] (T : ι → Finset α) {r d : ℕ} (hr : ∀ (i : ι), (T i).card = r) (hd : ∀ (a : α), {i : ι | a ∈ T i}.card = d) (hd1 : 1 ≤ d) (hxy : Fintype.card ι ≤ Fintype.card α) :
                ∃ (f : ι → α), Function.Injective f ∧ ∀ (i : ι), f i ∈ T i

                [MNRS14, Corollary 1] (a consequence of Hall's theorem, Jukna, Extremal Combinatorics, ch. 5): r-element subsets T i of a universe of y elements such that each element belongs to the same number d ≥ 1 of them, with x ≤ y sets, have a system of distinct representatives.

                theorem Crn.ApproxMajority.exists_injective_subset {n m : ℕ} (hm : n ≤ 2 * m) :
                ∃ (σ : Finset (Fin n) → Finset (Fin n)), (∀ (S : Finset (Fin n)), S.card = m → σ S ⊆ S ∧ (σ S).card = n - m) ∧ Set.InjOn σ {S : Finset (Fin n) | S.card = m}

                [MNRS14, proof of Theorem 4]: if n − m ≤ m, every m-subset S of the agents can be assigned an (n − m)-subset A_S ⊆ S, injectively.

                Almost sure absorption: helper lemmas #

                The initiator never changes its state.

                A blank initiator leaves the responder unchanged.

                theorem Crn.ApproxMajority.rule_snd_rule_snd {s : Species} (hs : s ≠ Species.B) (t : Species) :
                (rule (s, (rule (s, t)).2)).2 = s

                An initiator in state s ≠ B activated twice on the same responder brings it to s (a blank responder is recruited at once; an opposite one is first turned blank).

                theorem Crn.ApproxMajority.graphStep_fst {n : ℕ} (G : SimpleGraph (Fin n)) (c : Fin n → Species) (d : G.Dart) :
                graphStep G c d d.toProd.1 = c d.toProd.1

                The initiator keeps its state.

                theorem Crn.ApproxMajority.graphStep_snd {n : ℕ} (G : SimpleGraph (Fin n)) (c : Fin n → Species) (d : G.Dart) :
                graphStep G c d d.toProd.2 = (rule (c d.toProd.1, c d.toProd.2)).2

                The responder takes the second component of the rule.

                theorem Crn.ApproxMajority.graphStep_of_ne {n : ℕ} (G : SimpleGraph (Fin n)) (c : Fin n → Species) (d : G.Dart) {v : Fin n} (h1 : v ≠ d.toProd.1) (h2 : v ≠ d.toProd.2) :
                graphStep G c d v = c v

                The agents other than the two endpoints keep their states.

                theorem Crn.ApproxMajority.graphStep_of_unanimous {n : ℕ} (G : SimpleGraph (Fin n)) {s : Species} {c : Fin n → Species} (hc : Unanimous s c) (d : G.Dart) :
                graphStep G c d = c

                A unanimous configuration is fixed by every step.

                theorem Crn.ApproxMajority.graphStep_eq_of_fst {n : ℕ} (G : SimpleGraph (Fin n)) {c : Fin n → Species} {d : G.Dart} {s : Species} (hd : c d.toProd.1 = s) {v : Fin n} (hv : c v = s) :
                graphStep G c d v = s

                An agent in state s keeps it when the initiator is in state s.

                A configuration with a non-blank agent keeps one after a step.

                theorem Crn.ApproxMajority.graphReaches_const {n : ℕ} (G : SimpleGraph (Fin n)) (hG : G.Connected) {s : Species} (hs : s ≠ Species.B) {c : Fin n → Species} (hc : ∃ (u : Fin n), c u = s) :
                protocol.GraphReaches G c fun (x : Fin n) => s

                Spreading on a connected graph: from a configuration with an agent in state s ≠ B, the configuration in which every agent is in state s is reachable (activate twice an edge from an agent in state s to an agent in another state, until there is none).

                theorem Crn.ApproxMajority.exists_iterate_lt_one {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] {a b : Fin n → Species} (h : protocol.GraphReaches G a b) {g : (Fin n → Species) → ℝ} (hg : ∀ (x : Fin n → Species), g x ≤ 1) (hb : g b < 1) :
                ∃ (k : ℕ), (graphKernel G).iterate k g a < 1

                Access: if b is reachable from a on G and an observable g ≤ 1 is below 1 at b, then its expectation at some finite time from a is below 1.

                theorem Crn.ApproxMajority.iterate_unanimous_blank {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (t : ℕ) {c : Fin n → Species} (hc : ¬Unanimous Species.B c) :
                (graphKernel G).iterate t (fun (b : Fin n → Species) => if Unanimous Species.B b then 1 else 0) c = 0

                From a configuration with a non-blank agent, all agents are never simultaneously blank.

                Theorem 4 #

                Unanimity is absorbing, so the finite-time convergence probabilities are nondecreasing.

                theorem Crn.ApproxMajority.winProb_mem_Icc {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (m : ℕ) (s : Species) (t : ℕ) :
                winProb G m s t ∈ Set.Icc 0 1

                The finite-time convergence probabilities lie in [0, 1].

                The convergence probability is the limit of the finite-time probabilities.

                [MNRS14, Theorem 4], finite-time form. On every graph with an edge, if the m ≥ n − m agents of the majority type Y and the n − m agents of the minority type X are placed uniformly at random, then at every time t the probability that every agent is X (the minority has won) is at most the probability that every agent is Y (the majority has won).

                [MNRS14, Theorem 4]. On every graph with an edge, with a uniformly random placement of m ≥ n − m majority agents, the protocol of [AAE08] converges to the initial majority with probability at least the probability that it converges to the initial minority.

                Almost sure convergence (implicit in [MNRS14, Theorem 4]): on a connected graph, from every configuration with a non-blank agent, the probability that the protocol has converged to X or to Y by time t tends to 1.

                theorem Crn.ApproxMajority.half_le_absorbProb_majority {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] [Nonempty G.Dart] (hG : G.Connected) {m : ℕ} (hm : n ≤ 2 * m) (hmn : m ≤ n) :

                [MNRS14, Theorem 4], as stated. On a connected graph, with a uniformly random placement of m ≥ n − m majority agents (m ≤ n), the protocol of [AAE08] converges to the initial majority with probability at least 1/2.