Analysis techniques for nudged random processes

Abstract

The random walk X_t = X_t-1 + Po [special characters omitted]- 1 can be viewed as a simplification of a neuron firing model if we reset X_t = 1 whenever X_t = 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.