Take the tour ×


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

Thank you in advance!

share|improve this question
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". –  Ori Gurel-Gurevich Feb 24 '12 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). –  Woland Feb 25 '12 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? –  Ori Gurel-Gurevich Feb 25 '12 at 6:39
@Ori: Why can't it be $(R_1+\cdots+R_t)/t$ as Volodymyr says? –  Brendan McKay Feb 25 '12 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? –  Brendan McKay Feb 26 '12 at 23:02
show 7 more comments

1 Answer

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

With the OP's clarifications of the question (above), this answer is obsolete so please discard it.

share|improve this answer
I don't understand your comment very well, but that's probably because my question wasn't clear in the first place. I hope my comments above made it more clear... –  Woland Feb 27 '12 at 0:41
add comment

Your Answer


