**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.

you? That is, are you saying you can prove it, or do you not know whether or not it is true? $\endgroup$5more comments