الجبر الخطي · سلسلة ماركوف

سلسلة ماركوف

تنتقل سلسلة ماركوف عشوائيًا بين الحالات، وتعتمد احتمالات الحالة التالية على الحالة الحالية وحدها. إذا كانت ⁦P⁩ مصفوفة الانتقال، فتوزيع الغد هو توزيع اليوم مضروبًا من اليمين في ⁦P⁩. ومع التكرار نقترب غالبًا من توزيع مستقر ⁦π⁩ يحقق ⁦πP = π⁩، أي متجه ذاتي أيسر للقيمة الذاتية ⁦1⁩.

سلسلة ماركوف في هذا الرسم

في سلسلة ماركوف تعتمد احتمالات الحالة التالية على الحالة الحالية وحدها. والحالات هنا هي الصحو والغيوم والمطر. يسرد الصف ⁦ii⁩ من مصفوفة الانتقال ⁦PP⁩ احتمالات الغد إذا كنا اليوم في الحالة ⁦ii⁩، لذا كل صف متجه احتمالات. إذا كان توزيع اليوم هو متجه الصف ⁦pp⁩، فتوزيع الغد ⁦pPpP⁩، وبعد ⁦nn⁩ أيام يصبح ⁦pn=p0Pnp_n = p_0 P^n⁩. مع ثلاث حالات يمثَّل كل توزيع بنقطة في مثلث. كل رأس يعني أن حالة واحدة مؤكدة، والاحتمالات الثلاثة هي أوزان الرؤوس. النقاط الداكنة هي صفوف ⁦PP⁩، والنقطة الزرقاء هي البداية، والمسار الأحمر يصل بين ⁦p0,p1,p2,…p_0, p_1, p_2, \dots⁩.

ما الذي يحدث في خطوة واحدة؟

ترسل خطوة واحدة كل رأس إلى الصف المقابل له. إذا كان الصحو مؤكدًا اليوم، فتوزيع الغد هو الصف الأول. أي توزيع آخر ⁦pp⁩ متوسط موزون للرؤوس، لذا فإن ⁦pPpP⁩ متوسط الصفوف بالأوزان نفسها. ينتقل المثلث كله إلى المثلث الأصغر الذي تحدّده الصفوف، وبعد خطوتين إلى مثلث صفوف ⁦P2P^2⁩. إذا كانت جميع عناصر قوة ما للمصفوفة ⁦PP⁩ موجبة، ضاقت هذه المثلثات المتداخلة حتى نقطة واحدة هي التوزيع المستقر ⁦π\pi⁩.

لماذا ⁦π⁩ متجه ذاتي، وبأي سرعة يقترب منه ⁦p⁩ₙ؟

تحقق النقطة الثابتة ⁦πP=π\pi P = \pi⁩، ومن ثم فإن ⁦π\pi⁩ متجه ذاتي أيسر للقيمة الذاتية ⁦1 (⁩وبصيغة الأعمدة ⁦PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}⁩). مجموع مركّبات الفرق ⁦p0−πp_0 - \pi⁩ صفر. وعلى هذا الفضاء الجزئي تكون قيمتا ⁦PP⁩ الذاتيتان هما القيمتين الأخريين ⁦λ2,λ3\lambda_2, \lambda_3⁩. تضرب كل خطوة المتجه الواقع على اتجاه ذاتي في قيمته الذاتية. إذا كان معيار كل منهما أصغر من ⁦1⁩ فإن ⁦pnp_n⁩ يقترب من ⁦π\pi⁩، ويحدد المعيار الأكبر ⁦∣λ2∣|\lambda_2|⁩ معدل التقارب. في سلسلة الطقس ⁦∣λ2∣≈0.462|\lambda_2| \approx 0.462⁩، فيبقى بعد كل خطوة أقل بقليل من نصف المسافة عند كبر ⁦nn⁩، إذا كان للبداية مركّبة في اتجاه ⁦λ2\lambda_2⁩. وإذا كانت القيمتان مركّبتين يدور المسار أيضًا أثناء تقلّصه.

متى لا يتقارب التوزيع؟

في الدورة يتعاقب الصحو والغيوم والمطر بلا انقطاع. معيار كل من القيمتين الذاتيتين الأخريين يساوي ⁦1⁩، فيستمر ⁦pnp_n⁩ في الدوران إلا إذا بدأ من ⁦π\pi⁩. مع حالتين ماصّتين، يبقى الصحو والمطر كلٌّ على حاله، وتتكرر القيمة الذاتية ⁦1⁩ مرتين، ويثبت أي مزيج منهما. لذا يتقارب ⁦pnp_n⁩ ولكن غايته تعتمد على البداية. في سلسلة منتهية الحالات، يتقارب ⁦pnp_n⁩ إلى ⁦π\pi⁩ نفسه من كل بداية إذا وفقط إذا وُجدت فئة تواصل مغلقة واحدة وكانت غير دورية. يمكن الوصول من كل حالة فيها إلى كل حالة أخرى ولا يمكن مغادرتها. ويكفي، مثلًا، أن تكون كل عناصر قوة ما ⁦PmP^m⁩ موجبة.

ما يجدر ملاحظته

  • في سلسلة الطقس يعطي التوزيع المستقر احتمالات حالة الطقس في يوم بعيد أيًا كانت البداية. أما الطقس نفسه فيواصل التغيّر من يوم إلى آخر.
  • إذا زاد عدد الحالات على ثلاث، تملأ التوزيعات بسيطًا هندسيًا، وهو نظير المثلث في أبعاد أعلى. ويبقى الاستدلال نفسه صالحًا.

التحكم

  • اسحب نقطة داكنة لتغيير صف من مصفوفة الانتقال، أو النقطة الزرقاء لتغيير البداية. تحرّك مفاتيح الأسهم النقطة المحددة بمقدار ⁦0.01⁩.

مفاهيم ذات صلة