Expected number of times the empirical mean will exceed a value - Cross Validated most recent 30 from stats.stackexchange.com 2019-07-16T06:54:21Z https://stats.stackexchange.com/feeds/question/64432 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://stats.stackexchange.com/q/64432 11 Expected number of times the empirical mean will exceed a value fairidox https://stats.stackexchange.com/users/5321 2013-07-15T23:55:20Z 2014-02-04T02:32:16Z <p>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)$$</p> <p>If we assume that $c = a + \mathbb{E}[X]$ for some $a &gt; 0$, we can use <a href="http://en.wikipedia.org/wiki/Hoeffding%27s_inequality">Hoeffding's inequality</a> to arrive at </p> <p>\begin{align} \mathcal{T} &amp; \leq \sum_{j=1}^n e^{-2ja^2} \\ &amp; = \frac{1 - e^{-2 a^2 n}}{e^{2 a^2}-1} \end{align}</p> <p>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. </p> <p><strong>edit</strong>: The restriction on $c$ being greater than the mean can be removed if we use <a href="http://en.wikipedia.org/wiki/Markov%27s_inequality">Markov's Inequality</a> as follows:</p> <p>\begin{align} \mathcal{T} &amp; \leq \sum_{j=1}^n \frac{\frac{1}{j}\mathbb{E}[X]}{c} \\ &amp; = \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]$.</p> https://stats.stackexchange.com/questions/64432/-/66607#66607 1 Answer by Alecos Papadopoulos for Expected number of times the empirical mean will exceed a value Alecos Papadopoulos https://stats.stackexchange.com/users/28746 2013-08-05T19:40:11Z 2013-09-06T01:13:42Z <p>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 </p> <p>$$\mathcal{T} \overset{def}{=} \sum_{j=1}^n \left(1-F_j(c)\right) = n- \sum_{j=1}^n F_j(c)$$</p> <p>Consider a sample size $m$ after which the distribution of the sample mean is almost normal, denote it $\hat G$. Then we can write</p> <p>$$\mathcal{T} = n- \sum_{j=1}^m F_j(c)-\sum_{j=m+1}^n \hat G_j(c) &lt; n-\sum_{j=m+1}^n \hat G_j(c)$$</p> <p>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</p> <p>$$\mathcal{T} &lt; m+\sum_{j=m+1}^n \Phi\left(\frac{\sqrt j}{\sigma}(-a)\right)$$</p> <p>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, <em>assume</em> 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&gt;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).<br> Somewhat more generally, we note that for $n\rightarrow \infty$ the Hoeffding bound converges to </p> <p>$$H_b\rightarrow \frac{1}{e^{2 a^2}-1}$$ while my bound to $$A_b \rightarrow m$$</p> <p>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.</p>