A Demonic Outcome Logic for Randomized Nondeterminism
summary
Introduces Demonic Outcome Logic that models randomized programs with adversarial nondeterminism using the convex power set semantics, proving a distributive law of probabilistic over nondeterministic choice and exposing a common unsound compositional rule (must split probabilistic outcomes first). Gives loop rules that prove almost-sure termination and exact outcome distributions — e.g., an adversarial von Neumann trick where the adversary picks bias in [ε,1−ε] yet the protocol yields a fair coin and terminates with probability 1; also analyzes Monty Hall and a probabilistic SAT heuristic.
AI-written summary · about