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. [Added 30/12/2018: George Montañez has referred to this post in his BIO-Complexity article “A Unified Model of Complex Specified Information.” I should make explicit something that is implied by the identification, below, of $\nu$ with an algorithmic probability measure: there is no requirement that the probabilities of atomic outcomes sum to unity, i.e., that $\mu(\Omega) = 1$ and $\nu(\Omega) = 1.$ The loosening of the upper bound on $\mu(E)$ assumes that $\nu(\mathcal{E}) \leq 1$ holds for all events $\mathcal{E} \subseteq \Omega.$]

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)$.

Tolstoy on the studious deceit of children by the church

Nothing captures my experience with the church better than does this passage from Leo Tolstoy’s The Kingdom of God is Within You (1894).

The chief and most pernicious work of the Church is that which is directed to the deception of children — these very children of whom Christ said: Woe to him that offendeth one of these little ones. From the very first awakening of the consciousness of the child they begin to deceive him, to instill into him with the utmost solemnity what they do not themselves believe in, and they continue to instill it into him till the deception has by habit grown into the child's nature. They studiously deceive the child on the most important subject in life, and when the deception has so grown into his life that it would be difficult to uproot it, then they reveal to him the whole world of science and reality, which cannot by any means be reconciled with the beliefs that have been instilled into him, leaving it to him to find his way as best he can out of these contradictions.

If one set oneself the task of trying to confuse a man so that he could not think clearly nor free himself from the perplexity of two opposing theories of life which had been instilled into him from childhood, one could not invent any means more effectual than the treatment of every young man educated in our so-called Christian society.

(I provide context here.) It’s not exactly surprising that people who refer to indoctrination as Christian education should regard education as indoctrination when it happens to conflict with their beliefs.