Question Overview:

Is it already known that, when using Hoeffding's inequality to lower bound the mean of i.i.d. random variables, you can replace the upper bound on the random variables with the largest observed sample?

Question Detail:

Is the following result known?

Let $X_1,\dotsc,X_n$ be $n$ i.i.d. random variables where each $X_i \in [a,b]$. Then, for any $\delta \in (0,0.5]$: $$ \Pr \left (\mathbf{E}\left [ X_1 \right ] > \frac{1}{n}\sum_{i=1}^n X_i - (\max\{X_1,\dotsc,X_n\}-a)\sqrt{\frac{\ln(1/\delta)}{2n}} \right )\geq 1-\delta. $$

Notice that, if using Hoeffding's inequality, $\max\{X_1,\dotsc,X_n\}$ would be replaced with $b$. For random variables with large possible upper bounds that are rarely realized, this could make a big difference.

  • $\begingroup$ Is the result known to you? That is, are you saying you can prove it, or do you not know whether or not it is true? $\endgroup$ Aug 2, 2016 at 4:03
  • 3
    $\begingroup$ It is true - it follows from Anderson's 1969 concentration inequality. I needed to put Anderson's bound into the form of Hoeffding's inequality for something I'm doing, and I got this result after loosening Anderson's bound a bit. I was surprised by this result and couldn't find it online. I'm curious whether this is known / if it's surprising to others / if I can just reference someone else to state this rather than having to include it as a claim that is unrelated to the topic of my paper (but which I need). $\endgroup$
    – PThomasCS
    Aug 2, 2016 at 4:16
  • $\begingroup$ This does look interesting and somewhat surprising, and Anderson's paper seems very nice. Is your derivation of your inequality from Anderson's result available? $\endgroup$ Aug 2, 2016 at 4:46
  • 1
    $\begingroup$ I've uploaded it here. I hesitate to call it a different inequality from Anderson's - it's really just putting his in a different form (which requires loosening it slightly). $\endgroup$
    – PThomasCS
    Aug 2, 2016 at 5:17
  • $\begingroup$ Can you replace $a$ with the minimum? $\endgroup$ Aug 2, 2016 at 8:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.