This summer, I began studying the Probabilistic Method under Prof. Young from the book The Probabilistic Method by Noga Alon and Joel H Spencer.
The book is very interesting but equally advanced. I have only managed to complete three chapters in three months. Most of the exercises are beyond me but the subject is fascinating.
The first chapter was about the method itself and a few “basic” examples. Say, we want to find a structure with some desired properties. Sometimes, it’s difficult to find the actual structure. But, what we can do is define a probability space of structures which have these properties. Also, we show that these properties hold in the space with positive probability. Thus, although we can’t find the actual structure(s) with this method, we can confirm its existence.
The second chapter dealt with Linearity of Expectation. Easy enough. The main fact is that if we have some random variables and , then . The applications this simple result has can never fail to amaze you.
The third chapter was on Alterations. Sometimes, the random structure we deal with may not have all the desired properties. There may be a few “blemishes” as Alon and Spencer put it. Then we tweak the method a bit to remove these blemishes. This chapter is quite non-trivial and requires some higher concepts from general mathematics.
I hope I can finish this book in some time. It will take me more than a year at my current speed and the difficulty seems to be increasing exponentially.