On Wormald's differential equation method

05/22/2019

∙

by   Lutz Warnke, et al.

∙

0

∙

share

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