Skip to main content
2 of 6
edited title
Gala
  • 8.6k
  • 2
  • 32
  • 44

Expected number of times the empirical mean will exceed a value

Given a sequence of i.i.d. RVs, say, $X_i \in [0,1]$ for $i = 1,2,...,n$, I'm trying to bound the expected number of times the empirical mean $\frac{1}{n}\sum_{i=1}^n X_i$ will exceed a value, $c \geq 0$, as we continue to draw samples, that is: $$ \mathcal{T} \overset{def}{=} \sum_{j=1}^n j * \mathbb{P}(\{ \frac{1}{j}\sum_{i=1}^j X_i \geq c\}) $$

If we assume that $c = a + \mathbb{E}[X]$ for some $a > 0$, we can use Hoeffding's IE to arrive at

\begin{align} \mathcal{T} & \leq \sum_{j=1}^n j * e^{-2ja^2} \\ & = \frac{e^{-2 a^2 n} \left(e^{2 a^2 (n+1)}-e^{2 a^2} (n+1)+n\right)}{\left(e^{2 a^2}-1\right)^2} \end{align}

Which looks nice (maybe) but is actually quite a loose bound, are there any better ways of bounding this value? I expect so since I'm actually looking for an expectation in the end and Hoeffding's is more general than is needed.

fairidox
  • 1.3k
  • 7
  • 18