A New Probability Inequality Using Typical Moments and Concentration Results
Ravindran Kannan · 2009
We present two probability inequalities. The simpler first inequality weakens both hypotheses in Hoffding-Azumaine quality. Using it, we generalize concentration results previously known for the uniform density for the TSP, MWST and Random Projections to long-tailed inhomogeneous distributions. The second more complicated inequality further weakens the moment requirements and using it, we prove the best possible concentration for the long-studied bin packing problem as well as some others.