MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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|cite|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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.