18
$\begingroup$

Suppose you have $n$ i.i.d. random variables taking values in $\{0,1\}$, and $X$ represents their sum. Then you can use a Chernoff bound to control the deviation of $X$ from its expectation. The Chernoff bound has two useful forms: the typical bound which controls the additive deviation, in terms of the number of random variables $n$, and the multiplicative bound, which controls the relative deviation from the expectation, with a bound that is independent of the number of random variables $n$.

When the quantity that one is interested in is not the sum of $n$ i.i.d. random variables, but instead some other $1$-Lipschitz function of the random variables, then Mcdiarmid's inequality gives essentially the same bound as the additive version of the Chernoff bound.

My question: Is there a multiplicative version of Mcdiarmid's inequality that bounds the relative deviation of an arbitrary $1$-Lipschitz function of $n$ i.i.d. random variables in a way that is independent of $n$, akin to the multiplicative version of the Chernoff bound?

$\endgroup$
3
  • $\begingroup$ I recently studied Mcdiarmid's inequality in a Theoretical Statistics course, and have not seen anything like what you ask. But I will keep looking for it, and asking the professor. $\endgroup$
    – Næreen
    Feb 15, 2016 at 21:30
  • 1
    $\begingroup$ The wiki article shows that the multiplicative chernoff bound is for binary random variables. So maybe we can try to find the same kind of bound using Mcdiarmid's inequality, using binary random variables. $\endgroup$ Feb 19, 2016 at 16:37
  • $\begingroup$ @SamratMukhopadhyay the "multiplicative Chernoff" holds for more than simplify binary r.v.'s, it is much more applicable than that. (Bounded, for example.) $\endgroup$
    – Clement C.
    Jul 5, 2019 at 5:12

1 Answer 1

4
$\begingroup$

McDiarmid's is proven applying Azuma's inequality (which is "additive") to a suitable martingale.

You should be able to obtain "multiplicative McDiarmid-type" inequalities by applying a "multiplicative Azuma-type inequality" (i.e., "Chernoff bounds for dependent r.v.'s) as in, e.g., this MathOverflow question, to the same martingale.

$\endgroup$
1
  • $\begingroup$ (Yes, this is a long time after the original question... but I stumbled upon the question while looking for similar things.) $\endgroup$
    – Clement C.
    Jul 5, 2019 at 5:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .