#### Degree Type

Dissertation

#### Date of Award

2001

#### Degree Name

Doctor of Philosophy

#### Department

Mathematics

#### First Advisor

Krishna B. Athreya

#### Second Advisor

Jack Lutz

#### Abstract

As typical examples for nonlinear dynamical systems, the logistic maps mapping x to cx(1 - x) with x is in [0,1] and c is a constant in [0,4] have been extensively studied. Bhattacharya and Rao (1993) studied the case that c is a random variable rather than a constant. In this case, each of the logistic maps above defines a Markov Chain on [0,1]. In this dissertation, we give some sufficient conditions for the existence of an invariant probability on (0,1) and some sufficient conditions for the nonexistence of invariant probability measures on (0,1) as well. When there exists an invariant probability on (0,1), we study the problem of the uniqueness of invariant probability measure on (0,1). We give some sufficient conditions for the invariant probability measure to be unique. We also provide an example where c takes only two values such that there exist two distinct invariant probability distributions supported by the open interval (0,1). This settles a question raised by R. N. Bhattacharya. In this dissertation, we also study the resource bounded measure that was introduced by Jack Lutz in 1992. It is shown that under Jack Lutz's Strong Hypothesis, for any integer k that is at least 2, there is a sequence of k languages that is sequentially complete for NP, but no nontrivial permutation of this sequence is sequentially complete for NP. We also prove a stronger version of Resource-Bounded Kolmogorov Zero-One Law. We prove that if a class X of languages is a tail set, and has outer-measure less than 1, then it is measurable and has resource-bounded measure 0.

#### DOI

https://doi.org/10.31274/rtd-180813-9917

#### Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu

#### Copyright Owner

Jack Jie Dai

#### Copyright Date

2001

#### Language

en

#### Proquest ID

AAI3003234

#### File Format

application/pdf

#### File Size

70 pages

#### Recommended Citation

Dai, Jack Jie, "Some results in probability and theoretical computer science " (2001). *Retrospective Theses and Dissertations*. 420.

https://lib.dr.iastate.edu/rtd/420