الدرس 1 من 2 · العمليات العشوائية
سلاسل ماركوف والتوزيع المستقر Markov Chains and Stationary Distributions
سلسلة ماركوف عملية عشوائية يعتمد مستقبلها على حاضرها فقط؛ تُوصف بمصفوفة انتقال صفوفها احتمالات، وتوزيعها بعد n خطوة \(p_0P^n\)، وتتقارب السلسلة غير القابلة للاختزال وغير الدورية إلى توزيع مستقر وحيد \(\pi = \pi P\).
محتويات الدرس
1 مقدمة
الطقس غداً يعتمد في نموذج بسيط على طقس اليوم فقط، لا على ما سبقه. هذه «خاصية ماركوف»، وهي تجعل نمذجة العمليات العشوائية المعقدة ممكنة بمصفوفة واحدة.
الأهداف التعليمية
- تعريف خاصية ماركوف ومصفوفة الانتقال
- حساب التوزيع بعد n خطوة بضرب المصفوفات
- إيجاد التوزيع المستقر بحل \(\pi = \pi P\)
- شرح شروط التقارب ودور القيمة الذاتية الثانية
2 لماذا ندرس هذا الموضوع؟
سلاسل ماركوف حاضرة في كل مكان في الذكاء الاصطناعي: التعلم المعزز مبني على عمليات قرار ماركوف (MDP)، وPageRank توزيع مستقر لسلسلة على روابط الويب، وطرق MCMC تولد عينات من توزيعات معقدة ببناء سلسلة توزيعها المستقر هو المطلوب، والنماذج اللغوية البسيطة (n-gram) سلاسل ماركوف على الكلمات.
3 الشرح النظري
خاصية ماركوف
\[P(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = P(X_{t+1} = j \mid X_t = i) = P_{ij}\]
المصفوفة P مصفوفة انتقال: عناصرها غير سالبة ومجموع كل صف 1 (مصفوفة عشوائية Stochastic Matrix).
التطور عبر الزمن
إذا كان \(p_t\) متجه صف لتوزيع الحالة عند الزمن t فإن \(p_{t+1} = p_t P\)، ومنه \(p_n = p_0 P^n\). وعنصر \((P^n)_{ij}\) هو احتمال الانتقال من i إلى j في n خطوة. في مثال الطقس (مشمس، غائم، ممطر):
\[P = \begin{bmatrix}0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.3 & 0.5\end{bmatrix}\]
احتمال أن يكون الجو مشمساً بعد يومين من يوم مشمس: \((P^2)_{11} = 0.7^2 + 0.2(0.3) + 0.1(0.2) = 0.57\).
التوزيع المستقر
التوزيع π مستقر إذا لم يتغير بخطوة: \(\pi = \pi P\) مع \(\sum_i \pi_i = 1\). أي أن π متجه ذاتي يساري لـ P بالقيمة الذاتية 1. لمثال الطقس \(\pi \approx (0.4565, 0.2826, 0.2609)\).
متى تتقارب السلسلة؟
- عدم القابلية للاختزال: يمكن الوصول من كل حالة إلى كل حالة.
- عدم الدورية: لا تُفرض على العودة دورة ثابتة الطول.
تحت هذين الشرطين (لحالات منتهية) يوجد π وحيد و\(p_n \to \pi\) من أي بداية، وسرعة التقارب يحكمها \(|\lambda_2|\) أكبر القيم الذاتية بعد 1 قيمة مطلقة: الخطأ يتناقص تقريباً مثل \(|\lambda_2|^n\). لمثال الطقس \(|\lambda_2| \approx 0.473\). أما السلسلة \(\begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}\) فدورية: تتأرجح ولا تتقارب، رغم أن لها توزيعاً مستقراً \((0.5, 0.5)\).
مبرهنة الإرجوديك
لسلسلة غير قابلة للاختزال، نسبة الوقت التي يقضيها مسار واحد طويل في الحالة i تقترب من \(\pi_i\). وهذا أساس MCMC: نشغّل سلسلة طويلاً ونستخدم مسارها عينات من π.
4 التعريفات الرياضية
- خاصية ماركوف
- المستقبل مستقل عن الماضي بمعلومية الحاضر.
- مصفوفة الانتقال
- مصفوفة عناصرها احتمالات الانتقال بين الحالات ومجموع كل صف فيها 1.\[P_{ij}=P(X_{t+1}=j|X_t=i)\]
- التوزيع المستقر
- توزيع على الحالات لا يتغير بخطوة من السلسلة.\[\pi=\pi P\]
- السلسلة الإرجودية
- سلسلة غير قابلة للاختزال وغير دورية تتقارب إلى توزيع مستقر وحيد.
- سلسلة ماركوف (Markov Chain)
- عملية عشوائية يعتمد فيها توزيع الحالة التالية على الحالة الحالية فقط.\[p_{t+1}=p_tP\]
- مصفوفة الانتقال (Transition Matrix)
- مصفوفة احتمالات الانتقال بين الحالات، مجموع كل صف فيها 1.\[P_{ij}=P(X_{t+1}=j|X_t=i)\]
- التوزيع المستقر (Stationary Distribution)
- توزيع لا يتغير بخطوة من السلسلة، وهو متجه ذاتي يساري بالقيمة الذاتية 1.\[\pi=\pi P\]
5 المعادلات
6 مثال محلول خطوة بخطوة
خطوتان
المسألة: من يوم مشمس، ما احتمال يوم مشمس بعد يومين؟
- \((P^2)_{11} = \sum_k P_{1k}P_{k1}\).
- \(= 0.49 + 0.06 + 0.02\).
النتيجة: \(0.57\)
توزيع مستقر لحالتين
المسألة: أوجد π لـ \(Q = \begin{bmatrix}0.9 & 0.1\\ 0.5 & 0.5\end{bmatrix}\).
- \(\pi_1 = 0.9\pi_1 + 0.5\pi_2\) أي \(0.1\pi_1 = 0.5\pi_2\).
- \(\pi_1 = 5\pi_2\) و\(\pi_1 + \pi_2 = 1\).
النتيجة: \(\pi = (5/6, 1/6) \approx (0.8333, 0.1667)\)
التوزيع المستقر للطقس
المسألة: أوجد π لمصفوفة الطقس.
- حل \(\pi(P - I) = 0\) مع \(\sum \pi_i = 1\).
- أو كرر \(p \leftarrow pP\) حتى الاستقرار.
النتيجة: \(\pi \approx (0.4565, 0.2826, 0.2609)\)
7 تطبيق عملي في الذكاء الاصطناعي
- التعلم المعزز: عملية قرار ماركوف تضيف إلى السلسلة أفعالاً ومكافآت؛ والسياسة الثابتة تجعل الحالات سلسلة ماركوف.
- MCMC: خوارزميات مثل Metropolis–Hastings تبني سلسلة توزيعها المستقر هو التوزيع اللاحق المطلوب.
- PageRank: رتب الصفحات هي التوزيع المستقر لمتصفح عشوائي.
8 مختبر تفاعلي مرتبط بالدرس
مصفوفة انتقال تعدّلها مع تطور التوزيع والتوزيع المستقر وقيمتها الذاتية الثانية، ومحاكاة مسار السلسلة ومقارنة التكرار التجريبي بالتوزيع المستقر، والمشي العشوائي مع نطاق الانحراف المعياري.
افتح مختبر سلاسل ماركوف9 تمارين تدريبية
أسئلة مراجعة للتفكير
- لماذا تكون 1 دائماً قيمة ذاتية لمصفوفة عشوائية؟
- ما الذي يمنع السلسلة الدورية من التقارب؟
- كيف تستفيد MCMC من مبرهنة الإرجوديك؟
أخطاء شائعة
- ضرب P في متجه عمود بدلاً من متجه صف (أو العكس) دون الانتباه إلى الاصطلاح.
- افتراض أن كل سلسلة تتقارب إلى توزيعها المستقر؛ الدورية لا تتقارب.
- نسيان شرط مجموع π يساوي 1 عند حل \(\pi = \pi P\).
- الخلط بين احتمال الانتقال في خطوة واحدة وفي n خطوة.
10 ملخص الدرس
- المستقبل يعتمد على الحاضر فقط.
- \(p_n = p_0P^n\).
- π متجه ذاتي يساري بالقيمة الذاتية 1.
- \(|\lambda_2|\) يحدد سرعة التقارب.
11 اختبار قصير
5 أسئلة · 10 دقائق · النجاح من 60% — اجتيازه يُكمل الدرس.
