Deducing Vertex Weights from Empirical Occupation Times.

摘要

We consider the following problem arising from the study of human problem solving: Let G be a vertex-weighted digraph with marked "start" and "end" vertices. Suppose that a random walker begins at the start vertex, steps to neighbors of vertices with probability proportional to their weights, and stops upon reaching the end vertex. Could one deduce the weights from the paths that many such walkers take? We analyze an iterative numerical solution to this reconstruction problem, in particular, given the empirical mean occupation times of the walkers. We then consider the existence of a choice of weights for a given list set of occupation times, showing several equivalent conditions for a solution to exist, and giving an algorithm for finding a solution when one exists.;We then consider a generalization of projective space which takes as an input a hypergraph. We discuss some of the properties of these spaces, using a natural CW-complex to distinguish between them, and give some small examples.;Finally we apply the space as a natural space for vertex weights on a graph, and discuss how to extend the solution of the random-walk problem on the graph to the appropriate projective space. Several open problems are discussed.