6 ms·

Mediant

ggeorgovassilis 4y ago
TIL: the mediant of two fractions a/b < (a+c)/(b+d) < c/d
- eps 4y ago
  Easy to prove too.
  - GuB-42 4y ago
    Just found the proof, that's also how I noticed it doesn't work when one of the denominators is negative. If one of the denominators (not both) is negative, you are guaranteed to be outside of the range.
GuB-42 4y ago
Watch out for negative numbers The mediant inequation is: a/b < (a+c)/(b+d) < c/d If a=1, b=2, c=-1, d=-1 1/2 < 0/1 < -1/-1 1/2 < 0 is obviously wrong If you remove negative signs in the denominators by multiplying by -1/-1, it works 1/2 < 2/3 < 1
- dxbydt 4y ago
  > The mediant inequation is: a/b < (a+c)/(b+d) < c/d The equality is more fun & shows up frequently on the Nationals. It states: a/b = c/d => a/b = c/d = (a+c)/(b+d) For example - On the AIME 2023 this Tuesday (Feb 7), Problem 12 was literally this equality. (see solution 2 below) https://artofproblemsolving.com/wiki/index.php/2023_AIME_I_Problems/Problem_12 https://artofproblemsolving.com/wiki/index.php/2023_AIME_I_P...
haskman 4y ago
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.
- GuB-42 4y ago
  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.
  - madcaptenor 4y ago
    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.)
  - geysersam 4y ago
    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.
    - madcaptenor 4y ago
      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.
- ggeorgovassilis 4y ago
  That was also a (up to now) unanswered question a reader posted.
- geysersam 4y ago
  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.
qsort 4y ago
Went on a tangent on Wikipedia and found this: > assume that the pair of reduced fractions a/c < b/d has the property that the reduced fraction with smallest denominator lying in the interval (a/c, b/d) is equal to the mediant of the two fractions. Then the determinant relation bc − ad = 1 holds. Okay sounds reasonable... > This fact may be deduced e.g. with the help of Pick's theorem Wait what?
- madcaptenor 4y ago
  if you want to keep having your mind blown follow the "Pick's theorem" tangent - apparently there are lots of proofs.
deleted 4y ago
[deleted]
arketyp 4y ago
Is there an efficient method of iterating this so that it converges to the mean? I can think of ways that would include storing the previous iterations...
- huhtenberg 4y ago
  It's not given that it will converge. Feels like it should, but still needs to be proven.
cjfd 4y ago
This does not make an awful lot of sense. I have 1/2 and 3/4. The mediant is 4/6 which is 2/3. Okay. Now I have 1/2 and 6/8. Actually, these are the same numbers, it is just a different representation of 3/4. Now the mediant is 7/10..... Uhm.....
- puffoflogic 4y ago
  This is completely irrelevant.
- uoaei 4y ago
  Author is demonstrating a kind of binary search. Of course, binary search requires a target value, something to search, so your toy problem is underspecified. Then your next interval would be (1/2, 2/3) or (2/3, 3/4) depending on whether s > 2/3 or s < 2/3, where s is your search term.
cannam 4y ago
The same author wrote another very useful post in 2010 that also involved mediants: https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/ https://www.johndcook.com/blog/2010/10/20/best-rational-appr...
recursive 4y ago
There are pathological cases where this can converge very slowly. If the denominators are very different, the new "midpoint" is very close to one of the previous bounds. For example, estimating 0.5000000000001 this way takes a ton of iterations. I found a potential optimization though. If you find that you're repeatedly adjusting the upper/lower bound, you can start adding increasing multiples. It's a provisional step, dependent on the result still being on the same side of the target.

TIL: the mediant of two fractions a/b < (a+c)/(b+d) < c/d

eps 4y ago
Easy to prove too.
- GuB-42 4y ago
  Just found the proof, that's also how I noticed it doesn't work when one of the denominators is negative. If one of the denominators (not both) is negative, you are guaranteed to be outside of the range.

Watch out for negative numbers The mediant inequation is: a/b < (a+c)/(b+d) < c/d If a=1, b=2, c=-1, d=-1 1/2 < 0/1 < -1/-1 1/2 < 0 is obviously wrong If you remove negative signs in the denominators by multiplying by -1/-1, it works 1/2 < 2/3 < 1

dxbydt 4y ago
> The mediant inequation is: a/b < (a+c)/(b+d) < c/d The equality is more fun & shows up frequently on the Nationals. It states: a/b = c/d => a/b = c/d = (a+c)/(b+d) For example - On the AIME 2023 this Tuesday (Feb 7), Problem 12 was literally this equality. (see solution 2 below) https://artofproblemsolving.com/wiki/index.php/2023_AIME_I_Problems/Problem_12 https://artofproblemsolving.com/wiki/index.php/2023_AIME_I_P...

haskman 4y ago

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.

GuB-42 4y ago
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.
- madcaptenor 4y ago
  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.)
- geysersam 4y ago
  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.
  - madcaptenor 4y ago
    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.
ggeorgovassilis 4y ago
That was also a (up to now) unanswered question a reader posted.
geysersam 4y ago
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.

qsort 4y ago

Went on a tangent on Wikipedia and found this: > assume that the pair of reduced fractions a/c < b/d has the property that the reduced fraction with smallest denominator lying in the interval (a/c, b/d) is equal to the mediant of the two fractions. Then the determinant relation bc − ad = 1 holds. Okay sounds reasonable... > This fact may be deduced e.g. with the help of Pick's theorem Wait what?

madcaptenor 4y ago
if you want to keep having your mind blown follow the "Pick's theorem" tangent - apparently there are lots of proofs.

deleted 4y ago

[deleted]

arketyp 4y ago

Is there an efficient method of iterating this so that it converges to the mean? I can think of ways that would include storing the previous iterations...

huhtenberg 4y ago
It's not given that it will converge. Feels like it should, but still needs to be proven.

cjfd 4y ago

This does not make an awful lot of sense. I have 1/2 and 3/4. The mediant is 4/6 which is 2/3. Okay. Now I have 1/2 and 6/8. Actually, these are the same numbers, it is just a different representation of 3/4. Now the mediant is 7/10..... Uhm.....

puffoflogic 4y ago
This is completely irrelevant.
uoaei 4y ago
Author is demonstrating a kind of binary search. Of course, binary search requires a target value, something to search, so your toy problem is underspecified. Then your next interval would be (1/2, 2/3) or (2/3, 3/4) depending on whether s > 2/3 or s < 2/3, where s is your search term.

cannam 4y ago

The same author wrote another very useful post in 2010 that also involved mediants: https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/ https://www.johndcook.com/blog/2010/10/20/best-rational-appr...

recursive 4y ago

There are pathological cases where this can converge very slowly. If the denominators are very different, the new "midpoint" is very close to one of the previous bounds. For example, estimating 0.5000000000001 this way takes a ton of iterations. I found a potential optimization though. If you find that you're repeatedly adjusting the upper/lower bound, you can start adding increasing multiples. It's a provisional step, dependent on the result still being on the same side of the target.