# Reference request: Hoeffding-type inequality

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

• 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. – Ori Gurel-Gurevich Sep 14 '15 at 19:42
• 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. – user36212 Sep 14 '15 at 21:48
• No need to be hard on yourself. I'll post it if only so that the question can be marked as answered. – Ori Gurel-Gurevich Sep 14 '15 at 22:52

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.