Discrete Stochastic Differentiation

Joshua Copper

ABSTRACT: Suppose that a random walker on a vertex-weighted graph chooses neighboring vertices at each step with probabilities in proportion to those vertices' weights. If the walker is started at a "source" vertex, and stops when she reaches a "sink" vertex, one may ask, what is the expected number of visits (i.e., occupation times) to each vertex? The answer is simple to derive from standard Markov Chain theory, but the inverse question, which we term "discrete stochastic differentiation" (DSD) is apparently wide open: given a graph with designated source and sink, for which vectors of occupation times is it possible to find a corresponding weighting of the vertices of G? How does one find it if it exists? We state a natural conjecture and several results about DSD. We also discuss a few promising applications to machine learning and educational psychology.