Some results in probability and theoretical computer science

Thumbnail Image
Date
2001-01-01
Authors
Dai, Jack
Major Professor
Advisor
Krishna B. Athreya
Jack Lutz
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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.

Comments
Description
Keywords
Citation
Source
Subject Categories
Keywords
Copyright
Mon Jan 01 00:00:00 UTC 2001