1
$\begingroup$

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!

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ 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". $\endgroup$
    – Ori Gurel-Gurevich
    Commented Feb 24, 2012 at 22:58
  • $\begingroup$ 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). $\endgroup$
    – Woland
    Commented Feb 25, 2012 at 3:40
  • 1
    $\begingroup$ 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? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Feb 25, 2012 at 6:39
  • $\begingroup$ @Ori: Why can't it be $(R_1+\cdots+R_t)/t$ as Volodymyr says? $\endgroup$
    – Brendan McKay
    Commented Feb 25, 2012 at 7:52
  • 1
    $\begingroup$ 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? $\endgroup$
    – Brendan McKay
    Commented Feb 26, 2012 at 23:02

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Woland
    Commented Feb 27, 2012 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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