Deducing Vertex Weights from Empirical Occupation Times

Details Deducing Vertex Weights from Empirical Occupation Times Deducing Vertex Weights from Empirical Occupation Times

2009-05-27

arxiv.org/abs/0905.4391v1

Mathematics

Combinatorics

23 pages

Scientific paper

We consider the following problem arising from the study of human problem solving: Let $G$ be a vertex-weighted graph with marked "in" and "out" vertices. Suppose a random walker begins at the in-vertex, steps to neighbors of vertices with probability proportional to their weights, and stops upon reaching the out-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. In the process, a result concerning the differentiation of a matrix pseudoinverse is given, which may be of independent interest. We then consider the existence of a choice of weights for the given occupation times, formulating a natural conjecture to the effect that -- barring obvious obstructions -- a solution always exists. It is shown that the conjecture holds for a class of graphs that includes all trees and complete graphs. Several open problems are discussed.

Affiliated with

Also associated with

No associations

Rating

Deducing Vertex Weights from Empirical Occupation Times does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deducing Vertex Weights from Empirical Occupation Times, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deducing Vertex Weights from Empirical Occupation Times will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527568