Return to 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.

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

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 so since I'm actually looking for an expectation in the end and Hoeffding's is more general than is needed.

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.

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 j \times \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 j \times 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.

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 so since I'm actually looking for an expectation in the end and Hoeffding's is more general than is needed.