Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
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. – Næreen Feb 15 at 21:30
    
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. – Samrat Mukhopadhyay Feb 19 at 16:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.