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.

Special Session on Computability and Complexity

Cameron Freer and I organized a special session at the AMS meeting at UH during March 3-4, 2012.

Program

Speakers

Logan Axon (Gonzaga University, Washington)Axon’s slides
Jennifer Chubb Reimann (University of San Francisco)
Denis Hirschfeldt (University of Chicago)Hirschfeldt’s slides
John Hitchcock (University of Wyoming)
Greg Igusa (UC Berkeley)Igusa’s slides
Joseph S. Miller (University of Wisconsin, Madison)Miller’s slides
Mia Minnes (UCSD) Minnes’ slides
Pavel Semukhin (Pacific Institute for Mathematical Sciences (PIMS), University of Regina, Saskatchewan, Canada)Semukhin’s slides


View Special Session speakers in a larger map

Abstracts

1078-03-400 Algorithmic Randomness and Computational 13-dec-2011
Learning.
John M Hitchcock*, jhitchco@cs.uwyo.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-400.pdf

1078-03-399 Cupping with random sets. 13-dec-2011
Joseph S. Miller*, jmiller@math.wisc.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-399.pdf

1078-03-377 Algorithmic randomness and complexity 13-dec-2011
via automata.
Mia Minnes*, minnes@math.ucsd.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-377.pdf

1078-03-363 The reverse mathematics of homogeneous 13-dec-2011
models.
Denis R. Hirschfeldt*, drh@math.uchicago.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-363.pdf

1078-03-354 Effective properties of approximable 13-dec-2011
functions.
Jennifer Chubb Reimann*, jcc31@psu.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-354.pdf

1078-03-313 Martin-L\”of random closed sets. 12-dec-2011
Logan Axon*, axon@gonzaga.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-313.pdf

1078-03-237 Nonexistence of Minimal Pairs for 10-dec-2011
Generic Computation.
Gregory Igusa*, igusa@math.berkeley.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-237.pdf

1078-03-127 Automatic models of first-order theories. 01-dec-2011
Pavel Semukhin*, pavel@semukhin.name
Frank Stephan
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-127.pdf

Top Ten pages

(unique pageviews)

Part of my faculty service assignment is to maintain the site math.hawaii.edu. Here are the top ten most visited pages within it during 2011 (some pages did not exist or were not tracked during part of the year). 2012 results further down the page.

Position 2011 2012 2013
1 / / /
2 /home/ /online-grapher/ /wordpress/placement-exam/

Analysis: the home page / will always be number one. In 2011 due to a temporary issue the home page was for a while redirected to /home/, so that got the number 2 spot. Number 3 was the now archaic-sounding /home/Placement.shtml. In 2012 the number 2 spot went to /online-grapher/ followed by /people/ at number 3. For 2013, due to a redesign the Online Grapher was split between wordpress/online-grapher and online-grapher thereby losing the number to slot to /wordpress/placement-exam/.

In summary, 2011 was dominated by plain server-side include and .shtml URLs, 2012 by introduction of URL rewriting rules, and 2013 by WordPress delivering some of the most visited pages.

  1. /

    This is the homepage, so it is to be expected that it’s number one.

  2. /home/

    This was the address of the homepage for a while due to a temporary configuration. Ideally this should not be on the list.

  3. /home/Placement.shtml

    This was the address of the page /placement/ for a long time. The page features exam sign-up, practice exams, and detailed rules regarding an exam taken by many undergraduates on campus.

  4. /home/directory.shtml

    This was the address of the page /people/ for a long time. A natural use of the site is to go to /people/, then /people/specificperson/, and then click on the link to the specific person’s home page, /~whateveritis/.

  5. /?online-grapher

    Somehow our department has the #1 hit for the search term “online grapher” on Google. This page is now called /online-grapher/.

  6. /home/?directory

    Another name for the /people/ page that was in use for a while.

  7. /online-grapher/
  8. /home/?Placement

    Another name for the /placement/ page that was in use for a while.

  9. /home/Courses.shtml

    A name for the page /courses/ that was in use for a long time.

  10. /?page=online-grapher

    A name for /online-grapher/ that was in use for a while.

For 2012 the list was (again by Unique Pageviews):

Page Pageviews Unique Pageviews Avg. Time on Page Entrances Bounce Rate % Exit Page Value
1.
/
89,070 64,187 00:02:07 60,555 42.11% 38.72% \$0.00
2.
/online-grapher/
23,377 18,139 00:02:10 18,003 78.44% 75.01% \$0.00
3.
/people/
24,617 15,476 00:00:29 2,647 22.33% 8.30% \$0.00
4.
/placement/
22,607 15,156 00:03:45 10,486 63.85% 55.53% \$0.00
5.
/fortran/3/
14,732 13,581 00:03:56 12,663 91.66% 85.45% \$0.00
6.
/fortran/1/
7,843 6,698 00:03:06 5,384 84.66% 69.83% \$0.00
7.
/courses/
11,011 6,268 00:00:46 609 37.11% 13.70% \$0.00
8.
/computer-lab/
6,256 5,422 00:01:59 4,622 83.64% 71.08% \$0.00
9.
/wordpress/placement-exam-coming-up/
7,846 5,413 00:01:15 1,361 39.82% 27.43% \$0.00
10.
/undergraduate/
6,634 4,713 00:00:26 233 52.36% 12.10% \$0.00

Transition to Advanced Mathematics

Math 321

Textbook: Numbers, groups, and codes (Humphreys and Prest), 2nd edition
Times: TuTh 12-1:15

Each homework set is worth the same amount. The top 8 out of 10 homeworks count 2.5% of the course each for a total of 20% for homework. The best out of two midterms counts 40%. The final counts 40%.

HW1: 1.1: 3, 6 (Greatest common divisors); 1.2: 3, 7 (Induction)
HW2: 1.3: 6, 7, 8 (Unique factorization); 1.4: 5, 6, 7 (Congruence classes)
HW3: 1.5: 1, 4 (Solving linear congruences); 1.6: 1, 4, 7, 10, 12 (Cryptography)
HW4: 2.1: 3, 7, 8; 2.2: 7, 8, 9, 11
HW5: 2.3: 2, 3, 5, 10; 2.4: 2, 4
HW6: 3.1: 2, 4; 3.2: 1; 3.3: 3
HW7: 4.1: 2, 5; 4.2: 3, 4, 5, 8, 12
HW8: 4.3: 3, 4, 7; 4.4: 3, 4, 5, 6, 8, 14
HW9: 5.1: 1, 2, 6, 7; 5.2: 1, 3
HW10: 5.3: 2, 3, 5, 8; 5.4: 2, 3, 5

Note on 5.4: The syndrome of $w=(x|y)$ ($x$ followed by $y$) is $xA+y$ (whereas juxtaposition denotes matrix multiplication). If $z$ is a coset leader with $z=u|v$ and the same syndrome $uA+v=xA+y$, then $w+z=(x|y)+(u|v) = (x+u)|(y+v) = (x+u)|((x+u)A)$, so $w+z$ is a codeword. Moreover since the coset leaders are low weight (sparse), $w+z$ is close to $w$.