All posts by admin

The probability distribution as a computational resource for randomness testing

The probability distribution as a computational resource for randomness testing
Journal of Logic and Analysis 2 (2010), no. 10, 1—13.

This paper grew out of my assignment to teach Math 472, Statistical Inference, in Spring 2009 at UH. By analyzing the proof of the law of large numbers and some other work I showed that Hippocratic and Galenic randomness coincide for Bernoulli measures. [There has been follow-up work to this paper which it would make sense to describe here.]

Effective dimension of points visited by Brownian motion

Effective dimension of points visited by Brownian motion
(with Anil Nerode). Theoretical Computer Science 410 (2009), no. 4-5, 347—354.

Preliminary version: The law of the iterated logarithm for algorithmically random paths of Brownian motion.
Logical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 4514, Springer, Berlin, 2007, pp. 310—317.

In this paper we answered a question of Fouché regarding algorithmically random Brownian motion. The key idea was to use Carathéodory’s measure algebra isomorphism theorem.

Nearest walk to Brownian motion

Mathematics 472 (Statistical Inference), University of Hawaii at Manoa, Spring 2009.
This project concerns the distribution of the nearest walk of length \(n\) to a randomly chosen walk of length \(m>n\),
where the walks have step size \(1/n\) on the \(x\)-axis and \(1/\sqrt n\) on the \(y\)-axis.
It is well known that the distribution of such walks converges to Brownian motion.

Two of the groups in the class found that strings of the form \(1^a0^b\) and \(0^a 1^b\) were the least likely nearest walks, whereas strings of the form \(0101\ldots\) or \(1010\ldots\) were the most likely. Strings of the form \(000\ldots\) or \(111\ldots\) were the second least likely.

math overflow questions:

Blurb

I work in mathematical logic, computability theory and algorithmic randomness.

In algorithmic randomness we try to determine what it takes to produce randomness, and what you can do with it once you have it.

Logic and computability deal with the borders between the complete and the incomplete, the decidable and the undecidable, the computable and the non-computable. A fundamental result in the area is Gödel’s 1931 incompleteness theorem, which is a precise version of the following sentiment of Ishmail in Moby Dick.

I promise nothing complete; because any human thing supposed to be complete, must for that very reason infallibly be faulty.

Some open problems are available in a Banff research station archive file.

Finding paths through narrow and wide trees

History of the paper

2006

The paper was written at UConn.

2009

Paper appeared in print:

Finding paths through narrow and wide trees
(with Stephen E. Binns). Journal of Symbolic Logic 74 (2009), no. 1, 349—360.

2012

Laurent Bienvenu and Paul Shafer discovered an apparent error in the proof of Lemma 4.6. There it is stated that A wtt-reduces to B; however, it seems that the reduction of A to B also requires oracle access to f. Corollary 4.7 also seems false (take f to be a ML random of hyperimmune-free degree, and A=f; then A is complex but not f-complex).