Question

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

Thank you in advance!

Answer 1

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