Dissertation/Thesis Abstract

Analysis techniques for nudged random processes
by Freire, Juliana, Ph.D., New York University, 2009, 203; 3365699
Abstract (Summary)

The random walk Xt = Xt-1 + Po [special characters omitted]- 1 can be viewed as a simplification of a neuron firing model if we reset Xt = 1 whenever Xt = 0 happens. The Last Crash is the last time such a reset occurs. We show that the critical window for that time is n ±αn 2/3 and bound, as a function of α, the probability that the last crash has occurred by that time.

The Propp Machine is a de-randomization of a random walk by indivisible chips being routed in a specific order from each position. Here we study it in [special characters omitted] The walk is considered Proppian if the difference between the number of chips at each position at each time and the expected number of chips by the random walk is bounded by a constant independent of the initial configuration. This was previously known to be true for some specific walks on [special characters omitted] Here we show that it is true for all zero drift walks on [special characters omitted]

A packing in a Steiner Triple System is a maximal set of non-overlapping edges. A packing is perfect if it uses all vertices in the case n = 6k + 3 or all but one vertex in the case n = 6k + 1. It is known that every STS with n vertices has a packing using all but at most [special characters omitted] vertices. A random greedy packing gives results on this order. Appending a randomized end-game strategy, we find perfect packings.

Indexing (document details)
Advisor: Spencer, Joel
Commitee: Chudnovsky, Maria, Khot, Subhash, Pach, Janos, Peskin, Charles
School: New York University
Department: Mathematics
School Location: United States -- New York
Source: DAI-B 70/07, Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Mathematics
Keywords: Critical window, Derandomization, Propp machine, Random greedy algorithm, Random walks, Steiner triple systems
Publication Number: 3365699
ISBN: 978-1-109-25854-7
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest