Jak to udowodnić

9

Próbowałem ustalić nierówność

|Ti|=|XiX¯|Sn1n

gdzie to średnia próbki, a standardowe odchylenie próbki, to znaczy .X¯SS=i=1n(XiX¯)2n1

Łatwo zauważyć, że a więc ale to nie jest bardzo blisko tego, czego szukałem, ani nie jest to przydatne ograniczenie. Eksperymentowałem z Cauchy-Schwarzem i nierównościami trójkąta, ale nigdzie nie poszedłem. Musi być jakiś subtelny krok, którego mi brakuje. Byłbym wdzięczny za pomoc, dziękuję.i=1nTi2=n1|Ti|<n1

JohnK
źródło

Odpowiedzi:

10

To jest nierówność Samuelsona i potrzebuje tego znak. Jeśli weźmiesz wersję Wikipedii i przerób ją nan1 Definicja S, przekonasz się, że to się stanie

|XiX¯|Sn1n
soakley
źródło
Jest podana jako absolutna nierówność w książce, ale naprawiłem to, dzięki.
JohnK
5

Po uproszczeniu problemu za pomocą rutynowych procedur można go rozwiązać, przekształcając go w program podwójnej minimalizacji, który ma dobrze znaną odpowiedź z podstawowym dowodem. Być może ta dualizacja jest „subtelnym krokiem”, o którym mowa w pytaniu. Nierówność można również ustalić w sposób czysto mechaniczny poprzez maksymalizację|Ti| przez mnożniki Lagrange'a.

Najpierw jednak oferuję bardziej eleganckie rozwiązanie oparte na geometrii najmniejszych kwadratów. Nie wymaga wstępnego uproszczenia i jest niemal natychmiastowy, zapewniając bezpośrednią intuicję w wyniku. Jak sugerowano w pytaniu, problem sprowadza się do nierówności Cauchy'ego-Schwarza.


Rozwiązanie geometryczne

Rozważać x=(X1,X2,,Xn) jako n-wymiarowy wektor w przestrzeni euklidesowej ze zwykłym iloczynem kropkowym. Pozwolićy=(0,0,,0,1,0,,0) być ith wektor podstawowy i 1=(1,1,,1). pisaćx^ i y^ dla rzutów ortogonalnych z x i y do ortogonalnego uzupełnienia 1. (W terminologii statystycznej są to reszty w odniesieniu do średnich.) Następnie, odXja-X¯=x^y i S.=||x^||/n-1,

|Ti|=n1|x^y|||x^||=n1|x^y^|||x^||

jest składnikiem y^ w x^kierunek. Według Cauchy-Schwarz maksymalizuje się dokładnie, kiedyx^ jest równoległy do y^=(1,1,,1,n1,1,1,,1)/n, dla którego

Ti=±n1y^y^||y^||=±n1||y^||=±n1n,
CO BYŁO DO OKAZANIA.

Nawiasem mówiąc, to rozwiązanie zapewnia wyczerpującą charakterystykę wszystkich przypadków, w których |Ti| jest zmaksymalizowany: wszystkie są formą

x=σy^+μ1=σ(1,1,,1,n1,1,1,,1)+μ(1,1,,1)

dla wszystkich prawdziwych μ,σ.

Ta analiza uogólnia się łatwo do przypadku, w którym {1}jest zastępowany przez dowolny zestaw regresorów. Najwyraźniej maksimumTi jest proporcjonalny do długości reszty y, ||y^||.


Uproszczenie

Ponieważ Ti jest niezmienny w przypadku zmian lokalizacji i skali, możemy założyć bez utraty ogólności, że Xi suma do zera, a ich kwadraty do n1. To identyfikuje|Ti| z |Xi|, od S (średni kwadrat) to 1. Maksymalizacja jest równoznaczna z maksymalizacją|Ti|2=Ti2=Xi2. Przyjmowanie nie powoduje utraty ogólnościi=1, ponieważ, ponieważ Xi są wymienne.


Rozwiązanie dzięki podwójnemu sformułowaniu

Podwójnym problemem jest ustalenie wartości X12 i zapytaj, jakie wartości pozostałych Xj,j1są potrzebne, aby zminimalizować sumę kwadratówj=1nXj2 jeśli się uwzględni j=1nXj=0. PonieważX1 jest podane, jest to problem minimalizacji j=2nXj2 jeśli się uwzględni j=2nXj=X1.

Rozwiązanie można łatwo znaleźć na wiele sposobów. Jednym z najbardziej elementarnych jest pisanie

Xj=X1n1+εj, j=2,3,,n

dla którego j=2nεj=0. Rozszerzenie funkcji celu i wykorzystanie tej tożsamości sumowania do zera w celu jej uproszczenia daje

j=2nXj2=j=2n(X1n1+εj)2=(X1n1)22X1n1εj+εj2=Constant+εj2,

od razu pokazuje unikalne rozwiązanie εj=0 dla wszystkich j. W przypadku tego rozwiązania

(n1)S2=X12+(n1)(X1n1)2=(1+1n1)X12=nn1X12

i

|Ti|=|X1|S=|X1|n(n1)2X12=n1n,

QED .


Rozwiązanie za pomocą maszyn

Wróć do uproszczonego programu, od którego zaczęliśmy:

Maximize X12

z zastrzeżeniem

i=1nXi=0 and i=1nXi2(n1)=0.

Metoda mnożników Lagrange'a (która jest prawie czysto mechaniczna i prosta) utożsamia nietrywialną liniową kombinację gradientów tych trzech funkcji do zera:

(0,0,,0)=λ1D(X12)+λ2D(i=1nXi)+λ3D(i=1nXi2(n1)).

Te elementy po komponencie n równania są

0=2λ1X1+λ2+2λ3X10=λ2+2λ3X20=0=λ2+2λ3Xn.

Ostatni n1 z nich implikuje również X2=X3==Xn=λ2/(2λ3) lub λ2=λ3=0. (Możemy wykluczyć ten drugi przypadek, ponieważ wówczas implikuje pierwsze równanieλ1=0, trywializacja kombinacji liniowej.) Powstaje ograniczenie sumy do zera X1=(n1)X2. Ograniczenie sumy kwadratów zapewnia dwa rozwiązania

X1=±n1n; X2=X3==Xn=1n.

Oboje ulegają

|Ti|=|X1||±n1n|=n1n.
Whuber
źródło
Dziękuję za uzupełnienie, geometria jest bardzo mocna, a ze wszystkich trzech rozwiązań jest dla mnie najbardziej intuicyjna.
JohnK
0

Podana nierówność jest prawdziwa. Intuicyjnie jasne jest, że otrzymujemy najtrudniejszy przypadek nierówności (to znaczy maksymalizacji lewej stronyS2), wybierając jedną wartość, powiedzmy x1tak duży, jak to możliwe, przy równych wszystkich pozostałych. Spójrzmy na przykład z taką konfiguracją:

n=4,x1=x2=x3=0,x4=4,x¯=1,S2=4,
teraz |xix¯|S={12 or 32 zależy od i, podczas gdy podana górna granica jest równa 412=1.5co wystarczy. Ten pomysł można uzupełnić do dowodu.

EDYTOWAĆ

Udowodnimy teraz roszczenie, jak wskazano powyżej. Po pierwsze, dla dowolnego wektorax=(x1,x2,,xn) w tym problemie możemy go zastąpić xx¯bez zmiany żadnej ze stron nierówności powyżej. Przyjmijmy, że poniżejx¯=0. Możemy również założyć, że poprzez ponowne oznakowaniex1jest największy. Następnie, wybierając najpierwx1>0 i wtedy x2=x3==xn=x1n1możemy sprawdzić za pomocą prostej algebry, czy mamy równość w twierdzonej nierówności. To jest ostre.

Następnie zdefiniuj region (wypukły) R przez

R={xR:x¯=0,(xix¯)2/(n1)S2}
dla danej dodatniej stałej S2. Zauważ, żeR jest przecięciem hiperpłaszczyzny ze sferą wyśrodkowaną na początku, podobnie jak sfera w (n1)-przestrzeń. Nasz problem można teraz sformułować jako
maxxRmaxi|xi|
od czasu xmaksymalizacja tego będzie najtrudniejszym przypadkiem nierówności. Jest to problem znalezienia maksimum funkcji wypukłej nad zestawem wypukłym, co ogólnie jest trudnym problemem (minimum jest łatwe!). Ale w tym przypadku obszar wypukły jest kulą wyśrodkowaną na początku, a funkcją, którą chcemy zmaksymalizować, jest wartość bezwzględna współrzędnych. Oczywiste jest, że maksimum to znajduje się na granicy sferyRi biorąc |x1| maksymalna, nasz pierwszy przypadek testowy jest wymuszony.
kjetil b halvorsen
źródło
@JohnK możesz teraz usunąć swoje komentarze, post został poprawiony
kjetil b halvorsen
Chociaż ta odpowiedź pokazuje, że nierówność (zakładając, że jest to prawda, która jest) jest ścisła , nie jest oczywiste, w jaki sposób tę pojedynczą kalkulację można „uzupełnić do dowodu”. Czy możesz podać jakieś wskazówki, jak to zrobić?
whuber
Will, ale jutro muszę przygotować jutro klasę.
kjetil b halvorsen
Dziękuję - doceniam staranne sformułowanie problemu. Ale twój „dowód” wydaje się dochodzić do stwierdzenia, że ​​„to oczywiste”. Zawsze możesz zastosować mnożniki Lagrange'a, aby zakończyć zadanie, ale fajnie byłoby zobaczyć podejście, które (a) faktycznie jest dowodem, a (b) zapewnia wgląd.
whuber
2
@whuber Jeśli masz czas, byłbym wdzięczny, jeśli możesz opublikować swoje rozwiązanie mnożników Lagrange. Myślę, że ogólna nierówność nie jest tak znana, jak powinna być.
JohnK