Dissertation

Computing Stationary Distributions: Perron Vectors, Random Walks, and Ride-Sharing Competition

Ahmadinejad, AmirMahdi

2020

Overview

Stationary distributions appear in a wide variety of problems in areas like computer science, mathematics, statistics, and economics. The knowledge of stationary distribution has a crucial impact on whether we are able to solve such problems, or how efficiently we can solve them. In this thesis, I present three of my projects which have a common theme of dealing with stationary distributions.In the first work, called Perron-Frobenius theory in nearly linear time, we give a nearly linear time algorithm for computing stationary distribution of matrices characterized by the Perron-Frobenius theorem. Through our algorithm, we non-trivially extend the class of matrices known to be solvable in nearly linear time by graph Laplacian solvers.In the second work, called high precision small space estimation of random walk probabilities, we try to make a step toward derandomization of the complexity class RL or randomized log space, which is a long-standing open problem in complexity theory. In this context, the knowledge of stationary distribution for directed graphs seems to be a barrier in achieving such a result. While we are not able to resolve L vs. RL problem, we give a small space deterministic algorithm to estimate random walk probabilities to high precision in undirected graphs, as well as directed Eulerian graphs.In the last work, with the rise of ride-sharing platforms, we study a set of important questions naturally arise in this context. Although we use a different set of technical tools compared to the previous two works, we still deal with characterizing equilibria in stationary systems. One of the main questions we answer is whether the competition between two platforms can lead to market failure by pushing the drivers out of the market.

• Publisher: ProQuest Dissertations & Theses
• Subject: Engineering
• ISBN: 9798684640414