Linear multi-objective drift analysis

The tools of drift analysis enable bounds on run-times (or first hitting times) of stochastic processes, such as randomised algorithms, based on bounds on the expected progress at each time step in terms of a distance measure. In this paper, we generalise the multiplicative drift theorem to apply to processes which are best described by more than one distance function. We provide four examples to illustrate the application of this method: the run-time analysis of an evolutionary algorithm on a multi-objective optimisation problem; the analysis of a variant of the voter model on a network; a parallel evolutionary algorithm taking place on islands with limited migration; a synchronous network epidemiology model. In the latter example, we show that populations with limited neighbourhoods (such as the ring topology) are able to resist epidemics much more effectively than well-mixed populations.