Difference between revisions of "Talk:2435: Geothmetic Meandian"

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
(Proof of convergence: new section)
Line 34: Line 34:
  
 
Side-thought: is GMDN (nowhere near as logical an ETLA contraction of the title term as, say, 'GMMD' or 'GTMD') actually an oblique reference to the GNDNs as popularised/coined by Trek canon? Worth a citation/Trivia? [[Special:Contributions/162.158.158.97|162.158.158.97]] 04:12, 11 March 2021 (UTC)
 
Side-thought: is GMDN (nowhere near as logical an ETLA contraction of the title term as, say, 'GMMD' or 'GTMD') actually an oblique reference to the GNDNs as popularised/coined by Trek canon? Worth a citation/Trivia? [[Special:Contributions/162.158.158.97|162.158.158.97]] 04:12, 11 March 2021 (UTC)
 +
 +
== Proof of convergence ==
 +
 +
Can any of you come up with a mathematical proof that repeated application of F on a set of (say) positive real numbers is guaranteed to converge toward a single real number, i.e. that the GMDN of a set of positive real numbers is well-defined?
 +
 +
One observation I've made is that if you consider that maximum and minimum numbers in the original set to be x1 and xn (without loss of generality), something we know for sure is that AM(x1, ..., xn), GM(x1, ..., xn) and Median(x1, ..., xn) are all at least x1 and at most xn that is to say...
 +
 +
x1 <= AM(x1, ..., xn), GM(x1, ..., xn), Median(x1, ..., xn) <= xn
 +
 +
So range(AM(x1, ..., xn), GM(x1, ..., xn), Median(x1, ..., xn)) is necessarily <= range(x1, ..., xn).
 +
 +
And given that we know that unless x1, ..., xn are all equal, that x1 < AM(x1, ..., xn) < xn, we have an even stricter result (unless x1, ..., xn are all equal) that is
 +
range(AM(x1, ..., xn), GM(x1, ..., xn), Median(x1, ..., xn)) < range(x1, ..., xn).
 +
 +
So, it's clear that range(x1, ..., xn) > range(F(x1, ..., xn)) > range(F(F(x1, ..., xn))) > range(F(F(F(x1, ..., xn)))) > ... and it's also clear that all of these ranges are >= 0. There is a result in number theory that says that any infinite sequence of real numbers which monotonically decreases and is bounded from below converges.
 +
 +
So we know for sure that range(F(F(...F(x1, ..., xn)...))) converges but we still have to show that it converges to 0 to show that the GMDN converges to a single real number.
 +
 +
I'm not sure how to proceed. Does anyone have any ideas?
 +
 +
[[Special:Contributions/172.69.135.44|172.69.135.44]] 05:07, 11 March 2021 (UTC) Anirudh Ajith

Revision as of 05:07, 11 March 2021

Oh, this one's good. Just checked in (no, I wasn't hovering over the refresh button, my first visit today!) and one glance had me in paroxysms of laughter. But how to explain it? Gonna have to think about that. 141.101.98.96 01:12, 11 March 2021 (UTC)

I made a really bad spreadsheet to understand better how it works: https://docs.google.com/spreadsheets/d/1fqmHwDmirJrsKPdf94PutFDw31DMAYxNeR7jef1jneE/edit?usp=sharing

Someone fix my awful transcript edits please. --Char Latte49 (talk) 02:31, 11 March 2021 (UTC)

Seeing the Python added to the Explanation, try this Perl (typed straight here, so not tested)...

## Your prefered variations of "#!/usr/bin/perl", "use strict;" and "use warnings;" here! ##
sub F { my (@vals)=@_; my $invVals=1/int(@vals);
 my ($geo,$arith,$med)=(1); # Only defining $geo, so first *= works correctly!
 while (@vals) { my($lo,$hi)=(shift @vals,pop @vals); # $hi may be undef - this is intended!
  $arith+=$lo; $geo*=$lo; unless (defined $hi) {  $med =  $lo;     last }
  $arith+=$hi; $geo*=$hi; unless (@vals)       { ($med)=F($lo,$hi)      }
 }
 return ($arith*$invVals, $geo**$invVals, $med);
}
sub GMDN { my (@vals)=sort @_; my $lim=10**(-5); # Adjust $lim to taste...
  return "Error: No vals!" unless  @vals; # Catch!
  return $vals[0]          unless ($vals[$#vals]-$vals[0]) > $lim;
  return GMDM(F(@vals));
}
my @test=(1,1,2,3,5);
print "Values:              @test\nGeothmetic Meandian: ".GMDN(@test)."\n";

...debugged in my head, so probably fatally flawed but easily fixed/adapted anyway. 141.101.99.109 03:04, 11 March 2021 (UTC)

Why so complicated?

perl -e 'use strict; use warnings; sub F { my ($s,$p) = (0,1); my @srt = sort {$a<=>$b} @_; for (@_) { $s += $_; $p *= $_; } return ($s/@_,$p**(1/@_),$srt[$#_/2]); } sub Gmdn { print join(", ",@_=F(@_)),"\n" for 0..20; return @_; } print join(", ",Gmdn(1,1,2,3,5)),"\n";'

(With interim results) SCNR -- Xorg (talk) 03:18, 11 March 2021 (UTC)

I can read your version (and I see you do explicit {$a<=>$b}, which indeed may be necessary in mine for real use, along with additional sanity checks, I will check later) but I wanted to make mine neat, and slightly tricksy in implementation, but still not quite so entirely obfuscated to the more uninitiated. TIMTOWTDI, etc, so I like your (almost) bare-bones version too. ;)
(Is 20 cycles enough to converge in sufficiently extreme cases? Won't give "Too deep" error, though, even if it takes at least that long. There's a definite risk that mine might, as written.) 141.101.99.229 03:45, 11 March 2021 (UTC)
Given the lack of precision in Randall's example usage, I think 20 cycles ought to be enough for everyone ;-P. I'm trying to prove that the interval's size has to shrink by somewhat close to a factor of 1/2 every cycle, but it's tricky and it's late. If I can assume a factor of 1/2 in the long run, 64 iterations should pin down a 64-bit float.
I actually didn't try to obfuscate, I was just too lazy to type more ;-). Otherwise I might have left out the "return"s and passing parameters at all. -- Xorg (talk) 04:21, 11 March 2021 (UTC)

Side-thought: is GMDN (nowhere near as logical an ETLA contraction of the title term as, say, 'GMMD' or 'GTMD') actually an oblique reference to the GNDNs as popularised/coined by Trek canon? Worth a citation/Trivia? 162.158.158.97 04:12, 11 March 2021 (UTC)

Proof of convergence

Can any of you come up with a mathematical proof that repeated application of F on a set of (say) positive real numbers is guaranteed to converge toward a single real number, i.e. that the GMDN of a set of positive real numbers is well-defined?

One observation I've made is that if you consider that maximum and minimum numbers in the original set to be x1 and xn (without loss of generality), something we know for sure is that AM(x1, ..., xn), GM(x1, ..., xn) and Median(x1, ..., xn) are all at least x1 and at most xn that is to say...

x1 <= AM(x1, ..., xn), GM(x1, ..., xn), Median(x1, ..., xn) <= xn

So range(AM(x1, ..., xn), GM(x1, ..., xn), Median(x1, ..., xn)) is necessarily <= range(x1, ..., xn).

And given that we know that unless x1, ..., xn are all equal, that x1 < AM(x1, ..., xn) < xn, we have an even stricter result (unless x1, ..., xn are all equal) that is range(AM(x1, ..., xn), GM(x1, ..., xn), Median(x1, ..., xn)) < range(x1, ..., xn).

So, it's clear that range(x1, ..., xn) > range(F(x1, ..., xn)) > range(F(F(x1, ..., xn))) > range(F(F(F(x1, ..., xn)))) > ... and it's also clear that all of these ranges are >= 0. There is a result in number theory that says that any infinite sequence of real numbers which monotonically decreases and is bounded from below converges.

So we know for sure that range(F(F(...F(x1, ..., xn)...))) converges but we still have to show that it converges to 0 to show that the GMDN converges to a single real number.

I'm not sure how to proceed. Does anyone have any ideas?

172.69.135.44 05:07, 11 March 2021 (UTC) Anirudh Ajith