3
$\begingroup$

The following (easy) inequality seems to be quite useful. It also seems to me likely to be known, however I do not know of any reference - is it known?

Given random variables $Y_1,\dots,Y_n$ with $Y_i\in[0,a_i]$ for each $i$, where the $a_i$ are positive real numbers, suppose that there exist a real $p_1$ and functions $p_i(y_1,\dots,y_{i-1})$ for each $2\le i\le n$ with the following properties. For each $i$ we have

$\mathbb{E}(Y_i|Y_1,\dots,Y_{i-1})\le p_i(Y_1,\dots,Y_{i-1})$

and almost surely we have $p_1+\dots+p_n\le\mu$.

Then for each $t>0$ we have

$\Pr(Y_1+\dots+Y_n\ge\mu+t)\le e^{-2t^2/\sum_{i=1}^na_i^2}\,.$

The special case in which each $p_i$ is a constant function is Hoeffding's inequality, but I don't know of a reference for this generalisation.

Despite appearances, it seems unlikely to be a consequence of any martingale inequalities (but I would be interested in knowing if this is false): one can use it to establish concentration as $n\to\infty$ around $n/2$ of the sum $Y_1+\dots+Y_n$ of Bernoulli random variables where $\mathbb{E}(Y_1)=\tfrac12$, the $Y_2,\dots,Y_{n/2}$ have expectation $\tfrac13(1+Y_1)$, and the random variables $Y_{n/2+1},\dots,Y_n$ have expectation $\tfrac13(2-Y_1)$, and the $Y_2,\dots,Y_n$ are independent. The point in this example is that the value of $Y_1+\dots+Y_{n/2}$ is not concentrated. (I know one can analyse this with martingale inequalities by breaking it into two pieces, but this is `cheating' as one doesn't have to do this with the Hoeffding-type inequality).

$\endgroup$
  • 1
    $\begingroup$ Not sure why you think martingale inequalities don't solve this. If you define $Z_i=Y_i-p_i(Y_1,\ldots,Y_{i-1})$ then the sum $Z_1+\ldots+Z_n$ is a supermartingale and the probability of it being bigger then $t$ gives you what you wanted. $\endgroup$ – Ori Gurel-Gurevich Sep 14 '15 at 19:42
  • $\begingroup$ Most likely because I'm not a good probabilist - indeed, I agree that works; actually it gives a stronger bound than my proof (compute the moment generating function by induction and apply Markov) as it allows the statement to be strengthened by replacing $\mu$ with the actual sum for the given history. Thanks - if you want whatever points I can give, post it as an answer. $\endgroup$ – user36212 Sep 14 '15 at 21:48
  • $\begingroup$ No need to be hard on yourself. I'll post it if only so that the question can be marked as answered. $\endgroup$ – Ori Gurel-Gurevich Sep 14 '15 at 22:52
6
$\begingroup$

If you define $Z_i=Y_i−p_i(Y_1,…,Y_{i−1})$ then the sum $Z_1+…+Z_n$ is a supermartingale and the probability of it being bigger then $t$ gives you what you wanted.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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