Flaxman A.,UW Institute for Health Metrics and Evaluation |
Gamarnik D.,Massachusetts Institute of Technology |
Random Structures and Algorithms | Year: 2011
This paper studies the time constant for first-passage percolation, and the Vickrey-Clarke-Groves (VCG) payment, for the shortest path on a ladder graph (a width-2 strip) with random edge costs, treating both in a unified way based on recursive distributional equations. For first-passage percolation where the edge costs are independent Bernoulli random variables we find the time constant exactly; it is a rational function of the Bernoulli parameter. For first-passage percolation where the edge costs are uniform random variables we present a reasonably efficient means for obtaining arbitrarily close upper and lower bounds. Using properties of Harris chains we also show that the incremental cost to advance through the medium has a unique stationary distribution, and we compute stochastic lower and upper bounds. We rely on no special properties of the uniform distribution: the same methods could be applied to any well-behaved, bounded cost distribution. For the VCG payment, with Bernoulli-distributed costs the payment for an n-long ladder, divided by n, tends to an explicit rational function of the Bernoulli parameter. Again, our methods apply more generally. © 2011 Wiley Periodicals, Inc.
Green S.T.,UW Institute for Health Metrics and Evaluation |
Flaxman A.D.,UW Institute for Health Metrics and Evaluation
AAAI Spring Symposium - Technical Report | Year: 2010
Many resource-poor countries lack the capacity to accurately track vital registration data, such as cause of death, which are crucial inputs to health and development decision making. Verbal autopsy provides a means to ascertain cause of death in the poorest countries through the means of a standard questionnaire, but because doctors are scarce and their time is better spent treating the ill, methods of classifying deaths based on questionnaire input have become increasingly important. In this paper we present preliminary work on the use of machine learning algorithms to classify cause of death in developing countries. © 2009.