Computing stationary distributions : perron vectors, random walks, and ride-sharing competition
Abstract/Contents
- Abstract
- 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
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2020; ©2020 |
| Publication date | 2020; 2020 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Ahmadinejad, AmirMahdi |
|---|---|
| Degree supervisor | Saberi, Amin |
| Thesis advisor | Saberi, Amin |
| Thesis advisor | Sidford, Aaron |
| Thesis advisor | Charikar, Moses |
| Thesis advisor | Ugander, Johan |
| Degree committee member | Sidford, Aaron |
| Degree committee member | Charikar, Moses |
| Degree committee member | Ugander, Johan |
| Associated with | Stanford University, Department of Management Science and Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | AmirMahdi Ahmadinejad |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering |
| Thesis | Thesis Ph.D. Stanford University 2020 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2020 by AmirMahdi Ahmadinejad
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...