# Concentration bound for weakly dependent random variables

Hi,

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

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)$?

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

Are there any tools out there that can be used for this problem?

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

• The parameter $p$ seems completely redundant in your current setting. Also, do you assume a bound on the $R_i$? In any case, try searching for "Azuma's inequality" and "concentration of measure". Commented Feb 24, 2012 at 22:58
• It's not clear to me that $p$ is redundant, because if an $R_t$ is not "activated" with probability $p$, then it is not counted in $X_t$. Also, I don't see how Azuma's inequality would apply, because the $X_t$ are not a martingale (as far as I can tell). Commented Feb 25, 2012 at 3:40
• Maybe I misunderstood your question. Can you give precise definition of $X_t$? is it $R_1+,\ldots,+R_t$ divided by the number of nonzeros among them? Commented Feb 25, 2012 at 6:39
• @Ori: Why can't it be $(R_1+\cdots+R_t)/t$ as Volodymyr says? Commented Feb 25, 2012 at 7:52
• Volodymyr, is $R$ bounded? Otherwise, where does your bound on $|X_t-X_{t-1}|$ come from? Also, are $s(t)$ and $S(t)$ the same? Commented Feb 26, 2012 at 23:02

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