Expected number of times the empirical mean will exceed a value

Question

Given a sequence of i.i.d. random variables, 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 \mathbb{P} \left(\left\{ \frac{1}{j}\sum_{i=1}^j X_i \geq c\right\}\right) $$

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

\begin{align} \mathcal{T} & \leq \sum_{j=1}^n e^{-2ja^2} \\ & = \frac{1 - e^{-2 a^2 n}}{e^{2 a^2}-1} \end{align}

Which looks nice (maybe) but is actually quite a loose bound, are there any better ways of bounding this value? I expect there may be a way since the different events (for each $j$) are clearly not independent, I'm not aware of any way to exploit this dependence. Also, it would be nice to remove the restriction that $c$ is greater than the mean.

edit: The restriction on $c$ being greater than the mean can be removed if we use Markov's Inequality as follows:

\begin{align} \mathcal{T} & \leq \sum_{j=1}^n \frac{\frac{1}{j}\mathbb{E}[X]}{c} \\ & = \frac{\mathbb{E}[X]H_n}{c} \end{align} Which is more general, but much worse than the above bound, although it's clear that $\mathcal{T}$ must diverge whenever $c \leq \mathbb{E}[X]$.

Answer 1

This is a rather hand-made approach, and I would really appreciate some comment on it, (and the criticizing ones are usually the most helpful). If I understand correctly, the OP calculates sample means $\bar x_j$, where each sample contains the previous sample +1 observation from a new r.v. Denote $F_j$ the distribution of each sample mean. Then we can write

$$\mathcal{T} \overset{def}{=} \sum_{j=1}^n \left(1-F_j(c)\right) = n- \sum_{j=1}^n F_j(c)$$

Consider a sample size $m$ after which the distribution of the sample mean is almost normal, denote it $\hat G$. Then we can write

$$\mathcal{T} = n- \sum_{j=1}^m F_j(c)-\sum_{j=m+1}^n \hat G_j(c) < n-\sum_{j=m+1}^n \hat G_j(c)$$

Solving $\hat G_j(c)$ we obtain $$\hat G_j(c) = 1- \Phi\left(\frac{\sqrt j}{\sigma}(\mu-c)\right) $$ where $\Phi$ is the standard normal cdf, $\sigma$ is the standard deviation of the i.i.d process, and $\mu$ is its mean. Inserting into the bound and re-arranging we get

$$\mathcal{T} < m+\sum_{j=m+1}^n \Phi\left(\frac{\sqrt j}{\sigma}(-a)\right)$$

Note that this bound depends also on the variance of the process. Is this a better bound than the one presented in the question? This will depend crucially on how "quickly" the distribution of the sample mean becomes "almost normal". To give a numerical example, assume that $m= 30$. Assume also that the random variables are uniform in $[0,1]$. Then $\sigma = \sqrt \frac{1}{12}$ and $\mu = \frac 12$. Consider a 10% deviation from the mean, i.e. set $a=0.05$. then : already for $n=34$ the bound I propose (which is meaningful for $n>30$) becomes tighter. For $n=100$ the Hoeffding bound is $78.5$ while the bound I propose is $36.2$. The Hoeffding bound converges to $\approx 199.5$ while the bound I propose to $\approx 38.5$ If you increase $a$ the discrepancy between the two bounds reduces but remains visible: for a 20% deviation, $a=0.1$, the Hoeffding bound converges to $49.5$ while the bound I propose converges to $30.5$ (i.e the sum of the normal cdfs contributes very little to the overall bound).
Somewhat more generally, we note that for $n\rightarrow \infty$ the Hoeffding bound converges to

$$H_b\rightarrow \frac{1}{e^{2 a^2}-1} $$ while my bound to $$A_b \rightarrow m$$

Since for small values of $a$ (which is rather the case of interest) $H_b$ becomes a large number, there is still the case that $A_b$ may outperform it in tightness, even if the sample is such that the distribution of the sample mean converges slowly to the normal distribution.