Processes driven by independent uniform rounds #
Many dynamics in this repository are given by a deterministic update
step : S → R → S applied to a sequence of i.i.d. uniform rounds r : R,
with expectations computed by expList. ofStep step is the corresponding
finite Markov kernel, and iterate_ofStep identifies its iterates with the
expList expectations, so results about kernels (for instance
Dynamics.Kernel.nested_phases) apply to such round-based processes.
The probability missProb of missing a target after T rounds composes over stages
(missProb_comp) and, for a target closed under every round, amplifies over consecutive blocks
(missProb_amplify).
The Markov kernel of one uniformly random round of step.
Equations
- Dynamics.Kernel.ofStep step s = (Dynamics.Distribution.uniform R).map (step s)
Instances For
Escaping a moving target. If a round-based process starts in G 0
and, for every t < T, one round from any state of G t misses G (t + 1)
with probability at most p, then after T rounds it lies outside G T with
probability at most T p. This is the union bound over rounds used by lower
bounds such as Theorem 4.2 of Becchetti et al. (SPAA 2014).
Missing a target after i.i.d. rounds #
Probability that the process driven by T i.i.d. uniform rounds of step, started at s,
is outside B after T rounds.
Equations
- Dynamics.missProb step B T s = Dynamics.expList R T fun (l : List R) => if List.foldl step s l ∈ B then 0 else 1
Instances For
Composition of stages (Markov property): if from every state of B the process misses
D after T₂ rounds with probability at most e, then from s it misses D after T₁ + T₂
rounds with probability at most missProb step B T₁ s + e.
Amplification (the expList form of Dynamics.Kernel.event_amplify): if a target closed
under every round is missed after T rounds with probability at most p from every state, then
it is missed after k T rounds with probability at most p ^ k, since each block of T rounds
fails independently of the previous ones.