Some results in probability and theoretical computer science
Is Version Of
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.