## Sunday, March 29, 2015

### Deobfuscating a theorem of Ewert, Marks, and Dembski

Back in July, I found that I couldn’t make heads or tails of the theorem in a paper by Winston Ewert, Robert J. Marks II, and William A. Dembski, On the Improbability of Algorithmic Specified Complexity. As I explained,

The formalism and the argument are atrocious. I eventually decided that it would be easier to reformulate what I thought the authors were trying to say, and to see if I could generate my own proof, than to penetrate the slop. It took me about 20 minutes, working directly in LaTeX.
I posted a much improved proof, but realized the next day that I’d missed something very simple. With all due haste, here is that something. The theorem is best understood as a corollary of an underwhelming result in probability.

### The simple

Suppose that $\mu$ and $\nu$ are probability measures on a countable sample space $\Omega$, and that $c$ is a positive real number. What is the probability that $\nu(x) \geq c \cdot \mu(x)$? That’s a silly question. We have two probabilities of the event $E = \{x \in \Omega \mid \nu(x) \geq c \cdot \mu(x) \}.$ It’s easy to see that $\nu(E) \geq c \cdot \mu(E)$ when $\nu(x) \geq c \cdot \mu(x)$ for all $x$ in $E$. The corresponding upper bound on $\mu(E)$ can be loosened, i.e., \begin{equation*} \mu(E) \leq \frac{\nu(E)}{c} \leq \frac{1}{c}. \end{equation*} Ewert et al. derive $\mu(E) \leq c^{-1}$ obscurely.

### The information-ish

To make the definition of $E$ information-ish, assume that $\mu(x) > 0$ for all $x$ in $\Omega$, and rewrite \begin{align} \nu(x) &\geq c \cdot \mu(x) \nonumber \\ \nu(x) / \mu(x) &\geq c \nonumber \\ \log_2 \nu(x) - \log_2 \mu(x) &\geq \alpha, \end{align} where $\alpha = \log_2 c$. This lays the groundwork for über-silliness: The probability of $\alpha$ or more bits of some special kind of information is at most $2^{-\alpha}$. This means only that $\mu(E) \leq c^{-1} = 2^{-\alpha}.$

### The ugly

Now suppose that $\Omega$ is the set of binary strings $\{0, 1\}^*$. Let $y$ be in $\Omega$, and define an algorithmic probability measure $\nu(x) = 2^{-K(x|y)}$ for all $x$ in $\Omega$. (I explained conditional Kolmogorov complexity $K(x|y)$ in my previous post.) Rewriting the left-hand side of Equation (1), we obtain \begin{align*} \log_2 2^{-K(x|y)} - \log_2 \mu(x) &= -\!\log_2 \mu(x) - K(x|y) \\ &= ASC(x, \mu, y), \end{align*} the algorithmic specified complexity of $x$. Ewert et al. express an über-silly question, along with an answer, as $\Pr[ASC(x, \mu, y) \geq \alpha] \leq 2^{-\alpha}.$ This is ill-defined, because $ASC(x, \mu, y)$ is not a random quantity. But we can see what they should have said. The set of all $x$ such that $ASC(x, \mu, y) \geq \alpha$ is the event $E$, and $2^{-\alpha} = c^{-1}$ is a loose upper bound on $\mu(E)$.