9
$\begingroup$

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.

$\endgroup$
  • $\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$ – Nate Eldredge Aug 2 '16 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 '16 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$ – Iosif Pinelis Aug 2 '16 at 4:46
  • $\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 '16 at 5:17
  • $\begingroup$ Can you replace $a$ with the minimum? $\endgroup$ – Ori Gurel-Gurevich Aug 2 '16 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.