17 Nierówności
Przypomnijmy nierówność, która pojawiła się podczas wykładu z Miary i Całki:
Twierdzenie 17.1 (Nierówność H"oldera) Jeżeli \(\mathbb{E}\left[ |X|^p \right] <\infty\) i \(\mathbb{E}\left[ |Y|^q\right] <\infty\) dla \(p,q>1\) takich, że \(1/p+1/q=1\) , to \[ \mathbb{E} \left[ |XY| \right] \le \left( \mathbb{E}\left[ |X|^p \right]\right)^{1/p} \left( \mathbb{E}\left[ |Y|^q\right]\right)^{1/q}. \]
17.1 Nierówność Czebyszewa
W rachunku prawdopodobieństwa częściej używana jest nierówność Czebyszewa, która w najogólniejszej wersji mówi
Twierdzenie 17.2 (Nierówność Czebyszewa) Niech \(X\) będzie zmienną losową i niech \(f:[0,\infty) \mapsto [0,\infty)\) będzie niemalejącą funkcją taką, że \(f(x)>0\) dla każdego \(x>0\). Wtedy dla każdego \(\lambda > 0\) \[ \mathbb{P}[|X|\ge \lambda] \le \frac{\mathbb{E} [f(|X|)]}{f(\lambda)}. \]
Proof. Piszemy \[ \mathbb{P}[|X|\ge \lambda] = \mathbb{E}\left[{\bf 1}_{\{|X|\ge \lambda\}} \right] \le \frac 1{f(\lambda)} \mathbb{E}\left[ f(|X|){\bf 1}_{\{|X|>\lambda\}} \right] \le \frac{\mathbb{E}[ f(|X|)]}{f(\lambda)}. \] □
Zazwyczaj używa się powyższej nierówności w szczególnych przypadkach. Jeżeli zmienna losowa \(X\) jest nieujemna, a \(f(x)=x\), to nierówność przyjmuje klasyczną postać.
Wniosek 17.1 Jeżeli \(X\geq0\), to dla każdej \(\lambda >0\) mamy \[\begin{equation} \mathbb{P}[X \geq \lambda] \leq \frac{\mathbb{E}[X]}{\lambda}. \tag{17.1} \end{equation}\]
Jeżeli natomiast zastąpimy \(X\) przez \(X -\mathbb{E}[X]\) i przyjmiemy \(f(x)=x^2\), to w nierówności Czebyszewa pojawia się wariancja \(X\).
Wniosek 17.2 Jeżeli \(X\) jest całkowalna z kwadratem, to dla każdej \(\lambda>0\) mamy \[\begin{equation} \mathbb{P}\left[ |X-\mathbb{E} [X]|\ge \lambda \right] \le \frac{\mathbb{V}ar[X]}{\lambda^2}. \tag{17.2} \end{equation}\]
Zobaczy teraz jak te dwie nierówności działają w praktyce.
Przykład 17.1 Niech \(n\in \mathbb{N}\). Rozważmy \(n\) rzutów symetryczną monetą. Niech \(X\) będzie liczbą otrzymanych orłów. Chcemy oszacować prawdopodobieństwo, że \(X\) wynosi co najmniej \(3n/4\). Aby zastosować nierówność (17.1) przypomnijmy, że \(\mathbb{E}[X]=n/2\). Rzeczywiście, \(X = \sum_{j=1}^n X_j\), gdzie \(X_j\in \{0,1\}\) i \(X_j=1\) wtedy i tylko wtedy, gdy w \(j\)-tym rzucie wypadł orzeł. Wówczas \[\begin{equation*} \mathbb{P}[X_j=1] = \mathbb{P}[X_j=1]=1/2. \end{equation*}\] Stąd \(\mathbb{E}[X_j]=1/2\) a co za tym idzie \(\mathbb{E}[X]=n/2\). Stosując nierówność (17.1) otrzymujemy \[\begin{equation*} \mathbb{P}[X> 3n/4] \leq \frac{4}{3n}\mathbb{E}[X] = \frac 23. \end{equation*}\] Aby porównać to z nierównością (17.2) przypomnijmy jeszcze, że \(\mathbb{V}ar[X]=n/4\). Skoro \[\begin{equation*} \mathbb{V}ar[X_j]=\mathbb{E}\left[X_j^2\right] - \mathbb{E}[X_j]^2 = \frac 12 -\frac 14 = \frac 14. \end{equation*}\] Skoro zmienne \(\{X_j\}_j\) są niezależne, to \[\begin{equation*} \mathbb{V}ar[X] = \sum_{j=1}^n \mathbb{V}ar[X_j] = n/4. \end{equation*}\] Wracając do nierówności (17.2) otrzymujemy \[\begin{align*} \mathbb{P}[X>3n/4] & = \mathbb{P}[X - \mathbb{E}[X]> n/4] \\ & \leq \mathbb{P}[|X - \mathbb{E}[X]|> n/4] \leq \frac{4}{n}. \end{align*}\]
17.2 Nierówność Chernoffa
Przy analizie ostatniego przykładu pojawia się naturalne pytanie o to, czy można otrzymać lepsze szacowania.
Definicja 17.1 Funkcją generująca momenty zmiennej losowej \(X\) nazywamy \(M_X \colon \mathbb{R} \to (0, +\infty]\) zadaną przez \[\begin{equation*} M_X(\beta) = \mathbb{E} \left[ e^{\beta X} \right]. \end{equation*}\]
Zanim przejdziemy do zastosowań \(M_X\) wyjaśnimy jej nazwę. Dla \(n\in \mathbb{N}\), \(n\)-tym momentem zmiennej losowej \(X\) nazywamy \(\mathbb{E}\left[X^n\right]\). Załóżmy, że dla pewnej dodatniej \(\beta_0\), \(M_X(\beta_0)\), \(M_X(-\beta_0)<\infty\). Wówczas \[\begin{equation*} \mathbb{E}\left[e^{\beta_0|X|} \right] \leq \mathbb{E}\left[e^{\beta_0X} + e^{-\beta_0X} \right]<\infty. \end{equation*}\] Dla \(h<\beta_0/2\) mamy \[\begin{equation*} \left| \frac{e^{hX}-1}{h} \right| \leq |X| e^{hX} \leq C e^{2h|X|} \leq C e^{\beta_0|X|}. \end{equation*}\] Skoro \[\begin{equation*} \frac{M_X(h) - 1}{h} = \mathbb{E}\left[ \frac{e^{hX}-1}{h} \right] \end{equation*}\] to korzystając z twierdzenia o zbieżności ograniczonej \[\begin{equation*} M_X'(0) = \mathbb{E}[X]. \end{equation*}\] Rozumując analogicznie pokazujemy, że jeżeli \(M_X(\beta_0)\), \(M_X(-\beta_0)<\infty\) to dla każdego \(n \in \mathbb{N}\), \[\begin{equation*} M^{(n)}_X(0) = \mathbb{E}\left[X^n \right]. \end{equation*}\] Stąd, dla \(|\beta|<\beta_0\), \[\begin{equation*} M_X(\beta) = \sum_{j=0}^\infty \frac{\beta^n}{j!}\mathbb{E}\left[X^n \right]. \end{equation*}\]
Przykład 17.2 Rozważmy \(X\) o rozkładzie \(\mathrm{Exp}(\alpha)\) dla \(\alpha>0\). Dla \(\beta<\alpha\), \[\begin{equation*} M_X(\beta) = \int_0^\infty \alpha e^{-\alpha x} e^{\beta x} \mathrm{d}x = \frac{\alpha}{\alpha-\beta} \end{equation*}\] oraz \(M_X(\beta) = \infty\) dla \(\beta \geq \alpha\). Wykres \(M_X\) dla \(\alpha=3\) wygląda następująco.
Widzimy, że dla \(n\in \mathbb{N}\), \[\begin{equation*} M_X^{(n)}(\beta) =\alpha n!(\alpha-\beta)^{-n-1} \end{equation*}\] a co za tym idzie \[\begin{equation*} \mathbb{E}\left[X^n \right]= M_X^{(n)}(0) = \frac{n!}{\alpha^n}. \end{equation*}\]
Wykorzystując funkcję tworzącą momenty możemy wyciągnąć jeszcze jeden wniosek z nierówności Czebyszewa.
Wniosek 17.3 (Nierówność Chernoffa) Dla dowolnej \(\lambda \geq 0\), \[\begin{equation*} \mathbb{P}\left[X \geq \lambda \right] \leq \inf_{\beta >0} e^{-\lambda \beta}M_X(\beta). \end{equation*}\]
Proof. Ustalmy dowolną \(\beta>0\). Dla \(f(x) = e^{x\beta}\) mamy \[\begin{equation*} \mathbb{P}[X\geq \lambda ]\leq e^{-\lambda \beta}\mathbb{E}\left[e^{\beta X} \right] = e^{-\lambda \beta}M_X(\beta). \end{equation*}\] Teza wynika teraz przez rozważenie kresu dolnego dla \(\beta>0\). □
Przykład 17.3 Wróćmy jeszcze raz do prawdopodobieństwa wyrzucenia więcej niż \(3n/4\) orłów przy \(n\) rzutach symetryczną monetą. Przypomnijmy, że liczba otrzymanych orłów \(X\) zapisuje się jako \(X = \sum_{j=1}^nX_j\), gdzie zmienne \(\{X_j\}_j\) są niezależne i \[\begin{equation*} \mathbb{P}\left[X_j=0 \right] = \mathbb{P}\left[X_j=1 \right] = 1/2. \end{equation*}\] Stąd \[\begin{equation*} M_X(\beta) = \mathbb{E} \left[e^{\beta X_1}e^{\beta X_2}\cdots e^{\beta X_n} \right] = M_{X_1}(\beta)^n. \end{equation*}\] Mamy \[\begin{equation*} M_{X_1}(\beta) = \frac{e^{\beta} +1}{2}. \end{equation*}\]
Różniczkując funkcję pod kresem sprawdzamy, że minimum jest przyjęte dla \(\beta = \log(3)\). Stąd \[\begin{equation*} \mathbb{P}[X \geq 3n/4] \leq (0.88)^n \end{equation*}\]
Przykład 17.4
Zauważmy, że rozumowanie z poprzedniego przykładu możemy zastosować do subtelniejszych szacowań. Dla \(\epsilon>0\) mamy \[\begin{equation*} \mathbb{P}[X \geq (1/2+\epsilon)n] \leq = \left( \inf_{\beta>0} e^{-\beta \epsilon} \frac{e^{\beta/2} +e^{-\beta/2}}{2} \right)^n \end{equation*}\] Tym razem wyrażenie pod kresem jest trochę mniej zachęcające. Dla \(\epsilon=0.1\) wykres wygląda następująco.
Widzimy, że im mniejszy \(\epsilon\) tym punkt realizujący minimum jest bliżej zera. Zauważmy, że \[\begin{equation*} \frac{\mathrm{d}}{\mathrm{d}\beta} \left.e^{-\beta \epsilon} \frac{e^{\beta/2} +e^{-\beta/2}}{2} \right|_{\beta=0} = -\epsilon<0. \end{equation*}\] Stąd \[\begin{equation*} \inf_{\beta>0} e^{-\beta \epsilon} \frac{e^{\beta/2} +e^{-\beta/2}}{2} =\gamma_\epsilon<1. \end{equation*}\] Czyli \[\begin{equation*} \mathbb{P}[X\geq (1/2+\epsilon)n]\leq \gamma_\epsilon^n. \end{equation*}\] Przez symetrię (zamieniając orły na reszki) \[\begin{equation*} \mathbb{P}[X\leq (1/2-\epsilon)n]\leq \gamma_\epsilon^n. \end{equation*}\] Stąd \[\begin{equation*} \mathbb{P}[|X/n -1/2|\geq \epsilon]\leq 2\gamma_\epsilon^n. \end{equation*}\]