1

Can the probability of error of the sample mean, i.e., $\Pr(|\bar{X}-E[X]| \geq \epsilon)$, be bounded using Chebyshev inequality (or something similar)? $X$ is a discrete random variable with an unknown distribution and unknown variance, and $\bar{X}$ is the sample mean, i.e, $\frac{1}{n} \sum X_i$. Furthermore, $X_1,...,X_n$ are iid random samples.

I am not interested in approximate or asymptotic solutions. Also, I am aware of the sample version of Chebyshev inequality (particularly this question, and this Wikipedia page), but that seems to apply to $|X_i - \bar{X}|$ as opposed to $|\bar{X}-E[X]|$.

Community
  • 1
sasan
  • 41
  • 5
  • 2
    Can you clarify your question and precisely what you mean by "bound the estimation error"? That is precisely what Chebyshev is doing (in probability). Are you looking for a bound with probability one? (In that case, the only thing you can possibly hope for is rather trivial.) – cardinal Nov 24 '14 at 14:56
  • @cardinal hopefully the edit makes it clear now. – sasan Nov 24 '14 at 15:28
  • The edit does not address the basic problem alluded to by @Cardinal: the answer remains trivial until you stipulate some restrictions on the distribution of the $X_i$. – whuber Nov 24 '14 at 16:30
  • @whuber One thing I would like to know in particular is whether in the Chebyshev inequality the population variance can be replaced by the sample variance divided by the sample size. From what I've understood from Cardinal's answer to the question mentioned above, doing so is not correct. Am I right? – sasan Nov 24 '14 at 16:46
  • That's a different question. Your current question, as it is written, makes no reference to the sample variance in the probability expression it is asking about. Your best option is to edit your question so that it explicitly asks what you want to know. – whuber Nov 24 '14 at 18:22
  • @whuber Okay, I'll post a new question on that, but can you please at least confirm whether or not any versions of the Chebyshev inequality can be applied to $|\bar{X} - E[X]|$? – sasan Nov 24 '14 at 18:45
  • If the $X_i$'s are almost surely bounded, meaning that $\Pr(X_i\in[a_i,b_i])=1$, you have room to work – Zen Nov 24 '14 at 19:00
  • @Zen Using Hoeffding's inequality? – sasan Nov 24 '14 at 19:01
  • Exactly. Are the $X_i$'s a.s. bounded? – Zen Nov 24 '14 at 19:01
  • In my problem, I can actually bound $X$ such that $X_i \in [a, b]$, but that would be a different question. Also, the original version of Hoeffding's inequality seems to target only infinite populations. – sasan Nov 24 '14 at 19:12
  • But [this paper from Microsoft Research](http://research.microsoft.com/apps/pubs/default.aspx?id=219983) claims that the Hoeffding inequality needs to be "corrected" to be applicable to finite populations. – sasan Nov 24 '14 at 19:16

0 Answers0