On Wormald's differential equation method

MaRDI QIDQ6319136zbMATH OpenFDO

Authors Lutz Warnke

Publication date 21 May 2019

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Combinatorial probability (60C05)

Abstract: This note contains a short and simple proof of Wormald's differential equation method (that yields slightly improved approximation guarantees and error probabilities). This powerful method uses differential equations to approximate the time-evolution/dynamics of random processes and algorithms.

This page was built for publication: On Wormald's differential equation method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6319136)