Documentation

Epidemics.SmallWorldExplore

Subcritical exploration of a percolation cluster (EPI-6) #

The upper bound on cluster sizes of [BCDPTZ22] for SWG(n, c/n) (Lemma C.1) explores the cluster of a node s in the percolation graph perc G ω breadth-first, with deferred decisions on the edge coins. Here the coins are independent Bernoulli(r e) with possibly different probabilities, and the search processes one node per step: it reads at once the block of all pairs from the current node to its undiscovered G-neighbours, and appends the open ones to the queue.

Every discovered node y ≠ s carries the weight h e of the pair e through which it was discovered (the root carries w₀). If the expected weight discovered from a node of weight w is at most λ w (hypothesis hstep, with κ λ ≤ 1, the subcritical condition), the potential exp θ (discovered weight − κ λ · processed weight) is a supermartingale (the core's Distribution.expect_prod_hist_le_one_of_fresh); a cluster with more than t nodes forces t processed nodes and a large potential, whence, by Markov's inequality (prob_cluster_gt_le), P(|C(s)| ≥ t + 1) ≤ exp (-θ ((1 - κ λ) t w_min - w_max)).

For SWG(n, c/n) the weights distinguish nodes reached through a cycle edge from nodes reached through a bridge, the two types behind the paper's Galton–Watson comparison (Appendix C).

structure Epidemics.Explore.State (V : Type u_2) :
Type u_2

State of the breadth-first search: discovered nodes in discovery (= processing) order, the number of processed nodes, and the weights of the discovered nodes.

Instances For
    def Epidemics.Explore.fresh {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (σ : State V) (v : V) :

    The undiscovered G-neighbours of v.

    Equations
    Instances For

      The block of pairs read when processing the current node σ.order[σ.proc] (empty when the search is over).

      Equations
      Instances For
        def Epidemics.Explore.newV {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (σ : State V) (v : V) (A : Finset (Sym2 V)) :

        The nodes discovered from v when the open pairs are A.

        Equations
        Instances For
          noncomputable def Epidemics.Explore.update {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h : Sym2 V → ℝ) (σ : State V) (A : Finset (Sym2 V)) :

          One step of the search, given the set A of open pairs of the block.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            noncomputable def Epidemics.Explore.state {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h : Sym2 V → ℝ) (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) :

            The state after the observations l, starting from the root s of weight w₀.

            Equations
            Instances For
              theorem Epidemics.Explore.state_nil {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) :
              state G h s w₀ [] = { order := [s], proc := 0, wt := fun (x : V) => w₀ }
              theorem Epidemics.Explore.state_append {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) (A : Finset (Sym2 V)) :
              state G h s w₀ (l ++ [A]) = update G h (state G h s w₀ l) A
              theorem Epidemics.Explore.update_of_lt {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} {σ : State V} (hp : σ.proc < σ.order.length) (A : Finset (Sym2 V)) :
              update G h σ A = { order := σ.order ++ (newV G σ σ.order[σ.proc] A).toList, proc := σ.proc + 1, wt := fun (y : V) => if y ∈ newV G σ σ.order[σ.proc] A then h s(σ.order[σ.proc], y) else σ.wt y }
              theorem Epidemics.Explore.update_of_ge {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} {σ : State V} (hp : ¬σ.proc < σ.order.length) (A : Finset (Sym2 V)) :
              update G h σ A = σ
              theorem Epidemics.Explore.block_of_lt {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {σ : State V} (hp : σ.proc < σ.order.length) :
              block G σ = Finset.image (fun (y : V) => s(σ.order[σ.proc], y)) (fresh G σ σ.order[σ.proc])
              theorem Epidemics.Explore.block_of_ge {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {σ : State V} (hp : ¬σ.proc < σ.order.length) :
              block G σ = ∅
              theorem Epidemics.Explore.mem_fresh {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {σ : State V} {v y : V} :
              y ∈ fresh G σ v ↔ y ∉ σ.order ∧ G.Adj v y
              theorem Epidemics.Explore.mem_newV {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {σ : State V} {v y : V} {A : Finset (Sym2 V)} :
              y ∈ newV G σ v A ↔ (y ∉ σ.order ∧ G.Adj v y) ∧ s(v, y) ∈ A

              Invariants #

              structure Epidemics.Explore.Inv {V : Type u_1} {G : SimpleGraph V} {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (σ : State V) :

              The invariants of the search.

              Instances For
                theorem Epidemics.Explore.inv_update {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} {s : V} {w₀ : ℝ} {σ : State V} (hσ : Inv s w₀ σ) (A : Finset (Sym2 V)) :
                Inv s w₀ (update G h σ A)
                theorem Epidemics.Explore.inv_state {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) :
                Inv s w₀ (state G h s w₀ l)
                theorem Epidemics.Explore.update_mono {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (σ : State V) (A : Finset (Sym2 V)) :
                σ.order <+: (update G h σ A).order ∧ σ.proc ≤ (update G h σ A).proc ∧ ∀ y ∈ σ.order, (update G h σ A).wt y = σ.wt y

                The order only grows, and proc only grows.

                theorem Epidemics.Explore.state_mono {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) {j : ℕ} (hj : j ≤ l.length) :
                (state G h s w₀ (List.take j l)).order <+: (state G h s w₀ l).order ∧ (state G h s w₀ (List.take j l)).proc ≤ (state G h s w₀ l).proc ∧ ∀ y ∈ (state G h s w₀ (List.take j l)).order, (state G h s w₀ l).wt y = (state G h s w₀ (List.take j l)).wt y
                theorem Epidemics.Explore.proc_state {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) :
                (state G h s w₀ l).proc = l.length ∨ (state G h s w₀ l).proc < l.length ∧ (state G h s w₀ l).proc = (state G h s w₀ l).order.length

                proc counts the steps until the search is over.

                Freshness of the blocks #

                theorem Epidemics.Explore.readSet_sub {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) (e : Sym2 V) :
                e ∈ Dynamics.readSet (fun (l : List (Finset (Sym2 V))) => block G (state G h s w₀ l)) l → ∃ u ∈ List.take (state G h s w₀ l).proc (state G h s w₀ l).order, ∃ (y : V), e = s(u, y)

                Every pair read along the history l has a processed endpoint.

                theorem Epidemics.Explore.block_fresh {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) :
                Disjoint (block G (state G h s w₀ l)) (Dynamics.readSet (fun (l : List (Finset (Sym2 V))) => block G (state G h s w₀ l)) l)

                The search on the actual coins #

                noncomputable def Epidemics.Explore.obs {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) (ω : Sym2 V → Bool) :

                The observation process of the search on the coins ω: the open pairs of each block.

                Equations
                Instances For
                  theorem Epidemics.Explore.closed_state {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (ω : Sym2 V → Bool) (k : ℕ) (v : V) :
                  v ∈ List.take (state G h s w₀ (Dynamics.hist (obs s w₀) ω k)).proc (state G h s w₀ (Dynamics.hist (obs s w₀) ω k)).order → ∀ (y : V), (perc G ω).Adj v y → y ∈ (state G h s w₀ (Dynamics.hist (obs s w₀) ω k)).order

                  After processing a node, all its open neighbours are discovered.

                  The potential and the supermartingale #

                  noncomputable def Epidemics.Explore.pot {V : Type u_1} (c : ℝ) (σ : State V) :

                  The potential of the search: discovered weight (root excluded) minus c times the weight of the processed nodes.

                  Equations
                  Instances For
                    noncomputable def Epidemics.Explore.fac {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (θ c : ℝ) (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) (A : Finset (Sym2 V)) :

                    The factor of the supermartingale after the history l, when the open pairs of the block are A.

                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      theorem Epidemics.Explore.fac_nonneg {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (θ c : ℝ) (s : V) (w₀ : ℝ) (l : List (Finset (Sym2 V))) (A : Finset (Sym2 V)) :
                      0 ≤ fac θ c s w₀ l A
                      theorem Epidemics.Explore.image_newV {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {σ : State V} (hp : σ.proc < σ.order.length) {A : Finset (Sym2 V)} (hA : A ⊆ block G σ) :
                      Finset.image (fun (y : V) => s(σ.order[σ.proc], y)) (newV G σ σ.order[σ.proc] A) = A

                      The open pairs of the block are the pairs to the newly discovered nodes.

                      theorem Epidemics.Explore.pot_update {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} {s : V} {w₀ c : ℝ} {σ : State V} (hσ : Inv s w₀ σ) (hp : σ.proc < σ.order.length) {A : Finset (Sym2 V)} (hA : A ⊆ block G σ) :
                      pot c (update G h σ A) = pot c σ + (∑ e ∈ A, h e - c * σ.wt σ.order[σ.proc])
                      theorem Epidemics.Explore.pot_nil {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (c : ℝ) (s : V) (w₀ : ℝ) :
                      pot c (state G h s w₀ []) = 0
                      theorem Epidemics.Explore.histProd_eq {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (θ c : ℝ) (s : V) (w₀ : ℝ) (ω : Sym2 V → Bool) (k : ℕ) :
                      Dynamics.histProd (obs s w₀) (fac θ c s w₀) ω 0 k = Real.exp (θ * pot c (state G h s w₀ (Dynamics.hist (obs s w₀) ω k)))

                      Along the search on the coins ω, the product of the factors is exp (θ · potential).

                      theorem Epidemics.Explore.wt_bounds {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {h : Sym2 V → ℝ} {s : V} {w₀ wmin wmax : ℝ} {σ : State V} (hσ : Inv s w₀ σ) (hh : ∀ (e : Sym2 V), wmin ≤ h e ∧ h e ≤ wmax) (hw₀ : wmin ≤ w₀ ∧ w₀ ≤ wmax) (y : V) :
                      y ∈ σ.order → wmin ≤ σ.wt y ∧ σ.wt y ≤ wmax

                      The weights of the discovered nodes lie in [wmin, wmax].

                      theorem Epidemics.Explore.length_mul_le_sum_map {V : Type u_1} (l : List V) (wt : V → ℝ) {a : ℝ} (ha : ∀ y ∈ l, a ≤ wt y) :
                      ↑l.length * a ≤ (List.map wt l).sum
                      theorem Epidemics.Explore.pot_ge {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {h : Sym2 V → ℝ} {s : V} {w₀ wmin wmax c : ℝ} {σ : State V} (hσ : Inv s w₀ σ) (hh : ∀ (e : Sym2 V), wmin ≤ h e ∧ h e ≤ wmax) (hw₀ : wmin ≤ w₀ ∧ w₀ ≤ wmax) (hwmin : 0 ≤ wmin) (hc1 : c ≤ 1) {t : ℕ} (hproc : σ.proc = t) (hlen : t + 1 ≤ σ.order.length) :
                      (1 - c) * ↑t * wmin - wmax ≤ pot c σ

                      Lower bound on the potential when t nodes are processed and t + 1 discovered.

                      The tail bound #

                      theorem Epidemics.Explore.ncard_le_of_finished {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (ω : Sym2 V → Bool) (k : ℕ) (hfin : (state G h s w₀ (Dynamics.hist (obs s w₀) ω k)).proc = (state G h s w₀ (Dynamics.hist (obs s w₀) ω k)).order.length) :
                      ((perc G ω).connectedComponentMk s).supp.ncard ≤ (state G h s w₀ (Dynamics.hist (obs s w₀) ω k)).order.length

                      When the search is over (every discovered node processed), the discovered nodes contain the cluster of the root.

                      theorem Epidemics.Explore.proc_eq_of_lt_ncard {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (s : V) (w₀ : ℝ) (ω : Sym2 V → Bool) (t : ℕ) (ht : t < ((perc G ω).connectedComponentMk s).supp.ncard) :
                      (state G h s w₀ (Dynamics.hist (obs s w₀) ω t)).proc = t ∧ t + 1 ≤ (state G h s w₀ (Dynamics.hist (obs s w₀) ω t)).order.length

                      A cluster with more than t nodes forces t processed and t + 1 discovered nodes after t steps.

                      theorem Epidemics.Explore.expect_fac_le_one {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (r : Sym2 V → ℝ) (hr0 : ∀ (e : Sym2 V), 0 ≤ r e) (hr1 : ∀ (e : Sym2 V), r e ≤ 1) {wmax lam θ κ : ℝ} (hh0 : ∀ (e : Sym2 V), 0 ≤ h e) (hhmax : ∀ (e : Sym2 V), h e ≤ wmax) (hθ : 0 ≤ θ) (hθκ : θ * wmax ≤ κ - 1) (hκ2 : κ ≤ 2) (s : V) (w₀ : ℝ) (hstep : ∀ (σ : State V), Inv s w₀ σ → ∀ (hp : σ.proc < σ.order.length), ∑ y ∈ fresh G σ σ.order[σ.proc], r s(σ.order[σ.proc], y) * h s(σ.order[σ.proc], y) ≤ lam * σ.wt σ.order[σ.proc]) (l : List (Finset (Sym2 V))) :
                      ((Dynamics.Distribution.independent fun (e : Sym2 V) => Dynamics.Distribution.bernoulli (r e) ⋯ ⋯).expect fun (ω : Sym2 V → Bool) => fac θ (κ * lam) s w₀ l (obs s w₀ l ω)) ≤ 1

                      One step of the supermartingale: the factor has expectation at most 1.

                      theorem Epidemics.Explore.prob_cluster_gt_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {h : Sym2 V → ℝ} (r : Sym2 V → ℝ) (hr0 : ∀ (e : Sym2 V), 0 ≤ r e) (hr1 : ∀ (e : Sym2 V), r e ≤ 1) {w₀ wmin wmax lam θ κ : ℝ} (hh : ∀ (e : Sym2 V), wmin ≤ h e ∧ h e ≤ wmax) (hw₀ : wmin ≤ w₀ ∧ w₀ ≤ wmax) (hwmin : 0 ≤ wmin) (hθ : 0 ≤ θ) (hθκ : θ * wmax ≤ κ - 1) (hκ2 : κ ≤ 2) (hc1 : κ * lam ≤ 1) (s : V) (hstep : ∀ (σ : State V), Inv s w₀ σ → ∀ (hp : σ.proc < σ.order.length), ∑ y ∈ fresh G σ σ.order[σ.proc], r s(σ.order[σ.proc], y) * h s(σ.order[σ.proc], y) ≤ lam * σ.wt σ.order[σ.proc]) (t : ℕ) :
                      ((Dynamics.Distribution.independent fun (e : Sym2 V) => Dynamics.Distribution.bernoulli (r e) ⋯ ⋯).prob fun (ω : Sym2 V → Bool) => t < ((perc G ω).connectedComponentMk s).supp.ncard) ≤ Real.exp (-(θ * ((1 - κ * lam) * ↑t * wmin - wmax)))

                      Tail of the cluster size (subcritical exploration with weights): with independent Bernoulli(r e) coins, weights h e ∈ [wmin, wmax], root weight w₀ ∈ [wmin, wmax], and expected weight discovered from every node of weight w at most λ w (hstep), the cluster of s has more than t nodes with probability at most exp (-θ ((1 - κ λ) t wmin - wmax)), for every θ ≥ 0 and κ ≤ 2 with θ wmax ≤ κ - 1.