Perturbed round-based processes #
A round-based process step : S → R → S, driven by i.i.d. uniform rounds, is perturbed within
Adm along a function P : List R → S of the rounds played so far when P [] = s and, after
every round r, the new state P (l ++ [r]) is related by Adm to the unperturbed
step (P l) r. Since P may depend on the whole list of rounds, this covers adaptive
adversaries; the process is no longer a Markov chain on S, but every bound below only needs
one-round estimates that hold for every admissible perturbation of the round.
failInd: the indicator of the failure of a proposition (thePropform ofDynamics.Kernel.outside);Perturbed.shift: the process seen after the roundsl₀is again perturbed;expList_le_of_drift_perturbed(fixed-time drift): if every perturbed round mapsφto at mostρ φ + εin expectation, then afterTrounds𝔼 φ ≤ ρ ^ T φ + T ε;expList_path_perturbed(chains of moves): if every perturbed round fromB imissesB (i + 1)with probability at mostε, the whole pathP (l.take t) ∈ B t,t ≤ T, fails with probability at mostT ε(the perturbed, path form ofDynamics.expList_escape).
Two phases of such a run are glued with Dynamics.expList_le_of_split.
Indicator of the failure of a proposition: 0 if it holds, 1 otherwise (for a membership
b ∈ B, this is Kernel.outside B b).
Equations
- Dynamics.failInd p = if p then 0 else 1
Instances For
A proposition that holds does not fail.
P is a run of step from s perturbed within Adm: it starts at s and, after every
round r, the new state is related by Adm to the output of step.
Equations
Instances For
Fixed-time drift for perturbed runs. If every perturbed round maps the potential φ to
at most ρ φ + ε in expectation (0 ≤ ρ ≤ 1, 0 ≤ ε), then after T rounds the expected
potential is at most ρ ^ T φ + T ε.
Chains of moves for perturbed runs. If, for every i, every perturbed round from a
state of B i misses B (i + 1) with probability at most ε, then a perturbed run from B 0
fails to follow P (l.take t) ∈ B t for all t ≤ T with probability at most T ε.