Concentration bound for weakly dependent random variables - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T01:03:21Z http://mathoverflow.net/feeds/question/89450 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89450/concentration-bound-for-weakly-dependent-random-variables Concentration bound for weakly dependent random variables Woland 2012-02-24T22:33:55Z 2012-02-27T02:23:47Z <p>Hi,</p> <p>Suppose we observe a sequence $R_1, ..., R_T$ of iid. random variables that equal $0$ with probability $p$ and with probability $1-p$ are sampled from a distribution with expected value $E(R) > 0$.</p> <p>Given $t \leq T$, let $X_t$ denote the mean of the $R_1, ..., R_t$ that were sampled from the distribution. What can we say about the convergence of $\sum_{t=1}^T X_t$ around its mean $T E(R)$?</p> <p>I would like to obtain some kind of Chernoff-Heoffding bound, but the variables $X_t$ are not independent. However, $|X_t - X_{t-1}| &lt; O(1/S(t))$, where $s(t)$ is the number of random variables that were sampled from the distribution at time $t$. Also, note that a variable $X_t$ is independent of $X_{t-2},...,X_1$ given $X_{t-1}$.</p> <p>Are there any tools out there that can be used for this problem?</p> <p>Also, if the above problem can be solved, I would like to obtain an analogous bound on $\sum_{t=1}^T 1/(X_t)^2$ (assuming that $P(X_t = 0) = 0$).</p> <p>Thank you in advance!</p> http://mathoverflow.net/questions/89450/concentration-bound-for-weakly-dependent-random-variables/89471#89471 Answer by Brendan McKay for Concentration bound for weakly dependent random variables Brendan McKay 2012-02-25T07:58:46Z 2012-02-27T02:23:47Z <p>$\sum_{t=1}^T X_t$ is the sum of $t$ independent random variables, for example $\sum_{t=1}^4 X_t = \frac{25}{12}R_1 + \frac{13}{12}R_2 + \frac{7}{12}R_3 + \frac{1}{4}R_4$. To get a Hoeffding-type tail estimate you might need information about the tails of $R$. Similarly for a Berry-Esseen bound. I don't understand your comment about $s(t)$ and $S(t)$ at all.</p> <p><strong>With the OP's clarifications of the question (above), this answer is obsolete so please discard it.</strong></p>