Deterministic automaton complexity of strings

The deterministic automaton complexity of a finite binary string \(x=x_1\ldots x_k\) is defined to be the least number \(A(x)\) of states of a finite state automaton \(M\) such that \(x\) is the only string of length \(k\) in the language accepted by \(M\). It was introduced by Shallit and Wang (2001).

In a Discrete Mathematics class in Spring 2009, students Jason Axelson, Chris Ho and Aaron Kondo wrote a C program that calculated the complexity of all strings of length at most 7.

Results:
\[A()=1,\quad A(0)=2,\]
\[A(x_1\ldots x_k)\le k \quad\text{ for } k\ge 2,\]
\[A(x_1\ldots x_k)\le k-1 \quad\text{ for } k\ge 5.\]
\[A(x)\le 5 \quad\text{ for } k=7.\]

The string \(011100\) is the only string (starting with a 0) of length 6 or less with the property that its complexity is increased when read backwards:
\[A(011100)=4\ne 5=A(001110).\]


String 011100
Automaton witnessing the complexity of the string 011100. (For simplicity, the trash state where any missing arrow goes is not shown.)

A table of complexities is available:

Table of constants \(c\) with given property \(\forall x\in\{0,\dots,b-1\}^n\)

In the large-alphabet limit, Kayleigh graphs apply and we upper bound is \(\lfloor n/2\rfloor + 2\).
The example \(x=01\) shows the deterministic \(A(x)\) is not well defined unless
we also specify \(b\).
http://math.hawaii.edu/~bjoern/dfa-complexity-of-01-as-3-ary

Length \(n\) \(b=1\), \(A(x)\le cn + 1\) \(b=2\), \(A(x)\le cn\) \(b=3\), \(A(x)\le cn\) \(b=4\), \(A(x)\le cn\)
0 0 \(\infty\) \(\infty\) \(\infty\)
1 0 2 2 2
2 0 1 3/2? 1
3 0 1 1 1
4 0 1 1 1
5 0 0.8 1 1
6 0 0.83 in progress
7 0 0.714285
8 0 0.75
9 0 0.777 or 0.666

News (September 6, 2015): For binary strings of length at most 8, you may view witnessing automata using the format

http://math.hawaii.edu/~bjoern/dfa-complexity-of-011

Thus, the following table is now partially obsolete.

Complete table for binary strings of length \(\leq 7\) and partial table for length \(8\)

In the following table we only consider strings starting with 0, since strings starting with 1 have the same complexity as the string obtained by flipping each bit (e.g., \(K(001)=K(110)\)).

Some witnessing automata are linked to, they were drawn using svg-edit.

In the following table, \(\delta_i = 0102\) means that \((\delta(0,i),\delta(1,i),\delta(2,i),\delta(3,i)) = (0,1,0,2)\)
in a witnessing DFA with 4 states, found by the MATH 301 students’ program.
Curiously, note that below there are no instances of permutation automata (where \(\delta_i\) is a bijection) except for the empty string.

\(A^-(x)\) denotes incomplete DFA complexity, i.e., there is no requirement that the transition functions be total.
We have \(A_N(x)\le A^-(x)\le A(x).\)

String \(x\) Complexity \(A(x)\) \(\delta_0\) \(\delta_1\) \(A^-(x)\)

1 0 0 1
0 2 00 10 1
00 2 01 11 1
01 2 00 10 2
000 2 01 11 1
001 3 110 200 2
010 3 100 210 2
011 3 111 220 2
0000 2 01 11 1
0001 3 022 122 2
0010 4 1120 2321 3
0011 3 202 100 3
0100 4 1130 2211 3
0101 3 122 202 2
0110 4 1110 2231 3
0111 3 122 212 (avoids 0) 2
00000 2 01 11
00001 3 022 122
00010 4 1120 2322
00011 4 1122 2320
00100 4 1102 2331
00101 4 1132 2301
00110 4 1101 2332
00111 4 1131 2302
01000 4 1302 2131
01001 4 1223 2320
01010 3 122 202
01011 4 1221 2320
01100 4 1001 2303
01101 4 1322 2120
01110 4 1220 2321
01111 3 122 212 (avoids 0)
000000 2 01 11
000001 3 022 122
000010 4 0313 2333
000011 4 0333 2313
000100 5 11240 23221
000101 5 11241 23220
000110 5 11220 23241
000111 4 2033 1002
001000 5 13240 22211
001001 4 1321 2220
001010 4 2313 1233 (avoids 0)
001011 4 2032 1003
001100 4 1320 2223
001101 5 13241 22230
001110 5 13220 22243 4 (\(A_N=3\))
001111 4 2313 3133
010000 4 2133 3313
010001 5 12243 23220
010010 4 1220 2321
010011 5 12231 23240
010100 4 2313 1303
010101 3 122 202
010110 5 12210 23241
010111 5 12211 23240
011000 5 13240 21221
011001 4 2002 1033
011010 5 13220 21241
011011 4 1221 2320
011100 4 1220 2323
011101 5 12241 23210
011110 4 2313 1323 (avoids 0)
011111 3 122 212
0000000 2
0000001 3
0000010 4
0000011 4
0000100 5
0000101 5
0000110 5
0000111 5
0001000 5
0001001 5
0001010 5
0001011 5
0001100 5
0001101 5
0001110 5
0001111 5
0010000 5
0010001 5
0010010 4
0010011 5
0010100 4
0010101 4
0010110 5
0010111 5
0011000 5
0011001 5
0011010 5
0011011 5
0011100 5
0011101 5
0011110 5
0011111 4
0100000 4
0100001 5
0100010 5
0100011 5
0100100 4
0100101 5
0100110 5
0100111 5
0101000 5
0101001 5
0101010 3
0101011 4
0101100 5
0101101 5
0101110 5
0101111 5
0110000 5
0110001 5
0110010 5
0110011 5
0110100 5
0110101 5
0110110 4
0110111 5
0111000 5
0111001 5
0111010 5
0111011 5
0111100 5
0111101 5
0111110 4
0111111 3
String Complexity Witness
00000000 2 \(0^*\)
00000001 3 \(0^* 1\)
00000010 4 \(0^* 10\)
00000011 4 \(0^* 11\)
00000100 5 \(0^* 100\)
00000101 5 \(0^* 101\)
00000110 5 \(0^* 110\)
00000111 5 \(0^* 111\)
00001000 6 \(0^* 1000\)
00001001 6 \(0^* 1001\)
00001010 6 \(0^* 1010\)
00001011 6 \(0^* 1011\)
00001100 6 \(0^* 1100\)
00001101 6 \(0^* 1101\)
00001110 6 \(0^* 1110\)
00001111 5 d0: (1, 2, 3, 3, 0), d1: (4, 0, 1, 2, 0) better than \(0^* 1111\)
00010000 6 \(0001 0^*\)
00010001 \(\le\)5 \((0001)^*\)
00010010 \(\le\)6 \(0(001)^* 0\)
00010011 \(\le\)6 \(0(001)^* 1\)
00010100 \(\le\)6 \( 00 (01010…)00\)
00010101 \(\le\)5 \( 00 (01)*\)
00010110 5 witness (K-H)
00010111 5 no trash
00011000 \(\le\)6 \( 00011,00011,…\)
00011001 \(\le\)6 \( 0 (0011,0011,…)\)
00011010 6 witness (K-H)
00011011 \(\le\)6 \( 00(011)^*\)
00011100 5 witness (K-H)
00011101 6 witness (K-H)
00011110 \(\le 6\) (Christina M) (Jiehua H)
00011111 \(\le 5\) (Jiehua H)
00100000 \(\le 5\) (Christina M) (Jiehua H)
00100001 \(\le 6\) (Christina M) (Jue W)
00100010 \(\le 6\) (Jue W)
00100011 \(\le 6\) (Jue W)
00100100 \(\le 6\) (Jue W)
00100101 \(\le 5\) (Jue W)
00100110 \(\le 6\) (Jue W)
00100111 \(\le 6\) (Jue W)
00101000 \(\le 6\): \(a \rightarrow_0 b \rightarrow_0 c \rightarrow_1 b\) and \(c \rightarrow_0 d \rightarrow_0 e\) plus one thrash (Frank S)
00101001 \(\le 6\) (Jue W)
00101010 \(4\) (Christina M)
00101011 5\(\le 7\) d0: (1, 2, 1, 0, 4), d1: (3, 0, 4, 0, 2)
00101100 \(\le 7\)
00101101 \(\le 7\)
00101110 \(\le 7\)
00101111 \(\le 6\) (Christina M)
00110000 \(\le 6\) (Christina M) (Jue W)
00110001 \(\le 6\) (Jue W)
00110010 \(\le 7\)
00110011 \(\le 7\)
00110100 \(\le 7\)
00110101 \(\le 7\)
00110110 \(\le 7\)
00110111 \(\le 7\)
00111000 \(\le 6\) (Jue W)
00111001 \(\le 7\)
00111010 \(\le 6\) (Jue W)
00111011 \(\le 7\)
00111100 \(\le 6\) (Christina M) (Jue W)
00111101 \(\le 6\) (Christina M) (Jue W)
00111110 \(\le 5\) (Christina M) (Jue W)
00111111 \(4\) (Christina M) (Jue W)
01000000 \(4\) (Christina M) (Jue W)
01000001 \(\le 5\) (Christina M) (Jue W)
01000010 \(\le 6\) (Christina M) (Jue W)
01000011 \(\le 6\) (Christina M) (Jue W)
01000100 \(\le 7\)
01000101 \(\le 7\)
01000110 \(\le 7\)
01000111 \(\le 7\)
01001000 \(\le 7\)
01001001 \(\le 7\)
01001010 \(\le 7\)
01001011 \(\le 7\)
01001100 \(\le 7\)
01001101 \(\le 7\)
01001110 \(\le 7\)
01001111 \(\le 6\) (Christina M)
01010000 \(\le 6\) (Christina M)
01010001 \(\le 6\) (Christina M)
01010010 \(\le 6\) (Christina M)
01010011 \(\le 6\) (Christina M)
01010100 4 \(\le 4\) (Christina M)
01010101 3 (\(\le 4\) Christina M)
01010110 \(\le 6\) (Christina M)
01010111 \(\le 6\) (Christina M)
01011000 \(\le 7\)
01011001 \(\le 7\)
01011010 \(\le 7\)
01011011 \(\le 7\)
01011100 \(\le 7\)
01011101 \(\le 7\)
01011110 \(\le 6\) (Christina M)
01011111 \(5\) (Christina M)
01100000 \(5\) (Christina M)
01100001 \(\le 6\) (Christina M)
01100010 \(\le 7\)
01100011 \(\le 7\)
01100100 \(\le 7\)
01100101 \(\le 7\)
01100110 \(\le 7\)
01100111 \(\le 7\)
01101000 \(\le 7\)
01101001 \(\le 7\)
01101010 \(\le 7\)
01101011 \(\le 7\)
01101100 \(\le 7\)
01101101 \(\le 7\)
01101110 \(\le 7\)
01101111 \(\le 6\) 4 consecutive
01110000 \(\le 6\) (Christina M)
01110001 \(\le 7\)
01110010 \(\le 7\)
01110011 \(\le 7\)
01110100 \(\le 7\)
01110101 \(\le 7\)
01110110 \(\le 7\)
01110111 \(5\) (Jue W)
01111000 \(\le 6\) (Christina M)
01111001 \(\le 6\) 4 consecutive
01111010 \(\le 6\) (Christina M)
01111011 \(\le 6\) (Chelsea T) (Christina M)
01111100 \(5\) (Chelsea T) (Christina M)
01111101 \(5\) (Chelsea T) (Christina M)
01111110 \(4\) (Chelsea T) (Christina M)
01111111 \(3\) (Chelsea T) (Christina M)

Research statement

The primary focus of my research is algorithmic randomness, especially its relation to randomness extraction and to probability and statistics. More generally I have worked in various areas of computability theory (recursion theory).

The basic idea of algorithmic randomness is to declare an object to be algorithmically random if it belongs to no “computable” set of measure zero. Since only computable sets can truly be understood by humans, an algorithmically random object will be as random as one can desire. This way one can formulate questions such as: can one compute a random object from an object that is almost random? Can one compute anything useful from a random object? etc. So algorithmic randomness is a natural setting for randomness extraction (although not the only natural setting).

Martin-Löf (ML-) randomness is a notion of algorithmic randomness, arguably the most natural one. It basically corresponds to the class of all Turing machines, whereas other randomness notions correspond to those Turing machines that always halt, say. It turns out that the collection of all Martin-Löf random sets is simpler in terms of definability than rival notions. It is a \(\Sigma^0_2\) class, whereas other notions tend to give \(\Pi^0_3\) classes or worse. It is an \(F_\sigma\) set rather than \(F_{\sigma\delta}\). Thus each ML-random set belongs to a closed set containing nothing but ML-random sets, and this is a basic tool in the area.

Open problem: Let \(\text{MLR}\) denote the collection of all Martin-Löf random subsets of \(\mathbb N\) and let \(\le_T\) denote Turing reducibility.

Suppose \(A\subseteq B\subseteq C\), \(A\in\text{MLR}\), and \(C\in\text{MLR}\). Then is it true that \((\exists X\in\text{MLR})(X\le_T B)\)?

Note: Hertling (2005) showed that it is not necessarily true that \(B\in\text{MLR}\).

This is one of many questions of the form: if a set is close to being random, then can we extract randomness from it? I have worked primarily on two notions of being close to random: being close in asymptotic Hamming distance, and being an infinite subset.

The current state of knowledge about infinite subsets is that each Schnorr 2-random set \(X\) has an infinite subset \(Y\) such that no Martin-Löf random set is Turing reducible to \(Y\). This is the main result of the paper A strong law of computationally weak subsets. The main idea of the proof is to combine the Extinction Criterion for Galton-Watson processes with a construction from the paper Comparing DNR and WWKL.

In the case of asymptotic Hamming distance, the paper Recovering randomness from an asymptotic Hamming distance has some results. One can define asymptotic Hamming distance in two ways: either require that the Hamming distance of the prefixes of \(X\) and \(Y\) of length \(n\) is small for all \(n\), or merely for infinitely many \(n\). It turned out to be most natural, in a way, to require small distance on an infinite computable set of values of \(n\). This is related to Michel Weber’s strengthening of the Law of the Iterated Logarithm. This law has a somewhat strange form, involving the logarithm of the logarithm function. However, when one looks at what happens at an infinite sparse set of times, this strangeness disappears. In terms of this notion of asymptotic Hamming distance I obtained the following type of result:

For each Turing reduction \(\Phi\) and each sufficiently random set \(X\), there is a set \(Y\) which is close to \(X\), such that \(\Phi^Y\) is not random.

This has the corollary that from a set \(Y\) that is complex in the sense of Kjos-Hanssen, Merkle, and Stephan (TAMS, 2011), and simultaneously has positive effective packing dimension, one cannot uniformly compute any set \(Z\) that is even Mises-Wald-Church stochastic. A goal is to strengthen this so that \(Y\) has positive effective Hausdorff dimension. Another possible way it can be strengthened is to deal with all Turing reductions at once. Conceivably there is a route here to prove that for each sufficiently random set \(X\), there is a set \(Y\) that is so close to \(X\) as to force \(Y\) to have effective Hausdorff dimension 1; and such that no 1-random set is Turing reducible to \(Y\). This would strengthen a result of Greenberg and Miller which asserts that such sets \(Y\) exist, if we remove the assumption of being close to a random set.

Front-end heavy web sites

Sometimes it is necessary or preferable for a web site to be almost front-end only, i.e., to have no backend scripts written in PHP/Perl/Python/whatever, only server side includes. While this is not the case for the UH Manoa Mathematics web site, at some point it was. A snapshot of the site at the time is available on Google App Engine:

Since there is little backend one can mostly understand the setup just using View Source in the browser. (Actually in this example the SSI backend has been replicated/simulated using PHP for Google App Engine.)

You may notice that a rudimentary “database” system is used, namely the databases are JSON (Javascript object notation) files that are accessed using Ajax. Another approach is to just put the data in a .js file which can be included using a <script> tag.

Increasing approximation to $e$

As is well known, $f(x)=(1+\frac{1}{x})^x$ converges to $e$ as $x\rightarrow\infty$. Sometimes it is good to know that this convergence is monotone which for future reference I will discuss here. We first note that $f(x)=\exp(g(x))$ where
$$\label{1}\tag{1}
g(x)=x\ln\left(1+\frac{1}{x}\right)
$$ and $\exp(x)=e^x$. So it suffices to show $g$ is monotonically increasing to the limit $1$. To that end, rewrite
$$
g(x)=\frac{\ln(1+\frac1x)}{1/x}
$$
and then apply L’Hopital’s rule, and we have that the limit is 1.
How do we know the convergence is monotone? Well, using (\ref{1}) it is readily calculated that $g”(x)<0$ for all $x>0$.

Claim: A function that is concave down and converges to a finite limit as $x\rightarrow\infty$ must necessarily be increasing.

Proof: If we ever had $g’(a)<0$ then $g’(x)\le g’(a)<0$ for all $x\ge a$. By the Mean Value Theorem, on every interval $[n,n+1]$ with $n\ge a$ the function $g$ decreases by at least $|g’(a)|$.

(Namely, if $g(n+1)-g(n)> g’(a)$ then ${\frac{g(n+1)-g(n)}{(n+1)-n}} > g’(a)
$ and so there would be some $x\in [n,n+1]$ with $g’(x)>g’(a)$.)

Consequently $\lim_{x\rightarrow\infty}g(x)=-\infty$.
End of proof of claim.

Excerpts of a talk from Luminy, 2009


Randomness with respect to a measure

Martin-Löf randomness for arbitrary measures on $2^\omega$:

Definition.
A test for $\mu$-randomness is a uniformly $\Sigma^0_1(\mu)$ sequence $\{U_n\}_{n\in\omega}$ with $\mu(U_n)\le 2^{-n}$.

The test $\{U_n\}_{n\in\mathbb{N}}$ defines a null set $\cap_n U_n$. $X$ passes the test for randomness $\{U_n\}_{n\in\mathbb{N}}$ if $X\not\in \cap_n U_n$. If $X$ passes all $\mu$-randomness tests then $X$ is $\mu$-random.

Bernoulli measures

For each $n\in\omega$,
$$\mu_p(\{X: X(n)=1\})=p$$
$$\mu_p(\{X:X(n)=0\})=1-p$$
and $X(0),X(1),X(2),\ldots$ are mutually independent random variables.

Example.
The Strong Law of Large Numbers for $\mu_p$ states that for almost all $X$ according to the measure $\mu_p$, we have
$$\forall\varepsilon>0\,\exists N\,\forall n>N\, \left| \frac{\text{the $\#$ of 1s up to $n$ in $X$}}{n}-p\right| <\varepsilon.$$
Suppose $X$ does not satisfy the SLLN, as witnessed by a number $\varepsilon_0$. Let
$$U_N=\{Z: \exists n>N \, \left| \frac{\text{the $\#$ of 1s up to $n$ in $X$}}{n}-p\right| \ge \varepsilon_0\}.$$
Then $U_N$ is open and in fact $\Sigma^0_1(\mu_p)$; and $\mu(U_N)$ goes effectively to $0$. Thus, $X$ is not Martin-Löf random with respect to $\mu_p$.

Definition.
A set $Y\subseteq \mathbb{N}$ is feeble if it is infinite, and no Martin-Löf random set is computable from $Y$.

Theorem[Law of Feeble Subsets]
Almost every $X\subseteq\mathbb{N}$, according to $\mu:=\mu_{1/2}$, has a feeble subset $Y\subseteq X$.

(Passing from $X$ to $Y$ we suffer a “loss of randomness beyond algorithmic repair.”)

Example.
Let $X$ be Martin-Löf random and let $Y$ be a computably chosen subset of $X$. Say,
$$Y=\langle X(0),0,X(2),0,X(4),0,\ldots\rangle.$$
Then $Y$ is an infinite subset of $X$, but $Y$ does compute a Martin-Löf random set, namely
$$Z=\langle X(2),X(4),X(6),X(8),\ldots\rangle$$
so $Y$ is not feeble.

Generally, if $X$ is Martin-Löf random and $R$ is computable ($R\le_T\emptyset$) then $X\cap R$ is not feeble.

Question.
If there a Martin-Löf random set $X$ and a set $R\le_T X$ such that $R\cap X$ is feeble?

Partial negative result: such an $X$ can not be hyperimmune-free.

von Neumann’s randomness extractor

Let $X$ be Martin-Löf random let $Y$ be a “randomly chosen” subset of $X$. That, is each 1 in $X$ is converted to a 0 with probability $\frac{1}{2}$. Then $Y$ does compute a Martin-Löf random set. Namely, let $Z$ be obtained from $X$ by making the following replacements:
$$\langle X(2n),X(2n+1)\rangle \mapsto Z(n)$$
$$\langle 0,0\rangle \mapsto \langle \rangle$$
$$\langle 1,1\rangle \mapsto \langle \rangle$$
$$\langle 0,1\rangle \mapsto \langle 0\rangle$$
$$\langle 1,0\rangle \mapsto \langle 1\rangle$$

How dense can a feeble subset $Y\subseteq X$ be?

The principal function of a set $Y$ is given by $p(n)=$ the smallest element of $Y$ that is $>p(n-1)$.

  • K., 2007: principal function bounded by $4^n$.
  • Miller, 2008: principal function bounded by $n^{2+\varepsilon}$.

Question.
Can a Martin-Löf random set $X$ have a feeble subset $Y$ of linear density, i.e. principal function bounded by $c\cdot n$?

One way to approach this question is to start with stronger reducibilities.

Definition.
Let $r$ be a reducibility. $Y$ is $r$-feeble if $Y$ is infinite and $Y$ does not $r$-compute any ML-random set.

$c$, $d$, and $btt$-feeble subsets of linear density

Take $Y$ to be a $\mu_p$-random subset of $X$. Then $Y$ has principal function bounded by $({p}^{-1}+\varepsilon)n$ ($Y$ has linear density) and $Y$ is $c$-feeble, $d$-feeble, and $btt$-feeble.

However, using von Neumann’s extractor one can show that $Y$ is not $tt$-feeble. By using different algorithms one can show that $Y$ is also not $l$-feeble nor $p$-feeble.

Question.
Is there an $r$-feeble subset of $X$ of linear density, for $r\in\{p,l\}$? Or even for $r\in\{tt,T\}$?

The 7 clones in Post’s lattice containing the constant functions correspond to reducibilities $m$, $btt(1)$, $c$, $d$, $p$, $l$, $tt$ and out of these 7 a $\mu_p$-random set is feeble for exactly 4.

Reducibilities for which a $\mu_p$-random set is feeble:

  • $m$: $\{0,1\}$
  • $btt(1)$: $\{0,\neg\}$
  • $c$: $\{0,1,\wedge\}$ (conjunctive)
  • $d$: $\{0,1,\vee\}$ (disjunctive)

and those for which it is not:

  • $p$: $\{0,1,\wedge,\vee\}$ (positive)
  • $\ell$: $\{0,\iff\}$
  • $tt$: $\{\neg,\vee\}$

When is a measure “close enough” to uniform?

Theorem[Kakutani 1948]
Let $\mu$ and $\nu$ be strongly positive (i.e. the $p_i$, $q_i$ are bounded away from $0$ and $1$) generalized Bernoulli measures of parameters $\{p_i\}_{i\in\mathbb{N}}$ and $\{q_i\}_{i\in\mathbb{N}}$, respectively. If $\sum_i (p_i-q_i)^2<\infty$ then $\mu$ and $\nu$ are equivalent (i.e. have the same null sets).

Theorem[Vovk 1987]
Let $\mu$ and $\nu$ be computable strongly positive generalized Bernoulli measures of parameters $\{p_i\}_{i\in\mathbb{N}}$ and $\{q_i\}_{i\in\mathbb{N}}$, respectively. If $\sum_i (p_i-q_i)^2<\infty$ then $\mu$MLR=$\nu$MLR.

Linear reducibility

$Z$ is linearly reducible to $Y$ ($Z\le_\ell Y$) if the truth of the equation $Z(n)=1$ can effectively be reduced to the truth of a linear equation in the variables $Y(0), Y(1), \ldots$ over the finite field $\mathbb Z/2\mathbb Z = (\{0,1\},+)$:

$$Z(43)=1\Leftrightarrow Y(3)+Y(5)=0$$
$$Z(44)=1\Leftrightarrow Y(1)+Y(6)+Y(8)=1$$
$$\ldots$$
One way to state this:

Definition.
$Z\le_{\ell}Y$ if there is a recursive function $f$ such that for all $n$,
$$n\in Z\iff |D_{f(n)}\cap Y|\equiv 1(\text{mod }2).$$

An improved von Neumann extractor (in a sense)

Theorem
A $\mu_p$-random set is not $\ell$-feeble.

Proof.
Suppose $Y$ is $\mu_p$-random. The $\mu_p$-probability that $|D_{f(n)}\cap Y|\equiv 1(\text{mod }2)$ is computable from $p$ and converges effectively to $1/2$ as $|D_{f(n)}|\to\infty$. \footnote{\tiny{The reason is that if $D_{f(n)}$ is very large, then it is likely to contain a large amount of numbers from $Y$, and this amount is about equally likely to be odd or even. }}

Let $D_{f(n)}$ be disjoint finite sets that are so large that if $p_i:=\mu_p(\{Y:|D_{f(i)}\cap Y|\equiv 1(\text{mod }2)\})$ then $\sum_i (p_i-\frac{1}{2})^2<\infty$.

If $Z$ is reduced to $Y$ via $D_{f(n)}$, then $Z$ is ML-random.

Positive reducibility

$Z\le_p Y$ iff there is a recursive function $f$ such that for all $n$, $n\in Z$ iff $\exists i\le k_i$ $D_{f(n,i)}\subseteq Y$.

We can rewrite this:
\begin{equation}(*)
\tag{*}\neg \forall i\le k_i [D_{f(n,i)}\not\subseteq Y]
\end{equation}

If the $D_{f(n,i)}$ are disjoint then the events $[D_{f(n,i)}\not\subseteq Y]$ are independent and so we can calculate the probability of (*).

By taking $|D_{f(n,i)}|$ large enough and taking $k_i$ large enough we can get this probability as close to $1/2$ as desired. Thus,

Theorem[A second improved von Neumann extractor]
Let $0<q<1$. A $\mu_q$-random set is not $p$-feeble.

Cannot reduce meet to join

Here is an argument from Culver’s MA thesis from 2010.

Suppose the sequence $(A_0\wedge A_1,A_2\wedge A_3,\ldots)$ is $\vee$-reducible to $A$.
Let’s look at the use of the $\vee$-truth-table reduction for computing $A_8\wedge A_9$.
We claim that after seeing only $A_0,\ldots,A_7$ we can rule out one possibility for $(A_8,A_9)$, thereby making money on $A$ and thus showing $A$ is not random.

If the use is only $A_0,\ldots,A_7$ then let’s say the reduction predicts $A_8\wedge A_9=1$. Then we can rule out the pair $(0,1)$. If the reduction predicts $0$ we can rule out $(1,1)$.

If the use is only $A_0,\ldots,A_8$ then based on us looking at $A_0,\ldots,A_7$ we can determine that the reduction predicts $1\wedge A_9=1$ or we can determine that the reduction predicts $1\wedge A_9=0$. Then we can rule out the pair $(1,0)$, or $(1,1)$, respectively.

Finally, if the reduction uses all of $A_0,\ldots,A_9$ then based on us looking at $A_0,\ldots,A_7$ we can determine that the reduction predicts $1\wedge 1=1$ and we can determine that the reduction predicts $1\wedge 0=1$ and… the reduction cannot correctly predict the whole $\wedge$ function or else $\wedge$ would be an element of the clone $\{\vee\}$.

Transition to Advanced Math: Take-home midterm

Do the following problems from Humphreys and Prest:
1.4#2
2.2#5
2.4#6

For the next and last two problems refer to the page Automaton complexity.

Prove that
4. $A(x_1,\ldots,x_k)\le k+1$ for all $k$.
5. $A(x_1,\ldots,x_k)\le k$ for $k\ge 3$.

6. Extra credit (up to 4% of the course): improve some of the $\le$ estimates on the table of complexities.

(I proved in class that $A(x_1,\ldots,x_k)\le k+2$ for all $k$.)

It is essential to write legibly and show your work. If your work is absent or illegible, and
at the same time your answer is not perfectly correct, then no partial credit can be awarded.
Completely correct answers which are given without justification may receive little or no credit.

During this exam, you are permitted to use calculators, notes, or books.

You are not allowed to collaborate with others, except on the extra credit problem.

Statistical Inference: Take-Home Midterm

Take-Home Midterm

Do 4 of the 5 problems here:
Statistical inference take-home midterm
and do the following
Question 6:

Here we consider Bounce rate (see another midterm question) for visitors to www.math.hawaii.edu during January 1 – March 22, 2012, for two types of web traffic: Direct Traffic and Search Traffic. Conduct a t-test for equality of means as in Section 9.2, Case Study 9.2.1. The data is here (CSV format). You may use Excel, Google Docs, or whichever software you want; show all work by also turning in files used.

Solution to Question 6:

If we let $X$ and $Y$ denote direct traffic and search traffic then $\overline x = 0.652859756097561$ and $\overline y = 0.70355243902439$. Moreover $\sum x_i^2 = 35.44131437$ and $\sum y_i^2 = 40.87052961$. The sample variances (determined by the function “var” in Google Docs) are $s_x^2 = 0.006059182187594$ and $s_y^2 = 0.003477466475459$. Since the sample sizes are equal ($n=m$), the pooled sample variance is just the average of these two, $s_p^2 = 0.004768324331527$. The factor $\sqrt{1/n+1/m}=\sqrt{2/n}$ with $n=82$ is 0.156173761888606, and the value of the statistic $t$ is $$\frac{\overline x-\overline y}{s_p \sqrt{2/n}}$$ which comes out to -4.7006109896853.

This is far enough from zero that we reject the null hypothesis; i.e., search traffic has a significantly higher bounce rate. This may be because search traffic is often traffic on a very specific page (such as a Fortran page) which is the only page the visitor is interested in.