Six years ago, I sat in a randomized algorithms class taught by Dick Lipton, and he requested we students assemble a list of concentration inequalities. Perfectionistically, I scoured textbooks, paper articles, and the internet for every last inequality I could unearth, building a respectable assortment of one hundred results of varying utility and import. Dick had some design in mind on the assignment, though I never was able to determine his intentions, as he is famously scattered and hard to track down.
I posted them on my personal website years ago, and noticed lately that they’d found their way into lectures by computer scientist Junzhou Huang, a professor at one of my alma maters, the University of Texas at Arlington. It occurred to me that they might interest a broader audience.
As time permits, I’ll try to expand them, and perhaps produce a workbook of proofs for many of them.
Take a look at them here, and let me know what you think!