Hacker News Reader

Comment by haskman | Hacker News Reader

How does it follow that the mediant (a+c)/(b+d) is a better approximation than both a/b and c/d? One of the bounds could be very close to the quantity you are trying to approximate already.

View on HN

It doesn't. Neither is the average.

To say such a thing, we need:

1. Some assumption about the distribution of the true value. 2. And a metric measuring the "cost" of being wrong.

Assuming a uniform distribution, and measuring cost as the expected absolute value of the error, we find that the average of the interval is the best guess.

Using the same assumptions, any number in the interval is a better estimate than the endpoints.

From that it (obviously) follows that the mediant is a better approximation than both endpoints.

The average of the interval is the best guess if you are only trying to minimize the error. But if you want to also keep the denominator small that's when the problem gets more interesting.

Maybe it's better to formalize this in terms of having a rational interval as the approximation of an irrational - for example the interval [19/7, 87/32] approximates e. That's an interval of width 1/224. Then if [a/b, c/d] contains the irrational number x, then: - either [a/b, (a+c)/(b+d)] or [(a+c)/(b+d), b/d] contains x, and - whichever one contains x is smaller than the original. Written that way it's trivial, though. The real meat, I suppose, is that using the mediant keeps the numerators and denominators small.

In this case, [106/39, 87/32] has width 1/1248 and contains e, whereas using the mean would give you the interval [1217/448, 87/32] of width 1/448.

Looking at the comments, you can iterate this, and eventually you will get a better approximation than both a/b and c/d. But sure enough, after a single iteration, (a+c)/(b+d) is not always better.

If you iterate this, I think you get the continued fraction convergents, which are the "best" rational approximation to the irrational you're trying to approximate. (I did some numerical experiments and this looks true; I didn't prove it.)

I found the thing about iteration quite strange.

To iterate, we need to know if our mediant is larger or smaller than the true value.

How do we know that?

Edit: elsewhere in the thread someone explained that the purpose of iterating is to find an approximation with small denominator.

e isn't the best example for this, because you would need a good decimal expansion. But say we're trying to approximate sqrt(2) by this method. Say we've already established that it's in the interval [7/5, 10/7]. We can verify because 7^2 < 2*5^2 and 10^2 > 2*7^2. Then the mediant is 17/12, and since 17^2 = 289 > 288 = 2*12^2, we know 17/12 > sqrt(2). So [7/5, 17/12] is a smaller interval containing sqrt(2). Repeating this, [24/17, 17/12] is even better, and so on.

That was also a (up to now) unanswered question a reader posted.

Reply on news.ycombinator.com