# CSM

## Seminar

### A new probability inequality and some optimal concentration results

Seminar Room 1, Newton Institute

#### Abstract

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.

## Comments

Start the discussion!