Analiza kulek i pojemników w reżimie

$m$$n$$m \gg n$$X_i$$i$$X_\max$$X_\min$$X_{\mathrm{sec-max}}$$X_i - X_j \sim N(0,2m/n)$$|X_i - X_j| = \Theta(\sqrt{m/n})$ $i,j$$X_{\max} - X_{\min} = O(\sqrt{m\log n/n})$$n/2$ pary rozłącznych pojemników. Ten (nie do końca formalny) argument prowadzi nas do oczekiwania, że ​​różnica między $X_{\max}$ a$X_{\min}$ to $\Theta(\sqrt{m\log n/n})$ z dużym prawdopodobieństwem.

Interesuje mnie różnica między $X_\max$ a $X_{\mathrm{sec-max}}$ . Przedstawiony powyżej argument pokazuje, że $X_\max - X_{\mathrm{sec-max}} = O(\sqrt{m\log n/n})$ z dużym prawdopodobieństwem, ale czynnik $\sqrt{\log n}$ wydaje się obcy . Czy coś wiadomo o dystrybucji $X_\max - X_{\mathrm{sec-max}}$ ?

Mówiąc bardziej ogólnie, załóżmy, że każda piłka jest powiązana z nieujemnym wynikiem dla każdego kosza, a my jesteśmy zainteresowani całkowitym wynikiem każdego kosza po rzuceniu piłek. Zwykły scenariusz odpowiada wynikom formularza . Załóżmy, że rozkład prawdopodobieństwa wyników jest niezmienny w permutacji pojemników (w zwykłym scenariuszu odpowiada to temu, że wszystkie pojemniki są równoważne). Biorąc pod uwagę rozkład wyników, możemy użyć metody z pierwszego akapitu, aby uzyskać dobre wiązanie na . Powiązanie będzie zawierało współczynnik$m$$(0,\ldots,0,1,0,\ldots,0)$$X_{\max} - X_{\min}$$\sqrt{\log n}$ który pochodzi z granicy związku (poprzez prawdopodobieństwa ogona zmiennej normalnej). Czy ten czynnik można zmniejszyć, jeśli jesteśmy zainteresowani ograniczeniem$X_{\max} - X_{\mathrm{sec-max}}$ ?

Odpowiedź: $\Theta\left(\sqrt{\frac{m}{n\log n}}\right)$.

Stosując wielowymiarową wersję centralnego twierdzenia granicznego, otrzymujemy, że wektor $(X_1,\dots, X_n)$ ma asymptotycznie wielowymiarowy rozkład Gaussa z

$$\mathrm{Var}[X_i] = m\left(\frac{1}{n} - \frac{1}{n^2}\right),$$ a $$\mathrm{Cov}(X_i, X_j) = -m/n^2.$$ Zakładamy poniżej, że$X$ jestwektorem Gaussa (i nie tylko w przybliżeniu wektorem Gaussa). Dodajmy losową zmienną Gaussa$Z$o wariancji$m/n^2$do wszystkich$X_i$($Z$jest niezależne od wszystkich$X_i$). To znaczy, niech $$\begin{pmatrix} Y_1\\Y_2\\ \vdots\\Y_n \end{pmatrix} = \begin{pmatrix} X_1+Z\\X_2+Z\\ \vdots\\X_n +Z \end{pmatrix}.$$ Otrzymujemy wektor gaussowski$(Y_1, \dots, Y_n)$. Teraz każde$Y_i$ma wariancję$m/n$: a wszystkieYisą niezależne: Cov(Yi,Yj)=Cov(Xi,Xj)+ C o v ( X i , Z ) + C o v ( X j , Z ) $$\mathrm{Var}[Y_i] = \mathrm{Var}[X_i] + \underbrace{2\mathrm{Cov}(X_i,Z)}_{=\, 0}+\mathrm{Var}[Z] = m/n,$$ $Y_i$ $$\mathrm{Cov}(Y_i, Y_j) = \mathrm{Cov}(X_i, X_j) + \underbrace{\mathrm{Cov}(X_i,Z) + \mathrm{Cov}(X_j,Z)}_{=\, 0} +\mathrm{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 .$Y_i - Y_j = X_i - X_j$$Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}$$Y_i$$1$

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$$\gamma_1,\dots, \gamma_n$$\mu$$1$$\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}$

Odpowiedź: .$\Theta\left(\frac{1}{\sqrt{\log n}}\right)$

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 ) ≈ $\mu = 0$$\bar\Phi(t) = \Pr[\gamma > t]$$\gamma\sim{\cal N}(0,1)$$t$

$$\bar\Phi(t)\approx \frac{1}{\sqrt{2\pi}t} e^{-\frac{1}{2}t^2}.$$

Zauważ, że

• są równomiernie i niezależnie rozmieszczone w [ 0 , 1 ] ,$\Phi(\gamma_i)$$[0,1]$

• jest najmniejszą spośród Φ ( γ i ) ,$\Phi(\gamma_{\mathrm{max}})$$\Phi(\gamma_i)$

• jest drugim najmniejszym spośród Φ ( γ i ) .$\Phi(\gamma_{\mathrm{sec-max})}$$\Phi(\gamma_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 - $\Phi(\gamma_{\mathrm{max}})$$1/n$$\Phi(\gamma_{\mathrm{max}})$$2/n$$\bar\Phi(t)$

$$2\approx \bar\Phi(\gamma_{\mathrm{sec-max}})\left/\bar\Phi(\gamma_{\mathrm{max}})\right. \approx e^{\frac{1}{2}\left(\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2\right)}.$$

Zatem wynosi Θ ( 1 ) whp Zauważ, że γ m a x ≈ γ s e c - m a x = Θ ( $\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2$$\Theta(1)$. Mamy, γ m a x -γ s e c - m a x ≈ Θ ( 1 $\gamma_{\mathrm{max}}\approx \gamma_{\mathrm{sec-max}} = \Theta(\sqrt{\log n})$

$$\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}\approx \frac{\Theta(1)}{\gamma_{\mathrm{max}} + \gamma_{\mathrm{sec-max}}} \approx \frac{\Theta(1)}{\sqrt{\log n}}.$$

CO BYŁO DO OKAZANIA

Otrzymujemy, że

$$\begin{align} \mathbb{E}[{X_{\mathrm{max}} - X_{\mathrm{sec-max}}}] &= \mathbb{E}[{Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}}] \\ &= \sqrt{\mathrm{Var}[Y_i]} \times\mathbb{E}[{\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}}] = \Theta\left(\sqrt{\frac{m}{n\log n}}\right). \end{align}$$

Ten sam argument pojawia się, gdy mamy arbitralne wyniki. Pokazuje, że

$$\mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{sec-max}}] = c\, \left. \mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{min}}]\right/\log n.$$

For your first question, I think you can show that w.h.p. $X_{\max}-X_{\textrm{sec-max}}$ is

$$o\left(\sqrt{\frac{m}{n}\frac{\log^2\log n}{\log n}}\right).$$ Note that this is $o(\sqrt{m/n})$.

Compare your random experiment to the following alternative: Let $X_1$ be the maximum load of any of the first $n/2$ buckets. Let $X_2$ be the maximum load of any of the last $n/2$ buckets.

On consideration, $|X_1-X_2|$ is an upper bound on $X_{\max}-X_{\mathrm{sec-max}}$. Also, with probability at least one half, $|X_1-X_2| = X_{\max}-X_{\mathrm{sec-max}}$. So, speaking roughly, $X_{\max}-X_{\mathrm{sec-max}}$ is distributed similarly to $|X_1-X_2|$.

To study $|X_1-X_2|$, note that with high probability $m/2\pm O(\sqrt m)$ balls are thrown into the first $n/2$ bins, and likewise for the last $n/2$ bins. So $X_1$ and $X_2$ are each distributed essentially like the maximum load when throwing $m' = m/2\pm o(m)$ balls into $n' = n/2$ bins.

This distribution is well-studied and, luckily for this argument, is tightly concentrated around its mean. For example, if $m' \gg n\log^3 n$, then with high probability $X_1$ differs from its expectation by at most the quantity displayed at the top of this answer [Thm. 1]. (Note: this upper bound is, I think, loose, given Yuri's answer.) Thus, with high probability $X_1$ and $X_2$ also differ by at most this much, and so $X_{\max}$ and $X_{\mathrm{max-sec}}$ differ by at most this much.

Conversely, for a (somewhat weaker) lower bound, if, for any $t$, say, $\Pr[|X_1-X_2| \ge t] \ge 3/4$, then $\Pr[X_{\max}-X_{\textrm{sec-max}} \ge t]$ is at least

$$\Pr\big[|X_1-X_2| \ge t ~\wedge~ X_{\max}-X_{\textrm{sec-max}} = |X_1-X_2|\big]$$ which (by the naive union bound) is at least $1 - (1/4) - (1/2) = 1/4.$ I think this should give you (for example) the expectation of $X_{\max}-X_{\textrm{sec-max}}$ within a contant factor.