language: en

Learning Distributions from Random Walks

Funda Ergun S Ravi Kumar
Department of Computer Science Cornell University
Ithaca, NY 14853.
Ronitt Rubinfeld

Abstract We introduce a new model of distributions generated by random walks on graphs. This model suggests a variety of learning problems, using the definitions and models of distribution learning defined in [6]. Our framework is general enough to model previously studied distribution learning problems, as well as to suggest new applications. We describe special cases of the general problem, and investigate their relative difficulty. We present algorithms to solve the learning problem under various conditions.

1 INTRODUCTION