I'm working on using empirical Bernstein bounds to estimate the mean difference between 2 variables from different distribution.

The algorithm samples from each variable until it detects a significant difference between the 2 variables. Upon termination, it returns an estimate of the mean difference.

I noticed that the literature on empirical Bernstein bound has exclusively tested using simulated uniform and Bernoulli random variables, e.g. variables in the range 0,1. My question is how far the algorithm performs well when used with other distributions? (One may not always know the distribution of the data.)

From what I understand, the application to uniform and Bernoulli random variables stems from the fact that Hoeffding made the range (0,1) assumption to get a simple form of the bound. Hoeffding for example states that if the assumption of the range (0,1) is dropped, i.e. if the variable is non-negative with finite Mean, then the Markov inequality cannot be improved upon. At least this is the explanation I found in Hoeffding's paper (see footnote 4, p.15):

Quote: "If in Theorem 1 (Hoeffding inequality) the assumption Xi <1 is dropped that is, if it is only assumed that the Xi are non-negative with finite means, then Markov's inequality $Pr(\bar{X}-\mu\geq t)\leq\mu/(\mu+t)$ cannot be improved upon.(The bound is attained if Xi takes the values 0 and n(p+t) with respective probabilities $t/l(\mu+t)$ and $\mu/(\mu +t)$, and X2 = ... =Xn =0 with probability one.) Thus the assumption that the Xi are bounded on both sides is crucial to getting any improvement over Markov's bound."

If this is the case, I would like to better understand the implications of this. Does this mean that when I run the Empirical Bernstein bound to estimate the difference between 2 normally distributed variables, then an algorithm based on the Bernstein inequality would give the same result as one based on the Markov inequality?

Thanks for comments & suggestions


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.