A recent paper proves something that runners have long suspected: GPS overestimates the distance you have traveled. This isn’t due to any algorithmic error; it is instead an unavoidable consequence of two facts:

- The position measurements that GPS makes are noisy — there is some degree of random error to them.
- The distance between two points is a convex function of the coordinates of the points.

A convex function is one that curves upwards. Here are some examples:

For a function of one argument (such as the above examples), convexity means that the function has a positive second derivative. A convex function of several arguments curves upward no matter what direction you follow; that is, the *directional* second derivative is positive no matter what direction you choose.

Jensen’s Inequality states that

- if is a convex function
- and is a (possibly vector-valued) random variable

then

(Strictly speaking, you could have instead of , but only if the probability distribution for is concentrated at a single point.)

In this case, is the vector , where are the *measured* GPS coordinates for the starting point and are the *measured* GPS coordinates for the ending point, and

is the calculated distance between the two points. It is straightforward to show that this distance function is convex.

Note that and are noisy measurements, not the actual (imperfectly known) coordinates. If we assume that the GPS measurements, although noisy, are at least unbiased, then

where and are the *actual coordinates*. The calculated distance is , the actual distance is , and Jensen’s inequality guarantees that

## Leave a Reply