Ars Mathematica

I’ve been reading a bunch of papers on Bayesian statistical inference lately, somewhat to my regret. I have no particular objection to Bayesian statistics, but distressingly often, a Bayesian paper will include a gratuitous slam of all other types of statistics. D. V. Lindley’s papers (which are classics in the literature) are particularly noxious in this regard. It’s a strange pattern, and I’d be curious to know the history of the habit.

More pleasant is a paper by Brad Efron based on an address he gave at Phystat2003, Bayesians, Frequentists, and Physics, which offers a detente in the Bayesian-frequentist debate. He describes Stein’s paradox, which is a challenge from both the Bayesian and classical points of view, and discusses means of inference, such as empirical Bayes, which are (arguably) neither purely Bayesian nor purely frequentist.

Sanjeev Arora is writing a new book on computational complexity, and he’s posting the draft chapters online. Since the standard textbook on the subject, Papadimitriou’s Computational Complexity, is from 1993, a more-recent take on the subject is much appreciated.

I’m a total amateur in the subject, but my impression looking at the notes is that the big difference between 1993 and now is that in 1993 researchers were already beginning to suspect that the best idea in years for settling P versus NP (circuit complexity) wasn’t going to work, and now they’re pretty sure it won’t work.

In the introduction, Arora provides a more succinct summary of the post-1993 work than I possibly could:

The list of surprising and fundamental results proved in the 1990s alone could fill a book: these include new probabilistic definitions of classical complexity classes ( IP = PSPACE and the PCP Theorems) and their implications for the field of approximation algorithms; Shor’s algorithm to factor integers using a quantum computer; an understanding of why current approaches to the famous P versus NP will not be successful; a theory of derandomization and pseudorandomness based upon computational hardness; and beautiful constructions of pseudorandom objects such as extractors and expanders.

We’ve previously linked to some expository material on expanders.

Via Scott Aaronson.

Week 229 of John Baez’s This Week’s Finds in Mathematical Physics is up. And this time I’m even including the link right away, just to show there’s no hard feelings about the lack of flying cars.

It’s been a while since we’ve had an open thread. Feel free to use this opportunity to boast about your own personal math-related website.

The May Notices of the AMS are up. The lead article is Cells in Coxeter Groups. This month’s What is… is What is… Percolation?.

It also includes obituaries for Serge Lang and Raoul Bott.

On his blog, Sigfpe has proposed SIGFPE’s Law, that unlike the exponential growth of ordinary computers, the number of qubits in a quantum computer will only grow linearly. So when the mafia hacks into your bank account a la Sneakers because of their quantum public-encryption-cracking supercomputer, blame Sigfpe for getting it so terribly wrong. Also, blame him for the lack of flying cars.

(One subtlety to keep in mind — which Sigfpe alludes to — a 2-qubit computer is not the same thing as 2 1-qubit computers. The the states of each qubits must allow quantum superposition with each other to really count.)

The new Bulletin of the AMS is out. It has a review of Computational Homology, a book that I have not read, but was very tempted by at the bookstore. Sadly, my library doesn’t have it. Homology provides an interesting pedagogical challenge. If you just wanted to convey the idea of it, you would probably start with simplicial or cubical homology (I think this is the approach Rotman takes in his book), but if you wanted to train future researchers in the subject, you’d be tempted to skip that and go straight to singular or cellular homology. Most graduate courses probably opt for the latter, but perhaps we’ll begin to see applied courses that take the former route.

Week 228 of John Baez’s This Week in Mathematical Physics is up. He’s still obsessed with sand dunes.

I spotted a survey article, Behavioral Economics: Past, Present, and Future, which gives a guide to this fairly-new field of economics. The subject was born from a mathematical failure. Economists had given precise axioms as to how people would take into account time and uncertainty when making decisions. The axioms allowed precise predictions that (unlike most economics) could be tested in small-scale experiments with a few test subjects. The result was almost-total failure: nearly every prediction turned out to be wrong. Instead of this being the last word on the subject, this has inspired large amounts of research into finding empirical regularities in the discrepancies between the predictions and the experimental results, and formulating a new theory that is both precise and correct. It’s interesting because the original failure could have led to a turn away from mathematical modeling altogether, but it instead has led to research in improved mathematical modeling.

I’ve been doing some reading into alternatives to subjective probability, and one interesting alternative is to model an assignment of subjective probability by a convex set of probability distributions, rather than a single distribution. Convex sets encompass several natural situations where you have a vague sense of probabilities, but would be unwilling to specify an exact value. For example, a range of probabilities for an event can be expressed as a convex set, as well as the idea that one event is more likely than another (without expressing exact probabilities for each event). Convexity also has a natural probabilistic interpretation: if two distributions are in the set, then any mixture of the two is also in the set.

A nice introduction to the subject is Fabio Cozman’s online tutorial Introduction to the Theory of Sets of Probabilities. For some additional surveys on related approaches, see the homepage of the Imprecise Probabilities Project.