Graph-indexed rounds #
Round types for dynamics on a finite simple graph G, to be averaged with avg, iterated with
expList and turned into kernels with Kernel.ofStep.
NeighborRound G: a synchronous round in which every vertex samples one of its neighbours. It is the product over the vertices of their neighbour sets, so under the uniform distribution the samples are independent (avg_neighborRound_prod,avg_neighborRound_mul) and each is uniform among the neighbours (avg_neighborRound_eval). On the complete graph this is the round typeRumorPush.Tgt nofepidemics/(libraryRumorSpread). A uniform vertex together with a uniform synchronous round is the sequential "random vertex, random neighbour" step (avg_vertex_neighborRound).EdgeRound G: a sequential step in which one oriented edge (aSimpleGraph.Dart) is activated. A uniform oriented edge is a uniform edge (avg_edgeRound_edge) with a uniform orientation (avg_edgeRound_symm); averages over it are sums over adjacent ordered pairs divided by2 |E|(avg_edgeRound), and its tail is degree-biased (avg_edgeRound_fst). Plain sums over the darts are double sums over the adjacent ordered pairs (sum_dart, viadartEquiv); differences along a walk telescope over its darts (walk_sum_darts), and squared differences over distinct darts are bounded by the Dirichlet energy (sum_darts_sq_le). On the complete graph⊤it is a uniform ordered pair of distinct vertices (edgeRoundTopEquiv,card_edgeRound_top,sum_edgeRound_top), the scheduler of population protocols. A one-way protocol updates the responderd.sndagainst the initiatord.fst(oneWayStep).
Uniform averages over the neighbours of v are written avg (fun u : G.neighborSet v => g u),
equal to (∑ u ∈ G.neighborFinset v, g u) / G.degree v (avg_neighborSet).
A synchronous round on G: every vertex v picks a neighbour r v. Under the uniform
distribution the picks are independent and uniform among the neighbours.
Equations
- Dynamics.NeighborRound G = ((v : V) → ↑(G.neighborSet v))
Instances For
A sequential step on G: one oriented edge (d.fst, d.snd) of G is activated. Under the
uniform distribution this is a uniform edge with a uniform orientation.
Equations
- Dynamics.EdgeRound G = G.Dart
Instances For
One step of a one-way pairwise protocol with transition rule δ on the activated oriented
edge d: the responder d.snd takes δ (s d.snd) (s d.fst) against the initiator d.fst, and
every other vertex keeps its state.
Equations
- Dynamics.oneWayStep δ s d = Function.update s d.toProd.2 (δ (s d.toProd.2) (s d.toProd.1))
Instances For
Uniform neighbours and synchronous rounds: every vertex samples a neighbour #
The uniform average over the neighbours of v is their sum divided by the degree.
With no isolated vertex, every neighbour set is nonempty.
Synchronous rounds exist as soon as no vertex is isolated.
The number of synchronous rounds is the product of the degrees.
Independence: in a uniform synchronous round the vertices sample their neighbours independently, so averages of products over the vertices factor.
Marginal: in a uniform synchronous round each vertex samples a uniform neighbour.
Pairwise independence: in a uniform synchronous round two distinct vertices sample their neighbours independently.
Linearity over the vertices: the average of a sum of one-vertex observables is the sum of their neighbour averages.
Random vertex, then random neighbour: a uniform vertex v together with a uniform
synchronous round r realizes the sequential step "a uniform vertex v and a uniform neighbour
r v of v" (the death–Birth scheduler), so V × NeighborRound G is its round type.
Sequential rounds: one uniformly random oriented edge per step #
Sequential steps exist as soon as G has an edge.
The darts of G are the adjacent ordered pairs.
Equations
Instances For
Uniform orientation: averages are invariant under reversing the activated edge.
Squared differences over distinct darts are bounded by the Dirichlet energy
∑_{i ∼ j} (ψ i - ψ j)² (each edge counted in both orientations).
Uniform oriented edge: the average over the activated oriented edge is the sum over the
adjacent ordered pairs divided by 2 |E|.
Uniform edge: the underlying edge of a uniform oriented edge is a uniform edge.
Degree bias: the tail of a uniform oriented edge is v with probability
deg v / 2 |E|.
The complete graph: one uniformly random ordered pair of distinct vertices per step #
On the complete graph, an oriented edge is an ordered pair of distinct vertices (the "random ordered pair" scheduler of population protocols).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The complete graph on n vertices has n (n - 1) oriented edges: twice its
n choose 2 edges.