If are independent random variables and has bounded differences constants , thenand the same bound holds for the lower tail.
For a nonempty of relative size at least , its Hamming distance function has the bounded differences property with all constants one. If , the concentration bound at gives , so for . Then , proving that the radius- neighbourhood contains at least cube points.
Articles by others on the same topic
McDiarmid's inequality is a result in probability theory that provides a bound on the concentration of a function that is composed of independent random variables. It is particularly useful for analyzing the behavior of functions that depend on a finite number of independent random variables and have bounded differences.