The usual Azuma's inequality assumes absolute bounds on the Martingale differences. This is often too pessimistic, but seems inherently required in the usual moment-generating function method. We prove a new general inequality based on bounds on moments of Martingale differences rather than absolute bounds; while the method used is elementary, it is quite different from the m-g f method.
We present two applications - to bin packing and counting the number of triangles in a random graph. In the first, we prove that the number of bins required to pack n i.i.d. items, each with mean a and variance b^2 is concentrated in an interval of length O(a^{3/2} b) which we show is best possible. Then we prove that the number of triangles in a random graph G_{n,p} (with p
view more