Books to Read While the Algae Grow in Your Fur, December 2013

MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} }); MathJax.Hub.Config({ TeX: { equationNumbers: { autoNumber: "AMS" } } });

Attention conservation notice: I have no taste.

Julia Spencer-Fleming, Through Evil Days

Continuation of the long-running series. Pulls off the trick of making domestic troubles, ice storms, and not-very-bright criminals equally threatening. (Previously.)

Prudence Shen and Faith Erin Hicks, Nothing Can Possibly Go Wrong

Comic-book mind candy: a school story about evil cheerleaders vs. combat robots. Delightful, though I don't usually care for such unalloyed social realism.

G. E. R. Lloyd, Disciplines in the Making: Cross-Cultural Perspectives on Elites, Learning, and Innovation

A learned comparative examination of how fields like mathematics, art, law, religion, history, philosophy and medicine become marked off as cohesive and (more or less) self-regulating disciplines, and some of the consequences of doing so. There are no great revelations here (disciplines promote competence in accepted skills and concepts, which can depend understanding within a limited area but may or may not lead to progress), but the pay-off here is Lloyd's generous erudition, extending across multiple ancient classical cultures and ethnographic records.

Stéphane Boucheron, Gábor Lugosi and Pascal Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence

Maxim Raginsky and Igal Sason, "Concentration of Measure Inequalities in Information Theory, Communications and Coding", Foundations and Trends in Communications and Information Theory 10 (2013): 1--246, arxiv:1212.4663

Probability distributions in high-dimensional spaces are deeply weird creatures. Suppose we take a point uniformly from the interior of a high-dimensional hyper-sphere of radius 1. Our intuition, from experience with the disc and the three-dimensional ball, is that most such points will be far from the surface of the hyper-sphere. However, a little bit of calculus is enough to show that as the dimension grows, the ratio of the surface area to the volume also grows. This means that a thin, constant-thickness shell just inside the surface ends up containing almost all of the volume --- almost all random points are very close to the surface.

So far, these are just curious facts about high-dimensional geometry, but they have deeper consequences. This sort of "concentration of measure phenomenon" turns out to be quite generic for high-dimensional distributions where each coordinate follows its own distribution, independent of the other coordinates. There is usually some set which captures almost all of the probability, and other positive-probability sets have to be expanded just a little to overlap with it. If we can figure out how things look on this high-probability set, we know most of what the whole distribution will do.

More specifically, the concentration of the probability measure on a particular set turns out to be equivalent to the following: all sufficiently nice functions are, with very high probability, close to their expectation values or their medians. In fact, one can derive results of the form "for $n$ dimensions, the probability that any function $f$ in a well-behaved class $\mathcal{F}$ differs from its expectation value by $\epsilon$ or more is at most $C e^{-nr(\epsilon)}$", with explicit values for the constant $C$ and the rate-function $r$. (Often, $r = O(\epsilon^2)$, but not necessarily.) These might depend on the true distribution and on the function class $\mathcal{F}$, but not on the specific function $f$.

To appreciate the significance of this, one needs to think back to more classic parts of probability theory. The laws of large numbers say that the averages of many independent random variables converge, asymptotically, on expectation values. With some work, these results can be extended to other sorts of functions of many variables, not just averages, under conditions which amount to saying "the function can't depend too strongly on any one variable". Such laws do not say how fast the convergence happens. The