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

23الدوال المولّدة للاحتمالات

تعود متسلسلات القوى في الفصل 11 بمهمة احتمالية: فنربط بمتغير عشوائي ذي قيم في $\N$ متسلسلةَ القوى ذات المعاملات $\P(X = n)$ . وتحوّل هذه الدالة المولّدة مجاميع المتغيرات المستقلة إلى جداءات، والعزوم إلى مشتقات عند $1$ ، والمتطابقات التوفيقية الصعبة إلى ضرب من سطر واحد. ويختم الفصل الكتاب بقطعتين معروضتين: تقريب بواسون للأحداث النادرة، ومحك الانقراض من أجل مسارات التفرع — وهو حساب احتمالي لانهائي حقا يُحل كله بهندسة منحن محدب.

23.1 التعريف والخواص الأساسية

تعريف 23.1 (الدالة المولّدة للاحتمالات)

ليكن $X$ متغيرا عشوائيا ذا قيم في $\N$ ، $p_n = \P(X = n)$ . الدالة المولّدة للاحتمالات للمتغير $X$ هي مجموع متسلسلة القوى

G_X(t) = \E\bigl(t^X\bigr) = \sum_{n=0}^{\infty} p_n\,t^n .

مثال 23.2 (ردود الفعل الأولى)

للمتغير الثابت $X = c$ الدالة $G_X(t) = t^c$ ؛ والإزاحة تحقق $G_{X+c}(t) = t^c\,G_X(t)$ ؛ والتقويم عند نقط خاصة يقرأ معلومات دون أي نشر: $G_X(0) = \P(X = 0)$ ، $G_X(1) = 1$ ، و $G_X(-1) = \P(X\text{ زوجي}) - \P(X\text{ فردي})$ ، وهو ميزان الزوجية المستغل في التمرين 23.10. وتُستعمل هذه الأسطر المفردة بصمت في كل ما يلي — والتقويم $G_X(0)$ هو بالضبط كيف ستُستخرج احتمالات الانقراض من الدوال المولّدة المكررة في نهاية الفصل.

قضية 23.3 (نصف القطر والخواص الأولى)

للمتسلسلة التي تعرّف $G_X$ نصف قطر تقارب $\geq 1$ ؛ والدالة $G_X$ معرَّفة ومتصلة على $\intcc{-1}{1}$ ، ومن الصنف $\mathcal{C}^\infty$ على $\intoo{-1}{1}$ ، مع $G_X(1) = 1$ و $\abs{G_X(t)} \leq 1$ هناك. وعلاوة على ذلك تحدد $G_X$ قانون $X$ :

p_n = \frac{G_X^{(n)}(0)}{n!} .

برهان. بما أن $\sum p_n = 1$ متقاربة، فإن الحدود $p_n\,1^n$ محدودة، ومنه فنصف القطر $\geq 1$ (بمبرهنة آبل المساعدة، الفصل 11)؛ وعند $t = \pm1$ تتقارب المتسلسلة تقاربا مطلقا (فالمقدار $\sum p_n = 1$ يهيمن)؛ بل أفضل من ذلك، على الفترة $\intcc{-1}1$ كلها،

\sup_{\abs t\leq1}\,\abs{p_nt^n} = p_n \quad\text{مع}\quad \sum_np_n < \infty :

فالمتسلسلة تتقارب تقاربا ناظميا على $\intcc{-1}1$ ، ومنه فمجموعها متصل هناك (المبرهنات 10.16 و10.4). أما الملاسة في الداخل وصيغة المعاملات فهما النظرية العامة لمتسلسلات القوى؛ وبما أن المعاملات قابلة للاستعادة، فإن لمتغيرين لهما الدالة المولّدة نفسها القانون نفسه. ∎

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

برنولي $\mathcal{B}(p)$ : $G(t) = 1 - p + pt$ .
ثنائي الحد $\mathcal{B}(n, p)$ : $G(t) = \sum_k \binom nk (pt)^k(1-p)^{n-k} = (1 - p + pt)^n$ (بمبرهنة ذات الحدين).
الهندسي $\mathcal{G}(p)$ : $G(t) = \sum_{k\geq1}(1-p)^{k-1}p\,t^k = \dfrac{pt}{1 - (1-p)t}$ (بنصف قطر $\frac{1}{1-p} > 1$ ).
بواسون $\mathcal{P}(\lambda)$ : $G(t) = \sum_k e^{-\lambda}\frac{(\lambda t)^k}{k!} = e^{\lambda(t - 1)}$ (بنصف قطر $\infty$ ).

مثال 23.5 (مكاملة الدالة المولّدة)

تعطي مشتقات $G_X$ عند $1$ العزوم الموجبة؛ أما التكامل فيعطي عزما سالبا. انطلاقا من $\int_0^1t^k\dd t = \frac1{k+1}$ وبالمكاملة حدا حدا (بالتقارب الناظمي على $\intcc01$ ):

\int_0^1G_X(t)\,\dd t = \sum_{k\geq0}\frac{\P(X = k)}{k+1} = \E\Bigl(\frac1{1+X}\Bigr).

ومن أجل $X \sim \mathcal P(\lambda)$ :

\E\Bigl(\frac1{1+X}\Bigr) = \int_0^1\eu^{\lambda(t-1)}\,\dd t = \frac{1 - \eu^{-\lambda}}{\lambda},

فنستعيد في سطر واحد حساب المتسلسلة في المثال 22.10. فالدالة المولّدة أداة ذات اتجاهين: نفاضل عند $1$ من أجل العزمين $\E(X)$ و $\E(X(X-1))$ ، ونكامل على $\intcc01$ من أجل $\E\bigl(\frac1{1+X}\bigr)$ — كائن تحليلي واحد، يُستجوب في أي اتجاه تحتاج إليه المسألة.

مثال 23.6 (قانون نصف قطره يساوي واحدا بالضبط)

لنضع $\P(X = k) = \dfrac{6}{\pi^2k^2}$ من أجل $k \geq 1$ — وهو قانون احتمال بحكم متطابقة بازل (المثال 14.12). ولدالته المولّدة $G(t) = \frac6{\pi^2}\sum_{k\geq1}\frac{t^k}{k^2}$ نصف قطر تقارب يساوي $1$ بالضبط: فالحصر العام “نصف القطر $\geq 1$ ” في القضية 23.3 لا يمكن تحسينه. والمتوسط هو

\sum_{k\geq1}k\,\P(X = k) = \frac6{\pi^2}\sum_{k\geq1}\frac1k = \infty :

فالدالة $G$ متصلة على $\intcc{-1}1$ ، وملساء في الداخل، لكن مشتقتها تنفجر عند $1^-$ — فالتمثيل البياني يصل إلى النقطة $(1, 1)$ بمماس شاقولي. فالذيول الثقيلة مرئية هندسيا على الدالة المولّدة، عند النقطة الوحيدة $t = 1$ ؛ وتجعل مبرهنة العزوم أدناه هذا التقابل مضبوطا.

مبرهنة 23.7 (العزوم من الدالة المولّدة)

يقبل $X$ أملا رياضيا إذا وفقط إذا كانت $G_X$ قابلة للتفاضل عند $1^-$ (بالمشتقة اليسرى، وهي منتهية)، وعندئذ $\E(X) = G_X'(1)$ . وبالمثل يقبل $X$ عزما من الرتبة الثانية إذا وفقط إذا كانت $G_X$ قابلة للتفاضل مرتين عند $1^-$ ، وعندئذ

\E\bigl(X(X - 1)\bigr) = G_X''(1), \qquad V(X) = G_X''(1) + G_X'(1) - G_X'(1)^2 .

برهان. من أجل $t \in \intoo{0}{1}$ ، تعطي المفاضلة حدا حدا داخل القرص $G_X'(t) = \sum_{n\geq1} np_n t^{n-1}$ ، وهي متسلسلة ذات معاملات موجبة: ومنه فإن $t \mapsto G_X'(t)$ غير متناقصة على $\intoo{0}{1}$ ، وبالتقارب الرتيب للمجاميع الجزئية (أو بمبرهنة آبل من أجل المعاملات الموجبة، الفصل 11)،

\lim_{t \to 1^-} G_X'(t) = \sum_{n\geq1} n\,p_n \in \intcc{0}{+\infty} ,

ويكون كل طرف منتهيا بالضبط عندما يكون الآخر كذلك. وعندما يكون منتهيا، تحصر مبرهنة القيمة المتوسطة نسب الفروق $\frac{G_X(1) - G_X(t)}{1 - t}$ بين قيم $G_X'$ ، ومنه فإن $G_X$ قابلة للتفاضل عند $1^-$ مع $G_X'(1) = \sum np_n = \E(X)$ (بمبرهنة النقل). أما النص من الرتبة الثانية فيكرر الحجة درجة أعلى: فالمقدار $G''_X(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ غير متناقص على $\intoo01$ ونهايته الرتيبة $\sum_nn(n-1)p_n = \E(X(X-1))$ ، وهو منته بالضبط عندما يقبل $X$ عزما من الرتبة الثانية. وتنتج صيغة التباين عندئذ من صيغة كونيغ–هويغنز:

V(X) = \E(X^2) - \E(X)^2 = \E\bigl(X(X-1)\bigr) + \E(X) - \E(X)^2 = G''_X(1) + G'_X(1) - G'_X(1)^2 .

∎

مثال 23.8

بواسون: $G'(t) = \lambda e^{\lambda(t-1)}$ ، ومنه $\E(X) = \lambda$ ؛ و $G''(1) = \lambda^2$ ، ومنه $V(X) = \lambda^2 + \lambda - \lambda^2 = \lambda$ — أي حسابا الفصل 22 في سطر واحد لكل منهما.

مثال 23.9 (منوال قانون بواسون)

أين يكون $\P(X = k)$ أكبر ما يكون من أجل $X \sim \mathcal P(\lambda)$ ؟ تُقارن الأوزان المتتالية عبر النسبة

\frac{\P(X = k+1)}{\P(X = k)} = \frac{\lambda}{k + 1} ,

التي تتجاوز $1$ ما دام $k < \lambda - 1$ وتهبط دون $1$ بمجرد أن $k > \lambda - 1$ : فالأوزان تصعد ثم تهبط، والمنوال $\floor\lambda$ (مع تساو بين $\lambda - 1$ و $\lambda$ عندما يكون $\lambda$ عددا صحيحا: فمن أجل $\lambda = 3$ ، $\P(X = 2) = \P(X = 3) = \frac92\eu^{-3} \approx 0.224$ ). واختبارات النسب على المعاملات كثيرا ما تكون أسرع طريق إلى حقائق نوعية عن قانون متقطع — دون حاجة إلى دالة مولّدة، لكن المعاملات هي الدالة المولّدة، مقروءة حدا حدا.

23.2 مجاميع المتغيرات المستقلة

مبرهنة 23.10 (الضربية)

إذا كان $X$ و $Y$ متغيرين عشوائيين مستقلين ذوي قيم في $\N$ ، فإن

G_{X + Y}(t) = G_X(t)\,G_Y(t) \qquad (\abs t \leq 1),

وبالتراجع $G_{X_1 + \dots + X_n} = \prod_i G_{X_i}$ من أجل متغيرات مستقلة $X_1, \dots, X_n$ .

برهان. برهانان، وكلاهما مفيد. بالآمال الرياضية: المتغيران $t^X$ و $t^Y$ مستقلان ومحدودان، ومنه (المبرهنة 22.11)

G_{X+Y}(t) = \E\bigl(t^{X+Y}\bigr) = \E\bigl(t^X t^Y\bigr) = \E\bigl(t^X\bigr)\E\bigl(t^Y\bigr) .

بجداءات كوشي: قانون $X + Y$ هو الالتفاف $\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k)$ ، ويضرب جداء كوشي للمتسلسلات المتقاربة مطلقا (الفصل 7) متسلسلتي القوى بالضبط وفق هذا الالتفاف. ∎

مثال 23.11 (استقرار القوانين الكلاسيكية)

تُجمع المتغيرات الثنائية المستقلة ذات $p$ نفسه: $(1 - p + pt)^m(1 - p + pt)^n = (1 - p + pt)^{m+n}$ ، ومنه $\mathcal{B}(m, p) + \mathcal{B}(n, p) = \mathcal{B}(m + n, p)$ — وبوجه خاص فإن مجموع $n$ متغير برنولي مستقل ثنائي الحد، وهو ما يعيد البرهان على قانون عدد النجاحات. وتُجمع متغيرات بواسون المستقلة: $e^{\lambda(t-1)}e^{\mu(t-1)} = e^{(\lambda + \mu)(t-1)}$ ، ومنه $\mathcal{P}(\lambda) + \mathcal{P}(\mu) = \mathcal{P}(\lambda + \mu)$ — أي حساب الالتفاف في التمرين 22.2، دون حساب الآن.

مثال 23.12 (نردان، وكثير حدود واحد مربّع)

من أجل نرد متزن واحد، $G(t) = \frac{t + t^2 + \dots + t^6}{6}$ ؛ ومن أجل مجموع نردين،

G(t)^2 = \frac{1}{36}\bigl(t^2 + 2t^3 + 3t^4 + 4t^5 + 5t^6 + 6t^7 + 5t^8 + 4t^9 + 3t^{10} + 2t^{11} + t^{12}\bigr) :

أي القانون المثلثي لمجاميع النرد (فالمنوال $7$ باحتمال $\frac6{36} = \frac16$ )، مقروءا من مربع كثير حدود يُنشر مرة واحدة في العمر. وكانت صيغة الالتفاف ستتطلب إحدى عشرة حجة عد منفصلة؛ أما الدالة المولّدة فتنجزها كلها في آن واحد، لأن ضرب كثيرات الحدود هو التفاف المعاملات. وهذه الترجمة الآلية — من القوانين إلى المعاملات، ومن المجاميع إلى الجداءات — هي نموذج عمل الفصل كله، ويدفعها التمرين 23.11 إلى نردي سيشرمان المدهشين.

مثال 23.13 (ثلاثة نرد واستخراج معامل)

من أجل مجموع $S$ لثلاثة نرد متزنة، يكون $\P(S = 10)$ معامل $t^{10}$ في $\bigl(\frac{t + \dots + t^6}6\bigr)^3$ . ونفكك وننشر بمتسلسلتي ذات الحدين والهندسية:

\Bigl(\frac{t(1 - t^6)}{6(1 - t)}\Bigr)^{\!3} = \frac{t^3}{216}\,\bigl(1 - 3t^6 + 3t^{12} - t^{18}\bigr)\sum_{j\geq0}\binom{j+2}2t^j .

ويقتضي معامل $t^{10}$ أخذ $t^7$ من الجداء: $j = 7$ مع الحد $1$ ، و $j = 1$ مع الحد $-3t^6$ :

\P(S = 10) = \frac{1}{216}\Bigl(\binom92 - 3\binom32\Bigr) = \frac{36 - 9}{216} = \frac{27}{216} = \frac18 .

والإحصاء المباشر للثلاثيات وعددها $27$ كثير الأخطاء؛ أما الجبر فآلي ويتحاكى مع أي عدد من النرد — فالاحتواء والاستبعاد الظاهر في $(1 - t^6)^3$ يقوم بمناقشة الحالات تلقائيا.

مثال 23.14 (قراءة قانون من دالته المولّدة)

أي قانون دالته المولّدة $G(t) = \dfrac1{2 - t}$ ؟ ننشره في متسلسلة قوى:

\frac{1}{2 - t} = \frac12\cdot\frac1{1 - t/2} = \sum_{k\geq0}\frac{t^k}{2^{k+1}} :

فالمعاملات موجبة ومجموعها $G(1) = 1$ ، ومنه فهذا قانون حقيقي، $\P(X = k) = 2^{-(k+1)}$ على $\N$ — أي قانون هندسي يبدأ عند $0$ . وبالوحدانية (القضية 23.3)، لا يشترك أي قانون آخر في هذه الدالة $G$ . والتعرف على القوانين من دوالها المولّدة مهارة تستحق التمرين: فهي كيف يُكشف المكرَّر التفرعي الحرج $G_n(t) = \frac{n - (n-1)t}{n+1 - nt}$ في مسألة نهاية الأسبوع على أنه قانون هندسي مشروط بالبقاء.

ملاحظة 23.15

يسير الاستقرار في اتجاه واحد فقط: فمجاميع متغيرات بواسون المستقلة بواسونية، أما الفروق فلا — إذ يأخذ $X - Y$ قيما سالبة، ومنه فليس له أي دالة مولّدة، ويقع قانونه (توزيع سكيلام) خارج عدة هذا الفصل. وبالمثل فإن $\mathcal B(m, p) + \mathcal B(n, p')$ مع $p \neq p'$ ليس ثنائي الحد: فللجداء $(1 - p + pt)^m(1 - p' + p't)^n$ موضعا جذر متمايزان، بينما لكل دالة مولّدة ثنائية الحد جذر مضاعف وحيد. وقراءة الاستقرار من أنماط الجذور استعراض صغير لمقدار البنية التي يرمّزها كثير الحدود.

ملاحظة 23.16 (مرشح جذور الوحدة)

التقويم عند $-1$ يفصل الزوجي عن الفردي؛ والتقويم عند جميع جذور الوحدة من الرتبة $m$ يفصل كل صف بواق: فمع $\omega = \eu^{2\iu\pi/m}$ ،

\P(X \equiv r \bmod m) = \frac1m\sum_{j=0}^{m-1}\omega^{-jr}\,G_X(\omega^j),

لأن متوسط $\omega^{j(k-r)}$ على $j$ يعطي $1$ إذا كان $k \equiv r$ و $0$ فيما عدا ذلك. ومثال على العائد: من أجل مجموع $S$ لنردين متزنين، يكون كل $G(\omega^j) = \frac16\sum_{k=1}^6 \omega^{jk} = -\frac16$ من أجل $j \neq 0$ (فمجموع جذور الوحدة السبعة من الرتبة السابعة معدوم)، ومنه

\P(7 \mid S) = \frac17\Bigl(1 + 6\cdot\frac1{36}\Bigr) = \frac16 ,

وهو ما يؤكد العد في المثال 23.12 — والطريقة تتحاكى مع أسئلة لا يتحاكى معها العد المباشر.

مبرهنة 23.17 (المجاميع العشوائية: متطابقة فالد من أجل الدوال المولّدة)

لتكن $(X_k)_{k\geq1}$ متغيرات مستقلة ذات قيم في $\N$ لها القانون نفسه والدالة المولّدة $G_X$ ، وليكن $N$ متغيرا ذا قيم في $\N$ مستقلا عن المتغيرات $X_k$ ، ودالته المولّدة $G_N$ . عندئذ يكون للمجموع العشوائي $S = X_1 + \dots + X_N$ (مع $S = 0$ عندما $N = 0$ ) الدالة المولّدة

G_S = G_N \circ G_X .

وبوجه خاص، إذا قبل $N$ و $X_1$ أملين رياضيين، فإن $\E(S) = \E(N)\,\E(X_1)$ .

برهان. نشترط على $N$ (بالاحتمالات الكلية، المبرهنة 21.14): فمن أجل $\abs t \leq 1$ ،

G_S(t) = \sum_{n=0}^\infty \P(N = n)\, \E\bigl(t^{X_1 + \dots + X_n}\bigr) = \sum_{n=0}^\infty \P(N = n)\,G_X(t)^n = G_N\bigl(G_X(t)\bigr),

باستعمال الضربية من أجل كل $n$ ثابتة وقابلية جمع العائلة المزدوجة كلها ( $\abs{G_X(t)} \leq 1$ ). وتبديل ترتيب الجمع هو مبرهنة فوبيني من أجل العائلات القابلة للجمع (الفصل 7). وبالمفاضلة عند $1^-$ بقاعدة السلسلة والمبرهنة 23.7: $\E(S) = G_N'(G_X(1))\,G_X'(1) = G_N'(1)G_X'(1) = \E(N)\E(X_1)$ . ∎

مثال 23.18 (بواسون المركب: خسائر التأمين السنوية)

تتلقى شركة تأمين $N \sim \mathcal P(\lambda)$ مطالبة في السنة، وتكلف كل مطالبة $X_k$ (بوحدات صحيحة، مستقلة ومتماثلة التوزيع، دالتها المولّدة $G_X$ ، ومتوسطها $\mu$ ، ومستقلة عن $N$ ). وبحسب المبرهنة 23.17، يكون للخسارة الكلية $S$

G_S(t) = \eu^{\lambda(G_X(t) - 1)}, \qquad \E(S) = \lambda\mu ,

وبالمفاضلة مرتين عند $1^-$ :

V(S) = \lambda\,G_X''(1) + \lambda^2\mu^2 + \lambda\mu - (\lambda\mu)^2 = \lambda\,\E(X^2) .

ويتضمن التباين العزم الثاني لمطالبة واحدة، لا تباينها: فمجموع بواسون المركب يشعر بالمطالبة الكبيرة العارضة مرتين — مرة عبر كم عددها، ومرة عبر كم حجمها. ومن أجل $\lambda = 10$ مطالبة ذات قانون هندسي متوسطه $2$ ( $\E X^2 = 6$ ): $\E S = 20$ ، $V(S) = 60$ ، وتعطي متراجحة تشيبيشيف (الفصل 22) هوامش ملاءة قابلة للاستعمال أصلا. وهذا النمط من “المجموع الموقوف عشوائيا” هو النمط نفسه الذي سيقود التراجع التفرعي في القضية 23.23: فتركيب الدوال المولّدة هو جبر المجتمعات العشوائية.

ملاحظة 23.19

استقلال $N$ عن الحدود ليس زينة. خذ $X_k \in \{0, 2\}$ بالاحتمالات نفسها واجعل $N = X_1$ (وهو متعلق على نحو صارخ): عندئذ يكون $S = X_1 + \dots + X_N$ هو $0$ عندما $X_1 = 0$ ، و $2 + X_2$ عندما $X_1 = 2$ ، ومنه $\E(S) = \frac12(2 + 1) = \frac32$ ، بينما $\E(N)\E(X_1) = 1\cdot1 = 1$ : فمتطابقة فالد تسقط. وعندما يُسمح لعدد الحدود بأن يتفاعل مع الحدود نفسها، تنهار البنية الجدائية النظيفة — والنظرية الكاملة لقواعد “التوقف” هذه هي فصل المارتينغال في مجلد السنة الثالثة.

23.3 تقريب بواسون

مبرهنة 23.20 (قانون الأحداث النادرة)

ليكن $X_n \sim \mathcal{B}(n, p_n)$ مع $n\,p_n \to \lambda > 0$ . عندئذ، من أجل كل $k \in \N$ :

\P(X_n = k) \xrightarrow[n\to\infty]{} e^{-\lambda}\frac{\lambda^k}{k!} :

أي إن القانون الثنائي لأحداث مستقلة نادرة كثيرة يتقارب نحو قانون بواسون ذي الوسيط $\lambda$ .

برهان. بحساب مباشر مع $p_n = \frac{\lambda_n}{n}$ ، $\lambda_n \to \lambda$ :

\P(X_n = k) = \binom nk p_n^k(1 - p_n)^{n-k} = \frac{n(n-1)\cdots(n-k+1)}{n^k}\cdot \frac{\lambda_n^k}{k!}\, \bigl(1 - \tfrac{\lambda_n}{n}\bigr)^{n-k} .

وعندما $n \to \infty$ مع $k$ ثابتة: يؤول العامل الأول إلى $1$ (فهو جداء $k$ عاملا $\to 1$ )؛ و $\lambda_n^k \to \lambda^k$ ؛ و $\bigl(1 - \frac{\lambda_n}{n}\bigr)^{n-k} = \exp\bigl((n-k)\ln(1 - \frac{\lambda_n}{n})\bigr) \to e^{-\lambda}$ لأن $(n - k)\ln\bigl(1 - \frac{\lambda_n}{n}\bigr) \sim -\lambda_n \to -\lambda$ (الفصل 6). وبديلا عن ذلك، على مستوى الدوال المولّدة: $G_{X_n}(t) = \bigl(1 + \frac{\lambda_n(t-1)}{n}\bigr)^n \to e^{\lambda(t - 1)} = G_{\mathcal{P}(\lambda)}(t)$ من أجل كل $t \in [0, 1]$ ثابتة — أي تقارب الدوال المولّدة، وهو مكافئ (من أجل المتغيرات ذات القيم في $\N$ ) لتقارب كل $\P(X_n = k)$ ؛ انظر التمرين 23.9. ∎

ملاحظة 23.21

ولهذا تنمذج قوانين بواسون عدود الأحداث النادرة — الأخطاء المطبعية في الصفحة، والتفككات الإشعاعية في الثانية، والحوادث في اليوم عند تقاطع: فكل فرصة تكاد تكون مهملة، والفرص كثيرة، ولا يبقى في النهاية إلا المعدل المتوسط $\lambda$ .

مثال 23.22 (مشاهدة نهاية بواسون وهي تتقارب)

نثبّت $\lambda = 2$ ونجعل $X_n \sim \mathcal B(n, 2/n)$ . واحتمال عدم وقوع أي حدث هو $\P(X_n = 0) = (1 - 2/n)^n$ بالضبط:

n = 10:\ 0.107, \qquad n = 20:\ 0.122, \qquad n = 50:\ 0.130, \qquad n = 100:\ 0.133,

مقابل النهاية $\eu^{-2} \approx 0.135$ . والتقارب رتيب وسرعته $O(1/n)$ — فبالنشر، $(1 - 2/n)^n = \eu^{-2}\bigl(1 - \tfrac2n + O(n^{-2})\bigr)$ — ومنه فمن أجل $n$ بالمئات يكون نموذج بواسون دقيقا أصلا إلى الرقم الثالث. وهذا هو المضمون العملي لقانون الأحداث النادرة: فالنمذج لا يعرف أبدا $n$ و $p$ على حدة (فكم فرصة مجهرية لخطأ مطبعي تحملها صفحة؟)، بل يعرف جداءهما $\lambda$ وحده، والقانون النهائي لا يتعلق برحمة بأي شيء آخر.

23.4 مسارات التفرع

لننظر في مجتمع ينطلق من سلف واحد؛ ولكل فرد، بصورة مستقلة، عدد عشوائي من الأبناء قانونه $(p_k)_{k \in \N}$ ودالته المولّدة $G$ (وهو قانون النسل). وليكن $Z_n$ حجم الجيل $n$ ( $Z_0 = 1$ )، وليكن $m = G'(1) = \E(Z_1)$ متوسط عدد الأبناء.

قضية 23.23

الدالة المولّدة للمتغير $Z_n$ هي المكرَّر رقم $n$ $G_{Z_n} = G \circ G \circ \dots \circ G$ ( $n$ مرة)، وتحقق احتمالات الانقراض $q_n = \P(Z_n = 0)$

q_0 = 0, \qquad q_{n+1} = G(q_n),

وتتزايد نحو احتمال الانقراض النهائي $q$ ، وهو نقطة ثابتة للدالة $G$ .

برهان. الجيل $n + 1$ هو المجموع العشوائي لنسل أفراد الجيل $n$ وعددهم $Z_n$ ، والعدود مستقلة بعضها عن بعض وعن $Z_n$ : ومنه يعطي المبرهنة 23.17 المقدار $G_{Z_{n+1}} = G_{Z_n} \circ G$ ، ويعطي التراجع انطلاقا من $G_{Z_0}(t) = t$ المكرَّر $n$ مرة — وهو ما يمكن قراءته بالقدر نفسه، بحكم تجميعية التركيب، على الصورة $G_{Z_{n+1}} = G \circ G_{Z_n}$ . وبتقويم هذه الصيغة الثانية عند $0$ : $q_{n+1} = G_{Z_{n+1}}(0) = G\bigl(G_{Z_n}(0)\bigr) = G(q_n)$ . والأحداث $\{Z_n = 0\}$ متزايدة (فالمجتمعات المنقرضة تبقى منقرضة)، ومنه $q_n \uparrow q = \P\bigl(\bigcup_n\{Z_n = 0\}\bigr)$ بالاتصال الرتيب (المبرهنة 21.6)، ويحول اتصال $G$ على $[0, 1]$ المقدار $q_{n+1} = G(q_n)$ إلى $q = G(q)$ عند النهاية. ∎

مثال 23.24 (مشاهدة الانقراض وهو يتقارب)

من أجل قانون النسل $(p_0, p_1, p_2) = (\tfrac14, \tfrac14, \tfrac12)$ في المثال 23.27، لدينا $G(t) = \tfrac14 + \tfrac14t + \tfrac12t^2$ ويعطي التكرار $q_{n+1} = G(q_n)$

q_1 = 0.25, \quad q_2 = 0.34375, \quad q_3 \approx 0.39502, \quad q_4 \approx 0.42678, \quad q_5 \approx 0.44776,

صاعدا نحو احتمال الانقراض $q = \tfrac12$ . والفروق $q - q_n$ هي $0.25$ ، $0.156$ ، $0.105$ ، $0.073$ ، $0.052$ : وكل منها نحو $\tfrac34$ من سابقه، وفعلا تعطي مبرهنة القيمة المتوسطة $q - q_{n+1} = G'(c_n)(q - q_n)$ مع $G'(q) = \tfrac14 + q = \tfrac34$ . وعبرتان: أن لخط عائلة لا يزال حيا عند الجيل $n$ ، وفق الحساب نفسه، احتمال $q - q_n$ في أن يكون محكوما عليه بالفناء لاحقا؛ وأن سرعة تقارب الدرج في الشكل أدناه هي المشتقة عند النقطة الثابتة — وتحول مسألة نهاية الأسبوع الملاحظتين كلتيهما إلى مبرهنتين.

مبرهنة 23.25 (محك الانقراض)

لنفترض $p_1 \neq 1$ . احتمال الانقراض $q$ هو النقطة الثابتة الصغرى للدالة $G$ في $\intcc{0}{1}$ ، ولدينا:

إذا كان $m \leq 1$ (تحت حرج أو حرج)، فإن $q = 1$ : أي إن الانقراض مؤكد؛
إذا كان $m > 1$ (فوق حرج)، فإن $q < 1$ : أي إن المجتمع يبقى إلى الأبد باحتمال موجب $1 - q$ .

برهان. $G$ محدبة على $\intcc{0}{1}$ (فهي متسلسلة قوى ذات معاملات موجبة: $G'' \geq 0$ )، وغير متناقصة، مع $G(1) = 1$ .

النقطة الثابتة الصغرى: لتكن $r \in \intcc{0}{1}$ نقطة ثابتة كيفما كانت. عندئذ $q_0 = 0 \leq r$ ، وبالتراجع $q_{n+1} = G(q_n) \leq G(r) = r$ (بالرتابة): ومنه $q = \lim q_n \leq r$ .

الحالة $m \leq 1$ : لنفترض أن $r < 1$ نقطة ثابتة. فبمبرهنة القيمة المتوسطة على $[r, 1]$ ، يوجد $c \in \intoo{r}{1}$ يحقق $G'(c) = \frac{G(1) - G(r)}{1 - r} = \frac{1 - r}{1 - r} = 1$ . لكن $G'$ غير متناقصة (بالتحدب) و $\lim_{t\to1^-}G'(t) = m \leq 1$ ، ومنه $G' \leq 1$ على $\intoo{0}{1}$ ؛ وتفرض المساواة $G'(c) = 1$ عندئذ أن تكون $G'$ ثابتة تساوي $1$ على $\intco{c}{1}$ ، ومنه $G'' = \sum n(n-1)p_nt^{n-2} \equiv 0$ هناك. ومتسلسلة قوى ذات معاملات موجبة تنعدم على فترة تكون هذه المعاملات كلها معدومة: $p_n = 0$ من أجل $n \geq 2$ ، ومنه $G(t) = p_0 + p_1t$ و $1 = G'(c) = p_1$ — وهو ما يناقض الفرضية $p_1 \neq 1$ . ومنه فإن $1$ هي النقطة الثابتة الوحيدة: $q = 1$ .

الحالة $m > 1$ : بجوار $1$ ، لمشتقة $G(t) - t$ القيمة $G'(t) - 1 \to m - 1 > 0$ عندما $t \to 1^-$ ، ومنه $G(t) - t < G(1) - 1 = 0$ على فترة ما $\intoo{1 - \delta}{1}$ : فالدالة المتصلة $G(t) - t$ تساوي $\geq 0$ عند $t = 0$ ( $G(0) = p_0 \geq 0$ ) وتكون $< 0$ تحت $1$ مباشرة، ومنه فهي تنعدم عند $r < 1$ ما (بمبرهنة القيم الوسطى). والنقطة الثابتة الصغرى عندئذ $q \leq r < 1$ . ∎

احتمالات الانقراض بوصفها تكرارا لنقطة ثابتة q_n+1 = G(q_n) انطلاقا من q_0 = 0 (بالدرج الأحمر). على اليسار: قانون نسل تحت حرج — فالمنحنى المحدب يبقى فوق القطر، ويصعد التكرار إلى النقطة الثابتة الوحيدة 1. وعلى اليمين: قانون فوق حرج — فالمنحنى يعبر القطر عند q < 1، حيث يتوقف التكرار: فاحتمال البقاء 1 - q > 0. — **شكل 23.1.** احتمالات الانقراض بوصفها تكرارا لنقطة ثابتة $q_{n+1} = G(q_n)$ انطلاقا من $q_0 = 0$ (بالدرج الأحمر). على اليسار: قانون نسل تحت حرج — فالمنحنى المحدب يبقى فوق القطر، ويصعد التكرار إلى النقطة الثابتة الوحيدة $1$ . وعلى اليمين: قانون فوق حرج — فالمنحنى يعبر القطر عند $q < 1$ ، حيث يتوقف التكرار: فاحتمال البقاء $1 - q > 0$ .

ملاحظة 23.26 (كيف تقرأ مخطط بيت العنكبوت)

في الشكل، تطبّق حركة شاقولية الدالة $G$ (من $(q_n, q_n)$ صعودا إلى $(q_n, G(q_n))$ )، وتحوّل حركة أفقية نحو القطر الخرج إلى دخل: فالدرج هو التراجع $q_{n+1} = G(q_n)$ . ولا يترك تحدب $G$ و $G(1) = 1$ إلا هندستين. فإما أن يبقى المنحنى فوق القطر على $\intco01$ (بمتوسط $m \leq 1$ ): فلا يجد الدرج موضعا يتوقف عنده قبل $1$ . وإما أن يعبر المنحنى عند $q < 1$ ما ( $m > 1$ ): فينحصر الدرج تحت نقطة العبور ويتقارب نحوها، بالمعدل الهندسي $G'(q) < 1$ المقيس في المثال 23.24. وكل تحليل مبرهنة الانقراض مرئي في هذه الصورة الواحدة — ولهذا تستحق أن تُرسم قبل الحساب.

مثال 23.27

قانون النسل: لا ابن، أو ابن واحد، أو ابنان بالاحتمالات $\frac14, \frac14, \frac12$ . عندئذ $m = \frac14 + 1 = \frac54 > 1$ و $G(t) = \frac14 + \frac14 t + \frac12 t^2$ . والنقط الثابتة: $\frac12 t^2 - \frac34 t + \frac14 = 0$ ، أي $2t^2 - 3t + 1 = (2t - 1)(t - 1) = 0$ : $q = \frac12$ . فينقرض خط العائلة باحتمال $\frac12$ — وباحتمال $\frac12$ يعيش إلى الأبد.

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

هذا الفصل مفترق طرق الكتاب، وقد وصل كل مكوّن من مكان مسمى: فجبر المتسلسلات من الفصل 7 والفصل 11، والاحتمالات من الفصل 21 (فالاتصال الرتيب يبرهن على $q_n \uparrow q$ ) ومن الفصل 22 (فالمقدار $G_X = \E(t^X)$ أمل رياضي، والضربية هي مبرهنة الجداء)، والتحدب من الفصل 8 عبر الفصل 17. بل حتى أمراض الذيول الثقيلة متصلة: فلمتغير سان بطرسبورغ في الفصل السابق الدالة $G(t) = \sum_k2^{-k}t^{2^k}$ ، وهي متسلسلة متقاربة تماما على $\intcc01$ لكن مشتقتها عند $1^-$ متباعدة — أي متوسط لانهائي، مرئي في لمحة. كائن واحد، وكل أدوات السنة: فصل أخير لائق.

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

(1) لا تنطبق الدوال المولّدة إلا على المتغيرات ذات القيم في $\N$ : ففي حالة المتغيرات ذات الإشارة أو غير الصحيحة يفقد الكائن $\E(t^X)$ بنيته بوصفه متسلسلة قوى (وتستبدل به السنة الثالثة تحويلات ملائمة للفضاء $\R$ ). (2) التحقق الأول من أي $G$ محسوبة هو $G(1) = 1$ ؛ والثاني هو أن تكون المعاملات موجبة — فالمعامل السالب يعني زلة جبرية لا قانونا جديدا. (3) وفي المجاميع العشوائية يهم ترتيب التركيب: $G_S = G_N \circ G_X$ ، فالدالة الخارجية هي التي تعد الحدود؛ والتركيب في الاتجاه الآخر بلا معنى (فالمقدار $G_X \circ G_N$ سيعد عناصر العناصر). (4) وتحتاج الضربية إلى الاستقلال وإلى مصادر عشوائية متمايزة: $G_{2X}(t) = G_X(t^2)$ ، لا $G_X(t)^2$ . (5) والمفاضلة عند $1$ عملية حدية: فعندما يكون نصف القطر $1$ بالضبط، كما في المثال 23.6، قد يكون $G'(1^-)$ لانهائيا، ولا تكون صياغة مبرهنة العزوم بالنهاية الرتيبة تنطعا بل هي النص الصادق.

ختام المجلد

الدالة المولّدة كائن ختامي لائق بهذا الكتاب: فهي في آن واحد متسلسلة قوى (الفصل 11)، وأداة من أدوات العائلات القابلة للجمع (الفصل 7)، وأمل رياضي (الفصل 22)، ودالة محدبة تقرر هندستها الانقراض (الفصل 8)، وتكرار نقطة ثابتة (الفصل 4). فرياضيات السنة الثانية موضوع واحد. وسيفتح مجلد السنة الثالثة الأبواب المتروكة مغلقة عمدا هنا: تكامل لوبيغ (فيسدد مبرهنة التقارب المهيمن في الفصل 9)، والاحتمالات بمعنى نظرية القياس على الفضاءات غير القابلة للعد، والبرهان الكامل لمبرهنة الدالة العكسية (الفصل 15) في إطار الهندسة التفاضلية.

23.5 تمارين

تمرين 23.1 ★

احسب الدالة المولّدة للقانون المنتظم على $\{1, 2, \dots, 6\}$ (أي نرد متزن). وبيّن أن مجموع نردين متزنين لا يمكن أن يكون منتظما على $\{2, \dots, 12\}$ : فكك $G_{X+Y}$ وعدّ الجذور. (فمجموع منتظم كان سيفرض $G_X(t)G_Y(t) = \frac{t^2}{11}\sum_{k=0}^{10}t^k$ ، وجذوره غير المعدومة هي جذور الوحدة من الرتبة $11$ عدا $1$ — ولا واحد منها حقيقي — بينما $G_X/t$ و $G_Y/t$ كثيرا حدود حقيقيان درجتهما $5$ ، ولكل منهما جذر حقيقي واحد على الأقل.)

حل

حل التمرين 23.1.

النرد المتزن: $G(t) = \frac16(t + t^2 + \dots + t^6) = \frac t6(1 + t + \dots + t^5)$ . فلو كان مجموع نردين متزنين منتظما على $\{2, \dots, 12\}$ ، لكان

G(t)^2 = \frac{t^2}{36}\,h(t)^2 = \frac{t^2}{11}\sum_{k=0}^{10}t^k , \qquad h(t) = 1 + t + \dots + t^5 .

والآن فإن $h$ كثير حدود حقيقي درجته فردية $5$ ، ومنه فله جذر حقيقي (بمبرهنة القيم الوسطى؛ وبصورة ملموسة $h(-1) = 0$ )، ومنه فللمقدار $h^2$ جذر حقيقي. لكن $\sum_{k=0}^{10}t^k$ ليس له أي جذر: فهو موجب من أجل $t \geq 0$ ، ومن أجل $t < 0$ يساوي $\frac{t^{11} - 1}{t - 1}$ ، وهو خارج قسمة عددين سالبين. وهو تناقض — فمجموع نردين متزنين لا يكون منتظما أبدا (كما يؤكد التوزيع المثلثي المألوف لمجاميع النرد).

تمرين 23.2 ★

باستعمال الدوال المولّدة، استعد $\E$ و $V$ من أجل القانونين الثنائي والهندسي (المبرهنة 23.7).

حل

حل التمرين 23.2.

ثنائي الحد: $G(t) = (1 - p + pt)^n$ ، $G'(t) = np(1 - p + pt)^{n-1}$ ، $G''(t) = n(n-1)p^2(1 - p + pt)^{n-2}$ ، ومنه

\E(X) = G'(1) = np, \qquad V(X) = G''(1) + G'(1) - G'(1)^2 = n(n-1)p^2 + np - n^2p^2 = np(1-p).

الهندسي ( $q = 1 - p$ ): $G(t) = \frac{pt}{1 - qt}$ ، ومنه $G'(t) = \frac{p}{(1 - qt)^2}$ و $G''(t) = \frac{2pq}{(1 - qt)^3}$ ؛ وعند $t = 1$ (باستعمال $1 - q = p$ ):

\E(X) = \frac{p}{p^2} = \frac1p, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{2q + p - 1}{p^2} = \frac{q}{p^2} ,

وهو يوافق التمرين 22.1 بعمل أقل.

تمرين 23.3 ★

نردان مزيَّفان: هل يمكن تزييف نردين (بصورة مستقلة، متماثلة أو غير متماثلة) بحيث يكون مجموعهما منتظما على $\{2, \dots, 12\}$ ؟ (بعائق التفكيك نفسه في التمرين 23.1: فالجواب لا، حتى بتزييفين مختلفين، لأن لكل عامل $G_X(t)/t$ درجة فردية $5$ ، ومنه جذر حقيقي، بينما الهدف بلا جذر حقيقي.)

حل

حل التمرين 23.3.

لا، حتى بتزييفين مختلفين. لنفترض أن $X, Y$ قانونان على $\{1, \dots, 6\}$ مجموعهما منتظم. عندئذ $G_X(t) = t\,a(t)$ و $G_Y(t) = t\,b(t)$ حيث $a, b$ كثيرا حدود حقيقيان درجتهما $5$ على الأكثر — ويجب أن يكون مجموع درجتيهما $10$ (فالمجموع يبلغ $12$ باحتمال موجب)، ومنه $\deg a = \deg b = 5$ ، وكلتاهما فردية. وكما في التمرين 23.1، فإن

a(t)\,b(t) = \frac{1}{11}\sum_{k=0}^{10}t^k

سيفرض جذرا حقيقيا في الطرف الأيسر (فلكل كثير حدود حقيقي درجته فردية جذر) ولا جذر في الطرف الأيمن. ومنه فلا تزييف لنردين مستقلين — متماثل أو غير متماثل — ينتج مجموعا منتظما.

تمرين 23.4 ★★

لتكن $X_1, X_2, \dots$ متغيرات برنولي مستقلة $\mathcal{B}(p)$ وليكن $N \sim \mathcal{P}(\lambda)$ مستقلا عنها. بيّن، عبر المبرهنة 23.17، أن $S = X_1 + \dots + X_N \sim \mathcal{P}(\lambda p)$ : أي إن عددا بواسونيا من العناصر، يُحتفظ بكل منها باحتمال $p$ ، يترك عددا بواسونيا — وهو الترقيق. واحسب أيضا قانون العدد المهمل وتأمل: فهو $\mathcal{P}(\lambda(1-p))$ ، ويمكن أن نبين أنه مستقل عن $S$ .

حل

حل التمرين 23.4.

بحسب المبرهنة 23.17 مع $G_N(s) = e^{\lambda(s-1)}$ و $G_X(t) = 1 - p + pt$ :

G_S(t) = e^{\lambda(1 - p + pt - 1)} = e^{\lambda p(t - 1)} :

$S \sim \mathcal{P}(\lambda p)$ . والعدد المهمل $D = N - S$ يعد العناصر نفسها محتفظا بها باحتمال $1 - p$ ، ومنه بالحساب نفسه $D \sim \mathcal{P}(\lambda(1 - p))$ . والاستقلال، مباشرة: من أجل $j, k \in \N$ ،

\begin{align*} \P(S = j,\ D = k) &= \P(N = j + k)\,\binom{j+k}{j}p^jq^k = e^{-\lambda}\frac{\lambda^{j+k}}{(j+k)!}\, \frac{(j+k)!}{j!\,k!}\,p^jq^k\\ &= \Bigl(e^{-\lambda p}\frac{(\lambda p)^j}{j!}\Bigr) \Bigl(e^{-\lambda q}\frac{(\lambda q)^k}{k!}\Bigr) \end{align*}

مع $q = 1 - p$ : فالقانون المشترك يتفكك على الصورة $\mathcal{P}(\lambda p) \otimes \mathcal{P}(\lambda q)$ . فتدفق بواسوني مقسوم عشوائيا يعطي تدفقين بواسونيين مستقلين — وهي معجزة صغيرة تُستعمل باستمرار في نظرية الطوابير.

تمرين 23.5 ★★

(ثنائي الحد السالب) ليكن $T_r$ عدد الرميات اللازمة للحصول على $r$ صورة (باحتمال صورة $p$ ). اكتب $T_r$ مجموعا لمتغيرات هندسية مستقلة عددها $r$ ، واستنتج

G_{T_r}(t) = \Bigl(\frac{pt}{1 - (1-p)t}\Bigr)^{r}, \qquad \E(T_r) = \frac rp, \qquad V(T_r) = \frac{r(1-p)}{p^2},

وانشر $G_{T_r}$ لإيجاد $\P(T_r = n) = \binom{n-1}{r-1} p^r(1-p)^{n-r}$ .

حل

حل التمرين 23.5.

أزمنة الانتظار بين الصور المتتالية متغيرات هندسية مستقلة $\mathcal{G}(p)$ (بانعدام الذاكرة: فبعد كل صورة تبدأ اللعبة من جديد)، ومنه $T_r = W_1 + \dots + W_r$ ، وتعطي الضربية (المبرهنة 23.10)

G_{T_r}(t) = \Bigl(\frac{pt}{1 - qt}\Bigr)^{r}, \qquad \E(T_r) = r\,\E(W_1) = \frac rp, \qquad V(T_r) = r\,V(W_1) = \frac{rq}{p^2}

( $q = 1 - p$ ؛ والتباينات تُجمع بالاستقلال). والنشر: بمتسلسلة ذات الحدين المعممة (الفصل 11)، $(1 - qt)^{-r} = \sum_{m\geq0} \binom{m + r - 1}{r - 1}q^mt^m$ ، ومنه فإن معامل $t^n$ في $p^rt^r(1 - qt)^{-r}$ هو (مع $m = n - r$ )

\P(T_r = n) = \binom{n-1}{r-1}p^r(1-p)^{n-r}, \qquad n \geq r ,

أي القانون الثنائي السالب — وتوفيقيا: تقع الصورة رقم $r$ عند الرمية $n$ إذا وفقط إذا اختارت الصور $r - 1$ السابقة مواضعها بين الرميات $n - 1$ الأولى.

تمرين 23.6 ★★

من أجل قانون النسل $p_0 = \frac18$ ، $p_1 = \frac38$ ، $p_2 = \frac38$ ، $p_3 = \frac18$ : احسب $m$ ، وقرر ما إذا كان فوق حرج، واحسب احتمال الانقراض $q$ بالضبط. (أخرج الجذر $t = 1$ من $G(t) - t$ بالتفكيك.)

حل

حل التمرين 23.6.

$m = 1\cdot\frac38 + 2\cdot\frac38 + 3\cdot\frac18 = \frac{3 + 6 + 3}{8} = \frac32 > 1$ : أي فوق حرج. والدالة المولّدة هي

G(t) = \frac{1 + 3t + 3t^2 + t^3}{8} = \frac{(1 + t)^3}{8} ,

ومنه تحل النقط الثابتة $(1 + t)^3 = 8t$ ، أي $t^3 + 3t^2 - 5t + 1 = 0$ . وبإخراج الجذر المضمون $t = 1$ :

t^3 + 3t^2 - 5t + 1 = (t - 1)\bigl(t^2 + 4t - 1\bigr),

ويعطي $t^2 + 4t - 1 = 0$ المقدار $t = -2 \pm \sqrt5$ . والجذر في $\intco{0}{1}$ هو $\sqrt5 - 2 \approx 0.236$ : ومنه، بحسب المبرهنة 23.25،

q = \sqrt 5 - 2 .

(وتحقق ممتع: قانون النسل هو قانون $3$ قطعة نقود متزنة مستقلة، $Z_1 \sim \mathcal{B}(3, \frac12)$ .)

تمرين 23.7 ★★★

(النسل الكلي) في مسار تفرع تحت حرج ( $m < 1$ )، ليكن $Y = \sum_{n\geq0} Z_n$ العدد الكلي للأفراد المولودين على الإطلاق. بيّن $\E(Y) = \sum_n m^n = \frac{1}{1 - m}$ (وبرر تبديل ترتيب الجمع)، وبرهن على أن الدالة المولّدة $H = G_Y$ تحقق المعادلة الدالية $H(t) = t\,G(H(t))$ . (السلف، مضافا إليه النسل الكلي لكل من أبنائه، وهي نسخ مستقلة من $Y$ .)

حل

حل التمرين 23.7.

الأمل الرياضي. أولا $\E(Z_n) = m^n$ : فبحسب المبرهنة 23.17، $\E(Z_{n+1}) = \E(Z_n)\,m$ ، و $\E(Z_0) = 1$ . والعائلة $\bigl(Z_n(\omega)\P(\{\omega\}) \bigr)_{n, \omega}$ موجبة، ومنه تنطبق مبرهنة فوبيني من أجل العائلات دون شرط:

\E(Y) = \sum_{n=0}^{\infty}\E(Z_n) = \sum_{n=0}^\infty m^n = \frac{1}{1 - m} < \infty

(وبوجه خاص فإن $Y$ منته بشكل شبه أكيد: بانسجام مع تأكد الانقراض في الحالة تحت الحرجة).

المعادلة الدالية. نفكك المجتمع بحسب أبناء السلف: فإذا كان للسلف $Z_1 = k$ ابنا، كان النسل الكلي $Y = 1 + Y_1 + \dots + Y_k$ ، حيث $Y_i$ هو النسل الكلي لخط الابن رقم $i$ — والمتغيرات $Y_i$ نسخ مستقلة من $Y$ ، مستقلة عن $Z_1$ (فالخطوط المتمايزة تستعمل أحداث تكاثر منفصلة مستقلة). وبالشرط على $Z_1$ كما في المبرهنة 23.17:

H(t) = \E\bigl(t^Y\bigr) = t\sum_{k=0}^\infty \P(Z_1 = k)\,H(t)^k = t\,G\bigl(H(t)\bigr),

مع العامل $t$ الذي يحسب السلف نفسه. (ومن أجل القانون $p_0 = 1 - p$ ، $p_2 = p$ للتفرع الثنائي، يمكن حل هذه المعادلة من الدرجة الثانية بدلالة $H$ صراحة ونشرها — فأعداد كاتالان في الفصل 11 تعد أشجار العائلة.)

تمرين 23.8 ★★★

ليكن $X$ ذا دالة مولّدة $G$ نصف قطر تقاربها $> 1$ . برهن على الحصر الذيلي الأسي: يوجد $C > 0$ و $\rho \in \intoo{0}{1}$ يحققان $\P(X \geq n) \leq C\rho^n$ . (بمتراجحة ماركوف مطبقة على $t^X$ من أجل $t > 1$ ثابت داخل القرص.) وبالعكس، بيّن أنه إذا كان $\P(X \geq n) \leq C\rho^n$ مع $\rho < 1$ ، فإن نصف قطر $G$ هو $\geq 1/\rho > 1$ .

حل

حل التمرين 23.8.

ليكن $R > 1$ نصف القطر ولنثبّت $t \in \intoo{1}{R}$ . عندئذ $\E(t^X) = G(t) < \infty$ ، وتعطي متراجحة ماركوف (المبرهنة 22.15) مطبقة على المتغير الموجب $t^X$ عند المستوى $t^n$ :

\P(X \geq n) = \P\bigl(t^X \geq t^n\bigr) \leq \frac{G(t)}{t^n} = C\rho^n, \qquad C = G(t),\quad \rho = \frac1t \in \intoo{0}{1}.

العكس: إذا كان $\P(X \geq n) \leq C\rho^n$ ، فإن $p_n \leq \P(X \geq n) \leq C\rho^n$ ، ومنه فإن المتسلسلة $\sum p_n\abs t^n$ مهيمن عليها من أجل $\abs t < \frac1\rho$ بالمتسلسلة الهندسية المتقاربة $C\sum(\rho\abs t)^n$ : فنصف القطر لا يقل عن $\frac1\rho > 1$ . فنصف قطر الدالة المولّدة والتلاشي الهندسي للذيل وجهان للخاصية نفسها.

تمرين 23.9 ★★★

(مبرهنة الاتصال، الحالة الأولية) لتكن $X, X_1, X_2, \dots$ ذات قيم في $\N$ مع $G_{X_n}(t) \to G_X(t)$ من أجل كل $t \in \intco{0}{1}$ . بيّن أن $\P(X_n = k) \to \P(X = k)$ من أجل كل $k$ . (بالتراجع على $k$ : من أجل $k = 0$ خذ $t \to 0$ — وبحذر: ثبّت $t$ صغيرة، واستعمل $\abs{\P(X_n = 0) - G_{X_n}(t)} \leq \frac{t}{1-t}$ ، وهو صالح لأن الذيل $\sum_{j \geq 1}p_jt^j \leq \frac{t}{1 - t}$ ؛ ثم قطّر. ومن أجل خطوة التراجع، انظر في $\frac{G(t) - \P(X = 0)}{t}$ ، وهي الدالة المولّدة لقانون مزاح.)

حل

حل التمرين 23.9.

نكتب $p_k^{(n)} = \P(X_n = k)$ ، $p_k = \P(X = k)$ .

الحالة $k = 0$ . من أجل $t \in \intoo{0}{1}$ ومن أجل أي قانون $(q_j)$ يحقق $\sum_j q_j \leq 1$ :

\Bigl|\,q_0 - \sum_j q_jt^j\Bigr| = \sum_{j \geq 1} q_j t^j \leq \sum_{j\geq1}t^j = \frac{t}{1 - t} .

ومنه

\abs{p_0^{(n)} - p_0} \leq \frac{2t}{1 - t} + \abs{G_{X_n}(t) - G_X(t)} .

وبمعطى $\varepsilon > 0$ ، نختار $t$ بحيث $\frac{2t}{1-t} < \frac\varepsilon2$ ، ثم $n_0$ بحيث يكون الحد الأخير $< \frac\varepsilon2$ من أجل $n \geq n_0$ : ومنه $p_0^{(n)} \to p_0$ .

خطوة التراجع. لنفترض $p_j^{(n)} \to p_j$ من أجل $j < k$ . ولننظر في الدوال المزاحة

g_n(t) = \frac{G_{X_n}(t) - p^{(n)}_0}{t} = \sum_{j\geq0} p^{(n)}_{j+1}t^j, \qquad g(t) = \frac{G_X(t) - p_0}{t} ,

وهي الدوال المولّدة لمتتاليات شبه احتمالية $(p^{(n)}_{j+1})_j$ (كتلتها الكلية $\leq 1$ ، وهو كل ما استعملته حجة $k = 0$ ). ومن أجل $t \in \intoo{0}{1}$ ثابتة، $g_n(t) \to g(t)$ بحكم الفرضية وحالة $k = 0$ . وتطبيق حجة $k = 0$ على $g_n$ يعطي $p_1^{(n)} \to p_1$ ؛ وتكرار الإزاحة $k$ مرة يعطي $p_k^{(n)} \to p_k$ من أجل كل $k$ . (وهذه هي الحالة المتقطعة الأولية من مبرهنة ليفي في الاتصال، التي تكون صيغتها العامة — من أجل الدوال المميزة — معلما من معالم السنة الثالثة.)

تمرين 23.10 ★

(حيلة الزوجية) بيّن أنه من أجل متغير $X$ ذي قيم في $\N$ ،

\P(X \text{ زوجي}) = \frac{1 + G_X(-1)}{2} ,

واحسب هذا الاحتمال من أجل $X \sim \mathcal P(\lambda)$ ومن أجل $X \sim \mathcal B(n, p)$ . وماذا يعني $G_X(-1) \to 0$ احتماليا؟

حل

حل التمرين 23.10.

نقطيا، يساوي $\frac{1 + (-1)^X}{2}$ المقدار $1$ عندما يكون $X$ زوجيا و $0$ عندما يكون فرديا، ومنه بأخذ الآمال (بمبرهنة النقل)،

\P(X \text{ زوجي}) = \frac{1 + \E\bigl((-1)^X\bigr)}2 = \frac{1 + G_X(-1)}2 .

بواسون: $\frac{1 + \eu^{-2\lambda}}2 \to \frac12$ عندما ينمو $\lambda$ . وثنائي الحد: $\frac{1 + (1 - 2p)^n}2$ . وفي الحالتين يقول $G_X(-1) \to 0$ إن زوجية $X$ تصير قطعة نقود متزنة: فالقانون ينتشر على أعداد صحيحة كثيرة وينسى زوجيته.

تمرين 23.11 ★★

(نردا سيشرمان) تحقق من تفكيك الدالة المولّدة للنرد المتزن

\frac{t + t^2 + \dots + t^6}{6} = \frac{t\,(1 + t)(1 + t + t^2)(1 - t + t^2)}{6},

وبيّن أن النردين ذوي الوجوه $\{1, 2, 2, 3, 3, 4\}$ و $\{1, 3, 4, 5, 6, 8\}$ لهما الدالتان المولّدتان $\frac{t(1+t)(1+t+t^2)}6$ و $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6$ ، وجداؤهما هو دالة نردين قياسيين: فهذان النردان الغريبان ينتجان كل مجموع $2, \dots, 12$ بالاحتمالات القياسية بالضبط.

حل

حل التمرين 23.11.

$t + \dots + t^6 = t\,\frac{1 - t^6}{1 - t}$ و $1 - t^6 = (1 - t)(1 + t)(1 + t + t^2)(1 - t + t^2)$ ، وهو ما يعطي التفكيك المذكور. ومن أجل النرد الأول، $(1 + t)(1 + t + t^2) = 1 + 2t + 2t^2 + t^3$ ، ومنه $\frac{t(1+t)(1+t+t^2)}6 = \frac{t + 2t^2 + 2t^3 + t^4}6$ : أي الوجوه $\{1, 2, 2, 3, 3, 4\}$ . ومن أجل الثاني، بنشر

(1 + 2t + 2t^2 + t^3)(1 - t + t^2)^2 = 1 + t^2 + t^3 + t^4 + t^5 + t^7,

نجد $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6 = \frac{t + t^3 + t^4 + t^5 + t^6 + t^8}6$ : أي الوجوه $\{1, 3, 4, 5, 6, 8\}$ . وجداء الدالتين المولّدتين يعيد تجميع العوامل الستة في $\bigl(\frac{t(1+t)(1+t+t^2)(1-t+t^2)}6 \bigr)^2$ ، وهو مربع دالة النرد القياسي: فلزوج سيشرمان القانون القياسي بالضبط من أجل المجموع — والدوال المولّدة تصنّف كل عمليات إعادة التجميع هذه.

تمرين 23.12 ★★★

(انتظار صورتين متتاليتين) تُرمى قطعة نقود احتمال الصورة فيها $p$ حتى تظهر صورتان متتاليتان؛ وليكن $T$ عدد الرميات (وهي لعبة التمرين 21.6). بالشرط على الرميات الأولى، اشتق جملة خطية للدوال المولّدة انطلاقا من الحالتين “لا صورة جارية” و“صورة جارية واحدة”، واستنتج

G_T(t) = \frac{p^2t^2}{1 - qt - pqt^2} \qquad (q = 1 - p);

وتحقق من $G_T(1) = 1$ و $\E(T) = \dfrac{1 + p}{p^2}$ ( $= 6$ من أجل قطعة متزنة).

حل

حل التمرين 23.12.

لتكن $A$ و $B$ الدالتين المولّدتين للمدة المتبقية انطلاقا من “لا صورة جارية” ومن “صورة جارية واحدة”. تُنفق رمية واحدة، ثم: انطلاقا من الحالة $0$ ، تعيد الكتابة إلى الحالة $0$ ، وتنقل الصورة إلى الحالة $1$ ؛ وانطلاقا من الحالة $1$ ، تنهي الصورة اللعبة وتعيد الكتابة إلى الحالة $0$ :

A(t) = t\bigl(q\,A(t) + p\,B(t)\bigr), \qquad B(t) = t\bigl(p + q\,A(t)\bigr).

وبالتعويض: $A(1 - qt) = pt\,B = pt(pt + qtA)$ ، ومنه

G_T(t) = A(t) = \frac{p^2t^2}{1 - qt - pq\,t^2} .

وعند $t = 1$ يكون المقام $1 - q - pq = p(1 - q) = p^2$ : $G_T(1) = 1$ ، فتنتهي اللعبة بشكل شبه أكيد (كما بين التمرين 21.6 بالتراجع). والمفاضلة اللوغاريتمية عند $1$ : $\E(T) = 2 - \frac{D'(1)}{D(1)}$ مع $D(t) = 1 - qt - pqt^2$ ، $D'(1) = -q - 2pq$ :

\E(T) = 2 + \frac{q + 2pq}{p^2} = \frac{2p^2 + q + 2pq}{p^2} = \frac{1 + p}{p^2},

وهو $6$ من أجل $p = \frac12$ .

23.6 مسألة: مسار غالتون–واطسون، محلولا

مسألة 23.1

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

يقسم محك الانقراض (المبرهنة 23.25) مسارات التفرع إلى تحت حرجة وحرجة وفوق حرجة — لكنه لا يقول شيئا عن المعدلات: كم بسرعة يموت خط محكوم عليه، وكم يكبر خط باق. وتحسب هذه المسألة ذلك. ونحتفظ برموز الفصل: قانون النسل $(p_k)$ ودالته المولّدة $G$ ، والمتوسط $m = G'(1)$ ، وأحجام الأجيال $Z_n$ ( $Z_0 = 1$ )، والمكرَّرات $G_n = G_{Z_n}$ ، واحتمالات الانقراض $q_n = \P(Z_n = 0) \uparrow q$ ؛ ونفترض دائما $p_1 \neq 1$ ، ونفترض $G''(1) < \infty$ حيث تظهر عزوم من الرتبة الثانية، ونكتب $\sigma^2 = V(Z_1)$ .

الجزء الأول — عزوم الأجيال.

بيّن $\E(Z_n) = m^n$ (بقاعدة السلسلة على $G_n = G \circ G_{n-1}$ عند $1^-$ ، باستعمال $G_{n-1}(1) = 1$ والمبرهنة 23.7).
أنشئ التراجع $G_n''(1) = G''(1)\,m^{2(n-1)} + m\,G_{n-1}''(1)$ وحله: $G_n''(1) = G''(1)\,m^{n-1}\dfrac{m^n - 1}{m - 1}$ من أجل $m \neq 1$ ، و $G_n''(1) = n\,G''(1)$ من أجل $m = 1$ .
استنتج

$V(Z_n) = \sigma^2m^{n-1}\,\frac{m^n - 1}{m - 1} \quad (m \neq 1), \qquad V(Z_n) = n\,\sigma^2 \quad (m = 1).$
(المعدل تحت الحرج، الحصر العلوي) من أجل $m < 1$ ، بيّن $\P(Z_n > 0) \leq m^n$ (بمتراجحة ماركوف على المتغير الصحيح $Z_n$ ): أي إن الانقراض مؤكد بمعدل هندسي — وهو تدقيق كمي لمحك الفصل.
(المعدل تحت الحرج، الحصر السفلي) باستعمال متراجحة كوشي–شوارتز على $Z_n\mathbf 1_{Z_n > 0}$ ، بيّن

$\P(Z_n > 0) \geq \frac{\E(Z_n)^2}{\E(Z_n^2)} \geq c\,m^{n} \quad\text{مع}\quad c = \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1} :$

أي إن المعدل الهندسي $m^n$ مضبوط إلى غاية ثوابت.

الجزء الثاني — العائلة الهندسية، محلولة بالضبط. ليكن قانون النسل هندسيا على $\N$ : $p_k = qp^k$ ( $k \geq 0$ )، مع $0 < p < 1$ ، $q = 1 - p$ .

احسب $G(t) = \dfrac{q}{1 - pt}$ و $m = \dfrac pq$ ؛ وحدد الأنظمة الثلاثة بدلالة $p$ .
حل $G(t) = t$ : بيّن أن النقطتين الثابتتين هما $1$ و $q/p = 1/m$ ، واستعد احتمال الانقراض $q_{\mathrm{ext}} = \min(1, 1/m)$ .
برهن بالتراجع على الصيغتين المغلقتين

$q_n = \frac{m^n - 1}{m^{n+1} - 1} \quad (m \neq 1), \qquad q_n = \frac{n}{n+1} \quad (m = 1).$
استنتج المعدلات المضبوطة: $1 - q_n \sim (1 - m)\,m^n$ في الحالة تحت الحرجة، و $q_{\mathrm{ext}} - q_n \sim \dfrac{m - 1}{m^{2}}\cdot m^{-n}$ في الحالة فوق الحرجة؛ وتحقق من أن نسبة التقلص فوق الحرجة هي $G'(q_{\mathrm{ext}}) = 1/m$ .
الحالة الحرجة ( $p = \tfrac12$ ): احسب $\sigma^2 = 2$ ولاحظ $1 - q_n = \frac1{n+1}$ : فاحتمال البقاء يتلاشى مثل $\frac1n$ — فلا هو هندسي ولا قابل للجمع.
وما زلنا في الحالة الحرجة: برهن بالتراجع على المكرَّر الكامل

$G_n(t) = \frac{n - (n-1)t}{n + 1 - nt},$

واستنتج أنه بشرط البقاء يكون $Z_n$ هندسيا على $\N^*$ بالوسيط $\frac1{n+1}$ :

$\P(Z_n = k \mid Z_n > 0) = \frac1{n+1} \Bigl(\frac{n}{n+1}\Bigr)^{k-1}, \qquad \E(Z_n \mid Z_n > 0) = n + 1 .$

فالخط المتوسط يموت، لكن الخطوط الباقية حجمها من رتبة $n$ .

الجزء الثالث — النسل الكلي. ليكن $Y = \sum_{n\geq0}Z_n \in \N^* \cup \{\infty\}$ العدد الكلي للأفراد المولودين على الإطلاق، وليكن $H(t) = \sum_{k\geq1}\P(Y = k)t^k$ .

برر $\P(Y < \infty) = q_{\mathrm{ext}}$ ، وذكّر من التمرين 23.7 بالمعادلة الدالية $H(t) = t\,G(H(t))$ (التي لم يستعمل اشتقاقها $m < 1$ ).
(التفرع الثنائي) من أجل $p_0 = p_2 = \frac12$ (الحرج)، حل المعادلة الدالية:

$H(t) = \frac{1 - \sqrt{1 - t^2}}{t},$

وانشرها بالمقدار المثال 11.21 للحصول على

$\P(Y = 2k + 1) = \frac{C_k}{2^{2k+1}}, \qquad C_k = \frac1{k+1}\binom{2k}k ;$

وتحقق من القيمتين $\P(Y = 1) = \frac12$ و $\P(Y = 3) = \frac18$ بالعد المباشر.
بمفاضلة المعادلة الدالية عند $1^-$ ، بيّن أن $\E(Y) = \frac{1}{1-m}$ من أجل $m < 1$ ، بينما تفرض الحرجية $\E(Y) = \infty$ : أي إن النسل الكلي الحرج منته بشكل شبه أكيد بمتوسط لانهائي.
مع السلوك المقارب للمعامل الثنائي المركزي (المثال 6.14)، بيّن

$\P(Y = 2k+1) \sim \frac{1}{2\sqrt\pi\,k^{3/2}},$

أي ذيلا ثقيلا $k^{-3/2}$ ، واستنتج $\P(Y > n) \asymp n^{-1/2}$ (ويكفي حصران علوي وسفلي من هذه الرتبة).
قارن مع السير العشوائي المتزن (مسألة نهاية الأسبوع في الفصل 21): فهناك أزمنة عودة مؤكدة بمتوسط لانهائي، وهنا نسل كلي مؤكد بمتوسط لانهائي، وكلاهما بقوانين موضعية $n^{-3/2}$ . وفقرة واحدة عن سبب إنتاج الحرجية لهذه البصمة.

الجزء الرابع — تقدير كولموغوروف عند الحرجية. لنفترض $m = 1$ ، $0 < \sigma^2 = G''(1) < \infty$ .

بيّن أن $G''$ يمتد بالاتصال إلى $\intcc01$ (فهو موجب متزايد ذو نهاية منتهية) واستنتج نشر تايلور عند $1$ :

$G(t) = t + b\,(1-t)^2 + o\bigl((1-t)^2\bigr), \qquad b = \frac{G''(1)}2 = \frac{\sigma^2}2 .$
من أجل $t \in \intco01$ ، ضع $h(t) = \dfrac1{1 - G(t)} - \dfrac1{1 - t}$ . بيّن

$h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)} \xrightarrow[t\to1^-]{} b .$
تلسكب على طول التكرار $q_{j+1} = G(q_j)$ :

$\frac1{1 - q_n} = 1 + \sum_{j=0}^{n-1}h(q_j),$

واختم بحجة تشيزارو أن

$\P(Z_n > 0) = 1 - q_n \sim \frac{2}{\sigma^2\,n}$

— وهو تقدير كولموغوروف: فكل مسار تفرع حرج يموت بالمعدل الشامل $1/n$ ، ولا يتذكر قانون النسل إلا الثابت.
تحقق من التقدير بمقابلته بالحالة الهندسية الحرجة في السؤال 10.
استنتج $\E(Z_n \mid Z_n > 0) = \dfrac{1}{1 - q_n} \sim \dfrac{\sigma^2 n}{2}$ (لاحظ $\E(Z_n \mathbf 1_{Z_n>0}) = \E(Z_n) = 1$ )، وتحقق منه بمقابلته بالسؤال 11: فبشرط البقاء ينمو المجتمع خطيا — وهو الحبل المشدود الحرج بين الموت والانفجار.

الجزء الخامس — تطبيقات وتركيب.

(الأوبئة والتفاعلات المتسلسلة) من أجل قانون نسل بواسوني $\mathcal P(\lambda)$ — إذ تعدي كل حالة $\mathcal P(\lambda)$ حالة جديدة — اكتب معادلة الانقراض $q = \eu^{\lambda(q-1)}$ وحلها عدديا من أجل $\lambda = 1.5$ ( $q \approx 0.417$ ) ومن أجل $\lambda = 2$ ( $q \approx 0.203$ ): فانطلاقا من حالة واحدة، لا يكون تفشٍّ كبير مؤكدا حتى عندما $\lambda > 1$ . واشرح لماذا يتقارب التكرار $q_{n+1} = \eu^{\lambda(q_n - 1)}$ انطلاقا من $q_0 = 0$ نحو الجذر الصحيح.
انطلاقا من $k$ سلفا بدل واحد، بيّن أن احتمال الانقراض هو $q^k$ . وتطبيقا: مع $\lambda = 1.5$ ، كم حالة ابتدائية تجعل احتمال التفشي لا يقل عن $99\%$ ؟
(شرط مسار فوق حرج على الانقراض) من أجل $m > 1$ باحتمال انقراض $q \in \intoo01$ : برهن أولا بالتحدب على أن $G'(q) < 1$ عند النقطة الثابتة الصغرى، واستنتج $q_{\mathrm{ext}} - q_n = O\bigl(G'(q)^n\bigr)$ (أي تقاربا هندسيا، كما يبين السؤال 9). ثم بيّن أن $\widehat G(t) = G(qt)/q$ دالة مولّدة لقانون نسل حقيقي، متوسطه $\widehat m = G'(q) < 1$ : أي مسار رفيق تحت حرج. وتحقق من ذلك على العائلة الهندسية: فشرط المسار فوق الحرج ذي الوسيط $(p, q)$ على الانقراض يبادل بين $p$ و $q$ . (والنص الكامل — وهو أن المسار المشروط هو المسار الرفيق — مبرهن في مجلد السنة الثالثة؛ وقد تحققت هنا من ظله على مستوى الدوال المولّدة.)
تركيب: ارسم جدول الثلاثية — من أجل $m < 1$ و $m = 1$ و $m > 1$ : قيمة $q$ ؛ ومعدل $\P(Z_n > 0)$ أو $q - q_n$ ؛ و $\E(Y)$ ؛ وحجم جيل باق. واذكر في جملة واحدة لكل أداة كيف حمل تركيب الدوال المولّدة والتحدب وتايلور عند $1^-$ ومتوسطات تشيزارو المسألة كلها، وماذا يضيف مجلد السنة الثالثة (المارتينغال $Z_n/m^n$ وقانون ياغلوم النهائي الأسي).

حل

حل المسألة 23.1.

1. من أجل $t \in \intoo01$ ، تعطي قاعدة السلسلة على $G_n = G \circ G_{n-1}$ المقدار $G_n'(t) = G'\bigl(G_{n-1}(t)\bigr)G_{n-1}'(t)$ . وعندما $t \to 1^-$ ، $G_{n-1}(t) \uparrow 1$ ، ويكون $G'$ غير متناقص ونهايته اليسرى $m$ عند $1$ ، ومنه فإن العامل الأول يؤول إلى $m$ ؛ وبالتراجع يؤول الثاني إلى $m^{n-1}$ . وبحسب المبرهنة 23.7، $\E(Z_n) = G_n'(1^-) = m^n$ .

2. بالمفاضلة مرة أخرى،

G_n'' = G''(G_{n-1})\,(G_{n-1}')^2 + G'(G_{n-1})\,G_{n-1}'',

وبجعل $t \to 1^-$ : $a_n = G''(1)m^{2(n-1)} + m\, a_{n-1}$ مع $a_n = G_n''(1)$ ، $a_1 = G''(1)$ . ومن أجل $m \neq 1$ نتحقق بالتراجع من أن $a_n = G''(1)\,m^{n-1} \frac{m^n - 1}{m - 1}$ (فالتراجع يضيف $G''(1)m^{2n-2}$ إلى $m\cdot G''(1)m^{n-2}\frac{m^{n-1}-1}{m-1}$ ، و $m^{n-1} + \frac{m^{n-1}-1}{m-1} = \frac{m^n - 1}{m-1}$ )؛ ومن أجل $m = 1$ ، $a_n = a_{n-1} + G''(1) = n\,G''(1)$ .

3. $V(Z_n) = a_n + m^n - m^{2n}$ و $G''(1) = \sigma^2 + m^2 - m$ . ومن أجل $m \neq 1$ ، يبسّط الجزء $(m^2 - m)m^{n-1}\frac{m^n-1}{m-1} = m^n(m^n - 1)$ المقدار $m^n - m^{2n}$ بالضبط، فيبقى $V(Z_n) = \sigma^2m^{n-1}\frac{m^n-1}{m-1}$ . ومن أجل $m = 1$ : $V(Z_n) = nG''(1) = n\sigma^2$ .

4. $Z_n$ متغير صحيح موجب، ومنه $\P(Z_n > 0) = \P(Z_n \geq 1) \leq \E(Z_n) = m^n$ بمتراجحة ماركوف (المبرهنة 22.15). ومن أجل $m < 1$ يتلاشى هذا هندسيا — وبقابلية للجمع، ومنه تعطي بوريل–كانتيلي حتى أن عددا منتهيا فقط من الأجيال غير خال، وهو الانقراض من جديد.

5. كوشي–شوارتز: $\E(Z_n)^2 = \E(Z_n\mathbf 1_{Z_n>0})^2 \leq \E(Z_n^2)\,\P(Z_n > 0)$ . ومع السؤال 3 و $m < 1$ :

\E(Z_n^2) = V(Z_n) + m^{2n} \leq \frac{\sigma^2m^{n-1}}{1-m} + m^{2n},

ومنه، بقسمة $m^{2n}$ على هذا الحصر والتبسيط بالمقدار $m^n$ ،

\P(Z_n > 0) \geq \frac{m^n}{\frac{\sigma^2}{m(1-m)} + m^n} \geq \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1}m^n ,

باستعمال $m^n \leq 1$ في المقام. ومع السؤال 4: $\P(Z_n > 0) \asymp m^n$ .

6. $G(t) = q\sum_k(pt)^k = \frac{q}{1 - pt}$ ، و $m = G'(1) = \frac{pq}{(1-p)^2} = \frac pq$ . فهو تحت حرج من أجل $p < \frac12$ ، وحرج من أجل $p = \frac12$ ، وفوق حرج من أجل $p > \frac12$ .

7. تُكتب $G(t) = t$ على الصورة $pt^2 - t + q = 0$ ، وجذورها $\frac{1 \pm \abs{p - q}}{2p}$ ، أي $1$ و $\frac qp = \frac1m$ . واحتمال الانقراض هو النقطة الثابتة الصغرى في $\intcc01$ (المبرهنة 23.25): $q_{\mathrm{ext}} = 1$ إذا كان $m \leq 1$ ، و $\frac1m$ إذا كان $m > 1$ .

8. من أجل $m \neq 1$ ، مع $p = \frac m{m+1}$ ، $q = \frac1{m+1}$ : فإذا كان $q_n = \frac{m^n - 1}{m^{n+1} - 1}$ ، فإن

1 - p\,q_n = \frac{(m+1)(m^{n+1} - 1) - m(m^n - 1)} {(m+1)(m^{n+1} - 1)} = \frac{m^{n+2} - 1}{(m+1)(m^{n+1} - 1)},

ومنه $q_{n+1} = \frac{q}{1 - pq_n} = \frac{m^{n+1} - 1}{m^{n+2} - 1}$ ؛ والحالة الأساسية $q_0 = 0$ تتحقق. ومن أجل $m = 1$ : $G(t) = \frac1{2 - t}$ و $q_{n+1} = \frac1{2 - \frac{n}{n+1}} = \frac{n+1}{n+2}$ ، مع $q_0 = 0$ .

9. $1 - q_n = \frac{m^n(m - 1)}{m^{n+1} - 1}$ . ومن أجل $m < 1$ يؤول المقام إلى $-1$ : $1 - q_n \sim (1 - m)\,m^n$ . ومن أجل $m > 1$ :

q_{\mathrm{ext}} - q_n = \frac1m - \frac{m^n - 1}{m^{n+1} - 1} = \frac{m - 1}{m\,(m^{n+1} - 1)} \sim \frac{m - 1}{m^{2}}\;m^{-n} .

والمقدار $G'(t) = \frac{pq}{(1 - pt)^2}$ مقوَّما عند $t = \frac qp$ (حيث $1 - pt = 1 - q = p$ ) يعطي $G'(q_{\mathrm{ext}}) = \frac qp = \frac1m$ : فالنسبة الملاحظة $m^{-1}$ هي بالضبط المشتقة عند النقطة الثابتة الجاذبة.

10. من أجل $p = \frac12$ : $G''(t) = \frac{1/4}{(1 - t/2)^3}$ ، ومنه $G''(1) = 2$ و $\sigma^2 = G''(1) + m - m^2 = 2$ . وتعطي الصيغة المغلقة $1 - q_n = \frac1{n+1}$ : فاحتمال البقاء يتلاشى مثل $1/n$ — ببطء لا يسمح بالقابلية للجمع، خلافا لأي معدل تحت حرج.

11. بالتراجع: $G_1(t) = \frac1{2-t}$ يوافق الصيغة من أجل $n = 1$ ، و

G(G_n(t)) = \cfrac{1}{2 - \cfrac{n - (n-1)t}{n+1 - nt}} = \frac{n + 1 - nt}{2(n+1) - 2nt - n + (n-1)t} = \frac{n+1 - nt}{n + 2 - (n+1)t} .

ثم

\frac{G_n(t) - q_n}{1 - q_n} = (n+1)\,\Bigl(\frac{n - (n-1)t}{n+1 - nt} - \frac{n}{n+1}\Bigr) = \frac{t}{n + 1 - nt} = \frac{\frac{t}{n+1}}{1 - \frac{n}{n+1}t} ,

وهي الدالة المولّدة للقانون الهندسي $\mathcal G\bigl(\frac1{n+1} \bigr)$ على $\N^*$ (المثال 23.4): فبشرط البقاء، $\P(Z_n = k \mid Z_n > 0) = \frac1{n+1}\bigl(\frac n{n+1}\bigr)^{k-1}$ ، بمتوسط شرطي $n + 1$ . والمتوسط غير المشروط $1 = \E(Z_n)$ هو جداء احتمال بقاء متلاش وحجم شرطي متزايد خطيا.

12. إذا انقرض الخط عند الجيل $n$ ، كان $Y = Z_0 + \dots + Z_{n-1}$ منتهيا؛ وإذا لم ينقرض أبدا، كان $Y \geq \sum_n 1 = \infty$ . ومنه فإن $\{Y < \infty\}$ هو حدث الانقراض و $\P(Y < \infty) = q_{\mathrm{ext}}$ . أما اشتقاق $H(t) = tG(H(t))$ في التمرين 23.7 — فالسلف يساهم بالعامل $t$ ، وأبناؤه يؤسسون نسخا مستقلة من $Y$ تُعد عبر $G$ — فلم يستعمل إلا المبرهنة 23.17، وهو صالح في كل نظام.

13. مع $G(s) = \frac{1 + s^2}2$ تُكتب المعادلة $tH^2 - 2H + t = 0$ ، ومنه $H = \frac{1 - \sqrt{1 - t^2}}{t}$ (وهو الجذر الذي يحقق $H(0) = 0$ ). وبالمقارنة مع متسلسلة كاتالان $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ (المثال 11.21): $H(t) = \frac t2\,C\bigl(\frac{t^2}4\bigr) = \sum_{k\geq0}C_k\,\frac{t^{2k+1}}{2^{2k+1}}$ ، أي $\P(Y = 2k+1) = C_k2^{-2k-1}$ . وللتحقق: $\P(Y = 1) = C_0/2 = \frac12$ (فالسلف بلا أبناء)؛ و $\P(Y = 3) = C_1/8 = \frac18$ (فابنان كلاهما بلا أبناء: $\frac12\cdot\frac12\cdot \frac12$ ).

14. بمفاضلة $H = tG(H)$ على $\intoo01$ وبجعل $t \to 1^-$ (بالنهايات الرتيبة كما في المبرهنة 23.7): $H'(1)\bigl(1 - G'(H(1))\bigr) = G(H(1))$ . وفي الحالة تحت الحرجة $H(1) = 1$ و $\E(Y) = H'(1) = \frac1{1 - m}$ . وفي الحالة الحرجة يجعل $G'(1) = 1$ العامل الأيسر معدوما بينما الطرف الأيمن $1$ : فلا يمكن وجود $H'(1)$ منته، ومنه $\E(Y) = \infty$ — ومع ذلك $\P(Y < \infty) = q = 1$ .

15. $C_k = \frac1{k+1}\binom{2k}k \sim \frac{4^k}{\sqrt\pi\,k^{3/2}}$ بحسب المثال 6.14، ومنه

\P(Y = 2k+1) = \frac{C_k}{2\cdot4^{k}} \sim \frac1{2\sqrt\pi\,k^{3/2}} .

وبجمع الذيل (بالمقارنة مع $\int_K^\infty k^{-3/2}\dd k = 2K^{-1/2}$ ، من الأعلى ومن الأسفل): $\P(Y > 2K) \asymp K^{-1/2}$ ، أي $\P(Y > n) \asymp n^{-1/2}$ — أي ذيل ثقيل بمتوسط لانهائي، يقيس السؤال 14.

16. الكائنان الحرجان كلاهما — زمن عودة السير المتزن (مسألة نهاية الأسبوع في الفصل 21) والنسل الكلي الحرج — منته بشكل شبه أكيد بمتوسط لانهائي، بقوانين موضعية أسّها $-3/2$ وبذيول أسّها $-1/2$ . وليست هذه مصادفة: فاستكشاف شجرة عائلة ابنا ابنا ينتج مسارا $\pm1$ (خطوة صاعدة لكل ولادة، وخطوة نازلة لكل وفاة) وهو بالضبط سير متزن، ويصير $Y$ زمن أول عبور. والحرجية تعني انعدام الانجراف: فالمسار دائما على شفا الانقراض والانفجار معا، وتنتج تقلبات العشوائية عديمة الانجراف على السلّم $\sqrt{}$ هذه الأسس بالضبط.

17. $G''(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ حدوده موجبة، ومنه فهو غير متناقص على $\intco01$ ونهايته منتهية $G''(1) = \sigma^2$ (فالحرجية تجعل $\E Z_1(Z_1 - 1) = \sigma^2$ )؛ والدالة غير المتناقصة التي نهايتها تساوي القيمة الحدية متصلة عند $1$ . وتايلور بالباقي التكاملي عند النقطة $1$ :

G(t) = 1 + (t - 1) + \int_1^t(t - s)G''(s)\,\dd s = t + \frac{G''(1)}2(1-t)^2 + o\bigl((1-t)^2\bigr),

لأن $G''(s) = G''(1) + o(1)$ عندما $s \to 1^-$ .

18. بتوحيد المقامات، $h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)}$ . وبحسب السؤال 17 يكون البسط $b(1-t)^2 + o((1-t)^2)$ و $1 - G(t) = (1 - t)\bigl(1 - b(1-t) + o(1-t)\bigr)$ ، ومنه $h(t) \to b$ .

19. بتعريف $h$ عند $t = q_j$ و $G(q_j) = q_{j+1}$ : $\frac1{1 - q_{j+1}} - \frac1{1-q_j} = h(q_j)$ ؛ والجمع انطلاقا من $j = 0$ ( $q_0 = 0$ ) يعطي الصيغة المكتوبة. وبما أن المسار الحرج ينقرض، فإن $q_j \uparrow 1$ ، ومنه $h(q_j) \to b$ ويكون متوسط تشيزارو $\frac1n\sum_{j<n}h(q_j) \to b$ : $\frac1{1-q_n} \sim bn$ ، أي

\P(Z_n > 0) \sim \frac1{bn} = \frac{2}{\sigma^2 n} .

20. الحالة الهندسية الحرجة: $\sigma^2 = 2$ (السؤال 10)، ومنه يتنبأ كولموغوروف بالمقدار $1 - q_n \sim \frac1n$ — والقيمة المضبوطة $\frac1{n+1}$ .

21. بما أن $Z_n\mathbf 1_{Z_n > 0} = Z_n$ ، فإن $\E(Z_n \mid Z_n > 0) = \frac{\E(Z_n)}{\P(Z_n > 0)} = \frac1{1 - q_n} \sim \frac{\sigma^2n}2$ . وفي الحالة الهندسية يساوي هذا $n + 1$ ، وهو يوافق السؤال 11 بالضبط ( $\sigma^2 = 2$ ). والصورة الحرجة: الانقراض مؤكد، والحجم المتوسط مجمد عند $1$ ، والخطوط النادرة الباقية حجمها ينمو خطيا — فيوازن كل عامل الآخر.

22. من أجل نسل $\mathcal P(\lambda)$ ، $G(t) = \eu^{\lambda(t-1)}$ ويكون احتمال الانقراض أصغر جذور $q = \eu^{\lambda(q-1)}$ . وعدديا: يعطي $\lambda = 1.5$ المقدار $q \approx 0.417$ (بتكرار $q \mapsto \eu^{1.5(q-1)}$ : $0, 0.223, 0.312, 0.356, \dots \to 0.4172$ )؛ ويعطي $\lambda = 2$ المقدار $q \approx 0.203$ . ومنه فإن حالة أولى واحدة تشعل تفشيا كبيرا باحتمال $58\%$ ( $\lambda = 1.5$ ) أو $80\%$ ( $\lambda = 2$ ) — أي مرجح، لا مؤكد. ويتقارب التكرار انطلاقا من $q_0 = 0$ نحو الجذر الأصغر لأن $G$ غير متناقصة: فبالتراجع $q_n \leq r$ من أجل أي نقطة ثابتة $r$ ، و $(q_n)$ متزايد (فهو $\P(Z_n = 0)$ )، ومنه فنهايته نقطة ثابتة دون جميع النقط الأخرى.

23. يؤسس الأسلاف $k$ أشجار عائلة مستقلة، والانقراض الكلي هو تقاطع $k$ حدث انقراض مستقل: أي باحتمال $q^k$ . ومن أجل $\lambda = 1.5$ : يقتضي احتمال تفش $1 - q^k \geq 0.99$ أن يكون $q^k \leq 0.01$ ، أي $k \geq \frac{\ln 0.01}{\ln 0.417} \approx 5.3$ : فست حالات ابتدائية تجعل التفشي مؤكدا بنسبة $99\%$ .

24. $G'(q) < 1$ : المقدار $G - \mathrm{id}$ محدب وينعدم عند $q$ وعند $1$ ، ومنه فهو $\leq 0$ على $\intcc q1$ ؛ فلو كان $G'(q) = 1$ ، لفرض المماس عند $q$ (الذي يضعه التحدب تحت $G$ ) أن يكون $G(t) \geq t$ على $\intcc q1$ ، ومنه $G \equiv \mathrm{id}$ هناك، وهو ما يقتل جميع المعاملات $p_n$ ( $n \geq 2$ ) ويناقض $m > 1$ . التقارب الهندسي: $q_n < q$ من أجل كل $n$ (بالتراجع، فالدالة $G$ متزايدة)، وتعطي مبرهنة القيمة المتوسطة $q - q_{n+1} = G'(c_n)(q - q_n)$ مع $c_n \in \intoo{q_n}q$ ، ومنه $G'(c_n) \leq G'(q) < 1$ و $q - q_n \leq q\,G'(q)^n$ . المسار الرفيق: للمقدار $\widehat G(t) = G(qt)/q = \sum_kp_kq^{k-1}t^k$ معاملات موجبة و $\widehat G(1) = G(q)/q = 1$ : فهو دالة مولّدة؛ ومتوسطه $\widehat G'(1) = G'(q) < 1$ : أي إنه تحت حرج. والعائلة الهندسية: $G(t) = \frac{q}{1-pt}$ ، $q_{\mathrm{ext}} = \frac qp$ ، و

\widehat G(t) = \frac pq\cdot\frac{q}{1 - p\frac qp t} = \frac{p}{1 - qt} :

أي قانون النسل الهندسي بعد تبادل $p$ و $q$ — فالمسار فوق الحرج منظورا إليه على حدث انقراضه هو المسار تحت الحرج المرآتي.

25. الجدول: $m < 1$ : $q = 1$ ، $\P(Z_n > 0) \asymp m^n$ (السؤالان 4 و5)، $\E(Y) = \frac1{1-m}$ ، وأجيال باقية متوسطها الشرطي محدود. $m = 1$ : $q = 1$ ، $\P(Z_n > 0) \sim \frac2{\sigma^2n}$ (كولموغوروف)، $\E(Y) = \infty$ مع $\P(Y > n) \asymp n^{-1/2}$ ، وباقون حجمهم $\sim \frac{\sigma^2n}2$ . $m > 1$ : $q < 1$ هو النقطة الثابتة الصغرى، و $q - q_n = O(G'(q)^n)$ ، ونمو $\E(Z_n) = m^n$ ، وبشرط الفناء يكون المسار هو المسار الرفيق تحت الحرج (السؤال 24). أما الأدوات: فقد حوّل تركيب الدوال المولّدة تراجع المجتمع إلى تكرار دوال؛ وثبّت التحدب هندسة النقط الثابتة؛ وحوّلت مبرهنة تايلور عند $1^-$ فرضيات العزوم إلى نشور محلية؛ واستخرج متوسط تشيزارو مقدار كولموغوروف $1/n$ من مجموع تلسكوبي. ويضيف مجلد السنة الثالثة المارتينغال $Z_n/ m^n$ — الذي تدقق نهايته شبه الأكيدة المقدار $\E(Z_n) = m^n$ فتجعله معدل نمو مسارا مسارا — ومبرهنة ياغلوم، وهي القانون النهائي وراء الهندسية الشرطية الملاحظة في السؤال 11.

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

الدالة المولّدة للاحتمالات

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