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



Reference request: Hoeffding-type inequality
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. 


