Vertex weights from sample mean occupation times
by
Joshua Cooper
University of South Carolina

Suppose that a random walker on a vertex-weighted graph chooses neighboring vertices at each step with probabilities proportional to their weights. If the walker is starts at a ``source'' vertex, and stops when she reaches a ``sink'' vertex, what is the expected number of visits (i.e., occupation times) to each vertex? The answer is straightforward from standard Markov Chain theory. However, the inverse question, which has applications in machine learning and educational psychology, appears new: given a graph with designated source and sink, for which vectors of expected occupation times is it possible to find a corresponding weighting of the vertices of G? We state a natural conjecture and some partial (affirmative) results. We also discuss a steepest-descent algorithm for the corresponding first-order method of moments problem, which raises an interesting question about differentiating pseudoinverses.

Date received: March 3, 2008