Stochastic tree processes / Kevin Tian.

Format:

Book

Manuscript

Thesis/Dissertation

Author/Creator:

Tian, Kevin, author.

Contributor:

Kannan, Sampath, degree supervisor.

Chakrabarty, Deeparnab, degree committee member.

Khanna, Sanjeev, degree committee member.

Mossel, E. (Elchanan), degree committee member.

Roth, Aaron, degree committee member.

University of Pennsylvania. Department of Computer and Information Science, degree granting institution.

Language:

English

Subjects (All):

Penn dissertations--Computer and Information Science.

Computer and Information Science--Penn dissertations.

Local Subjects:

Penn dissertations--Computer and Information Science.

Computer and Information Science--Penn dissertations.

Physical Description:

iv, 74 leaves : illustrations ; 29 cm

Production:

[Philadelphia, Pennsylvania] : University of Pennsylvania, 2016.

Summary:

Stochastic processes play a vital role in understanding the development of many natural and computational systems over time. In this thesis, we will study two settings where stochastic processes on trees play a significant role. The first setting is in the reconstruction of evolutionary trees from biological sequence data. Most previous work done in this area has assumed that different positions in a sequence evolve independently. This independence however is a strong assumption that has been shown to possibly cause inaccuracies in the reconstructed trees. In our work, we provide a first step toward realizing the effects of dependency in such situations by creating a model in which two positions may evolve dependently. For two characters with transition matrices M1 and M2, their joint transition matrix is the tensor product M1 ⊗ M2. Our dependence model modifies the joint transition matrix by adding an 'error matrix,' a matrix with rows summing to 0. We show when such dependence can be detected.

The second setting concerns computing in the presence of faults. In pushing the limits of computing hardware, there is tradeoff between the reliability of components and their cost. We first examine a method of identifying faulty gates in a read-once formula when our access is limited to providing an input and reading its output. We show that determining whether a fault exists can always be done, and that locating these faults can be done efficiently as long as the read-once formula satisfies a certain balance condition. Finally for a fixed topology, we provide a dynamic program which allows us to optimize how to allocate resources to individual gates so as to optimize the reliability of the whole system under a known input product distribution.

Notes:

Ph. D. University of Pennsylvania 2016.

Department: Computer and Information Science.

Supervisor: Sampath Kannan.

Includes bibliographical references.

OCLC:

974552394