Bagaimana membuktikan bahwa

9

Saya telah mencoba untuk membangun ketidaksetaraan

|Ti|=|XiX¯|Sn1n

di mana adalah mean sampel dan standar deviasi sampel, yaitu .X¯SS=i=1n(XiX¯)2n1

Sangat mudah untuk melihat bahwa dan seterusnya tapi ini tidak terlalu dekat dengan apa yang saya cari, juga bukan ikatan yang berguna. Saya telah bereksperimen dengan Cauchy-Schwarz dan ketidaksetaraan segitiga tetapi tidak ke mana-mana. Pasti ada langkah halus yang saya lewatkan di suatu tempat. Saya akan sangat menghargai bantuan, terima kasih.i=1nTi2=n1|Ti|<n1

JohnK
sumber

Jawaban:

10

Ini adalah ketidaksetaraan Samuelson dan perlu tanda . Jika Anda mengambil versi Wikipedia dan mengerjakannya kembali untuk definisi Anda akan mendapati bahwa itu menjadin - 1 S , | X i - ˉ X |n1S,

|XiX¯|Sn1n
soakley
sumber
Ini diberikan sebagai ketimpangan yang ketat dalam buku ini tetapi saya telah memperbaikinya, terima kasih.
JohnK
5

Setelah menyederhanakan masalah dengan cara prosedur rutin, itu dapat diselesaikan dengan mengubahnya menjadi program minimisasi ganda yang memiliki jawaban terkenal dengan bukti dasar. Mungkin dualisasi ini adalah "langkah halus" yang disebutkan dalam pertanyaan. Ketidaksetaraan juga dapat dibangun dengan cara yang murni mekanis dengan memaksimalkanmelalui pengganda Lagrange.|Ti|

Pertama, saya menawarkan solusi yang lebih elegan berdasarkan geometri kuadrat terkecil. Ini tidak memerlukan penyederhanaan awal dan hampir segera, memberikan intuisi langsung ke hasilnya. Seperti yang disarankan dalam pertanyaan, masalahnya berkurang pada ketimpangan Cauchy-Schwarz.


Solusi geometris

Pertimbangkan sebagai vektor dimensi dalam ruang Euclidean dengan produk titik yang biasa. Biarkan menjadi vektor dasar dan . Tulis dan untuk proyeksi ortogonal dari dan ke dalam komplemen ortogonal dari . (Dalam terminologi statistik, mereka adalah residu sehubungan dengan sarana.) Kemudian, karena dann y = ( 0 , 0 , ... , 0 , 1 , 0 , ... , 0 ) i th 1 = ( 1 , 1 , ... , 1 ) x y x y 1 X i - ˉ X =x=(X1,X2,,Xn)ny=(0,0,,0,1,0,,0)ith1=(1,1,,1)x^y^xy1S=| | x | | /XiX¯=x^yS=||x^||/n1 ,

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

adalah komponen dalam arah . Oleh Cauchy-Schwarz, ini dimaksimalkan tepat ketika sejajar dengan , untuk itu QED. x x y =(-1,-1,...,-1,n-1,-1,-1,...,-1)/nTi=±y^x^x^y^=(1,1,,1,n1,1,1,,1)/n

Ti=±n1y^y^||y^||=±n1||y^||=±n1n,

Kebetulan, solusi ini memberikan karakterisasi lengkap dari semua kasus di manadimaksimalkan: mereka semua berbentuk|Ti|

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

untuk semua nyata .μ,σ

Analisis ini digeneralisasikan dengan mudah ke kasus di mana digantikan oleh setiap set regressor. Jelas maksimum sebanding dengan panjang sisa ,.T i y | | y | |{1}Tiy||y^||


Penyederhanaan

Karena adalah invarian di bawah perubahan lokasi dan skala, kami dapat mengasumsikan tanpa kehilangan keumuman bahwa jumlah menjadi nol dan kuadratnya berjumlah . Ini mengidentifikasidengan, karena (mean square) adalah . Memaksimalkan itu sama dengan memaksimalkan . Tidak ada generalisasi yang hilang dengan mengambil , karena dapat ditukar.X i n - 1 | T i | | X i | S 1 | T i | 2 = T 2 i = X 2 i i = 1 X iTiXin1|Ti||Xi|S1|Ti|2=Ti2=Xi2i=1Xi


Solusi melalui formulasi ganda

Masalah ganda adalah untuk memperbaiki nilai dan menanyakan nilai tersisa diperlukan untuk meminimalkan jumlah kuadrat mengingat bahwa . Karena diberikan, ini adalah masalah meminimalkan mengingat bahwa . X j , j 1 n j = 1 X 2 jn j = 1 X j = 0 X 1 n j = 2 X 2 jn j = 2 X j = - X 1X12Xj,j1j=1nXj2j=1nXj=0X1j=2nXj2j=2nXj=X1

Solusinya mudah ditemukan dalam banyak cara. Salah satu yang paling dasar adalah menulis

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

yang . Memperluas fungsi objektif dan menggunakan jumlah-ke-nol identitas ini untuk menyederhanakannya menghasilkanj=2nεj=0

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

segera menampilkan solusi unik adalah untuk semua . Untuk solusi ini,jεj=0j

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

dan

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

QED .


Solusi melalui mesin

Kembali ke program sederhana yang kami mulai dengan:

Maximize X12

tunduk pada

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

Metode pengganda Lagrange (yang hampir murni mekanis dan langsung) menyamakan kombinasi linier nontrivial dari gradien dari ketiga fungsi ini menjadi nol:

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

Komponen demi komponen, persamaan ini adalahn

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

Yang terakhir dari mereka menyiratkan baik atau . (Kami dapat mengesampingkan kasus terakhir karena persamaan pertama menyiratkan , meremehkan kombinasi linear.) Batasan jumlah-ke-nol menghasilkan . Batasan jumlah-dari-kotak menyediakan dua solusiX 2 = X 3 = = X n = - λ 2 / ( 2 λ 3 ) λ 2 = λ 3 = 0 λ 1 = 0 X 1 = - ( n - 1 ) X 2n1X2=X3==Xn=λ2/(2λ3)λ2=λ3=0λ1=0X1=(n1)X2

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

Keduanya menghasilkan

|Ti|=|X1||±n1n|=n1n.
whuber
sumber
Terima kasih atas tambahan Anda, geometri sangat kuat dan dari ketiga solusi itu paling intuitif bagi saya.
JohnK
0

Ketidaksetaraan seperti yang dinyatakan benar. Sangat jelas secara intuitif bahwa kita mendapatkan kasus yang paling sulit untuk ketidaksetaraan (yaitu, memaksimalkan sisi hannd kiri untuk diberikan ) dengan memilih satu nilai, katakanlah sebesar mungkin, sementara semua yang lain sama. Mari kita lihat contoh dengan konfigurasi seperti ini:x 1S2x1

| x i - ˉ x |

n=4,x1=x2=x3=0,x4=4,x¯=1,S2=4,
sekarang tergantung pada , sedangkan batas atas yang diberikan sama dengan yang hanya cukup. Gagasan itu bisa diselesaikan sebagai bukti.|xix¯|S={12 or 32i412=1.5

EDIT

Kami sekarang akan membuktikan klaim, seperti yang ditunjukkan di atas. Pertama, untuk setiap vektor dalam masalah ini, kita dapat menggantinya dengan tanpa mengubah sisi ketidaksamaan di atas. Jadi, berikut ini mari kita asumsikan bahwa . Kita juga dapat dengan relabelling berasumsi bahwa adalah yang terbesar. Kemudian, dengan memilih dan kemudian kita dapat memeriksa dengan aljabar sederhana bahwa kita memiliki kesetaraan dalam ketidaksetaraan yang diklaim. Jadi, itu tajam.x=(x1,x2,,xn)xx¯x¯=0x1x1>0x2=x3==xn=x1n1

Kemudian, tentukan wilayah (cembung) oleh untuk konstanta positif yang diberikan . Perhatikan bahwa adalah persimpangan hyperplane dengan bola yang berpusat di titik asal, begitu juga bola di -ruang. Masalah kita sekarang dapat dirumuskan sebagai sejak suatuR = { x R : ˉ x = 0 , ( x i - ˉ x ) 2 / ( n - 1 ) S 2 } S 2 R ( n - 1 ) maks x R maks i | x i | x R | x 1 |R

R={xR:x¯=0,(xix¯)2/(n1)S2}
S2R(n1)
maxxRmaxi|xi|
xmemaksimalkan itu akan menjadi kasus paling sulit untuk ketidaksetaraan. Ini adalah masalah menemukan maksimum fungsi cembung di atas set cembung, yang secara umum merupakan masalah yang sulit (minimum mudah!). Tapi, dalam hal ini wilayah cembung adalah bola yang berpusat pada titik asal, dan fungsi yang ingin kita maksimalkan adalah nilai absolut dari koordinat. Jelas bahwa maksimum ditemukan di bidang batas , dan dengan mengambilmaksimal, test case pertama kami dipaksa.R|x1|
kjetil b halvorsen
sumber
@JohnK Anda dapat menghapus komentar Anda sekarang, posnya diperbaiki
kjetil b halvorsen
Meskipun jawaban ini menunjukkan bahwa ketidaksetaraan (dengan asumsi itu benar, yang mana) adalah ketat , tidak jelas bagaimana perhitungan tunggal itu bisa "dilengkapi dengan bukti." Bisakah Anda memberikan beberapa indikasi bagaimana itu akan dilakukan?
whuber
Will, tapi besok, sekarang aku harus mempersiapkan kelas besok.
kjetil b halvorsen
Terima kasih - Saya menghargai rumusan masalah Anda yang cermat. Tapi "buktimu" sepertinya sampai pada pernyataan bahwa "sudah jelas itu." Anda selalu dapat menerapkan pengganda Lagrange untuk menyelesaikan pekerjaan, tetapi akan menyenangkan untuk melihat pendekatan yang (a) sebenarnya adalah bukti dan (b) memberikan wawasan.
whuber
2
@whuber Jika Anda punya waktu, saya akan sangat menghargai jika Anda dapat memposting solusi pengganda Lagrange Anda. Saya pikir ketimpangan secara keseluruhan tidak setenar seharusnya.
JohnK