Arora, Barak, Brunnermeier and Ge have a new paper showing that it is possible to construct “toxic” financial derivative products such that detecting the bad assets is computationally intractable and even proving that a fraud has been committed is impossible. The paper gets a mention in BoingBoing.

The book “Concentration of Measure for the Analysis of Randomized Algorithms” by Dubhashi and Panconesi is out, and is fantastic.

It starts with the basic Chernoff-Hoeffding bounds: if X_1,\ldots,X_n are independent bounded random variables, each ranging in [0,1], then

Pr [ | \sum_i X_i - {\mathbb E} \sum_i X_i | \geq t ] \leq 2 e^{-2t^2/n}

and similar bounds hold also if the X_i have bounded variance.

In many applications, however, one may have to deal with random variables X_1,\ldots,X_n which are correlated, and with operations that are more complicated than sums. For example, suppose we want to prove that there are expanding d-regular graphs. Then we may try to apply the probabilistic method, and generate a d-regular graph by picking d random matchings and taking the union, then showing that for every cut k \leq |V|/2, and every subset of k vertices, the probability that the set of vertices is non-expanding is much less than {|V| \choose k}, so even summing over all sets we have probability less than one that the graph is non-expanding. The difficulty is how to reason about the number of edges leaving a set of size k in a process in which we pick d random matchings. Each of the d|V|/2 edges we generate has probability 2\cdot k \cdot (|V|-k) / |V|^2 of leaving the set, but these d|V|/2 events are not independent.

Usually, Azuma’s inequality is powerful enough to deal with such dependencies and recover a bound. In many interesting cases, however, the assumptions of Azuma’s inequality are not met, and one has to work with more powerful tools, such as Talagrand’s inequality, which is also covered in the book. Finally, in extreme cases, one may have to resort to log-Sobolev inequalities, which I have never had a chance to understand so far, and even they get a very clear treatment.

The book has its quirks. Lemma 2.3, for example, has a handwritten proof, attributed to Anupam Gupta’s penmanship.

About these ads