Odpowiedź: Θ(mnlogn−−−−−√).
Stosując wielowymiarową wersję centralnego twierdzenia granicznego, otrzymujemy, że wektor (X1,…,Xn) ma asymptotycznie wielowymiarowy rozkład Gaussa z
Var[Xi]=m(1n−1n2),
a
Cov(Xi,Xj)=−m/n2.
Zakładamy poniżej, że
X jestwektorem Gaussa (i nie tylko w przybliżeniu wektorem Gaussa). Dodajmy losową zmienną Gaussa
Zo wariancji
m/n2do wszystkich
Xi(
Zjest niezależne od wszystkich
Xi). To znaczy, niech
⎛⎝⎜⎜⎜⎜Y1Y2⋮Yn⎞⎠⎟⎟⎟⎟=⎛⎝⎜⎜⎜⎜X1+ZX2+Z⋮Xn+Z⎞⎠⎟⎟⎟⎟.
Otrzymujemy wektor gaussowski
(Y1,…,Yn). Teraz każde
Yima wariancję
m/n:
a wszystkie
Yisą niezależne:
Cov(Yi,Yj)=Cov(Xi,Xj)+ C o v ( X i , Z ) + C o v ( X j , Z ) ⏟Var[Yi]=Var[Xi]+2Cov(Xi,Z)=0+Var[Z]=m/n,
YiCov(Yi,Yj)=Cov(Xi,Xj)+Cov(Xi,Z)+Cov(Xj,Z)=0+Cov(Z,Z)=0.
Zauważ, że . Zatem nasz pierwotny problem jest równoważny problemowi znalezienia Y m a x - Y s e c - m a x . Niech nam najpierw dla uproszczenia analizy przypadku, gdy wszystkie Y i mają wariancję 1 .Yi−Yj=Xi−XjYmax−Ysec−maxYi1
Problem. Otrzymujemy niezależnego gaussowskiego rv γ 1 , … , γ n ze średnią μ i wariancją 1 . Oszacuj oczekiwanie γ m a x - γ s e c - m a x .nγ1,…,γnμ1γmax−γsec−max
Odpowiedź: .Θ(1logn√)
Nieformalny dowód.
Oto nieformalne rozwiązanie tego problemu (nie jest trudne sformalizowanie go). Ponieważ odpowiedź nie zależy od średniej, zakładamy, że . Niech ˉ Φ ( t ) = Pr [ γ > t ] , gdzie γ ∼ N ( 0 , 1 ) . Mamy (dla umiarkowanie dużego t ),
ˉ Φ ( t ) ≈ 1μ=0Φ¯(t)=Pr[γ>t]γ∼N(0,1)t
Φ¯(t)≈12π−−√te−12t2.
Zauważ, że
są równomiernie i niezależnie rozmieszczone w [ 0 , 1 ] ,Φ(γi)[0,1]
jest najmniejszą spośród Φ ( γ i ) ,Φ(γmax)Φ(γi)
jest drugim najmniejszym spośród Φ ( γ i ) .Φ(γsec−max)Φ(γi)
Zatem jest bliskie 1 / n, a Φ ( γ m a x ) jest bliskie 2 / n (nie ma koncentracji, ale jeśli nie dbamy o stałe, te szacunki są wystarczająco dobre; w rzeczywistości , są nawet całkiem dobre, jeśli zależy nam na stałych - ale to wymaga uzasadnienia). Stosując wzór na ˉ Φ ( t ) , otrzymujemy, że
2 ≈ ˉ Φ ( γ s e c - mΦ(γmax)1/nΦ(γmax)2/nΦ¯(t)
2≈Φ¯(γsec−max)/Φ¯(γmax)≈e12(γ2max−γ2sec−max).
Zatem wynosi Θ ( 1 ) whp Zauważ, że γ m a x ≈ γ s e c - m a x = Θ ( √γ2max−γ2sec−maxΘ(1). Mamy,
γ m a x -γ s e c - m a x ≈ Θ ( 1 )γmax≈γsec−max=Θ(logn−−−−√)
γmax−γsec−max≈Θ(1)γmax+γsec−max≈Θ(1)logn−−−−√.
CO BYŁO DO OKAZANIA
Otrzymujemy, że
E[Xmax−Xsec−max]=E[Ymax−Ysec−max]=Var[Yi]−−−−−−√×E[γmax−γsec−max]=Θ(mnlogn−−−−−−√).
Ten sam argument pojawia się, gdy mamy arbitralne wyniki. Pokazuje, że
E[Xmax−Xsec−max]=cE[Xmax−Xmin]/logn.