Finish section on concentration inequalities

[github-actions[bot]]

We would like to have a proper part on the concentration inequalities.

This is very important in computer science and in algorithms analysis because the runtime and the errors are bounded using tools like these. In particular, it would be very nice to collect all the useful formulations for Chernoff bound and Hoeffding, Bernstein inequality, law or large numbers, union bound, central limit theorem, their proofs, and some simple but important applications in the quantum domain.

Are there other concentration inequality that we should include? Let's discuss!

I have collected quite a lot of material on the subject:

• https://www.probabilitycourse.com/chapter6/6_2_3_chernoff_bounds.php ( I like a lot the Comparison between Markov, Chebyshev, and Chernoff Bounds)
• http://www.stat.rice.edu/~jrojo/PASI/lectures/TyronCMarticle.pdf
• https://yassine-hamoudi.github.io/files/other/PhDthesis.pdf (the preliminaries )
• https://twitter.com/zlatko_minev/status/1521108505247326210/photo/1
• Dubhashi, Panconesi - 2009 - Concentration of measure for the analysis of randomized algorithms (they have very good explanations and proofs)

If you decide to start this issue and you want some clarification or help, just contact me (@Scinawa ) on the discord of the unitary.fund, the slack channel of QOSF, @Scinawa on twitter, or write me at ale@nus.edu.sg.

[Avhijit-Nair]

I would like to start working on it. Very interesting topic and relatable to my background.

[Scinawa]

hello @Avhijit-codeboy ! That's great! As you can see there is already something in the draft. Maybe you can add the proof of the most interesting concentration inequality and merge together some material from the lecture notes that are linked there. If you contact me on discord I can give you more material!

[Avhijit-Nair]

Sure @Scinawa !