# Bayes’ rule is full of shit

273 words

We all know the type who think Bayes’ rule is the key to rational thought. They are talking out of their ass. This short note intends to explain why I say that, but without any trite arguments and just focusing on the computer science. In short, because Bayes’ rule is an information-theoretic concept without computational content.

For one, conditional probability distributions are not computable. Of course you say, but no sane person would limit themselves to only computable endeavors? And moreover, that result only applies when there is no noise, i.e., the realm of spherical cows! Your objection is valid, but we have to observe this theoretical impossibility result for the sake of completeness.

The real issue occurs in real-world complexity classes. Random SAT/UNSAT is hard in the appropriate density range.1I have trouble finding a specific reference, but anyone working on SAT solvers will tell you this. So if I pick a random SAT instance from a probability distribution known to both of us, and I tell you the bits encoding the instance one by one, your Bayesian updates on the probability that my instance is true will be hard as well. Both in theory2This is a slightly stronger claim than just $\mathcal P = \mathcal{NP}$. If I recall correctly, ACM SIGACT News Volume 50 Issue 1 or 2 will tell you that everyone believes this hardness statement. and in practice. No matter how much computing power you have, I can easily sample SAT instances that make your Bayes’ rule calculations suffer.

This hardness carries over to everyday problems. Bayes’ rule is typically insufficient to tell you the answers you are looking for.