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
(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