Non-ephemeral good nodes: the deterministic part of Lemma 4.2 #
Fix a reference state x₁ (the state at the start t₁ of the phase) and a threshold θ. The
deviation of a later state x at v is r_v = x_v - α - β₁ χ_v, where α is the (conserved)
average and β₁ χ the cut component of x₁; v is bad (badSet) if r_v² > θ. A round is
bad (IsBadStep) if its dart crosses the cut or has a bad endpoint.
not_mem_badSet_avgRun: a node that is not bad att₁and is touched only by rounds that are not bad is never bad: averaging two good nodes of the same community keeps both good, sinceα + β₁ χis constant on each community (proof of Lemma 4.2, Appendix C.3, setsA_t).card_filter_touched_le: the nodes for which this fails number at most|B| + 2 Z, withBthe bad set att₁andZthe number of bad rounds.
A dart crossing the cut.
Instances For
Equations
The deviation r_v = x_v - α - β₁ χ_v of x from the reference x₁ (Lemma 4.2).
Equations
- Averaging.Opportunistic.devVec V₁ x₁ x v = x v - Dynamics.avg x₁ - Averaging.Opportunistic.cutCoef V₁ x₁ * Averaging.Opportunistic.cutVec V₁ v
Instances For
The nodes with r_v² > θ.
Equations
- Averaging.Opportunistic.badSet V₁ θ x₁ x = {v : V | θ < Averaging.Opportunistic.devVec V₁ x₁ x v ^ 2}
Instances For
A bad round: the dart crosses the cut or has a bad endpoint.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
The deviation at an untouched node does not change, and at the two endpoints of an internal dart it becomes the average of the two deviations.
Good nodes stay good (proof of Lemma 4.2): a node that is not bad at the start and is touched only by rounds that are not bad is never bad.
The endpoints of the k-th dart of l (empty past the end).
Equations
Instances For
The k-th round of l is bad.
Equations
- Averaging.Opportunistic.IsBadRound V₁ θ x₁ l k = ∃ (e : G.Dart), l[k]? = some e ∧ Averaging.Opportunistic.IsBadStep V₁ θ x₁ (Averaging.Opportunistic.avgRun G x₁ (List.take k l)) e
Instances For
Counting: the nodes that are bad at the start or touched by a bad round number at most
|B| + 2 Z.