سلسلة ماركوف المتجانسة. سلاسل ماركوف العادية. هيكل بيانات الرسم التخطيطي

سلسلة ماركوف هي عملية ماركوف ذات الوقت المنفصل المحددة في مساحة قابلة للقياس.

مقدمة

تمت تسمية عمليات ماركوف العشوائية على اسم عالم الرياضيات الروسي البارز أ.ماركوف (1856-1922) ، الذي بدأ أولاً في دراسة الارتباط الاحتمالي للمتغيرات العشوائية وخلق نظرية يمكن أن يطلق عليها "ديناميات الاحتمالات".

في المستقبل ، أصبحت أسس هذه النظرية الأساس الأولي للنظرية العامة للعمليات العشوائية ، وكذلك للعلوم التطبيقية المهمة مثل نظرية عمليات الانتشار ، ونظرية الموثوقية ، ونظرية الطابور ، وما إلى ذلك. في الوقت الحاضر ، تستخدم نظرية عمليات ماركوف وتطبيقاتها على نطاق واسع في مختلف المجالات.

نظرًا للبساطة النسبية والوضوح للجهاز الرياضي ، والموثوقية العالية والدقة للحلول التي تم الحصول عليها ، حظيت عمليات ماركوف باهتمام خاص من المتخصصين المشاركين في أبحاث العمليات ونظرية اتخاذ القرار الأمثل.

مثال بسيط: رمي عملة معدنية

قبل وصف المخطط العام ، دعنا نلقي نظرة على مثال بسيط. لنفترض أننا نتحدث عن رمي عملة متتالية عند لعب "إرم" ؛ يتم رمي العملة في الأوقات المشروطة t = 0 ، 1 ، ... وفي كل خطوة يمكن للاعب الفوز بـ ± 1 بنفس الاحتمال 1/2 ، لذلك في الوقت t يكون ربحه الإجمالي متغيرًا عشوائيًا ξ (t) مع القيم الممكنة j = 0 ، ± 1 ، ...

بشرط أن ξ (t) = k ، في الخطوة التالية ، ستكون المكافأة مساوية بالفعل لـ ξ (t + 1) = k ± 1 ، مع أخذ القيم المشار إليها j = k ± 1 مع نفس الاحتمال 1/2.

تقليديا ، يمكننا القول أنه هنا ، مع الاحتمال المقابل ، هناك انتقال من الحالة ξ (t) = k إلى الحالة ξ (t + 1) = k ± 1.

الصيغ والتعاريف

بتعميم هذا المثال ، يمكن للمرء أن يتخيل "نظامًا" مع عدد لا يحصى من حالات "الطور" المحتملة ، والتي تنتقل عشوائيًا من حالة إلى حالة خلال وقت منفصل t = 0 ، 1 ، ....

لنفترض أن ξ (t) يكون موضعه في الوقت t نتيجة لسلسلة من التحولات العشوائية

ξ (0) - ξ (1) - ... - ξ (ر) - ... ... (1)

دعونا نشير رسميًا إلى جميع الحالات الممكنة من خلال الأعداد الصحيحة i = 0 ، ± 1 ، ... افترض أنه في حالة معروفة ξ (t) = k ، في الخطوة التالية يمر النظام إلى الحالة ξ (t + 1) = j مع الاحتمال الشرطي

ص كج = الفوسفور (ξ (ر + 1) = ي | ξ (ر) = ك) ... (2)

بغض النظر عن سلوكه في الماضي ، وبشكل أكثر دقة ، بغض النظر عن سلسلة التحولات (1) حتى اللحظة t:

الفوسفور (ξ (t + 1) = j | ξ (0) = i ، ... ، ξ (t) = k) = P (ξ (t + 1) = j | ξ (t) = k) للجميع ر ، ك ، ي ... (3) - ملكية ماركوف.

يسمى هذا المخطط الاحتمالي سلسلة ماركوف المتجانسة مع عدد لا يحصى من الدول- يكمن تجانسها في حقيقة أن (2) احتمالات الانتقال p kj، ∑ j p kj = 1 ، k = 0 ، ± 1 ، ... ، لا تعتمد على الوقت ، أي ، الفوسفور (ξ (t + 1) = j | ξ (t) = k) = P ij - مصفوفة احتمالية الانتقالفي خطوة واحدة لا تعتمد على ن.

من الواضح أن P ij عبارة عن مصفوفة مربعة بإدخالات غير سالبة ومجموع وحدات فوق الصفوف.

تسمى هذه المصفوفة (محدودة أو غير محدودة) بالمصفوفة العشوائية. يمكن لأي مصفوفة عشوائية أن تكون بمثابة مصفوفة لاحتمالات الانتقال.

في الممارسة العملية: تسليم المعدات من قبل المقاطعات

لنفترض أن شركة معينة تقدم معدات في موسكو: إلى المنطقة الشمالية (دعنا نشير أ) والجنوب (ب) والوسط (ج). الشركة لديها مجموعة من السعاة الذين يخدمون هذه المناطق. من الواضح أنه بالنسبة للتسليم التالي ، يذهب الساعي إلى المنطقة الأقرب إليه حاليًا. تم تحديد ما يلي إحصائيًا:

1) بعد التسليم إلى A ، يتم التسليم التالي في 30 حالة في A ، في 30 حالة - في B وفي 40 حالة - في C ؛

2) بعد التسليم إلى B ، يكون التسليم التالي في 40 حالة إلى A ، وفي 40 حالة إلى B ، وفي 20 حالة إلى C ؛

3) بعد التسليم إلى C ، يكون التسليم التالي في 50 حالة إلى A ، وفي 30 حالة إلى B ، وفي 20 حالة إلى C.

وبالتالي ، يتم تحديد منطقة التسليم التالي فقط من خلال التسليم السابق.

ستبدو مصفوفة احتمالية الانتقال كما يلي:

على سبيل المثال ، p 12 \ u003d 0.4 هو احتمال أنه بعد التسليم إلى المنطقة B ، سيتم التسليم التالي في المنطقة A.

لنفترض أن كل عملية تسليم ، متبوعة بالانتقال إلى المنطقة التالية ، تستغرق 15 دقيقة. بعد ذلك ، وفقًا للإحصاءات ، بعد 15 دقيقة ، سيكون 30 ٪ من السعاة الذين كانوا في A في A ، و 30 ٪ سيكونون في B و 40 ٪ في C.

نظرًا لأنه في اللحظة التالية ، سيكون كل من السعاة بالضرورة في إحدى المقاطعات ، فإن المجموع على الأعمدة هو 1. وبما أننا نتعامل مع الاحتمالات ، فإن كل عنصر من عناصر المصفوفة هو 0<р ij <1.

أهم ظرف يسمح لنا بتفسير هذا النموذج على أنه سلسلة ماركوف هو أن موقع الناقل في الوقت t + 1 يعتمد فقطمن الموقع في الوقت t.

الآن دعنا نطرح سؤالاً بسيطًا: إذا بدأ الساعي من C ، فما هو احتمال أن يكون في B ، بعد إجراء شحنتين ، أي كيف يمكنك تحقيق B في خطوتين؟ إذن ، هناك عدة مسارات من C إلى B في خطوتين:

1) أولاً من C إلى C ثم من C إلى B ؛

2) C -> B و B -> B ؛

3) ج -> أ و أ -> ب.

مع الأخذ في الاعتبار قاعدة مضاعفة الأحداث المستقلة ، نحصل على أن الاحتمال المطلوب يساوي:

P = P (CA) * P (AB) + P (CB) * P (BB) + P (CC) * P (CB)

استبدال القيم العددية:

P = 0.5 * 0.3 + 0.3 * 0.4 + 0.2 * 0.3 = 0.33

تشير النتيجة التي تم الحصول عليها إلى أنه إذا بدأ الساعي العمل من C ، فسيكون في 33 حالة من أصل 100 حالة في B بعد عمليتي تسليم.

من الواضح أن الحسابات بسيطة ، ولكن إذا كنت بحاجة إلى تحديد الاحتمال بعد 5 أو 15 عملية تسليم ، فقد يستغرق ذلك وقتًا طويلاً.

دعونا نعرض طريقة أبسط لحساب هذه الاحتمالات. من أجل الحصول على احتمالات الانتقال من حالات مختلفة في خطوتين ، نقوم بتربيع المصفوفة P:

ثم العنصر (2 ، 3) هو احتمال الانتقال من C إلى B في خطوتين ، والذي تم الحصول عليه أعلاه بطريقة مختلفة. لاحظ أن العناصر في مصفوفة P2 تتراوح أيضًا من 0 إلى 1 ، ومجموع الأعمدة هو 1.

الذي - التي. إذا كنت بحاجة إلى تحديد احتمالات الانتقال من C إلى B في 3 خطوات:

1 الطريق. p (CA) * P (AB) + p (CB) * P (BB) + p (CC) * P (CB) = 0.37 * 0.3 + 0.33 * 0.4 + 0.3 * 0.3 = 0.333 حيث p (CA) - احتمال الانتقال من C إلى A بخطوتين (أي ، هذا عنصر (1 ، 3) من المصفوفة P 2).

2 طريقة.حساب المصفوفة P 3:

ستبدو مصفوفة احتمالات الانتقال إلى القوة السابعة على النحو التالي:

من السهل ملاحظة أن عناصر كل صف تميل إلى بعض الأرقام. يشير هذا إلى أنه بعد عدد كبير بما فيه الكفاية من عمليات التسليم ، لم يعد من المهم في أي بلد بدأ الناقل العمل فيه. الذي - التي. في نهاية الأسبوع سيكون حوالي 38.9٪ في A و 33.3٪ في B و 27.8٪ في C.

يتم ضمان حدوث هذا التقارب إذا كانت جميع عناصر مصفوفة احتمالات الانتقال تنتمي إلى الفترة (0 ، 1).

عملية ماركوف- عملية عشوائية تحدث في النظام ، والتي لها الخاصية التالية: لكل لحظة من الزمن t 0 ، يعتمد احتمال أي حالة للنظام في المستقبل (لـ t> t 0) فقط على حالته في الوقت الحاضر ( بالنسبة إلى t = t 0) ولا تعتمد على ما إذا كان النظام قد وصل إلى هذه الحالة وكيف حدث ذلك (أي كيف تطورت العملية في الماضي).

من الناحية العملية ، غالبًا ما توجد عمليات عشوائية يمكن اعتبارها عمليات ماركوف بدرجات متفاوتة من التقريب.

يتم وصف أي عملية ماركوف باستخدام احتمالات الحالة واحتمالات الانتقال.

احتمالات الحالات P k (t) لعملية ماركوفهي احتمالات أن تكون العملية العشوائية (النظام) في الوقت t في الحالة S k:

احتمالات الانتقال لعملية ماركوفهي احتمالات انتقال العملية (النظام) من حالة إلى أخرى:

تسمى عملية ماركوف متجانسإذا كانت احتمالات الانتقال لكل وحدة زمنية لا تعتمد على مكان حدوث الانتقال على محور الوقت.

أبسط عملية هي سلسلة ماركوفهي عملية ماركوف العشوائية بزمن منفصل ومجموعة محدودة من الحالات.

في تحليل سلاسل ماركوف الرسم البياني للدولة، حيث يتم تحديد جميع حالات السلسلة (النظام) والاحتمالات غير الصفرية في خطوة واحدة.

يمكن التفكير في سلسلة ماركوف كما لو كانت نقطة تمثل نظامًا تتحرك بشكل عشوائي عبر رسم بياني للحالة ، أو تسحب من حالة إلى حالة في خطوة واحدة ، أو تبقى عدة خطوات في نفس الحالة.

تتم كتابة احتمالات الانتقال لسلسلة ماركوف في خطوة واحدة كمصفوفة P = || P ij || ، والتي تسمى مصفوفة احتمالية الانتقال أو ببساطة مصفوفة الانتقال.

مثال: مجموعة حالات طلاب التخصص كالتالي:

S 1 - طالبة ؛

S 2 - طالبة ... ؛

S 5 - طالب في السنة الخامسة ؛

ق 6 - أخصائي تخرج من الجامعة ؛

ق 7 - من درس في جامعة ولم يتخرج منها.

من الحالة S 1 في السنة ، يمكن الانتقال إلى الحالة S 2 مع احتمال r 1 ؛ S 1 مع الاحتمال q 1 و S 7 مع الاحتمال p 1 ، علاوة على ذلك:

ص 1 + س 1 + ص 1 = 1.

دعونا نبني رسمًا بيانيًا لحالات سلسلة ماركوف المحددة ونسميها باحتمالات انتقالية (بخلاف الصفر).

لنصنع مصفوفة لاحتمالات الانتقال:

تمتلك المصفوفات الانتقالية الخاصية:

جميع عناصرها غير سلبية ؛

مجموع الصفوف يساوي واحدًا.

تسمى المصفوفات مع هذه الخاصية العشوائية.

تسمح لك مصفوفات الانتقال بحساب احتمال أي مسار لسلسلة ماركوف باستخدام نظرية الضرب الاحتمالية.

بالنسبة لسلاسل Markov المتجانسة ، لا تعتمد مصفوفات الانتقال على الوقت.

عند دراسة سلاسل ماركوف ، الأكثر إثارة للاهتمام هي:

احتمالات الانتقال في خطوات م ؛

التوزيع حسب الدول في الخطوة م → ∞ ؛

متوسط ​​الوقت الذي يقضيه في دولة معينة ؛

متوسط ​​الوقت للعودة إلى هذه الحالة.

ضع في اعتبارك سلسلة ماركوف متجانسة مع عدد n من الدول. للحصول على احتمالية الانتقال من الحالة S i إلى الحالة S j بخطوات m ، وفقًا لصيغة الاحتمال الإجمالية ، قم بجمع نواتج احتمال الانتقال من الحالة Si إلى الحالة المتوسطة Sk في خطوات l من خلال احتمال الانتقال من Sk إلى Sj في الخطوات المتبقية m-l ، أي.

هذه النسبة لجميع أنا = 1 ، ... ، ن ؛ يمكن تمثيل j = 1،…، n كمنتج للمصفوفات:

P (m) = P (l) * P (m-l).

وهكذا لدينا:

P (2) = P (1) * P (1) = P2

P (3) = P (2) * P (1) = P (1) * P (2) = P 3 إلخ.

الفوسفور (م) = الفوسفور (م -1) * الفوسفور (1) = الفوسفور (1) * الفوسفور (م -1) = الف م ،

مما يجعل من الممكن العثور على احتمالات الانتقال بين الحالات في أي عدد من الخطوات ، مع معرفة مصفوفة الانتقال في خطوة واحدة ، وهي P ij (m) - عنصر من المصفوفة P (m) هناك احتمال للانتقال من الحالة S أنا أذكر S j بخطوات m.

مثال: يتغير الطقس في منطقة ما من ممطر إلى جاف لفترات طويلة من الزمن. إذا أمطرت ، فمع احتمال 0.7 ستمطر في اليوم التالي ؛ إذا كان الطقس جافًا في يوم ما ، فمن المحتمل أن يستمر 0.6 في اليوم التالي. ومن المعروف أن الطقس يوم الأربعاء كان ممطرًا. ما هو احتمال هطول الامطار الجمعة المقبل؟

دعنا نكتب جميع حالات سلسلة ماركوف في هذه المشكلة: D - طقس ممطر ، C - طقس جاف.

لنقم ببناء رسم بياني للحالة:

الجواب: ص 11 \ u003d ع (كعب D | D الأربعاء) \ u003d 0.61.

حدود الاحتمال р 1 (م) ، р 2 (م) ، ... ، р n (م) في م → ∞ ، إذا كانت موجودة ، تسمى الحد من احتمالات الدول.

من الممكن إثبات النظرية التالية: إذا كان من الممكن في سلسلة ماركوف الانتقال من كل حالة (لعدد أو آخر من الخطوات) إلى بعضها البعض ، فإن احتمالات الحد للحالات موجودة ولا تعتمد على الحالة الأولية حالة النظام.

وهكذا ، عند m → ∞ ، يتم إنشاء نظام محدد ثابت في النظام ، حيث يتم تنفيذ كل حالة من الحالات باحتمالية ثابتة معينة.

يجب أن يفي المتجه p ، المكون من احتمالات هامشية ، بالعلاقة: p = p * P.

متوسط ​​الوقت في الولاية S i في الوقت T تساوي p i * T ، حيث p i - الاحتمال المحدد للحالة S i. متوسط ​​الوقت للعودة إلى الحالة S i يساوي.

مثال.

بالنسبة للعديد من المشكلات الاقتصادية ، من الضروري معرفة تعاقب السنوات مع قيم معينة لتدفقات الأنهار السنوية. بالطبع ، لا يمكن تحديد هذا التناوب بدقة مطلقة. لتحديد احتمالات التناوب (الانتقال) ، نقسم التدفقات عن طريق إدخال أربعة تدرجات (حالات النظام): الأول (التدفق الأدنى) ، والثاني ، والثالث ، والرابع (أعلى تدفق). من أجل التحديد ، سنفترض أن التدرج الأول لا يتبعه أبدًا الرابع ، والرابع - بالتدرج الأول بسبب تراكم الرطوبة (في الأرض ، الخزان ، إلخ). أظهرت الملاحظات أنه في بعض المناطق ، من الممكن حدوث انتقالات أخرى ، و:

أ) يمكن للمرء أن ينتقل من التدرج الأول إلى كل من التدرجات الوسطى مرتين أكثر من التدرج الأول ، أي

ص 11 = 0.2 ؛ ص 12 = 0.4 ؛ ص 13 = 0.4 ؛ ص 14 = 0 ؛

ب) من التدرج الرابع ، تكون الانتقالات إلى التدرجين الثاني والثالث أكثر تواترًا بأربع وخمس مرات من العودة مثل e إلى الدرجة الثانية ، أي

صعب ، أي

إلى الرابع ، أي

p41 = 0 ؛ p42 = 0.4 ؛ p43 = 0.5 ؛ ص 44 = 0.1 ؛

ج) من الثاني إلى التدرجات الأخرى يمكن أن يكون أقل شيوعًا: في الأول - مرتين ، في الثالث بنسبة 25٪ ، في الرابع - أربع مرات أقل من الانتقال إلى الثاني ، أي

ص 21 = 0.2 ؛ ص 22 = 0.4 ؛ ص 23 = 0.3 ؛ ص 24 = 0.1 ؛

د) من التدرج الثالث ، يكون الانتقال إلى التدرج الثاني محتملًا مثل العودة إلى التدرج الثالث ، وتكون الانتقالات إلى التدرجين الأول والرابع أقل شيوعًا بأربع مرات ، أي

ص 31 = 0.1 ؛ ص 32 = 0.4 ؛ ص 33 = 0.4 ؛ ص 34 = 0.1 ؛

لنقم ببناء رسم بياني:

لنصنع مصفوفة لاحتمالات الانتقال:

أوجد متوسط ​​الوقت بين فترات الجفاف وسنوات ارتفاع المياه. للقيام بذلك ، تحتاج إلى إيجاد التوزيع المحدود. إنه موجود بسبب تم استيفاء شرط النظرية (المصفوفة P 2 لا تحتوي على أي عناصر صفرية ، أي في خطوتين ، يمكنك الانتقال من أي حالة للنظام إلى أي حالة أخرى).

حيث ص 4 \ u003d 0.08 ؛ p3 = ؛ ع 2 = ؛ p1 = 0.15

تكرار العودة إلى الحالة S i يساوي.

وبالتالي ، فإن تواتر السنوات الجافة يبلغ في المتوسط ​​6.85 ؛ 6-7 سنوات ، والامطار 12 سنة.

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

تسمى سلسلة ماركوف عاديإذا كان من الممكن الوصول إلى جميع حالات السلسلة من أي دولة أخرى. إذا كانت السلسلة منتظمة ، فيمكننا في أي وقت أن نكون في أي حالة ، بغض النظر عن الحالة الأولية. تسمى سلسلة ماركوف المتجانسة عادي، إذا كانت أي قوة من مصفوفة احتمالية الانتقال الخاصة بها P لا تحتوي على عناصر صفرية. كما هو معروف ، تسمى المصفوفة التي تفي بهذا الشرط إيجابي .

في عملية التشغيل ، يتخذ نظام الخدمة الخطوة من الدرجة الأولى إلى حالة أو أخرى باحتمال غير مشروط

في بعض الحالات ، لا تتغير هذه الاحتمالات لكل حالة من خطوة إلى أخرى ، أي

سلسلة ماركوف المتجانسة التي تكون فيها احتمالات الحالة هي نفسها ، أي لا تعتمد على فمُسَمًّى ثابت.خلاف ذلك ، تسمى الدائرة غير ثابتة.يسمى احتمالية الدول احتمالية ثابتة للدول.

لاحظ أن السلسلة العكسية ... ، 5 ، S „، S n l، ...سلسلة ماركوف الثابتة ... ، 5 ي ، S n ، S x، ... هي أيضًا سلسلة ماركوف ثابتة. سلسلة ماركوف الثابتة تفريغإذا وفقط إذا كانت هناك مجموعة من الأرقام الموجبة ص (ي) ،مجموعها يساوي 1 ، تلبية لشروط التوازن

لجميع الدول.

بالنسبة لدائرة ثابتة متجانسة ، تكون الصيغة صالحة

مما يدل على أنه في كل خطوة لا تتغير احتمالات حالات سلسلة ماركوف الثابتة وأن الضرب في مصفوفة احتمالات الانتقال ليس له أي تأثير. كما ترى ، فإن المتجه في (12.32) هو ملك (بلا حراك) ناقلاتمصفوفة P 5 تنتمي إلى العدد المميز A ، = 1. المصفوفة P 5 ستكون موجبة.

غالبًا ، في الخطوات الأولى ، يتصرف النظام على أنه غير ثابت ، وبعد عدد معين من الخطوات يكتسب خصائص الثبات. يسمى الوضع الثابت للنظام النظام القائم ،وغير ثابتة وضع الانتقال.

لسلسلة ماركوف ذات عدد محدود من الحالات ، بشرط ن rk (ع) > 0, ز ، ك = 1, ل،بدءا من بعض صهناك احتمالات محدودة (نهائية أو ثابتة) للدول

لذلك،

حالة : ، يعني أن P عبارة عن مصفوفة

احتمالات انتقال سلسلة منتظمة. في هذه الحالة ، المصفوفات P "تتلاقى مع بعض المصفوفات P:

حيث الكميات ، وتسمى هامش،أو أخير

نيويورك ، احتمالات الانتقال.من هنا

في نفس الوقت

بدمج المعادلتين الأخيرتين نحصل على (12.32).

إذا اخترنا eigenvector P / للمصفوفة العشوائية كمتجه للاحتمالات الأولية Pm (O) لسلسلة Markov المتجانسة ، فإن سلسلة Markov تكون ثابتة بدءًا من اللحظة t0.

تشكل الصفوف П y نفس متجه الاحتمال Р / ، ومكوناتها موجبة. المصفوفة P y هي أيضًا عشوائية:

نظرًا لأن صفوف P y هي نفسها ، فعند ضربها على اليسار بأي متجه احتمالي ، وفقًا لـ (12.7) ، يتم الحصول على صف من المصفوفة. لذلك ، فإن الاحتمالات النهائية لا تعتمد على الحالة الأولية.

تسمى المصفوفة العشوائية P وسلسلة ماركوف المتجانسة المقابلة صحيح،إذا كانت المصفوفة لا تحتوي على أرقام مميزة تختلف عن واحد وتساوي في القيمة المطلقة للواحد ، و عادي،إذا كان واحدًا بالإضافة إلى ذلك هو جذر بسيط للمعادلة المميزة للمصفوفة П.

توجد احتمالات الحد من الانتقال فقط لسلاسل ماركوف المتجانسة المنتظمة.

يكمن الرقم المميز للمصفوفة العشوائية دائمًا في الدائرة | أ |

إذا كانت المصفوفة P 5 موجودة ، فمن المستحسن حسابها دون إيجاد درجة المصفوفة P "وحدودها lim P" = P ° °.

ص-*? س

بالنسبة للمصفوفة العادية ، توجد مصفوفة P ، والتي يمكن حسابها بالصيغة:

حيث C (A) \ u003d (A1 - l) -1 cp (A) هي المصفوفة المصاحبة المخفضة ؛ cp (A) هو الحد الأدنى من كثير الحدود لمصفوفة منتظمة ؛ cp "(X) هو مشتق من كثير الحدود.

للمصفوفة العادية φ (A) = D (A) و ج (س) = ب (أ). لذلك،

أين - المصفوفة المرفقة أوه)هي كثيرة الحدود المميزة للمصفوفة العادية.

ضع في اعتبارك سلسلة ماركوف العادية ذات الحالتين مع مصفوفة احتمالية الانتقال (12.28). الأرقام المميزة المحسوبة للمصفوفة (12.29) مختلفة. لا يوجد سوى رقم مميز واحد ، يساوي 1 ، وهو جذر بسيط (وليس متعدد) للمعادلة المميزة (12.29). لحساب الاحتمالات النهائية ، نستخدم المصفوفة المرتبطة الموجودة مسبقًا (12.30). بالنسبة للجذر المميز Xj = 1

المشتق فيما يتعلق Xالمعادلات (12.29) أين

بحسب (12.34) ،

صفوف المصفوفة الناتجة هي نفسها ويجب أن تكون مساوية لاحتمالات الحالة النهائية. عند ضرب هذه المصفوفة على اليسار بأي متجه احتمالي (مجموع عناصر متجه الاحتمال يساوي 1) ، نحصل على صف من المصفوفة.

للمثال العددي الذي تم اعتباره سابقًا لإيجاد احتمالية أمر من قبل العميل في كل شهر

مصفوفة الاحتمالات النهائية تحسب على (12.35) ع

استبدال القيم العددية أ \ u003d 0.3 ، أ (3 \ u003d 0.4 ، نحصل عليها لذلك ، احتمالية الترتيب النهائي الاحتمال النهائي لعدم الطلب

وبالتالي ، عند استيفاء الشروط المذكورة أعلاه ، يميل متجه احتمالات الحالة غير المشروطة في الحد إلى متجه احتمالات الحالة الثابتة ، بغض النظر عن الحالات الأولية ، وتميل مصفوفة احتمالات الحالة الانتقالية ، بغض النظر عن متجه الحالة ، إلى مصفوفة ثابتة لاحتمالات الحالة الانتقالية. علاوة على ذلك ، فإن صفوف مصفوفة احتمالات الانتقال للحالات هي نفسها وتساوي متجه الحالات الثابتة.

سلاسل Ergodic Markov. يتم استدعاء سلاسل ماركوف التي توجد لها احتمالات نهائية ارجوديك.إذا كانت سلسلة ماركوف ergodic ، فمن الممكن من كل حالة من حالاتها الوصول إلى أي دولة أخرى. السلسلة المنتظمة هي دائمًا ergodic ، أي لا يحتوي على حالات لا رجعة فيها ولديه مجموعة فريدة من الحالات ergodic. يسمى النظام الموصوف بواسطة سلسلة ergodic Markov مستقرة إحصائيًا.

إذا كانت سلسلة ماركوف ergodic وتوجد احتمالات حالة ثابتة ، فمن الضروري حسابها. قبل ذلك ، تم إعطاء طرق لتحديد الاحتمالات الثابتة عن طريق حساب Eagle P "= P ° ° و P ° °.

ن->نظام التشغيل

ومع ذلك ، من الممكن حساب هذه الاحتمالات دون إيجاد المصفوفة الثابتة لاحتمالات الانتقال.

الاحتمالات النهائية ص ك ، ك = 1,ل،هي حل لنظام المعادلات

في تدوين المصفوفة (12.36) له الشكل

نظرًا لأن المعادلتين (12.36) و (12.37) احتمالية ، يجب أن تفي بشرط التطبيع

أو في تدوين المصفوفة

النظام (12.38) عبارة عن مصفوفة تعتمد خطيًا من الحجم مقصف صمفرد وله رتبة (ف - 1). لذلك ، لتجد لالاحتمالات النهائية غير المعروفة ، من الضروري استبدال إحدى معادلات النظام (12.36) بالمعادلة (12.38).

يمكن تمثيل المعادلة (12.37) كـ

لذلك ، لإيجاد حل ، من الضروري حل نظام المعادلات الخطية من النوع

عند الحل ، من الضروري استخدام شرط التسوية (12.39) ، لذلك يجب استبدال أحد أعمدة المصفوفة B بمتجه الوحدة 1 ، مما ينتج عنه المصفوفة C. إذا تم استبدال العمود الأخير من المصفوفة ، النظام (12.40) يتحول إلى النظام

أين

ضع في اعتبارك نظامًا مع دولتين. بحسب (12.36) ، دعونا نستبدل المعادلة الأخيرة للنظام بشرط التطبيع:

في رمز المصفوفة (12.41) ، ستكون عناصر المعادلة متساوية:

إذا كانت هناك مصفوفة معكوسة C -1 ، فيمكن إيجاد الحل في الصورة

بالنسبة للمثال قيد الدراسة ، توجد المصفوفة المعكوسة: لهذا

لأن ص ص\ u003d 1-7t 12 ، ص 21= 1-م 22 ، يمكن أيضًا كتابة الحل الموجود على هذا النحو

وهو ما يتوافق مع الحلول السابقة.

دعنا نوضح أنه إذا اخترنا متجه الحالات الثابتة كمتجه للحالات الأولية ، فستنتقل العملية فورًا إلى الحالة الثابتة في الخطوة الأولى.

سلاسل ماركوف

مقدمة

§ 1. سلسلة ماركوف

§ 2. سلسلة ماركوف المتجانسة. احتمالات الانتقال. مصفوفة الانتقال

§3. المساواة ماركوف

§4. التوزيع الثابت. نظرية الاحتمالات الهامشية

§5. دليل على نظرية الحد من الاحتمالات في سلسلة ماركوف

§6. تطبيقات سلاسل ماركوف

خاتمة

قائمة الأدب المستخدم

مقدمة

موضوع عملنا بالطبع هو سلسلة ماركوف. تمت تسمية سلاسل ماركوف على اسم عالم الرياضيات الروسي البارز ، أندريه أندرييفيتش ماركوف ، الذي درس العمليات العشوائية كثيرًا وقدم مساهمة كبيرة في تطوير هذا المجال. في الآونة الأخيرة ، يمكنك أن تسمع عن استخدام سلاسل Markov في مجموعة متنوعة من المجالات: تقنيات الويب الحديثة ، في تحليل النصوص الأدبية ، أو حتى في تطوير تكتيكات لعبة فريق كرة القدم. بالنسبة لأولئك الذين لا يعرفون ما هي سلاسل ماركوف ، قد يكون هناك شعور بأن هذا شيء معقد للغاية ولا يمكن فهمه تقريبًا.

لا ، العكس هو الصحيح. سلسلة ماركوف هي واحدة من أبسط الحالات لتسلسل الأحداث العشوائية. ولكن ، على الرغم من بساطتها ، يمكن أن تكون مفيدة في كثير من الأحيان حتى عند وصف الظواهر المعقدة نوعًا ما. سلسلة ماركوف هي سلسلة من الأحداث العشوائية التي يعتمد فيها احتمال كل حدث على الحدث السابق فقط ، ولكنه لا يعتمد على الأحداث السابقة.

قبل الخوض بشكل أعمق ، من الضروري النظر في بعض المشكلات المساعدة المعروفة جيدًا ، ولكنها ضرورية للغاية لمزيد من العرض.

الغرض من عملي هو الدراسة بمزيد من التفصيل لتطبيقات سلاسل ماركوف وبيان المشكلة ومشكلات ماركوف.

§1. سلسلة ماركوف

تخيل أنه يتم إجراء سلسلة من الاختبارات.

تعريف.سلسلة ماركوف هي سلسلة من المحاكمات ، في كل منها واحدة واحدة فقط

الأحداث غير المتوافقة للمجموعة الكاملة ، والاحتمال الشرطي لوقوع الحدث في التجربة -th ، بشرط أن يكون الحدث قد وقع في التجربة -th ، لا يعتمد على نتائج التجارب السابقة.

على سبيل المثال ، إذا كان تسلسل المحاكمات يشكل سلسلة ماركوف وتتكون المجموعة الكاملة من أربعة أحداث منفصلة

، ومن المعروف أن الحدث ظهر في التجربة السادسة ، ثم الاحتمال الشرطي لوقوع الحدث في التجربة السابعة لا يعتمد على الأحداث التي ظهرت في التجارب الأولى ، الثانية ، ... ، الخامسة.

لاحظ أن المحاكمات المستقلة هي حالة خاصة لسلسلة ماركوف. في الواقع ، إذا كانت التجارب مستقلة ، فإن حدوث حدث معين في أي تجربة لا يعتمد على نتائج التجارب التي أجريت سابقًا. ويترتب على ذلك أن مفهوم سلسلة ماركوف هو تعميم لمفهوم التجارب المستقلة.

في كثير من الأحيان ، عند تقديم نظرية سلاسل ماركوف ، فإنهم يلتزمون بمصطلحات مختلفة ويتحدثون عن بعض الأنظمة الفيزيائية

، والتي في كل لحظة من الوقت في إحدى الحالات: ، وتغير حالتها فقط في نقاط زمنية معينة ، أي أن النظام ينتقل من حالة إلى أخرى (على سبيل المثال ، من إلى). بالنسبة لسلاسل ماركوف ، فإن احتمال الذهاب إلى أي حالة في الوقت الحالي يعتمد فقط على الحالة التي كان فيها النظام في الوقت الحالي ، ولا يتغير من حقيقة أن حالاته أصبحت معروفة في لحظات سابقة. أيضًا ، على وجه الخصوص ، بعد الاختبار ، يمكن أن يظل النظام في نفس الحالة ("الانتقال" من حالة إلى أخرى).

للتوضيح ، فكر في مثال.

مثال 1تخيل أن جسيمًا يقع على خط مستقيم يتحرك على طول هذا الخط المستقيم تحت تأثير الصدمات العشوائية التي تحدث في لحظات

. يمكن أن يقع الجسيم في نقاط ذات إحداثيات صحيحة: ؛ عند نقاط وهناك جدران عاكسة. كل دفعة تحرك الجسيم إلى اليمين مع الاحتمال وإلى اليسار مع الاحتمال ، ما لم يكن الجسيم بالقرب من الحائط. إذا كان الجسيم موجودًا بالقرب من الحائط ، فإن أي دفع يحركه وحدة واحدة داخل الفجوة بين الجدران. هنا نرى أن هذا المثال لسير الجسيمات هو سلسلة ماركوف النموذجية.

وهكذا ، فإن الأحداث تسمى حالات النظام ، والاختبارات تسمى التغييرات في حالاته.

دعونا الآن نحدد سلسلة ماركوف باستخدام المصطلحات الجديدة.

سلسلة ماركوف ذات الوقت المنفصل هي سلسلة تتغير حالاتها عند نقاط زمنية ثابتة معينة.

سلسلة ماركوف المستمرة هي سلسلة تتغير حالاتها في أي وقت عشوائي ممكن.

§2. سلسلة ماركوف المتجانسة. احتمالات الانتقال. مصفوفة الانتقال

تعريف.يُقال أن سلسلة ماركوف متجانسة إذا كان الاحتمال الشرطي

(الانتقال من حالة إلى أخرى) لا يعتمد على رقم الاختبار. لذلك ، بدلا من الكتابة ببساطة.

مثال 1تجول عشوائي. دعه على خط مستقيم

يقع الجسيم المادي عند نقطة ذات إحداثيات عدد صحيح. في لحظات معينة من الزمن ، يتعرض الجسيم للصدمات. تحت تأثير الدفع ، يتم إزاحة الجسيم بواحد إلى اليمين مع احتمال وواحد إلى اليسار. من الواضح أن موضع (إحداثيات) الجسيم بعد الصدمة يعتمد على مكان وجود الجسيم بعد الصدمة السابقة مباشرة ، ولا يعتمد على كيفية تحركه تحت تأثير الصدمات السابقة الأخرى.

وبالتالي ، فإن السير العشوائي هو مثال على سلسلة ماركوف المتجانسة ذات الوقت المنفصل.

من تلقاء نفسها ، ونعتبرها جزئيًا بسبب حقيقة أن عرضها لا يتطلب إدخال عدد كبير من المصطلحات الجديدة.

ضع في اعتبارك مشكلة وقوف حمار بالضبط بين كومة من قش الجاودار وقش القمح (الشكل 10.5).

يقف الحمار بين صدمتين: "الجاودار" و "القمح" (الشكل 10.5). في كل دقيقة إما يتحرك عشرة أمتار نحو الصدمة الأولى (مع احتمال) ، أو نحو الصدمة الثانية (مع احتمال) ، أو يبقى حيث كان (مع احتمال) ؛ يسمى هذا السلوك أحادي البعد مشي عشوائي.سنفترض أن كلتا الصدمات "تمتص" بمعنى أنه إذا تعرض الحمار لإحدى الصدمات ، فسيظل هناك. بمعرفة المسافة بين الصدمتين والوضع الأولي للحمار ، يمكننا طرح عدة أسئلة ، على سبيل المثال: ما هي الصدمة التي من المرجح أن يجد نفسه فيها وما هو الوقت الذي سيحتاجه على الأرجح للوصول إلى هناك؟

أرز. 10.5.

لاستكشاف هذه المشكلة بمزيد من التفصيل ، افترض أن المسافة بين الصدمات خمسون متراً وأن حمارنا يبعد عشرين متراً عن صدمة "القمح". إذا كانت الأماكن التي يمكنك التوقف فيها ، فحدّد من خلالها (- الصدمات نفسها) ، عندئذٍ يمكن تحديد موضعها الأولي بواسطة المكوِّن المتجه -th الذي يساوي احتمال وقوعه في البداية. علاوة على ذلك ، بعد دقيقة واحدة ، يتم وصف احتمالات موقعها بواسطة المتجه ، وبعد دقيقتين - بواسطة المتجه. من الواضح أن الحساب المباشر لاحتمالية وجوده في مكان معين بعد مرور دقائق يصبح صعبًا. اتضح أنه من الأنسب تقديم هذا مصفوفة الانتقال.

فليكن احتمال أن ينتقل من إلى في دقيقة واحدة. على سبيل المثال ، و. تسمى هذه الاحتمالات احتمالات الانتقال، والمصفوفة تسمى مصفوفة الانتقال. لاحظ أن كل عنصر من عناصر المصفوفة غير سالب وأن مجموع عناصر أي من الصفوف يساوي واحدًا. من كل هذا يتبع ذلك - متجه الصف الأولي المحدد أعلاه ، يتم وصف موقع الحمار بعد دقيقة واحدة بواسطة متجه الصف ، وبعد دقائق - بواسطة المتجه. بعبارة أخرى ، يحدد المكون -th للناقل احتمالية أن ينتهي الأمر بالحمار.

يمكن تعميم هذه المفاهيم. لنتصل متجه الاحتمالمتجه صف جميع مكوناته غير سالبة ويجمع ما يصل إلى واحد. ثم مصفوفة الانتقالتُعرَّف بأنها مصفوفة مربعة يكون فيها كل صف متجهًا احتماليًا. الآن يمكنك تحديد سلسلة ماركوف (أو مجرد سلسلة) كزوج حيث يوجد - مصفوفة الانتقال، وهناك متجه صف. إذا تم اعتبار كل عنصر من احتمالًا للانتقال من موضع إلى آخر ، و- كمتجه أولي للاحتمالات ، فإننا نأتي إلى المفهوم الكلاسيكي سلسلة ماركوف الثابتة المنفصلة، والتي يمكن العثور عليها في الكتب حول نظرية الاحتمال (انظر Feller V. مقدمة لنظرية الاحتمال وتطبيقاتها. T.1. M.: Mir. 1967) وعادة ما يسمى الموقف حالة السلسلة. دعونا نصف طرق مختلفة لتصنيفها.

سنهتم بما يلي: هل من الممكن الانتقال من حالة إلى أخرى ، وإذا كان الأمر كذلك ، في أي حد أدنى من الوقت. على سبيل المثال ، في مشكلة الحمار ، يمكن للمرء أن ينتقل من إلى في غضون ثلاث دقائق ولا يمكنه عمومًا الانتقال من إلى. لذلك ، سنكون مهتمين بشكل أساسي ليس بالاحتمالات نفسها ، ولكن فيما إذا كانت إيجابية أم لا. ثم هناك أمل في أن يتم تمثيل كل هذه البيانات في شكل رسم بياني ، تتوافق رؤوسه مع الحالات ، وتشير الأقواس إلى ما إذا كان من الممكن الانتقال من حالة إلى أخرى في دقيقة واحدة. بتعبير أدق ، إذا تم تمثيل كل ولاية برأسها المقابل).