Tensorizations of Hoeffding’s Lemma

Relatively simple large-deviation inequalities have been proved previously as consequences of the work of Hoeffding, using exponential moment generating functions. Lipschitz-like functions can be seen as concentrating about their mean using a tensorization of Hoeffding’s lemma in what is known as McDiarmid’s inequality. We consider the concentration of certain variables using a tensorization of Hoeffding’s lemma to address so-called oscillatory behaviors related to independence. We start with the Boolean cube itself and the concentration of the Hamming metric. The concentration of the Hamming metric is guaranteed for product distributions in high dimensions, as it is a sum of bounded random variables. In fact, in the product setting, the rate at which the metric concentrates is the order of the dimension, independent of the fixed point. This fails, however, for certain dependent distributions. We bound the exponential moment generating function of a given variable on the Boolean cube and characterize the concentration by means of a certain correlation condition. Our methods are advantageous since they are both simple and comprehensive. We extend these bounds from sums on the Boolean cube to sums on a finite, discrete sample space. We characterize the dependency structure by an oscillation term related to the n n th marginal distribution, which vanishes when the variables are independent. Using Markov’s inequality, we obtain concentration inequalities for some general classes of dependent random variables.