Let $X_i$ be an i.i.d. Bernoulli distributed sequence, with probability $p$ being 1. Now consider an empirical estimation of $p$ with $l$ samples and I am looking for a lower bound for following probability with assumption of $lp>1$

$$ \mathbb{P}\left\{ \frac{1}{l} \sum_{i=1}^l X_i \geq p \right\} $$

The desired lower bound should be independent of $l$ and $p$. My guess is $1/4$.

Note: It's $\geq$, not $>$.

Some background: I am reading Vapnik's "Statistical Learning Theory". Proof of the lemma 4.1 claims that for $lp > 1$, $$ \mathbb{P}\left\{ \frac{1}{l} \sum_{i=1}^l X_i > p \right\} \leq 1/4 $$ However, note that here it is an upper bound and it breaks the proof. I think we should seek for a lower bound the bias probability instead.



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.