Concentration of Lipschitz Functions of Negatively Dependent Variables

Kevin Garbe, Jan Vondrak

Published 2018-04-21Version 1

We explore the question whether Lipschitz functions of random variables under various forms of negative correlation satisfy concentration bounds similar to McDiarmid's inequality for independent random variables. We prove such a concentration bound for random variables satisfying the condition of negative regression, correcting an earlier proof by Dubhashi and Ranjan.