Skip to content



A new probability inequality and some optimal concentration results

Kannan, R (Microsoft Research Labs., India)
Tuesday 25 March 2008, 16:15-16:45

Seminar Room 1, Newton Institute


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<n^{-2/3}) is concentrated in an interval of length (np)^{3/2} which is again the best possible, since this is the standard deviation. We also outline applications to counting the number of H in G_{n,p} for any fixed graph H.




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧