Thesis Defense
"An Algorithm to Compute the Stochastically Stable Distribution of a Perturbed Markov Matrix"
John Wicks
Friday, August 29, 2008 at 9:00 A.M.
Room 368 (CIT 3rd floor)
Probabilistic models pervade almost all areas of computer science today (e.g., computer vision, graphics, intelligent agents, and natural language processing). One common modeling tool is that of a finite-state, stationary Markov process, which is characterized by an initial probability distribution and a transition matrix. Analysis of the long-term behavior of such a process can be carried out using standard linear algebra techniques. This long-term behavior may be summarized by another probability distribution, known as a "stable" distribution.
Economists and game theorists have also used such models to study, for example, market dynamics and learning in repeated games. Since individuals do not always behave behave "rationally" (i.e., optimally), some researchers have introduced an additional parameter, ε, to model the "mistakes" (i.e., sub-optimal choices) that individuals sometimes make. The resulting model is called a "perturbed" Markov process, and the corresponding transition matrix is then a "perturbed" Markov matrix (PMM), with entries that are functions of ε. Of particular interest is the limit of the stable distributions of a PMM as ε -> 0, the so-called "stochastically stable" distribution (SSD) of a PMM (Kandori et al., 1993; Young, 1993), which is known to exist and is unique.
A naive approach to computing the SSD of a PMM is to simply to fix ε at a very small value and to compute the corresponding stable distribution using traditional linear algebra techniques. Repeating this computation for a decreasing sequence of εs yields a sequence of approximations of the SSD. However, without precise analytic bounds on the error of such approximations (as a function of ε), they do not really say anything about the SSD. An exact combinatorial algorithm for computing the SSD is known (Friedlin and Wentzell, 1984), but it involves enumerating certain spanning subtrees of the graph associated with the PMM. Because sufficiently expressive Markov models tend to be very high-dimensional, and because the number of spanning subtrees grows exponentially with the dimension, such an approach is not feasible in general.
Recently, some researchers have attempted to exploit state-aggregation techniques to compute stable distributions of high-dimensional Markov matrices (Gambin and Pokarowski, 2001). While these researchers have devised an efficient, recursive algorithm, their results are only approximate. We improve upon past results by presenting a novel state aggregation technique, which we use to give the first exact algorithm (to our knowledge) for computing the SSD of a PMM. Since it is not combinatorial in nature, our algorithm is computationally feasible even for high-dimensional models. Researchers in economics have already used our approach to study the dynamics of housing markets. Given the widespread use of Markov models in computer science, we imagine that it will soon find direct applications there, as well.
Host: Amy Greenwald
| Page Owner: Webmaster | Last Modified: Mon Aug 18 10:40:44 2008 |