On Wormald's differential equation method
From MaRDI portal
Publication:6319136
arXiv1905.08928MaRDI QIDQ6319136FDOQ6319136
Authors: Lutz Warnke 
Publication date: 21 May 2019
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.
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)
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)
