Documentation

Dynamics.Consensus

Consensus and fixation #

Configurations are maps s : V → C (a colour, opinion or type per vertex). A consensus is a constant configuration, and nonConsensus is the indicator of not being one: the survival indicator for which the absorption theorem (Kernel.finite_absorption) is applied in the model packages (Voter.survival, Moran.unfixed, Undecided.notMono).

noncomputable def Dynamics.nonConsensus {V : Type u_1} {C : Type u_2} (s : V → C) :

Indicator of non-consensus: 0 on constant configurations, 1 otherwise.

Equations
Instances For
    theorem Dynamics.nonConsensus_binary {V : Type u_1} {C : Type u_2} (s : V → C) :
    theorem Dynamics.nonConsensus_le_one {V : Type u_1} {C : Type u_2} (s : V → C) :
    @[simp]
    theorem Dynamics.nonConsensus_const {V : Type u_1} {C : Type u_2} (c : C) :
    (nonConsensus fun (x : V) => c) = 0
    theorem Dynamics.nonConsensus_of_not {V : Type u_1} {C : Type u_2} (s : V → C) (h : ¬∃ (c : C), s = fun (x : V) => c) :
    theorem Dynamics.nonConsensus_bool {V : Type u_1} [Fintype V] (s : V → Bool) :
    nonConsensus s = if (¬s = fun (x : V) => true) ∧ ¬s = fun (x : V) => false then 1 else 0

    For two colours, non-consensus is being neither all-true nor all-false.

    theorem Dynamics.Kernel.nonConsensus_step {V : Type u_1} {C : Type u_2} [Fintype V] [DecidableEq V] [Fintype C] (K : Kernel (V → C)) (habs : ∀ (c : C) (f : (V → C) → ℝ), (K.apply f fun (x : V) => c) = f fun (x : V) => c) (s : V → C) :

    If every consensus configuration is absorbing, the non-consensus probability does not increase in one step.

    theorem Dynamics.Kernel.iterate_nonConsensus_bool {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel (V → Bool)) (n : ℕ) (s : V → Bool) :
    K.iterate n nonConsensus s = K.event (fun (t : V → Bool) => (¬t = fun (x : V) => true) ∧ ¬t = fun (x : V) => false) n s

    For two colours, finite-time non-consensus is an event.

    theorem Dynamics.Kernel.iSup_consensus_of_harmonic {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel (V → Bool)) (φ : (V → Bool) → ℝ) (hinv : K.apply φ = φ) (hne : (φ fun (x : V) => true) ≠ φ fun (x : V) => false) (habs : ((K fun (x : V) => true).prob fun (x : V → Bool) => x = fun (x : V) => true) = 1) (s : V → Bool) (hsurv : Filter.Tendsto (fun (n : ℕ) => K.iterate n nonConsensus s) Filter.atTop (nhds 0)) :
    ⨆ (T : ℕ), K.event (fun (x : V → Bool) => x = fun (x : V) => true) T s = (φ s - φ fun (x : V) => false) / ((φ fun (x : V) => true) - φ fun (x : V) => false)

    Gambler's ruin for two consensus configurations. If φ is harmonic for K and takes different values on all-true and all-false, all-true is absorbing, and the non-consensus probability tends to zero, then the probability of fixation in all-true from s is (φ(s) − φ(all-false)) / (φ(all-true) − φ(all-false)). For instance, a harmonic q^k, with k the number of true vertices out of n, gives (1 - q^k) / (1 - q^n), and a harmonic k gives k / n. This is iSup_event_of_invariant for the two consensus configurations.

    theorem Dynamics.Kernel.iSup_consensus_of_invariant {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel (V → Bool)) (ψ : (V → Bool) → ℝ) (hinv : K.apply ψ = ψ) (hone : (ψ fun (x : V) => true) = 1) (hzero : (ψ fun (x : V) => false) = 0) (habs : ((K fun (x : V) => true).prob fun (x : V → Bool) => x = fun (x : V) => true) = 1) (s : V → Bool) (hsurv : Filter.Tendsto (fun (n : ℕ) => K.iterate n nonConsensus s) Filter.atTop (nhds 0)) :
    ⨆ (T : ℕ), K.event (fun (x : V → Bool) => x = fun (x : V) => true) T s = ψ s

    Fixation from an invariant. If ψ is harmonic for K, equals 1 on all-true and 0 on all-false, all-true is absorbing, and the non-consensus probability tends to zero, then ψ is the probability of fixation in all-true. This is the normalized case of iSup_consensus_of_harmonic.