McDiarmid's inequality

In probability theory and theoretical computer science, McDiarmid's inequality (named after Colin McDiarmid ^[1]) is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a bounded differences property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function.

^ McDiarmid, Colin (1989). "On the method of bounded differences". Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference: 148–188. doi:10.1017/CBO9781107359949.008. ISBN 978-0-521-37823-9.

[1] McDiarmid, Colin (1989). "On the method of bounded differences". Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference: 148–188. doi:10.1017/CBO9781107359949.008. ISBN 978-0-521-37823-9.

[1]