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]$.

  • $\begingroup$ Your definition of $\mathcal{T}$ does not jive with your description of it. If the "$j\times$" were removed it would be the expected number of exceedances of $c$, but as written it is linear combination of the times. It is not manifestly an expectation because the probabilities are not mutually exclusive. For example, when $c\le 0$, $\mathcal{T} = n(n+1)/2$. $\endgroup$
    – whuber
    Jul 16, 2013 at 14:57
  • $\begingroup$ @whuber oh, right, good point thanks, I fixed it above. $\endgroup$
    – fairidox
    Jul 16, 2013 at 22:50
  • $\begingroup$ I notice you changed your upper bound. It now appears to be negative ;-). $\endgroup$
    – whuber
    Jul 16, 2013 at 22:52
  • $\begingroup$ Shouldn't the "$j$" in the exponential be squared? - Ok it simplifies with the domain [0,1] $\endgroup$ Aug 5, 2013 at 18:31

1 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.

  • $\begingroup$ "(i.e no more than the assumed sample-size threshold one needs to get the normal approximation in the distribution of the sample mean)" what are you talking about here? $\endgroup$
    – Glen_b
    Sep 5, 2013 at 2:16
  • $\begingroup$ Nothing important. As I write some lines above, a rule of thumb so that the distribution of the sample mean is "a lot" like normal, is that we need at least a sample size of 30. So for sample size 100, and a 20% deviation case, my bound is $\approx 30.5$ i.e. $m + 0.5$ - in other words the $\sum_{j=m+1}^n \Phi\left(\frac{\sqrt j}{\sigma}(-a)\right)$ part of the bound contributes very little. $\endgroup$ Sep 5, 2013 at 13:20
  • $\begingroup$ Unless you can state the circumstances under which it holds, please avoid calling that thing a rule of thumb in any general sense. The figure of 30 is completely arbitrary (usually either far too weak or far too strong), and that 30 also turns up in your case is, I believe simple coincidence. $\endgroup$
    – Glen_b
    Sep 5, 2013 at 22:39
  • 1
    $\begingroup$ @Glen_b "30" was not even a coincidence - I just used it to provide a numerical example. I have no objection to the issue, I don't like "rules of thumb" (especially when they are dubious). I have made some changes in my answer. Thanks for the input. $\endgroup$ Sep 6, 2013 at 1:15
  • $\begingroup$ @Glen_b Thanks for the possibly non-stationary (i.e. long) memory! $\endgroup$ Feb 4, 2014 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.