12
$\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.

Improve this question
$\endgroup$
10
  • $\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
    Commented 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
    Commented 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$
    – Iosif Pinelis
    Commented 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
    Commented Aug 2, 2016 at 5:17
  • $\begingroup$ Can you replace $a$ with the minimum? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Aug 2, 2016 at 8:11

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .