Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hoeffding inequality for the difference of two sample means?

  1. Aug 30, 2012 #1
    In W. Hoeffding's 1963 paper* he gives the well known inequality:

    [itex]P(\bar{x}-\mathrm{E}[x_i] \geq t) \leq \exp(-2t^2n) \ \ \ \ \ \ (1)[/itex],

    where [itex]\bar{x} = \frac{1}{n}\sum_{i=1}^nx_i[/itex], [itex]x_i\in[0,1][/itex]. [itex]x_i[/itex]'s are independent.

    Following this theorem he gives a corollary for the difference of two sample means as:

    [itex]P(\bar{x}-\bar{y}-(\mathrm{E}[x_i] - \mathrm{E}[y_k]) \geq t) \leq \exp(\frac{-2t^2}{m^{-1}+n^{-1}}) \ \ \ \ \ \ (2)[/itex],

    where [itex]\bar{x} = \frac{1}{n}\sum_{i=1}^nx_i[/itex], [itex]\bar{y} = \frac{1}{m}\sum_{k=1}^my_k[/itex], [itex]x_i,y_k\in[0,1][/itex]. [itex]x_i[/itex]'s and [itex]y_k[/itex]'s are independent.

    My question is: How does (2) follow from (1)?


    *http://www.csee.umbc.edu/~lomonaco/f08/643/hwk643/Hoeffding.pdf (equations (2.6) and (2.7))
  2. jcsd
  3. Aug 30, 2012 #2


    User Avatar
    Science Advisor

    Hey JanO and welcome to the forums.

    One idea I have is to let Z = X + Y and use Z instead of X in the definition.
  4. Aug 30, 2012 #3
    Thanks Chiro for your responce.

    However, I still do not understand how the term [itex](m^{-1} + n^{-1})[/itex] comes into the bound. Isn't [itex]z=\bar{x}-\bar{y}[/itex] is still bounded between [0,1]?

  5. Aug 30, 2012 #4


    User Avatar
    Science Advisor

    Think about what happens to the variances.
  6. Aug 31, 2012 #5
    It seems like bounded here means all most surely bounded. At least that's how Hoeffding inequality seems to be given elsewhere. I guess it then means that [itex]z=\bar{x}-\bar{y}[/itex] is bounded a.s. between [itex][\mu_x-\mu_y-\frac{1}{2}\sqrt{m^{-1}+n^{-1}}, \ \mu_x-\mu_y+\frac{1}{2}\sqrt{m^{-1}+n^{-1}}][/itex].?

    Thanks again for your help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook