# System of “stochastic equations”

Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x_i$, where $x_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a measurement $z \approx x_u - x_v$. More precisely, $z$ is a truly random quantity in $(x_u - x_v) \pm 1$, uniformly distributed and independent of all other measurements (edges).

I am given the graph and the measurements, with the distribution promise for above. I want to "solve" the system and obtain the vector of $x_i$'s. Is there some body of work on problems of this type?

Actually, I want to solve an even simpler problem: somebody points me to vertices $s$ and $t$, and I have to compute $x_s - x_t$. There are many things to try, like finding a shortest path, or finding as many disjoint paths as possible and averaging them (weighted by the inverse of the square root of the length). Is there an "optimal" answer?

The problem of computing $x_s - x_t$ is itself not completely defined (e.g. should I assume a prior on the variables?)

• while this is not an answer, using a Kalman filter along a path from s to t comes to mind as a way of getting a decent handle on the path length. – Suresh Venkat Nov 10 '10 at 23:19
• This might not help, or might be way more technology than is needed, but there's a developing theory of stochastic algebraic topology to address questions in robotics and molecular biology about complexes whose edges are imprecisely measured. There are theorems about asymptotics of random linkages (linkage = graph with edge weights). For example, I think the results in this paper would allow you to obtain the expected Betti numbers of your graph: arxiv.org/abs/0708.2997 – Aaron Sterling Nov 11 '10 at 0:45
• Is the fact that the errors are uniformly distributed in [-1,1] rather than some other distribution inherent to your problem or an arbitrary modeling decision? If the latter you can probably make things a lot simpler by using Gaussians instead. – Warren Schudy Nov 11 '10 at 17:59
• The $\pm 1$ error model is certainly inherent to the problem. – Mihai Nov 12 '10 at 2:16

If the measurements were Gaussian then minimizing the sum of squared residuals (like linear least squares curve fitting) would give you a max likelihood estimator. For your problem I haven't written anything down but I would guess (via Bayes rule) that any set of $x$s that could have generated your data is equally likely to have produced it. You can find one max likelihood solution by finding a point in a polytope (i.e. solving a linear program with no objective). Depending on what you want to do with your estimate (loss function) the best estimator is the one that minimizes the integral of your loss function over that polytope. I'll wait until you tell us what your loss function is before guessing about how to evaluate and minimize that integral efficiently.
• This seems hard to believe. Suppose my graph is series-parallel between $s$ and $t$, and every serial path has the same length. Every path gives me an independent measurement of the same quantity, and if the paths are long, the error becomes gaussian. It seems clear that the unique mle is to average the paths, no? – Mihai Nov 11 '10 at 16:42
• Good point. Anywhere in the polytope is a maximum likelihood estimator of the joint distribution of the $x$s, but I forgot that you were looking for an estimator of $x_s-x_t$ only. To get the max likelihood estimator of $x_s-x_t$ you need to find the plane $x_s - x_t = c$ with maximum intersection with that polytope. It appears that in general computing volumes of polytopes is hard to do exactly but can be approximated: mathoverflow.net/questions/979/… . So you can do a binary search for an approximate max likelihood value. – Warren Schudy Nov 11 '10 at 17:57