الرياضيات الجامعية — السنة 2 · Bachelor Year 2

22المتغيرات العشوائية المتقطعة

تنظم المتغيرات العشوائية الحسابات الاحتمالية حول الدوال بدل الأحداث. وعلى الفضاءات القابلة للعد، تشغّل النظريةَ العائلاتُ القابلة للجمع في الفصل 7: فالأمل الرياضي مجموع عائلة مفهرسة بالفضاء العيني، وجميع خواصه — الخطية، والنقل، وصيغة الجداء من أجل المتغيرات المستقلة — مبرهنات عن العائلات القابلة للجمع. ويبرهن الفصل على المتراجحات المفتاحية لماركوف وتشيبيشيف وكوشي–شوارتز وجنسن، وينتهي بالقوانين الكلاسيكية وبالقانون الضعيف للأعداد الكبيرة، الذي يصير برهانه سطرين بمجرد توفر متراجحة تشيبيشيف.

22.1 المتغيرات العشوائية وقوانينها

تعريف 22.1 (المتغير العشوائي المتقطع؛ القانون)

ليكن $(\Omega, \P)$ فضاء احتماليا قابلا للعد. المتغير العشوائي هو تطبيق $X \colon \Omega \to E$ (حيث $E$ مجموعة كيفما كانت؛ ونقول متغيرا عشوائيا حقيقيا عندما $E = \R$ ). وقانونه (أو توزيعه) هو القياس الاحتمالي $\P_X$ على المجموعة القابلة للعد $X(\Omega)$ المعرَّف بالعلاقة

\P_X(\{x\}) = \P(X = x) = \P\bigl(\{\omega : X(\omega) = x\}\bigr) .

مثال 22.2 (القوانين الكلاسيكية)

برنولي $\mathcal{B}(p)$ : $X \in \{0, 1\}$ ، $\P(X = 1) = p$ . وهو الدالة المميزة لحدث.
ثنائي الحد $\mathcal{B}(n, p)$ : $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ ، $0 \leq k \leq n$ : أي عدد النجاحات في $n$ تجربة برنولي مستقلة (مجلد الثانوية؛ ويُعاد البرهان عليه أدناه عبر مجاميع المتغيرات المستقلة).
الهندسي $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ ، $k \in \N^*$ : أي رتبة أول نجاح (المثال 21.5).
بواسون $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ ، $k \in \N$ — وهو قياس احتمالي بحكم المتسلسلة الأسية. وهو قانون الأحداث النادرة (الفصل 23).

ملاحظة 22.3 (أي قانون ينمذج ماذا)

تجيب القوانين الأربعة عن أربعة أسئلة أولية: برنولي، “هل وقع؟”؛ وثنائي الحد، “كم مرة في $n$ محاولة؟”؛ والهندسي، “كم يطول الانتظار حتى المرة الأولى؟”؛ وبواسون، “كم حدثا عند معدل معطى، عندما تكون المحاولات كثيرة وكل منها غير مرجح؟”. والتعرف على السؤال تسعة أعشار النمذجة: فمجاميع الدوال المميزة تشير إلى ثنائي الحد، وأزمنة الانتظار إلى الهندسي، وعدود الأحداث النادرة إلى بواسون — مع جعل المرور من ثنائي الحد إلى بواسون دقيقا بقانون الأحداث النادرة في الفصل 23.

قضية 22.4 (انعدام ذاكرة القانون الهندسي)

إذا كان $X \sim \mathcal{G}(p)$ ، فإن من أجل كل $m, n \in \N$ :

\P(X > m + n \mid X > m) = \P(X > n) ,

والقوانين الهندسية هي القوانين الوحيدة على $\N^*$ التي لها هذه الخاصية.

برهان. بجمع الأوزان الهندسية، $\P(X > n) = (1-p)^n$ . ومنه

\P(X > m + n \mid X > m) = \frac{\P(X > m + n)}{\P(X > m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = \P(X > n).

وبالعكس، إذا حقق $G(n) = \P(X > n)$ العلاقة $G(m + n) = G(m)G(n)$ مع $G(0) = 1$ ، فإن $G(n) = G(1)^n$ بالتراجع؛ و $q = G(1) \in \intco{0}{1}$ ، ويكون $q = 0$ أو يكون القانون $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

مثال 22.5 (لا رقم “مستحق” أبدا)

نرمي نردا انتظارا لستة: فزمن الانتظار $X \sim \mathcal G(1/6)$ . ويقول انعدام الذاكرة إنه بعد $10$ رمية بلا جدوى، يكون الانتظار المتبقي $X - 10$ ، علما بالحدث $X > 10$ ، هو $\mathcal G(1/6)$ من جديد: فالانتظار المتوقع شرطيا لا يزال $6$ رمية، تماما كما في البداية. فالنرد لا يتذكر، ولا “تستحق” أي ستة الظهور أبدا — ومغالطة المقامر هي الاعتقاد بأن القانون الشرطي كان ينبغي أن ينزاح. وبالعكس، يقول شق الوحدانية من القضية إن هذه اللامبالاة تميّز أزمنة الانتظار الهندسية: فكل زمن انتظار لا يتحدث تنبؤه أبدا يكون هندسيا. أما الطوابير والأعمار الحقيقية فعادة ما تتحدث، وهذا بالضبط كيف نكتشف أنها ليست هندسية.

22.2 الأمل الرياضي

تعريف 22.6 (الأمل الرياضي)

نقول إن متغيرا عشوائيا حقيقيا $X$ على $(\Omega, \P)$ يقبل أملا رياضيا إذا كانت العائلة $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ قابلة للجمع (الفصل 7)؛ وعندئذ يكون أمله الرياضي

\E(X) = \sum_{\omega \in \Omega} X(\omega)\,\P(\{\omega\}) .

مبرهنة 22.7 (مبرهنة النقل)

يقبل $X$ أملا رياضيا إذا وفقط إذا كانت العائلة $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ قابلة للجمع، وعندئذ

\E(X) = \sum_{x \in X(\Omega)} x\,\P(X = x) .

وبوجه أعم، من أجل $f \colon X(\Omega) \to \R$ ، يقبل المتغير $f(X)$ أملا رياضيا إذا وفقط إذا كان $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ ، وعندئذ $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

برهان. نجزّئ $\Omega$ إلى مجموعات المستوى $\Omega_x = \{X = x\}$ ، $x \in X(\Omega)$ . وبمبرهنة الجمع بالرزم من أجل العائلات القابلة للجمع (الفصل 7)، تكون العائلة $(X(\omega)\P(\{\omega\}))_\omega$ قابلة للجمع إذا وفقط إذا كانت كل رزمة كذلك (وهو تلقائي: $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) وكانت عائلة مجاميع الرزم $\bigl(x\,\P(X = x)\bigr)_x$ قابلة للجمع — وعندئذ يتطابق المجموعان الكليان. ومن أجل $f(X)$ : نطبق النص المبرهن على المتغير $Y = f \circ X$ ، الذي مجموعات مستواه $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ ؛ ويحوّل جمع بالرزم ثان المقدار $\sum_y y\,\P(Y = y)$ إلى $\sum_x f(x)\,\P(X = x)$ ، إذ ترزم الرزم الآن القيم $x$ بحسب صورتها $f(x)$ ، مع تكافؤ القابلية للجمع المطلقة لإحدى العائلتين مع القابلية للجمع المطلقة للأخرى. ∎

مبرهنة 22.8 (خواص الأمل الرياضي)

على مجموعة المتغيرات العشوائية التي تقبل أملا رياضيا:

(الخطية) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(الموجبية والرتابة) $X \geq 0 \Rightarrow \E(X) \geq 0$ ؛ $X \leq Y \Rightarrow \E(X) \leq \E(Y)$ ؛ و $\abs{\E(X)} \leq \E(\abs X)$ .
(الهيمنة) إذا كان $\abs X \leq Z$ وكان $Z$ يقبل أملا رياضيا، فكذلك $X$ .

برهان. كلها خواص لمجاميع العائلات القابلة للجمع (الفصل 7): خطية المجموع، والموجبية حدا حدا، ومحك الهيمنة من أجل القابلية للجمع. (ولاحظ أن الخطية فورية على التعريف على $\Omega$ ، بينما كانت ستكون محرجة على صيغة النقل — وهي إحدى فوائد تعريف $\E$ في الأعلى.) ∎

مثال 22.9

$X \sim \mathcal{B}(n, p)$ : بكتابة $X = X_1 + \dots + X_n$ مجموعا لدوال برنولي المميزة وباستعمال الخطية، $\E(X) = np$ — دون حاجة إلى أي معاملات ثنائية الحد. $X \sim \mathcal{G}(p)$ : $\E(X) = \sum_{k\geq1}k(1-p)^{k-1}p = p\cdot\frac{1}{(1 - (1-p))^2} = \frac1p$ ، بمفاضلة المتسلسلة الهندسية داخل قرصها (الفصل 11). $X \sim \mathcal{P}(\lambda)$ : $\E(X) = \sum_{k\geq1}k e^{-\lambda}\frac{\lambda^k}{k!} = \lambda e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda$ .

مثال 22.10 (النقل في العمل)

من أجل $X \sim \mathcal P(\lambda)$ ، احسب $\E\bigl(\frac1{1+X}\bigr)$ — فقانون $\frac1{1+X}$ نفسه محرج، لكن مبرهنة النقل لا تطلبه أبدا:

\E\Bigl(\frac1{1+X}\Bigr) = \sum_{k\geq0}\frac{1}{k+1}\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \frac{\eu^{-\lambda}}{\lambda}\sum_{k\geq0} \frac{\lambda^{k+1}}{(k+1)!} = \frac{\eu^{-\lambda}}{\lambda}\bigl(\eu^\lambda - 1\bigr) = \frac{1 - \eu^{-\lambda}}{\lambda} .

ودرسان. حسابيا: التعرف على متسلسلة أسية مزاحة هو العمل كله — فمبرهنة النقل تختزل آمال $f(X)$ إلى معالجة متسلسلات. وبنيويا: القيمة الساذجة بالتعويض ستكون $\frac1{1 + \E X} = \frac1{1 + \lambda}$ ، والجواب الحقيقي أكبر،

\frac{1 - \eu^{-\lambda}}{\lambda} \geq \frac{1}{1 + \lambda},

تماما كما تقتضي متراجحة جنسن من أجل الدالة المحدبة $t \mapsto \frac1{1+t}$ . فآمال الصور المحدبة تقع فوق القيمة الساذجة بالتعويض، وتجعل مبرهنة النقل مع تحقق من متسلسلة المتراجحة المجردة ملموسة.

مبرهنة 22.11 (الاستقلال والجداءات)

يكون المتغيران العشوائيان $X, Y$ مستقلين إذا كان $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ من أجل كل $x, y$ — وبصورة مكافئة، إذا كان الحدثان $\{X \in A\}$ و $\{Y \in B\}$ مستقلين من أجل كل $A, B$ . وإذا كان $X$ و $Y$ متغيرين حقيقيين مستقلين يقبلان أملا رياضيا، فإن $XY$ يقبل أملا رياضيا و

\E(XY) = \E(X)\,\E(Y) .

برهان. ينتج تكافؤ الصياغتين بالجمع النقطي للمتطابقة على $(x, y) \in A \times B$ (بالجمعية $\sigma$ مرتين). أما الجداء: فالعائلة المزدوجة $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ قابلة للجمع، لأنه بحسب مبرهنة فوبيني من أجل العائلات (الفصل 7)

\sum_{x, y}\abs x \abs y\,\P(X{=}x)\P(Y{=}y) = \Bigl(\sum_x \abs x \P(X{=}x)\Bigr) \Bigl(\sum_y \abs y \P(Y{=}y)\Bigr) < \infty ;

وبالاستقلال تكون هذه العائلة بالضبط $\bigl(xy\,\P(X = x, Y = y)\bigr)$ ، ومجموعها $\E(XY)$ بمبرهنة النقل مطبقة على المتغير $(X, Y) \mapsto xy$ ؛ وتقوّم مبرهنة فوبيني من جديد المجموع غير الموقّع بالجداء $\E(X)\E(Y)$ . ∎

مثال 22.12 (الجداءات، مع الاستقلال وبدونه)

نرمي نردين متزنين. فإذا كان $Y$ هو النرد الثاني (المستقل عن الأول)، فإن $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . أما إذا كان $Y = X$ (أي “جداء” نرد بنفسه)،

\E(X^2) = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6} \approx 15.17 \neq 12.25 :

فالقانونان الحديان أنفسهما في السيناريوهين، لكن القانونين المشتركين مختلفان، وآملا الجداء مختلفان. والعبرة، وهي جديرة بأن تُنقش: أن $\E(XY)$ دالة تخص الزوج، لا القانونين الحديين — والفرق $\E(X^2) - \E(X)^2 \approx 2.92$ هو بالضبط، بحسب كونيغ–هويغنز، تباين $\frac{35}{12}$ النرد.

22.3 التباين والتغاير والمتراجحات الكلاسيكية

تعريف 22.13 (العزوم والتباين)

نقول إن $X$ يقبل عزما من الرتبة 2 إذا كان $X^2$ يقبل أملا رياضيا (وعندئذ يقبله $X$ أيضا، بالهيمنة: $\abs X \leq \frac{1 + X^2}{2}$ ). وعندئذ يكون تباينه وانحرافه المعياري

V(X) = \E\bigl((X - \E(X))^2\bigr) = \E(X^2) - \E(X)^2 , \qquad \sigma(X) = \sqrt{V(X)} ,

(والصيغة الثانية — وهي صيغة كونيغ–هويغنز — بنشر المربع واستعمال الخطية:

\E\bigl((X - \E X)^2\bigr) = \E\bigl(X^2 - 2X\,\E X + \E(X)^2\bigr) = \E(X^2) - 2\,\E(X)^2 + \E(X)^2 ,

مع كون الحد الأوسط ناتجا عن كون $\E X$ ثابتا). ومن أجل $X, Y$ ذوي عزوم من الرتبة الثانية، يكون التغاير

\operatorname{Cov}(X, Y) = \E\bigl((X - \E X)(Y - \E Y)\bigr) = \E(XY) - \E(X)\E(Y) .

مبرهنة 22.14 (عدة التباين)

من أجل المتغيرات ذات العزوم من الرتبة الثانية:

$V(aX + b) = a^2\,V(X)$ ؛
$V(X + Y) = V(X) + V(Y) + 2\operatorname{Cov}(X, Y)$ ، وبوجه أعم

$V\Bigl(\sum_{i=1}^n X_i\Bigr) = \sum_{i=1}^n V(X_i) + 2\sum_{i < j}\operatorname{Cov}(X_i, X_j) ;$
إذا كان $X, Y$ مستقلين، فإن $\operatorname{Cov}(X, Y) = 0$ (والعكس غير صحيح)، ومنه فإن تباينات المتغيرات المستقلة تُجمع.

برهان. البندان 1 و2 نشران لمربعات مع الخطية؛ وللجداءات $X_iX_j$ آمال رياضية بحكم متراجحة كوشي–شوارتز أدناه (أو بحكم $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). والبند 3 هو المبرهنة 22.11 مطبقا على المتغيرين المركزيين. ومثال مضاد قياسي للعكس: $X$ منتظم على $\{-1, 0, 1\}$ و $Y = X^2$ غير مترابطين ( $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ) لكنهما متعلقان بوضوح. ∎

مبرهنة 22.15 (متراجحتا ماركوف وتشيبيشيف)

(ماركوف) إذا كان $X \geq 0$ يقبل أملا رياضيا، فإن من أجل كل $a > 0$ :

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(تشيبيشيف) إذا كان $X$ يقبل عزما من الرتبة الثانية، فإن من أجل كل $\varepsilon > 0$ :

$\P\bigl(\abs{X - \E(X)} \geq \varepsilon\bigr) \leq \frac{V(X)}{\varepsilon^2} .$

برهان. 1. نقطيا، $a\,\mathbf{1}_{X \geq a} \leq X$ (فعلى الحدث يكون الطرف الأيسر $a \leq X$ ؛ وخارجه $0 \leq X$ ). وبأخذ الآمال: $a\,\P(X \geq a) \leq \E(X)$ بالرتابة و $\E(\mathbf{1}_A) = \P(A)$ . 2. نطبق متراجحة ماركوف على المتغير الموجب $(X - \E X)^2$ عند المستوى $a = \varepsilon^2$ : فالحدث $\{(X - \E X)^2 \geq \varepsilon^2\}$ هو بالضبط $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

مثال 22.16 (غير مترابطين لكن ملتصقين)

نرمي نردين متزنين، $X$ و $Y$ مستقلين، ونضع $S = X + Y$ ، $D = X - Y$ . وبثنائية خطية التغاير،

\operatorname{Cov}(S, D) = V(X) - V(Y) + \operatorname{Cov}(Y, X) - \operatorname{Cov}(X, Y) = V(X) - V(Y) = 0 :

فالمجموع والفرق غير مترابطين. فهل هما مستقلان؟ قطعا لا: إذ يفرض $S = 12$ أن $D = 0$ ، بينما $\P(D = 0) = \frac16$ دون شرط. فالترابط لا يختبر إلا الجزء الخطي من التعلق؛ وهنا يحمل التعلقَ القيدُ القائل إن $S$ و $D$ لهما الزوجية نفسها، وهو غير مرئي للتغاير. (ومن أجل هذا الزوج، احتاج انعدام التغاير إلى $V(X) = V(Y)$ : فالتوزيعان المتطابقان، لا الاستقلال، هما اللذان أنجزا العمل.)

مثال 22.17 (متى تكون متراجحة ماركوف مساواة)

تكون متراجحة ماركوف مساواة بالضبط عندما لا يُهدر شيء في الحصر $a\,\mathbf 1_{X\geq a} \leq X$ : أي عندما لا يأخذ المتغير إلا القيمتين $0$ و $a$ . وبصورة ملموسة، إذا كان $\P(X = a) = \pi$ و $\P(X = 0) = 1 - \pi$ ، فإن $\E(X) = a\pi$ و

\P(X \geq a) = \pi = \frac{\E(X)}{a} .

وقراءة واقعية: ففي مجتمع متوسط الثروة فيه $100$ والثروة إما $0$ وإما $10^6$ ، تكون نسبة أصحاب الملايين هي $10^{-4}$ بالضبط — أي حصر ماركوف، مبلوغا بالضبط بمتراجحة قصوى. وكلما انتشر $X$ على قيم وسيطة كان الحصر تاما، وغالبا بفارق هائل؛ لكن كما تبين الحالة الحدية، لا يمكن استخراج متراجحة أفضل من المتوسط وحده.

مثال 22.18 (متراجحة تشيبيشيف أمثلية — دون فرضيات إضافية)

نثبّت $\varepsilon > 0$ ، $q \in \intoc01$ ، ونجعل $X$ يأخذ القيمتين $\pm\varepsilon$ باحتمال $\frac q2$ لكل منهما و $0$ باحتمال $1 - q$ . عندئذ $\E(X) = 0$ ، $V(X) = q\varepsilon^2$ ، و

\P\bigl(\abs{X - \E X} \geq \varepsilon\bigr) = q = \frac{V(X)}{\varepsilon^2} :

أي التساوي في متراجحة تشيبيشيف. ومنه فلا يمكن تحسين المتراجحة باستعمال التباين وحده — فالتلاشي $1/\varepsilon^2$ هو الثمن المضبوط لمعلومة العزم من الرتبة الثانية. أما التلاشي الأسرع فيتطلب فرضيات أقوى: فحصر المتغير يشتري تركيزا أسيا، كما يستعرض التمرين 22.7 وكما تطوره مسألة نهاية الأسبوع لهذا الفصل منهجيا.

مبرهنة 22.19 (كوشي–شوارتز وجنسن)

(كوشي–شوارتز) إذا كان للمتغيرين $X, Y$ عزمان من الرتبة الثانية، فإن $XY$ يقبل أملا رياضيا و $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ؛ ومنه $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
(جنسن) إذا كانت $\varphi \colon I \to \R$ محدبة على فترة تحوي $X(\Omega)$ ، وكان $X$ و $\varphi(X)$ يقبلان أملين رياضيين، فإن

$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$

برهان. 1. قابلية جمع $XY$ : $\abs{XY} \leq \frac{X^2 + Y^2}2$ . والتطبيق $(X, Y) \mapsto \E(XY)$ صورة ثنائية الخطية متناظرة موجبة على فضاء المتغيرات ذات العزوم من الرتبة الثانية، ومنه تنطبق متراجحة كوشي–شوارتز المجردة في الفصل 12 (فالصورة شبه المعرَّفة الموجبة تكفي من أجل المتراجحة). وتطبيقها على المتغيرين المركزيين يعطي حصر التغاير.

2. أولا، يقع $m = \E(X)$ في $I$ : فالفترة $I$ تحوي جميع قيم $X$ ، والأمل الرياضي رتيب، ومنه فإن $m$ بين $\inf X(\Omega)$ و $\sup X(\Omega)$ . وبمبرهنة المستقيم المساند من أجل الدوال المحدبة (الفصل 8)، يوجد $\alpha, \beta$ يحقق $\varphi(t) \geq \alpha t + \beta$ من أجل كل $t \in I$ و $\varphi(m) = \alpha m + \beta$ . وعندئذ، نقطيا على $\Omega$ ، $\varphi(X) \geq \alpha X + \beta$ ؛ وبأخذ الآمال،

\E\bigl(\varphi(X)\bigr) \geq \alpha\,\E(X) + \beta = \varphi\bigl(\E(X)\bigr). \qedhere

∎

مثال 22.20

تعطي متراجحة جنسن مع $\varphi(t) = t^2$ المقدار $\E(X)^2 \leq \E(X^2)$ — أي موجبية التباين؛ ومع $\varphi(t) = 1/t$ على $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ — أي إن المتوسط التوافقي دون المتوسط الحسابي، في صيغة عشوائية الآن.

ملاحظة 22.21 (مزالق شائعة)

(1) $\E(XY) = \E(X)\E(Y)$ يقتضي الاستقلال (أو على الأقل انعدام التغاير): فأخذ $Y = X$ يعطي $\E(X^2) \neq \E(X)^2$ كلما كان $V(X) > 0$ . (2) وبالمثل $V(X + X) = 4V(X)$ ، لا $2V(X)$ : فالتباينات لا تُجمع إلا على الحدود المستقلة (أو غير المترابطة). (3) وليس $\E(f(X))$ هو $f(\E(X))$ ؛ ومن أجل $f$ محدبة تخبرك متراجحة جنسن حتى باتجاه الخطأ، كما في المثال 22.10. (4) والوجود فرضية حقيقية: فمن أجل متغير سان بطرسبورغ $X = 2^K$ مع $\P(K = k) = 2^{-k}$ ( $k \geq 1$ )،

\sum_{k\geq1}2^k\cdot2^{-k} = \sum_{k\geq1}1 = \infty :

يكون $X$ منتهيا بشكل شبه أكيد ومع ذلك لا يقبل أملا رياضيا، ولا يوجد ثمن دخول عادل للعبة. فالقابلية للجمع في تعريف $\E$ ليست تنطعا في مسك الحسابات — بل هي حيث تُكتشف الذيول الثقيلة. (5) وأخيرا، تحتاج مبرهنة النقل إلى القابلية للجمع المطلقة قبل أن تكون أي إعادة ترتيب للمجموع على القيم مشروعة (الفصل 7).

مثال 22.22 (تشيبيشيف على مائة رمية)

من أجل $X \sim \mathcal B(100, \frac12)$ : $\E X = 50$ ، $V(X) = 25$ . وتشيبيشيف مع $\varepsilon = 6$ :

\P(45 \leq X \leq 55) = \P(\abs{X - 50} < 6) \geq 1 - \frac{25}{36} \approx 0.31 ,

بينما يعطي المجموع الثنائي المضبوط $\approx 0.73$ . فالمقدار المضمون $31\%$ بعيد عن الحقيقة، لكنه لم يتطلب إلا المتوسط والتباين — فالشهادة نفسها تنطبق حرفيا على أي متغير له $\E = 50$ و $V = 25$ ، مهما يكن غريبا، ويبين المثال 22.18 أن متغيرا من هذا النوع يشبعها. فللشمولية ثمن؛ وعندما يكون التوزيع ثنائي الحد فعلا، تغلق الأدوات الأسية في مسألة نهاية الأسبوع معظم الفجوة.

مثال 22.23 (ترابط الجزء مع الكل)

من أجل متغيرات $X, Y$ مستقلة ومتماثلة التوزيع تباينها $\sigma^2 > 0$ ، ما مقدار ترابط أحد الحدود مع المجموع $S = X + Y$ ؟ نحسب

\operatorname{Cov}(X, S) = \operatorname{Cov}(X, X) + \operatorname{Cov}(X, Y) = \sigma^2 + 0 = \sigma^2, \qquad V(S) = 2\sigma^2,

ومنه فإن معامل الترابط هو

\rho(X, S) = \frac{\operatorname{Cov}(X, S)}{\sigma(X)\,\sigma(S)} = \frac{\sigma^2}{\sigma\cdot\sigma\sqrt2} = \frac{1}{\sqrt2} \approx 0.707 ,

مهما يكن القانون المشترك — نردا أو قطعة نقود أو عدود بواسون. ومع $n$ حدا يعطي الحساب نفسه $\rho(X_1, S_n) = 1/\sqrt n$ : فتأثير كل حد مفرد على المجموع يتخفف كجذر تربيعي، وهو الظل الترابطي للسلّم $\sqrt n$ للتقلبات. وتضمن متراجحة كوشي–شوارتز $\abs\rho \leq 1$ دائما؛ وهنا يُبلغ الحصر بالضبط في الحالة المنحلة $n = 1$ ويتلاشى على نحو متوقع بعدها.

مثال 22.24 (متراجحة المتوسطين الموزونة من جنسن)

ليكن $Y$ يأخذ القيم الموجبة $a_1, \dots, a_k$ بالاحتمالات $\lambda_1, \dots, \lambda_k$ . والدالة $-\ln$ محدبة على $\intoo0\infty$ ، ومنه تعطي متراجحة جنسن $-\ln\E(Y) \leq \E(-\ln Y)$ ، أي

a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_k^{\lambda_k} \;\leq\; \lambda_1a_1 + \lambda_2a_2 + \dots + \lambda_ka_k :

وهي متراجحة المتوسطين الحسابي والهندسي الموزونة، مع التساوي إذا وفقط إذا كان $Y$ ثابتا. والأوزان المتساوية $\lambda_i = \frac1k$ تستعيد متراجحة المتوسطين الكلاسيكية. وهكذا برهنت الاحتمالات بصمت على مبرهنة جبرية محضة: فاختيار قانون احتمال ليس إلا أداة لمسك حسابات التوليفات المحدبة — أي وجهة نظر مراكز الثقل في الفصل 17 مرة أخرى، مع جنسن محركا هذه المرة.

22.4 القانون الضعيف للأعداد الكبيرة

مبرهنة 22.25 (القانون الضعيف للأعداد الكبيرة)

لتكن $(X_k)_{k \geq 1}$ متغيرات عشوائية مستقلة مثنى مثنى لها القانون نفسه وتقبل عزما من الرتبة الثانية؛ ونكتب $m = \E(X_1)$ و $S_n = X_1 + \dots + X_n$ . عندئذ، من أجل كل $\varepsilon > 0$ :

\P\Bigl(\,\Bigl|\frac{S_n}{n} - m\Bigr| \geq \varepsilon\Bigr) \;\leq\; \frac{V(X_1)}{n\,\varepsilon^2} \xrightarrow[n \to \infty]{} 0 .

برهان. بالخطية $\E(S_n/n) = m$ ؛ وبحسب المبرهنة 22.14 (فالاستقلال مثنى مثنى يقتل التغايرات) $V(S_n) = n\,V(X_1)$ ، ومنه $V(S_n/n) = V(X_1)/n$ . وتعطي متراجحة تشيبيشيف مطبقة على $S_n/n$ الحصر. ∎

ملاحظة 22.26

هذه هي المبرهنة التي تربط الاحتمال بالتواتر: فإذا كان $X_k$ الدالة المميزة لحدث $A$ في تكرارات مستقلة، كان $S_n/n$ هو التواتر الملاحظ للحدث $A$ ، ويقول قانون الأعداد الكبيرة إنه يتركز حول $\P(A)$ بمعدل $\frac{p(1-p)}{n\varepsilon^2}$ . أما القانون القوي ( $S_n/n \to m$ بشكل شبه أكيد) فمبرهنة من السنة الثالثة — غير أن برهانه من أجل العزوم من الرتبة الرابعة في المتناول: انظر التمرين 22.9، الذي يشغّل بوريل–كانتيلي على حصر من نوع تشيبيشيف. وقد شغّل التقدير التشيبيشيفي نفسه برهان كثيرات حدود برنشتاين لمبرهنة فايرشتراس في التقريب في الفصل 10 — فمبرهنة العدّ هناك كانت القانون الضعيف للأعداد الكبيرة متنكرا.

مثال 22.27 (جمع خمسين قسيمة)

جامع القسائم في التمرين 22.3 مع $n = 50$ لعبة متمايزة: فالعدد الكلي المتوقع هو

\E(T_{50}) = 50\,H_{50} = 50\sum_{k=1}^{50}\frac1k \approx 50 \times 4.499 \approx 225

علبة — أي أربع مرات ونصف التخمين الساذج $50$ . والنمو التوافقي هو القصة كلها: فاللعب $25$ الأولى تصل في نحو $50\ln2 \approx 35$ علبة، بينما تكلف اللعبة الأخيرة وحدها $50$ علبة وسطيا (وهو انتظار هندسي بالوسيط $\frac1{50}$ ). فمسائل الإكمال يهيمن عليها شوطها الأخير، ولهذا يجد التمرين 22.12 تقلبات من رتبة $n$ — أي حجم ذلك الانتظار الهندسي الأخير — حول المتوسط $n\ln n$ .

مثال 22.28 (كم يجب أن يكون $n$ كبيرا؟)

لتثبيت التواتر الملاحظ ضمن $\varepsilon = 0.01$ من $\P(A)$ بثقة $95\%$ ، يقتضي حصر تشيبيشيف

\frac{p(1-p)}{n\varepsilon^2} \leq \frac{1}{4n\varepsilon^2} \leq 0.05, \qquad\text{أي}\qquad n \geq \frac{1}{4\cdot0.05\cdot(0.01)^2} = 50\,000 .

والتعلق وحشي بالنسبة إلى $\varepsilon$ (تربيعي)، ولطيف بالنسبة إلى الثقة (خطي بدلالة $1/\alpha$ ). وكلتا الخاصيتين خاصية للحصر لا للحقيقة: فمتراجحات مسألة نهاية الأسبوع الأسية تخفض ثمن الثقة من $1/\alpha$ إلى $\ln(1/\alpha)$ — فالمواصفة نفسها ستكلف نحو $18\,500$ عينة هناك — بينما السلّم $1/\varepsilon^2$ حقيقي ولا يمكن تحسينه. ومعرفة أي جزء من الحصر مرتخ لا تقل فائدة عن الحصر نفسه.

قانون الأعداد الكبيرة في صورة: يحافظ قانون S_n/n (المرسوم تخطيطيا) على مركزه m لكنه يضيق مع نمو n، ومنه يتقلص احتمال الوقوع خارج النطاق [m- , m+ ] — أي الذيلين — إلى الصفر. وتحصر متراجحة تشيبيشيف الذيلين بالمقدار V(X_1)/(n 2)؛ وتبين مسألة نهاية الأسبوع أنهما في الواقع صغيران أسيا. — قانون الأعداد الكبيرة في صورة: يحافظ قانون $S_n/n$ (المرسوم تخطيطيا) على مركزه $m$ لكنه يضيق مع نمو $n$ ، ومنه يتقلص احتمال الوقوع خارج النطاق $\intcc{m-\varepsilon}{m+\varepsilon}$ — أي الذيلين — إلى الصفر. وتحصر متراجحة تشيبيشيف الذيلين بالمقدار $V(X_1)/(n\varepsilon^2)$ ؛ وتبين مسألة نهاية الأسبوع أنهما في الواقع صغيران أسيا.

ملاحظة 22.29 (آفاق داخل هذا المجلد)

إلى الأمام، يغذي كل ما هنا الفصل 23: فالأمل الرياضي $\E(t^X)$ لدالة ماكرة واحدة للمتغير $X$ يحزم القانون كله في متسلسلة قوى، وتصير العزوم مشتقات عند $1$ ، وتحمل متطابقات من نوع فالد من أجل المجاميع العشوائية نظرية مسارات التفرع؛ وتصير مبرهنة الجداء من أجل المتغيرات المستقلة ضربية الدوال المولّدة. وإلى الخلف، الأمل الرياضي مركز ثقل بأوزان احتمالية (الفصل 17)، ومتراجحة جنسن هي هندسة المستقيم المساند للدوال المحدبة (الفصل 8)، وطريقة العزوم الأسية في مسألة نهاية الأسبوع لهذا الفصل هي متراجحة ماركوف مطبقة على $\eu^{tX}$ — متراجحة واحدة، مرتقية بتغيير متغير واحد جيد، تمتد على ثلاثة فصول.

22.5 تمارين

تمرين 22.1 ★

احسب $\E(X)$ و $V(X)$ من أجل $X \sim \mathcal{B}(n, p)$ (عبر الدوال المميزة)، ومن أجل $X \sim \mathcal{P}(\lambda)$ (بيّن $V(X) = \lambda$ )، ومن أجل $X \sim \mathcal{G}(p)$ (بيّن $V(X) = \frac{1-p}{p^2}$ ؛ واستعمل $\E(X(X-1))$ والمشتقة الثانية للمتسلسلة الهندسية).

حل

حل التمرين 22.1.

ثنائي الحد: $X = \sum_{i=1}^n X_i$ بمتغيرات برنولي مستقلة $X_i$ ؛ و $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ ، وتباينات المتغيرات المستقلة تُجمع (المبرهنة 22.14):

\E(X) = np, \qquad V(X) = np(1-p) .

بواسون: $\E\bigl(X(X-1)\bigr) = \sum_{k\geq2}k(k-1)e^{-\lambda}\frac{\lambda^k}{k!} = \lambda^2 e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda^2$ ، ومنه

V(X) = \E(X^2) - \E(X)^2 = \lambda^2 + \lambda - \lambda^2 = \lambda .

الهندسي ( $q = 1 - p$ ): بمفاضلة $\sum_{k\geq0}q^k = \frac{1}{1-q}$ مرتين داخل القرص (الفصل 11)، $\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2}{(1-q)^3}$ ، ومنه

\E\bigl(X(X-1)\bigr) = pq\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2q}{p^2}, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{q}{p^2} = \frac{1-p}{p^2} .

تمرين 22.2 ★

ليكن $X \sim \mathcal{P}(\lambda)$ و $Y \sim \mathcal{P}(\mu)$ مستقلين. بيّن أن $X + Y \sim \mathcal{P}(\lambda + \mu)$ (وهو التفاف الأوزان؛ بمبرهنة ذات الحدين)، وأن القانون الشرطي للمتغير $X$ علما بالحدث $X + Y = n$ هو القانون الثنائي $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ .

حل

حل التمرين 22.2.

المجموع: من أجل $n \in \N$ ، بالانفصال والاستقلال،

\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k) = e^{-(\lambda + \mu)}\frac{1}{n!} \sum_{k=0}^n \binom nk \lambda^k\mu^{n-k} = e^{-(\lambda+\mu)}\frac{(\lambda + \mu)^n}{n!}

بمبرهنة ذات الحدين: $X + Y \sim \mathcal{P}(\lambda + \mu)$ . القانون الشرطي: من أجل $0 \leq k \leq n$ ،

\P(X = k \mid X + Y = n) = \frac{\P(X = k)\P(Y = n - k)}{\P(X + Y = n)} = \binom nk \Bigl(\frac{\lambda}{\lambda+\mu}\Bigr)^{k} \Bigl(\frac{\mu}{\lambda+\mu}\Bigr)^{n-k} ,

أي القانون الثنائي $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : فعلما بالعدد الكلي، “يختار” كل حدث المصدر الأول مستقلا باحتمال يتناسب مع معدله.

تمرين 22.3 ★

(جامع القسائم، الأمل الرياضي) تخفي علامة حبوب واحدة من $n$ لعبة متمايزة، بانتظام، في كل علبة. وليكن $T_n$ عدد العلب اللازمة لجمع اللعب $n$ كلها. بكتابة $T_n$ مجموعا لمتغيرات هندسية مستقلة (وهي زمن رؤية لعبة جديدة عندما لا تزال $k$ لعبة ناقصة)، بيّن

\E(T_n) = n\sum_{k=1}^{n}\frac{1}{k} \sim n\ln n

(وهو مكافئ بمقارنة المتسلسلة بالتكامل في الفصل 6).

حل

حل التمرين 22.3.

عندما تكون $k$ لعبة لا تزال ناقصة، تجلب كل علبة جديدة لعبة جديدة باحتمال $\frac kn$ ، مستقلا عن الماضي: فزمن الانتظار $W_k$ للعبة الجديدة التالية هندسي $\mathcal{G}\bigl(\frac kn\bigr)$ ، مع $\E(W_k) = \frac nk$ ، و $T_n = W_n + W_{n-1} + \dots + W_1$ (فالعلبة الأولى تعطي دائما لعبة جديدة: $W_n = 1$ ، بانسجام مع $\E = n/n$ ). وبالخطية،

\E(T_n) = \sum_{k=1}^n \frac nk = n\sum_{k=1}^n\frac1k \sim n\ln n ,

باستعمال $\sum_{k\leq n}\frac1k = \ln n + \gamma + o(1)$ (الفصل 6). فجمع اللعب الأخيرة هو ما يكلف: إذ يذهب نصف العلب إلى الحفنة الأخيرة.

تمرين 22.4 ★★

ليكن $X \geq 0$ ذا قيم صحيحة. برهن على صيغة الذيل

\E(X) = \sum_{n=1}^{\infty} \P(X \geq n)

(عندما يكون أحد الطرفين منتهيا)، بكتابة $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ وتبديل ترتيب الجمع (مبرهنة فوبيني من أجل العائلات الموجبة). واستعد $\E(X) = \frac1p$ من أجل القانون الهندسي.

حل

حل التمرين 22.4.

نقطيا، $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . والعائلة المزدوجة $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ موجبة، ومنه تنطبق مبرهنة فوبيني من أجل العائلات (الفصل 7) دون شرط: فالجمع بدلالة $n$ أولا يعطي $\E(X)$ ، والجمع بدلالة $\omega$ أولا يعطي $\sum_n \P(X \geq n)$ ؛ والمقداران منتهيان معا ومتساويان. ومن أجل $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ )، ومنه $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

تمرين 22.5 ★★

(المعاينة دون إرجاع أشد تركيزا) تحوي جرة $N$ كرة، منها $M$ بيضاء. نسحب $n \leq N$ دون إرجاع ونجعل $X$ يعد البيضاوات (وهو القانون فوق الهندسي). باستعمال الدوال المميزة $X = \sum_{i=1}^n Y_i$ مع $Y_i$ السحبة رقم $i$ : بيّن أن كل $Y_i$ برنولي بالوسيط $p = M/N$ (بالتناظر!)، واستنتج $\E(X) = np$ تماما كما في حالة الإرجاع، وبيّن $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ من أجل $i \neq j$ ، ومنه $V(X) = np(1-p)\frac{N - n}{N - 1} \leq np(1-p)$ .

حل

حل التمرين 22.5.

التناظر: الكرة رقم $i$ المسحوبة كرة منتظمة عشوائية من الجرة (فلكل كرة من الكرات $N$ الاحتمال نفسه في أن تحط في الموضع $i$ من ترتيب السحب)، ومنه $\P(Y_i = 1) = \frac MN = p$ و $\E(X) = np$ بالخطية — دون حاجة إلى أي استقلال.

التغاير: من أجل $i \neq j$ ، $\E(Y_iY_j) = \P(\text{السحبتان } i, j \text{ بيضاوان معا}) = \frac{M(M-1)}{N(N-1)}$ (فأزواج المواضع المتمايزة المرتبة تحصل على أزواج مرتبة من الكرات المتمايزة، بانتظام). ومنه

\operatorname{Cov}(Y_i, Y_j) = \frac{M(M-1)}{N(N-1)} - \frac{M^2}{N^2} = \frac{M(N - M)}{N^2}\cdot\frac{-1}{N-1} = -\frac{p(1-p)}{N-1} < 0 :

فسحب كرة بيضاء يجعل البيضاوات أندر من أجل السحبات الأخرى. وبحسب المبرهنة 22.14،

V(X) = np(1-p) + n(n-1)\Bigl(-\frac{p(1-p)}{N-1}\Bigr) = np(1-p)\,\frac{N - n}{N - 1} \leq np(1-p) :

فللمعاينة دون إرجاع المتوسط نفسه لكن تباينها أصغر من تباين المعاينة مع الإرجاع (مع التساوي من أجل $n = 1$ وحده)، إذ تعمل الترابطات السالبة مثبِّتا. ومن أجل $n = N$ ينعدم التباين: فالعدد حتمي عندئذ.

تمرين 22.6 ★★

ليكن $X$ ذا عزم من الرتبة الثانية. بيّن أن $c \mapsto \E\bigl((X - c)^2\bigr)$ أصغري بالضبط عند $c = \E(X)$ ، وأن قيمته الصغرى $V(X)$ . ثم بيّن أن $\P(X = \E(X)) = 1$ إذا وفقط إذا كان $V(X) = 0$ . (من أجل النقطة الثانية: إذا كان $V(X) = 0$ ، فاستعمل متراجحة تشيبيشيف مع $\varepsilon = 1/n$ والاتصال الرتيب، المبرهنة 21.6.)

حل

حل التمرين 22.6.

بالنشر حول $m = \E(X)$ :

\E\bigl((X - c)^2\bigr) = \E\bigl((X - m)^2\bigr) + 2(m - c)\,\E(X - m) + (m - c)^2 = V(X) + (m - c)^2 ,

وهو أصغري بالضبط عند $c = m$ بالقيمة $V(X)$ — فالأمل الرياضي هو أفضل متنبئ ثابت بالمعنى التربيعي المتوسط.

فإذا كان $\P(X = m) = 1$ ، انعدم $(X - m)^2$ باحتمال $1$ ، ومنه $V(X) = 0$ (فحدود العائلة المعرِّفة معدومة إلا على مجموعة معدومة). وبالعكس، إذا كان $V(X) = 0$ ، أعطت متراجحة تشيبيشيف (المبرهنة 22.15) المقدار $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ من أجل كل $n$ ؛ والأحداث $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ متزايدة نحو $\{X \neq m\}$ ، ومنه يعطي الاتصال الرتيب (المبرهنة 21.6) المقدار $\P(X \neq m) = 0$ .

تمرين 22.7 ★★★

(التركيز يتفوق على ماركوف) ليكن $S_n \sim \mathcal{B}(n, \frac12)$ (أي عدد الصور في $n$ رمية متزنة). قارن بين الحصور التي تعطيها متراجحة ماركوف ( $\P(S_n \geq \frac{3n}{4})$ )، ومتراجحة تشيبيشيف، والطريقة الأسية (تشيرنوف):

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \E\bigl(e^{tS_n}\bigr)e^{-3nt/4} = \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} \quad (t > 0),

وأمثل $t$ للحصول على حصر صغير أسيا. (عند $t = \ln 3$ : احصر $\bigl(2\cdot 3^{-3/4}\bigr)^n \approx (0.877)^n$ .)

حل

حل التمرين 22.7.

$\E(S_n) = \frac n2$ و $V(S_n) = \frac n4$ . ماركوف: $\P\bigl(S_n \geq \frac{3n}4\bigr) \leq \frac{n/2}{3n/4} = \frac23$ — وهو حصر ثابت، عديم الفائدة من أجل $n$ الكبيرة. تشيبيشيف: يستلزم الحدث $\abs{S_n - \frac n2} \geq \frac n4$ ، ومنه فالاحتمال $\leq \frac{n/4}{(n/4)^2} = \frac4n$ — فهو يتلاشى، لكن كثير حدود فقط. تشيرنوف: بالاستقلال، $\E(e^{tS_n}) = \prod_{i=1}^n\E(e^{tX_i}) = \bigl(\frac{1 + e^t}{2}\bigr)^n$ ، وتعطي متراجحة ماركوف مطبقة على $e^{tS_n} \geq e^{3nt/4}$ ، من أجل كل $t > 0$ ،

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} = \exp\Bigl(n\bigl(\ln\tfrac{1 + e^t}{2} - \tfrac{3t}4\bigr)\Bigr).

ونصغّر الأسّ: $\frac{\dd}{\dd t}\ln\frac{1+e^t}{2} = \frac{e^t}{1 + e^t} = \frac34$ عند $e^t = 3$ ، أي $t = \ln 3$ ، وهو ما يعطي

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{4}{2}\Bigr)^n 3^{-3n/4} = \bigl(2 \cdot 3^{-3/4}\bigr)^n \approx (0.877)^n ,

أي صغيرا أسيا. والتدرج ماركوف $\to$ تشيبيشيف $\to$ تشيرنوف هو السلّم القياسي: فكل درجة تطبق متراجحة ماركوف على دالة أسرع نموا للمتغير.

تمرين 22.8 ★★★

(فايرشتراس من جديد، احتماليا) لتكن $f \colon [0,1] \to \R$ متصلة وليكن $S_n \sim \mathcal{B}(n, x)$ . بيّن أن كثير حدود برنشتاين $B_nf(x) = \sum_{k=0}^n f\bigl(\frac kn\bigr)\binom nk x^k(1-x)^{n-k}$ يساوي $\E\bigl[f\bigl(\frac{S_n}{n}\bigr)\bigr]$ ، وأعد اشتقاق التقدير $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ في الفصل 10 بهذه اللغة الاحتمالية (بالتقسيم على $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ واستعمال متراجحة تشيبيشيف).

حل

حل التمرين 22.8.

بمبرهنة النقل (المبرهنة 22.7) مطبقة على $f\bigl(\frac{S_n}{n}\bigr)$ مع $S_n \sim \mathcal{B}(n, x)$ :

\E\Bigl[f\Bigl(\frac{S_n}{n}\Bigr)\Bigr] = \sum_{k=0}^n f\Bigl(\frac kn\Bigr)\binom nk x^k(1-x)^{n-k} = B_nf(x) .

نثبّت $\delta > 0$ ونقسم $\abs{f(S_n/n) - f(x)}$ على الحدث $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : فخارج $D$ ، لا يتجاوز الفرق مقياس الاتصال $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ؛ وعلى $D$ ، لا يتجاوز $2\norm f_\infty$ . وبأخذ الآمال واستعمال متراجحة تشيبيشيف مع $V\bigl(\frac{S_n}{n}\bigr) = \frac{x(1-x)}{n} \leq \frac{1}{4n}$ :

\abs{B_nf(x) - f(x)} \leq \E\,\abs{f(S_n/n) - f(x)} \leq \omega_f(\delta) + 2\norm f_\infty\,\P(D) \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2} .

ويجعل الاتصال المنتظم للدالة $f$ على $[0, 1]$ المقدار $\omega_f(\delta) \to 0$ : فنختار $\delta$ ثم $n$ ، ويكون $B_nf \to f$ بانتظام — وهي مبرهنة فايرشتراس في التقريب في الفصل 10، التي صارت “مبرهنة العد” فيها معروفة الآن بأنها متراجحة تشيبيشيف من أجل القانون الثنائي.

تمرين 22.9 ★★★

(القانون القوي تحت عزوم من الرتبة الرابعة) لتكن $(X_k)$ مستقلة ومتماثلة التوزيع ومركزية ( $\E X_1 = 0$ )، مع $\E(X_1^4) < \infty$ . بنشر $\E(S_n^4)$ وعدّ الحدود الباقية (فقط الحدود من نوع $\E(X_i^4)$ و $\E(X_i^2X_j^2)$ ، $i \neq j$ )، بيّن $\E(S_n^4) \leq C n^2$ من أجل ثابت $C$ . واستنتج $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ من أجل كل $\varepsilon > 0$ (بمتراجحة ماركوف من الرتبة 4) واختم ببوريل–كانتيلي (المبرهنة 21.25) أن $S_n/n \to 0$ بشكل شبه أكيد وفق صياغة مناسبة: أي إن احتمال الحدث $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ هو $1$ .

حل

حل التمرين 22.9.

ننشر $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ ونأخذ الآمال. وبالاستقلال والمركزية، ينعدم كل حد يحوي دليلا يظهر مرة واحدة بالضبط (إذ يخرج العامل $\E(X_i) = 0$ ). والحدود الباقية: الحدود القطرية $n$ وهي $\E(X_i^4)$ ، والحدود التي تزاوج زوجين من الأدلة المتساوية، $\E(X_i^2X_j^2) = \E(X_1^2)^2$ من أجل $i \neq j$ ، والظاهرة $3n(n-1)$ مرة: باختيار الزوج غير المرتب من القيم (بعدد $\binom n2$ طريقة)، ثم بعدد $\frac{4!}{2!\,2!} = 6$ طريقة لوضعها في الخانات الأربع — $6\binom n2 = 3n(n-1)$ . ومنه، مع $\E(X_1^2)^2 \leq \E(X_1^4)$ (بمتراجحة جنسن أو كوشي–شوارتز)،

\E(S_n^4) = n\,\E(X_1^4) + 3n(n-1)\,\E(X_1^2)^2 \leq C n^2, \qquad C = 4\,\E(X_1^4) .

ومتراجحة ماركوف من الرتبة 4:

\P\Bigl(\Bigl|\frac{S_n}{n}\Bigr| \geq \varepsilon\Bigr) = \P\bigl(S_n^4 \geq n^4\varepsilon^4\bigr) \leq \frac{Cn^2}{n^4\varepsilon^4} = \frac{C}{n^2\varepsilon^4} ,

وهي متسلسلة قابلة للجمع. وبحسب بوريل–كانتيلي 1 (المبرهنة 21.25)، يكون من أجل كل $j$ احتمال الحدث $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ هو $0$ ، ومنه $\P\bigl(\bigcup_j B_j\bigr) = 0$ بالجمعية التحتية القابلة للعد. وعلى المتمم — ذي الاحتمال $1$ — يوجد من أجل كل $j$ عدد $N$ يحقق $\abs{S_n/n} < \frac1j$ من أجل كل $n \geq N$ : وهو بالضبط $S_n/n \to 0$ . فالقانون القوي للأعداد الكبيرة يتحقق تحت عزم من الرتبة الرابعة؛ أما إسقاط تلك الفرضية (مبرهنة كولموغوروف) فعمل السنة الثالثة.

تمرين 22.10 ★

يُرمى نردان متزنان؛ وليكن $M$ الأكبر من النتيجتين. باستعمال صيغة الذيل في التمرين 22.4 (بصيغتها المنتهية)، بيّن

\E(M) = \sum_{k=1}^{6}\P(M \geq k) = 6 - \sum_{j=0}^5\Bigl(\frac j6\Bigr)^2 = \frac{161}{36} \approx 4.47 .

حل

حل التمرين 22.10.

$\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (فالنردان كلاهما لا يتجاوز $k$ ، بصورة مستقلة)، ومنه $\P(M \geq k) = 1 - \bigl(\frac{k-1}6\bigr)^2$ و

\E(M) = \sum_{k=1}^6\P(M \geq k) = 6 - \frac{0 + 1 + 4 + 9 + 16 + 25}{36} = 6 - \frac{55}{36} = \frac{161}{36} \approx 4.47 ,

وهو يفوق بأريحية متوسط نرد واحد $3.5$ ، كما ينبغي لقيمة عظمى.

تمرين 22.11 ★★

ليكن $F_n$ عدد النقط الثابتة لتبديلة منتظمة عشوائية على $\{1, \dots, n\}$ ( $n \geq 2$ ). بكتابة $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ ، احسب $\E(F_n) = 1$ و $\operatorname{Cov}(\mathbf 1_{\sigma(i)=i}, \mathbf 1_{\sigma(j)=j}) = \frac1{n^2(n-1)}$ من أجل $i \neq j$ ، واستنتج $V(F_n) = 1$ : أي إن رسالة واحدة وسطيا تبقى في مكانها، بتباين يساوي $1$ بالضبط، مهما يكن $n$ .

حل

حل التمرين 22.11.

مع $I_i = \mathbf 1_{\sigma(i) = i}$ : $\P(\sigma(i) = i) = \frac{(n-1)!}{n!} = \frac1n$ ، ومنه $\E(F_n) = n\cdot\frac1n = 1$ . ومن أجل $i \neq j$ : $\P(\sigma(i) = i, \sigma(j) = j) = \frac{(n-2)!}{n!} = \frac1{n(n-1)}$ ، ومنه

\operatorname{Cov}(I_i, I_j) = \frac1{n(n-1)} - \frac1{n^2} = \frac{1}{n^2(n-1)} .

وبعدة التباين (المبرهنة 22.14)،

V(F_n) = n\cdot\frac1n\Bigl(1 - \frac1n\Bigr) + n(n-1)\cdot\frac1{n^2(n-1)} = 1 - \frac1n + \frac1n = 1 .

فالمتوسط $1$ ، والتباين $1$ ، وهما مستقلان عن $n$ — بانسجام مع نهاية بواسون في مسألة التطابقات (التمرين 21.5).

تمرين 22.12 ★★★

(جامع القسائم، التركيز) في إطار التمرين 22.3، بيّن

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq n^2\sum_{k=1}^n\frac{1}{k^2} \leq \frac{\pi^2}{6}n^2,

باستعمال استقلال المراحل الهندسية و $V(\mathcal G(p)) = \frac{1-p}{p^2}$ (التمرين 22.1؛ والقيمة $\pi^2/6$ هي المثال 14.12). واستنتج بمتراجحة تشيبيشيف أن $\dfrac{T_n}{n\ln n} \to 1$ بالاحتمال: أي إن الزمن الكلي للجامع هو $n\ln n$ إلى غاية تقلبات من رتبة $n$ .

حل

حل التمرين 22.12.

$T_n = \sum_{k=1}^nG_k$ حيث $G_k \sim \mathcal G(k/n)$ هو زمن رؤية لعبة جديدة عندما تكون $k$ ناقصة، والمراحل مستقلة. ومنه

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq \sum_{k=1}^n\frac{n^2}{k^2} \leq \frac{\pi^2}6\,n^2 ,

بحسب المثال 14.12. ومع $\E(T_n) = nH_n$ ، $H_n = \sum_1^n\frac1k$ (التمرين 22.3)، تعطي متراجحة تشيبيشيف، من أجل $\varepsilon > 0$ ،

\P\bigl(\abs{T_n - nH_n} \geq \varepsilon\,n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2 n} = \frac{\pi^2}{6\,\varepsilon^2\ln^2n} \xrightarrow[n\to\infty]{} 0 .

وبما أن $H_n \sim \ln n$ ، فإن القسمة على $n\ln n$ تبين أن $T_n/(n\ln n) \to 1$ بالاحتمال: أي إن تقلبات $T_n$ من رتبة $n$ ، وهي مهملة أمام المتوسط $n\ln n$ .

22.6 مسألة: عدة التركيز، من ماركوف إلى هوفدينغ

مسألة 22.1

مسألة نهاية الأسبوع — التركيز الأسي باليد، وكم شخصا يجب أن يسأل استطلاع الرأي

تكلف متراجحة ماركوف عزما واحدا وتشتري تلاشيا $1/a$ ؛ وتكلف متراجحة تشيبيشيف عزمين وتشتري $1/\varepsilon^2$ — ويبين المثال 22.18 أن هذا كل ما يمكن لهذين العزمين أن يشترياه. وتصعد هذه المسألة بقية السلّم: الطريقة الأسية (تشيرنوف) بمعدلها المضبوط من أجل رمي قطع النقود، ومتراجحة هوفدينغ من أجل جميع المتغيرات المحدودة، والعائد — أي أحجام عينات صريحة وصادقة من أجل استطلاعات الرأي، وإعلان نتائج الانتخابات، واختبار قطع النقود. وفي كل ما يلي، $S_n \sim \mathcal B(n, p)$ مجموع $n$ متغير برنولي مستقل و $\widehat p_n = S_n/n$ هو التواتر التجريبي.

الجزء الأول — المعايرة على قطعة نقود متزنة. هنا $p = \frac12$ و $a \in \intoo{\frac12}{1}$ .

متراجحة ماركوف عند المستوى $an$ : بيّن $\P(S_n \geq an) \leq \frac1{2a}$ ، وهو حصر لا يؤول حتى إلى $0$ . فأين تخسر متراجحة ماركوف كل هذا؟
متراجحة تشيبيشيف: باستعمال تناظر القانون الثنائي المتزن حول $n/2$ ، بيّن

$\P(S_n \geq an) = \tfrac12\, \P\bigl(\abs{S_n - \tfrac n2} \geq n(a - \tfrac12)\bigr) \leq \frac{1}{8n(a - 1/2)^2},$

أي $\frac2n$ عند $a = \frac34$ : فتلاش كثير الحدود أخيرا.
(تشيرنوف، عند مستوى عام) احسب $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ وأمثل $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ على $t > 0$ : بيّن أن القيمة المثلى $t$ هي $\ln\frac{a}{1-a}$ وأن

$\P(S_n \geq an) \leq \eu^{-n\,I(a)}, \qquad I(a) = \ln 2 + a\ln a + (1-a)\ln(1-a) > 0 .$

وتحقق من أن $a = \frac34$ يستعيد الحصر $\bigl(2\cdot3^{-3/4}\bigr)^n$ في التمرين 22.7.
(الأسّ مضبوط) ليكن $k = an$ عددا صحيحا. انطلاقا من كون $\binom nk a^k(1-a)^{n-k}$ أكبر حدود التوزيع الاحتمالي وعددها $n + 1$ ، برهن على $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ مع $H(a) = -a\ln a - (1-a)\ln(1-a)$ ، واستنتج الحصر السفلي المطابق

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
جدول الحصور الثلاثة عند $n = 100$ ، $a = \frac34$ : ماركوف $\frac23$ ، وتشيبيشيف $0.02$ ، وتشيرنوف $\approx 2.1\cdot10^{-6}$ (والقيمة الحقيقية $\approx 2.8\cdot10^{-7}$ ). والعبرة، في جملة واحدة؟

الجزء الثاني — متراجحة هوفدينغ.

(حالة رادماخر) من أجل $\varepsilon = \pm1$ باحتمال $\frac12$ لكل منهما، برهن على

$\E(\eu^{t\varepsilon}) = \cosh t \leq \eu^{t^2/2} \qquad (t \in \R)$

بمقارنة المتسلسلتين حدا حدا ( $(2k)! \geq 2^kk!$ ).
استنتج، من أجل متغيرات رادماخر مستقلة $\varepsilon_1, \dots, \varepsilon_n$ ومن أجل كل $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
ترجم ذلك إلى قطع النقود المتزنة ( $X_i = \frac{1+\varepsilon_i}2$ ): $\P\bigl(\widehat p_n - \tfrac12 \geq \delta\bigr) \leq \eu^{-2n\delta^2}$ ، ومع الصيغة ذات الطرفين بعامل $2$ .
(مبرهنة هوفدينغ المساعدة) ليكن $X \in \intcc01$ مع $\E X = p$ ، و $\psi(t) = \ln\E(\eu^{tX})$ . برر أن $\psi$ قابل للتفاضل مرتين مع

$\psi''(t) = \E_t(X^2) - \E_t(X)^2, \qquad \E_t(Y) := \frac{\E(Y\eu^{tX})}{\E(\eu^{tX})},$

وهو تباين لمتغير معاد ترجيحه لا يزال يأخذ قيمه في $\intcc01$ ؛ واحصره بالمقدار $\frac14$ (بحجة الأصغرية في التمرين 22.6) واختم بمبرهنة تايلور:

$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$
(متراجحة هوفدينغ) من أجل متغيرات مستقلة $X_i \in \intcc01$ لها المتوسط المشترك $p$ ، استنتج

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
قارن معدل تشيبيشيف $\frac{p(1-p)}{n\delta^2}$ بمعدل هوفدينغ $2\eu^{-2n\delta^2}$ : أي فرضية يقتضي كل منهما، وانطلاقا من أي $n$ (تقريبا) يفوز الحصر الأسي عند $\delta = 0.03$ ، $p = \frac12$ ؟

الجزء الثالث — كم شخصا يجب أن يسأل استطلاع الرأي؟ يسأل استطلاع $n$ ناخبا مستقلا مختارا بانتظام؛ ويجيب كل منهم بصدق؛ و $p$ هي النتيجة الحقيقية و $\widehat p_n$ هي نتيجة الاستطلاع.

بيّن أن الاستطلاع دقيق في حدود $\pm\delta$ بثقة $1 - \alpha$ (أي $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) بمجرد أن يكون

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
احسب $n$ اللازم من أجل المواصفة القياسية “ثلاث نقاط، خمسة وتسعون في المائة” ( $\delta = 0.03$ ، $\alpha = 0.05$ ): $n \geq 2050$ ؛ ومن أجل نقطة واحدة: $n \geq 18\,445$ . ولاحظ — وفسّر — الحقيقة اللافتة القائلة إن الجواب لا يتضمن حجم المجتمع.
أعد السؤال 13 بمتراجحة تشيبيشيف ( $V(X_1) = p(1-p) \leq \frac14$ ): $n \geq \frac1{4\alpha\delta^2} = 5556$ عند ثلاث نقاط. ولاحظ أن المعاينة دون إرجاع لا تزيد الأمر إلا حسنا (التمرين 22.5: فالتباين يتقلص بالعامل $\frac{N-n}{N-1}$ ).
(إعلان نتيجة انتخابات) النتيجة الحقيقية لمرشح هي $p = 0.52$ . كم ناخبا يجب استطلاعه ليكون $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ؟ بيّن $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — فإعلان سباق متقارب يكلف أكثر بكثير من تقدير نتيجة.
ما لا تغطيه الرياضيات: اسرد فرضيات النمذجة المستعملة (المعاينة المنتظمة المستقلة، وصدق الإجابات، وثبات $p$ )، واشرح في فقرة قصيرة لماذا يهيمن التحيز على أخطاء الاستطلاعات الحقيقية (المعاينة غير المنتظمة، وعدم الاستجابة)، وهو ما لا تخفضه أي زيادة في $n$ .

الجزء الرابع — أدق وأرخص.

(وسيط المتوسطات: تلاش أسي انطلاقا من عزمين) نقسم ميزانية من $km$ عينة إلى $k$ مجموعة مستقلة من $m$ ؛ وليكن $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ متوسطات المجموعات و $M$ وسيطها. اختر $m$ بحيث تحقق كل مجموعة $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (تشيبيشيف: يكفي $m \geq \frac2{\delta^2}$ ). بيّن أنه إذا كان $\abs{M - p} \geq \delta$ فإن ما لا يقل عن $k/2$ مجموعة تخطئ، واستنتج

$\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil}\Bigl(\frac18 \Bigr)^{k/2} \leq 2^k\cdot 8^{-k/2} = 2^{-k/2} :$

أي تركيزا أسيا دون استعمال أي شيء يتجاوز التباينات.
(بالي–زيغموند) من أجل $X \geq 0$ ذي عزم من الرتبة الثانية، برهن على $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (بمتراجحة كوشي–شوارتز على $X\mathbf 1_{X>0}$ ): وهي الأداة في الاتجاه المعاكس — فالعزوم قد تفرض وقوع الأحداث أيضا.
(بينسكر مخففة) بيّن $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ على $\intoo{\frac12}1$ (فالفرق ينعدم حتى الرتبة الثانية عند $\frac12$ ومشتقته الثانية $\frac1{a(1-a)} - 4 \geq 0$ ): أي إن أسّ تشيرنوف المضبوط يتفوق دائما على أسّ هوفدينغ التربيعي.
انشر $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ واجمعه مع السؤال 4: ففي حالة الانحرافات الصغيرة يكون أسّ هوفدينغ $2n\delta^2$ مضبوطا مقاربا — فلا طريقة تتفوق عليه بأكثر من عوامل كثيرة الحدود.
ارسم جدول العدة: من أجل ماركوف، وتشيبيشيف، وحصر العزم من الرتبة الرابعة في التمرين 22.9، وهوفدينغ، وتشيرنوف بالأسّ $I$ ، اذكر في سطر واحد لكل منها: الفرضية المطلوبة، والتلاشي المحصل، والسؤال في هذه المسألة الذي كان فيه أدق ما يكون.

الجزء الخامس — العوائد.

(اختبار قطعة نقود) قطعة نقود إما متزنة وإما منحازة بالوسيط $p = 0.55$ . ترميها $n$ مرة وتعلن “منحازة” عندما $\widehat p_n > 0.525$ . بيّن أن احتمالي الخطأ كليهما لا يتجاوز $\eu^{-2n(0.025)^2}$ ، وأن $n \geq 3685$ رمية تضمن أن يكونا كلاهما دون $1\%$ .
(الأحداث النادرة تحتاج إلى حصر يعي التباين) ليكن $p = 0.01$ وخذ المواصفة النسبية $\delta = p/2 = 0.005$ ، $\alpha = 0.05$ . قارن أحجام العينات التي تقتضيها متراجحة هوفدينغ ( $n \approx 74\,000$ ) وتلك التي تقتضيها متراجحة تشيبيشيف بالتباين الحقيقي $p(1-p)$ ( $n \approx 7920$ ): فالحصر الأسي الأعمى عن التباين يخسر أمام العزم الثاني المتواضع. اذكر العبرة، ومن أين ستأتي الأداة الناقصة (حصر أسي يعي التباين؛ وتقريب بواسون في الفصل 23).
(القانون القوي من أجل قطع النقود) انطلاقا من $\sum_n 2\eu^{-2n\delta^2} < \infty$ وبوريل–كانتيلي (المبرهنة 21.25)، برهن على أن $\widehat p_n \to p$ بشكل شبه أكيد من أجل رميات مستقلة لقطعة نقود: صُغ الحدث شبه الأكيد على الصورة $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ كما في التمرين 22.9، واختم. (فالحصر يحل محل العزم من الرتبة الرابعة المستعمل هناك.)
تركيب. في خمس جمل: ماذا تكلف وماذا تشتري كل درجة من درجات السلّم (العزوم الأول والثاني والرابع؛ والأسي المحدود؛ والأسّ المضبوط)؛ ولماذا يكفي استطلاع $2050$ شخص من أجل بلد أيا يكن حجمه؛ وأي هذه الحصور سيشحذه مجلد السنة الثالثة ليصير الثوابت المضبوطة في مبرهنة النهاية المركزية.

حل

حل المسألة 22.1.

1. يعطي $\E(S_n) = \frac n2$ ومتراجحة ماركوف (المبرهنة 22.15) المقدار $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . فمتراجحة ماركوف لا تعرف إلا المتوسط: فهي لا تستطيع تمييز متغير مركز عند $n/2$ من متغير منتشر بين $0$ و $n$ ، ومنه فهي تسعّر الذيل كما لو أمكن أن تجلس الكتلة كلها هناك.

2. القانون الثنائي المتزن متناظر حول $n/2$ (فللمقدارين $S_n$ و $n - S_n$ القانون نفسه)، ومنه فمع $x = n(a - \frac12) > 0$ يكون الحدثان $\{S_n - \frac n2 \geq x\}$ و $\{S_n - \frac n2 \leq -x\}$ منفصلين ومتساويي الاحتمال: $\P(S_n \geq an) = \frac12\P(\abs{S_n - \frac n2} \geq x)$ . وتشيبيشيف مع $V(S_n) = \frac n4$ :

\P(S_n \geq an) \leq \frac12\cdot\frac{n/4}{n^2(a - 1/2)^2} = \frac1{8n(a - 1/2)^2},

وهو $\frac2n$ عند $a = \frac34$ .

3. بالاستقلال ومبرهنة الجداء، $\E(\eu^{tS_n}) = \bigl(\E \eu^{tX_1}\bigr)^n = \bigl(\frac{1 + \eu^t}2\bigr)^n$ . وبتطبيق متراجحة ماركوف على $\eu^{tS_n}$ :

\P(S_n \geq an) \leq \eu^{-tan}\Bigl(\frac{1 + \eu^t}2\Bigr)^{\!n} = \exp\Bigl(n\bigl(\ln\tfrac{1 + \eu^t}2 - ta\bigr)\Bigr).

ومشتقة الأسّ بدلالة $t$ هي $\frac{\eu^t}{1 + \eu^t} - a$ ، وتنعدم عند $\eu^t = \frac a{1-a}$ ، أي $t^* = \ln\frac a{1-a} > 0$ ؛ وهناك $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ ويساوي الأسّ

n\Bigl(-\ln 2 - \ln(1-a) - a\ln\frac a{1-a}\Bigr) = -n\bigl(\ln2 + a\ln a + (1-a)\ln(1-a)\bigr) = -n\,I(a),

مع $I(\frac12) = 0$ و $I'(a) = \ln\frac a{1-a} > 0$ على $\intoo{\frac12}1$ : $I(a) > 0$ . وعند $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ ، وهو حصر التمرين 22.7.

4. الأعداد $\binom nja^j(1-a)^{n-j}$ وعددها $n + 1$ مجموعها $1$ ، وأكبرها هو الذي عند $j = k = an$ (فمنوال $\mathcal B(n, a)$ هو $\floor{(n+1)a} = k$ هنا). والقيمة العظمى لعدد $n + 1$ من الأعداد مجموعها $1$ لا تقل عن $\frac1{n+1}$ :

\binom nk a^k(1-a)^{n-k} \geq \frac1{n+1} \quad\Longrightarrow\quad \binom nk \geq \frac{a^{-an}(1-a)^{-n(1-a)}}{n+1} = \frac{\eu^{nH(a)}}{n+1}.

ومنه $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : أي إن أسّ تشيرنوف هو الحقيقة، إلى غاية العامل كثير الحدود $n + 1$ .

5. $n = 100$ ، $a = \frac34$ : ماركوف $\frac23$ ؛ وتشيبيشيف $\frac2{100} = 0.02$ ؛ وتشيرنوف $(2\cdot3^{-3/4})^{100} = \eu^{-100\,I(3/4)} \approx 2.1\cdot10^{-6}$ ، مقابل القيمة المضبوطة $2.8\cdot10^{-7}$ . والعبرة: كل عزم من المعلومات يقسم الحصر قسمة كثيرة الحدود؛ أما العزم الأسي فيغير طبيعته.

6. $\cosh t = \sum_{k\geq0}\frac{t^{2k}}{(2k)!}$ و $\eu^{t^2/2} = \sum_{k\geq0}\frac{t^{2k}}{2^kk!}$ ؛ وينتج الادعاء حدا حدا من $(2k)! \geq 2^kk!$ ، الذي يتحقق بالتراجع: $(2k)! = 2k(2k-1)\cdot(2k-2)! \geq 2k\cdot 2^{k-1}(k-1)! = 2^kk!\cdot(2k-1) \geq 2^kk!$ .

7. بالاستقلال، $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ ، ومنه تعطي متراجحة ماركوف $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ؛ والتصغير عند $t = s/n$ يعطي $\eu^{-s^2/(2n)}$ .

8. مع $X_i = \frac{1 + \varepsilon_i}2$ ، $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ ، ومنه $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ ويعطي السؤال 7 الحصر $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . وللحدث المتناظر الحصر نفسه، ومن ثم العامل $2$ من أجل $\abs{\widehat p_n - \frac12} \geq \delta$ .

9. $\E(\eu^{tX}) = \sum_x\eu^{tx}\P(X = x)$ متسلسلة من الدوال الملساء بدلالة $t$ ومشتقاتها حدا حدا مهيمن عليها، على كل فترة متراصة للمتغير $t$ ، بالمقدار $\eu^{\abs t}\P(X = x)$ (لأن $0 \leq x \leq 1$ ): ومنه فهي قابلة للتفاضل مرتين بمبرهنة مفاضلة المتسلسلات المتقاربة ناظميا (المبرهنة 10.7)، وتعطي قاعدة خارج القسمة $\psi' = \E_t(X)$ و $\psi'' = \E_t(X^2) - \E_t(X)^2$ ، حيث $\E_t$ هو الأمل الرياضي بالنسبة إلى الأوزان المعاد ترجيحها $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ — وهي موجبة ومجموعها $1$ وتحملها القيم $x \in \intcc01$ نفسها. وتباين متغير ذي قيم في $\intcc01$ لا يتجاوز $\frac14$ : فبحسب التمرين 22.6، هو $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . ومبرهنة تايلور مع الباقي التكاملي، باستعمال $\psi(0) = 0$ ، $\psi'(0) = p$ :

\psi(t) = tp + \int_0^t(t - s)\,\psi''(s)\,\dd s \leq tp + \frac{t^2}2\cdot\frac14,

أي $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ من أجل كل عدد حقيقي $t$ .

10. بالاستقلال، $\E\bigl(\eu^{t(S_n - np)}\bigr) \leq \eu^{nt^2/8}$ ؛ وتعطي متراجحة ماركوف مع الأمثلة $t = 4\delta$

\P(\widehat p_n - p \geq \delta) \leq \eu^{nt^2/8 - tn\delta}\Big|_{t = 4\delta} = \eu^{-2n\delta^2};

وبتطبيق ذلك على المتغيرات $1 - X_i$ (وهي أيضا في $\intcc01$ ) نحصر الذيل الآخر، ومن ثم الصيغة ذات الطرفين $2\eu^{-2n\delta^2}$ .

11. تحتاج متراجحة تشيبيشيف إلى عزم من الرتبة الثانية فحسب وتعطي $\frac{p(1-p)}{n\delta^2}$ ؛ وتحتاج متراجحة هوفدينغ إلى الحصر وتعطي $2\eu^{-2n\delta^2}$ . وعند $p = \frac12$ ، $\delta = 0.03$ : يكون الحصران $\frac{278}{n}$ (تقريبا) مقابل $2\eu^{-0.0018n}$ ؛ وهما يتقاطعان بجوار $n \approx 1200$ ، وبعدها يفوز الحصر الأسي، وبفارق هائل ( $n = 5000$ : $0.056$ مقابل $2.5\cdot10^{-4}$ ).

12. بحسب متراجحة هوفدينغ (السؤال 10)، يكون $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ بمجرد أن يكون $2n\delta^2 \geq \ln\frac2\alpha$ ، أي $n \geq \frac{\ln(2/\alpha)}{2\delta^2}$ .

13. $\delta = 0.03$ ، $\alpha = 0.05$ : $n \geq \frac{\ln 40}{2\cdot0.0009} \approx 2049.4$ : أي $2050$ شخص. ومن أجل $\delta = 0.01$ : $n \geq \frac{\ln40}{0.0002} \approx 18\,445$ . ولا يظهر حجم المجتمع أبدا لأن كل ناخب معايَن يُنمذَج سحبةَ برنولي $(p)$ جديدة: فصعوبة الاستطلاع هي تباين قطعة نقود، لا حجم البلد. وتنصيف الهامش يكلف أربعة أضعاف العينة — وهو قانون $1/\delta^2$ .

14. تشيبيشيف: $\P(\abs{\widehat p_n - p} \geq \delta) \leq \frac{p(1-p)}{n\delta^2} \leq \frac1{4n\delta^2} \leq \alpha$ من أجل $n \geq \frac1{4\alpha\delta^2}$ ، أي $5556$ عند ثلاث نقاط — أي نحو $2.7$ ضعف ما تقتضيه متراجحة هوفدينغ. أما دون إرجاع فيُضرب التباين في $\frac{N - n}{N-1} < 1$ (التمرين 22.5)، ومنه فإن $n$ نفسه لا يمكن إلا أن يكون أفضل: فحساب المعاينة مع الإرجاع هو الحساب المتحفظ.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ ، ومنه بالحصر الهوفدينغي ذي الطرف الواحد يكون $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ بمجرد أن يكون $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : أي $5757$ ناخب. ويتحاكى الثمن مع مقلوب مربع الفارق، لا مقلوب مربع الدقة المرجوة: فالسباقات المتقاربة مكلفة.

16. المستعمل: أن العينة مسحوبة بانتظام واستقلال من جمهور الناخبين؛ وأن كل شخص معايَن يجيب، وبصدق، وأن $p$ لا يتحرك أثناء الاستطلاع. وتخرق الاستطلاعات الحقيقية الفرضيات الثلاث: فالمستجيبون القابلون للوصول والراغبون في الإجابة ليسوا عينة منتظمة (فهناك تحيز الاختيار وتحيز عدم الاستجابة)، وقد تكون الإجابات غير صادقة أو غير مستقرة. وهذه أخطاء تحيز: فهي تزيح $\E(\widehat p_n)$ عن $p$ بمقدار مستقل عن $n$ ، ومنه فلا حجم عينة يخفضها — ولا تتحكم رياضيات هذا الجزء إلا في حد التقلب.

17. تشيبيشيف من أجل مجموعة واحدة حجمها $m$ : $\P(\abs{ \widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ من أجل $m \geq \frac2{\delta^2}$ . فإذا أخطأت أقل من $k/2$ مجموعة، وقع أكثر من $k/2$ من القيم $\widehat p^{(i)}$ في الفترة المفتوحة $\intoo{p - \delta}{p + \delta}$ ، ووقع فيه وسيطها أيضا؛ ومنه فإن $\{\abs{M - p} \geq \delta\}$ يفرض ما لا يقل عن $\lceil k/2\rceil$ خطأ بين المجموعات المستقلة $k$ . ويعطي حصر الاتحاد على مجموعات المجموعات المخطئة الممكنة وعددها $\binom k{\lceil k/2\rceil}$

\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil} \Bigl(\frac18\Bigr)^{k/2} \leq 2^k\,8^{-k/2} = 2^{-k/2} :

أي تلاشيا أسيا بدلالة عدد المجموعات، مشترى بالتباينات وحدها — وهو مفيد بالضبط عندما تكون الحدود غير محدودة وتكون متراجحة هوفدينغ غير متاحة.

18. بمتراجحة كوشي–شوارتز (المبرهنة 22.19):

\E(X) = \E(X\,\mathbf 1_{X>0}) \leq \sqrt{\E(X^2)}\sqrt{\E(\mathbf 1_{X>0}^2)} = \sqrt{\E(X^2)\,\P(X > 0)} ;

ثم نربّع ونقسم.

19. لنضع $h(a) = I(a) - 2(a - \tfrac12)^2$ . عندئذ $h(\tfrac12) = 0$ ، وينعدم $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ عند $\tfrac12$ ، و

h''(a) = \frac1a + \frac1{1-a} - 4 = \frac{1}{a(1-a)} - 4 \geq 0

لأن $a(1-a) \leq \frac14$ . ومنه فإن $h'$ متزايد انطلاقا من $0$ على $\intco{\frac12}1$ ، ومنه $h' \geq 0$ و $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ ، ويعطي $I''(a) = \frac1{a(1-a)}$ المقدار $I''(\tfrac12) = 4$ ، و $I'''(\tfrac12) = 0$ (فالدالة متناظرة حول $\tfrac12$ )، ومنه $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . ويحصر السؤال 4 عندئذ الذيل الحقيقي من الأسفل بالمقدار $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : فمن أجل $\delta$ الصغيرة يكون أسّ هوفدينغ $2n\delta^2$ مضبوطا مقاربا — ولا تمكن التحسينات إلا بعوامل كثيرة الحدود بدلالة $n$ .

21. ماركوف: عزم واحد، والتلاشي $1/a$ ، وهي مفيدة فقط محركا وراء الأخريات (ويبين السؤال 1 أنها مسطحة). تشيبيشيف: عزمان، والتلاشي $\frac{V}{n\delta^2}$ ، وهي أمثلية دون فرضيات إضافية (المثال 22.18)، وهي أفضل أداة في السؤال 23. العزم من الرتبة الرابعة (التمرين 22.9): التلاشي $C/n^2$ ، وهو بالكاد يكفي من القابلية للجمع من أجل قانون قوي. هوفدينغ: متغيرات محدودة، والتلاشي $2\eu^{-2n\delta^2}$ ، وهي حصان عمل الجزء الثالث. تشيرنوف بالمعدل المضبوط $I(a)$ : عزوم أسية كاملة، وأسّ لا يُهزم (السؤالان 4 و20)، وهو المرجع لكل ما عداه.

22. إذا كانت القطعة متزنة: $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . وإذا كان $p = 0.55$ : $\P(\widehat p_n \leq 0.525) \leq \P(\widehat p_n - 0.55 \leq -0.025) \leq \eu^{-2n(0.025)^2}$ . ويكون الخطآن كلاهما دون $0.01$ عندما $2n(0.025)^2 \geq \ln 100$ ، أي $n \geq 3684.2$ : أي $3685$ رمية. (فالتمييز بين فرضيتين تفصل بينهما $2.5$ نقطة يكلف ما يكلفه التقدير في حدود $\pm2.5$ نقطة.)

23. هوفدينغ: $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . وتشيبيشيف بالتباين الحقيقي $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ — أي أرخص تسع مرات. فأسّ هوفدينغ $2n\delta^2$ يسعّر التباين بأسوأ حالاته $\frac14$ ، وهو تشاؤم سخيف عندما $p = 0.01$ ؛ أما العزم الثاني المتواضع فيعرف أفضل. والأداة الناقصة هي حصر أسي يعي التباين (متراجحة برنشتاين، في السنة الثالثة) — أو، من أجل الأحداث النادرة، تقريب بواسون المبرهن في الفصل 23، الذي يعمل على السلّم النسبي الطبيعي.

24. نثبّت $\delta > 0$ : $\sum_n 2\eu^{-2n\delta^2} < \infty$ (وهي متسلسلة من نوع هندسي)، ومنه تعطي بوريل–كانتيلي 1 (المبرهنة 21.25) المقدار $\P(\abs{\widehat p_n - p} \geq \delta \text{ عددا لانهائيا من المرات}) = 0$ ، أي إن احتمال الحدث $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ هو $1$ من أجل كل $j$ . ويبقى احتمال التقاطع القابل للعد $\bigcap_jE_j$ مساويا $1$ (بالجمعية التحتية على المتممات)، وعليه $\widehat p_n \to p$ : وهو القانون القوي للأعداد الكبيرة من أجل رميات قطعة النقود، مع أداء الحصر الدور الذي أدّاه العزم من الرتبة الرابعة في التمرين 22.9.

25. عزم واحد يشتري حصرا مسطحا؛ وعزمان يشتريان $1/(n\delta^2)$ ، ولا أكثر (بحسب مثال الأمثلية)؛ وأربعة تشتري $1/n^2$ ، وهو يكفي للتلسكب إلى قانون شبه أكيد؛ والحصر يشتري $\eu^{-2n\delta^2}$ ؛ والعزم الأسي الكامل يشتري المعدل المضبوط $I$ ، الذي لا تهزمه أي طريقة. ويكفي استطلاع $2050$ شخص من أجل أي بلد لأن تقلب العينة يحكمه تباين قطعة النقود لا حجم المجتمع — فبطاقتا الثمن $1/\delta^2$ و $\ln(1/\alpha)$ شاملتان. وتحل مبرهنة النهاية المركزية في مجلد السنة الثالثة محل هذه المتراجحات، على السلّم $\sqrt n$ ، بقانون نهائي مضبوط بثوابت صريحة — فتحول كل حصر في هذه المسألة إلى مساواة مقاربة.

المصطلحات المعرَّفة في هذا الفصل

عرض كل المصطلحات (395) في المسرد