Built on Facts

Sunday Function

This Christmas I got a little handheld GPS, which I’ve been using mostly for geocaching. As the device acquires signals from the various satellites dutifully orbiting overhead, it displays your position coordinates and a figure indicating the estimated uncertainty. At the beginning of the acquisition or if the view of the sky is poor, it might be something like 50 feet. If you have a clear view of the sky and are receiving signals from many satellites, it might be as low as 11 or 12 feet.*

This figure is called the circular error probable. In essence, there is a 50% probability that your GPS-reported position is within one CEP distance of the actual position. The terminology originates in military bombing of ground targets, and was used in the context of “50% of bombs will land within one CEP of the target”. The assumption is that the position error obeys a Gaussian distribution, which is not such a bad assumption for GPS, which is subject to a lot of small error sources and thus more or less subject to the central limit theorem.

However, we’re measuring a distance on a 2-d plane. Distances can’t be negative, so the standard bell curve doesn’t work. We have to use the 2-dimensional Gaussian function, which quoting Wikipedia is:

i-88516ca505d84f969b7ab15a965c3fb3-2.png

This is more complicated than we need. The uncertainties are the same in both directions, and since we have that symmetry we don’t need to bother with x and y anyway. We’ll just assume the function is centered at the origin and use x^2 + y^2 = r^2 and write the function in terms of r. This gives:

i-d18063683dcc0d42b9be45451a84d1e3-3.png

We’ll go ahead and call this our Sunday Function. This is positive everywhere and decays smoothly out from the origin, as it should. I’ll graph it, picking A to normalize the function and σ so that the CEP is 1:

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

The ordinary 1-d Gaussian distribution has its width given by its standard deviation, but we could give the width in terms of something like a CEP, where 50% of the population is within a distance D of the mean. If we did this, we could calculate that 82% are within 2D of the mean, 95.6% are within 3D of the mean, and so forth. But it turns out that the 2-d Gaussian function that characterizes GPS error doesn’t generate the same values, (Because there’s an extra factor of r inside the integral, due to the Jacobian. Might make a good though somewhat technical post later.)

As it happens, if the CEP is 1, there’s already a 93.7% chance you’re within twice the CEP, and a 99.8% chance you’re within three times the CEP. If we graph both the cumulative probability distributions for being within x of the mean for both the 1-d and 2-d Gaussians, they look like this:

i-8d7070ce28f0af28047c7a5fb8246d53-4.png

Here I’ve picked the widths for each so that both cumulative distributions are equal to 1/2 at x = 1. The 2-d function approaches 1 considerably faster. This is pretty convenient for GPS users, for instance. Even if there’s only a 50% chance you’re within (say) 20 feet of the reported position, it’s highly likely that you won’t be all that much farther away even in the worst case.

Comments

  1. #1 Stefano
    January 17, 2011

    Hi, I have two questions for you.

    1. Shouldn’t you take the 3d (or 4d maybe?!) version of the Gaussian bell? As far as I know GPS gives you a point in space and a time, not a position on the Earth’s surface.

    2. When you go to the limit for dimension to infinity, the cumulative distribution will look like a step?

    Thanks for the nice posts!

  2. #2 6EQUJ5
    January 17, 2011

    “Circular error probable” does not scan as English. Adjective-noun-adjective? The term arose when someone in artillery misremembered what they were told “CEP” stood for. The correct term is “circle of equal probability”: the shots are as likely to fall inside that radius as outside it. This misnomer has propagated for a century.

    The military often uses “Julian day” to mean the ordinal day of year, running from 001 to 366 for leap years, in the Gregorian calendar. Actually, the Julian day (invented by Joseph Justus Scaliger), right now is 2455579.284722, and a Julian date is a date in the Julian calendar, which began being abandoned with the adoption of the Gregorian calendar.

    In the military things are learned by rote, by monkey-see-monkey-do, and catechism, which is the teaching of the young by shouting at them, so I would not blame the troops for idiotic military usages. The fault lies with the brass.

  3. #3 Eric Lund
    January 17, 2011

    1. Shouldn’t you take the 3d (or 4d maybe?!) version of the Gaussian bell? As far as I know GPS gives you a point in space and a time, not a position on the Earth’s surface.

    For some applications, yes, but locating your position on the Earth’s surface isn’t one of them. For one thing, your position is constrained to be on the Earth’s surface, so if it claims your altitude is 1600 m and you’re in Florida, something’s amiss, but if you’re in Denver it’s a perfectly reasonable result. Obviously, if you are an airplane/rocket/satellite using GPS to determine your position, then the third spatial dimension does come into play.Second, the people who built those satellites have gone to significant trouble to ensure that the timing is precise, and they have done so to such an extent that they have to include the correction for relativistic frame dragging. The one exception on timing would be if you are trying to measure total electron content along the line of sight from you to the satellite, but in that case you already know your position to a high degree of accuracy because you are observing at a fixed site.

  4. #4 Stefano
    January 17, 2011

    Second, the people who built those satellites have gone to significant trouble to ensure that the timing is precise

    Yes, but it is the time of the GPS receiver that is not precise! Otherwise we would have to think of 0-dimensional Gaussian bell because the satellites know where they are.

  5. #5 matthiasr
    January 17, 2011

    I think the point in giving a 2-dimensional error estimate is that GPS is optimised to locate you longitude- and latitude-, but not elevation-wise. It can do that, but it’s not as accurate.

    Since longitude and latitude are what the normal GPS user is most interested in, this what the information you get from our device is focusing on; including the up/down insecurity would make you overestimate your long/lat insecurity.

    (I can’t find a source for this right now, but it’s plausible: most of the time, most satellites will not be overhead, since most of the part the sphere the satellites are in that you can see is near your horizon. Thus, going up or down a few meters won’t affect the distance to the satellites as much as moving north/south or east/west)

  6. #6 matthiasr
    January 17, 2011

    Addendum: Here’s some actual data from a station in southern Germany. The current data appears to be broken, but dig into the archive: The height error is consistently about 20%-30% larger than the long/lat error.

  7. #7 Mac
    January 17, 2011

    “The height error is consistently about 20%-30% larger than the long/lat error.”

    That is by design. The coding scheme was cleverly designed to give more of the accuracy budget to the horizontal position instead of the vertical position.

    It is an extremely well thought out scheme … one of the most clever features is that it doesn’t really rely on the accuracy of the timing of the receiver … so the receivers can be made very cheaply.

    The GPS is one of the great triumphs of coding.

  8. #8 Don
    January 17, 2011

    “The height error is consistently about 20%-30% larger than the long/lat error.”

    I don’t know about the coding, it must be brilliant to account for things like earth tide. But, I always thought the height error being larger than the lat/long error was due to the fact that the satellites are all in the same plane which is in the same direction as the height measurement. This would be why, when you triangulate a location with a laser theodolite, the three measurements should be made in as different a direction as possible.

  9. #9 Matt Springer
    January 17, 2011

    If you include elevation it would complicate things, but for most purposes of personal navigation you’re not worried about that. I expect instead of a 3-d Gaussian with equal error in each direction you’d get something of a vertically elongated ellipsoid.

    Airplanes, on the other hand, are very interested in accurate elevation for things like no-visibility landing. The relatively new WAAS satellite system is meant to account and correct for several of the major sources of GPS error, ideally reducing the CEP to around a meter even in the vertical direction.

  10. #10 Annonymous
    January 18, 2011

    The 2 dimensional distribution function is 1 – 2^(-n^2)
    for the probability of being within nD

  11. #11 dman
    January 19, 2011

    CLOBBERING TIME

    dawkins – got you…

    who’s the WINGNUT?

    richarddawkins.net/videos/579240-the-truth-about-the-lunatic-religious-right-in-america?page=1

    THE AMERICAN REVOLUTION – JAN 1, 2011

    OMENS OF DEATH:

    an example and warning of the fate of those who try to divide people….

    freethought-forum.com/forum/showthread.php?t=24191

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.