Марковын гинжин хэлхээний хязгаарлах магадлалыг ол. Марковын хэлхээ нь энгийн: зарчмыг нарийвчлан авч үзье

Марковын гинж

Танилцуулга

§ 1. Марковын хэлхээ

§ 2. Нэг төрлийн Марковын хэлхээ. Шилжилтийн магадлал. Шилжилтийн матриц

§3. Марковын тэгш байдал

§4. Суурин хуваарилалт. тухай теорем ахиу магадлал

§5. Марковын гинжин хэлхээнд магадлалыг хязгаарлах теоремын баталгаа

§6. Марковын гинжин хэлхээний хэрэглээ

Дүгнэлт

Ашигласан уран зохиолын жагсаалт

Танилцуулга

Бидний сэдэв курсын ажилМарковын гинж. Марковын гинжийг Оросын нэрт математикч Андрей Андреевич Марковын нэрээр нэрлэжээ. санамсаргүй үйл явцмөн энэ салбарын хөгжилд ихээхэн хувь нэмэр оруулсан. IN сүүлийн үедМарковын гинжийг ашиглах талаар хамгийн их сонсож болно өөр өөр газар нутаг: орчин үеийн вэб технологиуд, уран зохиолын текстийг шинжлэх эсвэл бүр хөлбөмбөгийн багийн тактик боловсруулах үед. Марковын гинж гэж юу болохыг мэдэхгүй хүмүүст энэ нь маш нарийн төвөгтэй, бараг ойлгомжгүй зүйл мэт санагдаж магадгүй юм.

Үгүй ээ, яг эсрэгээрээ. Марковын гинж нь хамгийн алдартай нь юм энгийн тохиолдлууддараалал санамсаргүй үйл явдлууд. Гэсэн хэдий ч энэ нь энгийн боловч нэлээд төвөгтэй үзэгдлүүдийг дүрслэх үед ч тустай байдаг. Марковын гинжин хэлхээ нь санамсаргүй үйл явдлын дараалал бөгөөд үйл явдал бүрийн магадлал нь зөвхөн өмнөх үйл явдлуудаас хамаардаг боловч өмнөх үйл явдлуудаас хамаардаггүй.

Гүнзгийрүүлэхээсээ өмнө бид ерөнхийд нь мэддэг, гэхдээ цаашдын тайлбарлахад зайлшгүй шаардлагатай хэд хэдэн туслах асуудлыг авч үзэх хэрэгтэй.

Миний курсын ажлын зорилго бол Марковын хэлхээний хэрэглээ, асуудлын мэдэгдэл, Марковын бодлогуудыг илүү нарийвчлан судлах явдал юм.

§1. Марковын гинж

Дараалсан туршилтууд хийгдэж байна гэж төсөөлөөд үз дээ.

Тодорхойлолт.Марковын гинжин хэлхээ нь туршилтын дараалал бөгөөд тус бүрд дараах зүйлсийн зөвхөн нэг нь гарч ирдэг. үл нийцэх үйл явдлуудбүтэн бүлэг, ба нөхцөлт магадлалдах туршилтанд үйл явдал тохиолдох болно , үйл явдал th шүүх хурал болсон тохиолдолд , өмнөх сорилтын үр дүнгээс хамаарахгүй.

Жишээлбэл, хэрэв туршилтын дараалал нь Марковын гинжин хэлхээг бүрдүүлж, бүрэн бүлэг нь үл нийцэх дөрвөн үйл явдлаас бүрдэх бөгөөд энэ үйл явдал зургаа дахь шүүх хуралдаанд болсон нь мэдэгдэж байгаа бол долоо дахь туршилтад тохиолдох нөхцөлт магадлалаас хамаарахгүй. Эхний хоёр дахь, ..., тав дахь туршилтуудад ямар үйл явдал гарсан.

Үүнийг анхаарна уу бие даасан туршилтуудМарковын гинжин хэлхээний онцгой тохиолдол юм. Үнэн хэрэгтээ, хэрэв тестүүд бие даасан байвал зарим нь харагдах болно тодорхой үйл явдалаливаа туршилтын хувьд өмнө нь хийсэн шинжилгээний үр дүнгээс хамаардаггүй. Үүнээс үзэхэд Марковын гинжин хэлхээний тухай ойлголт нь бие даасан туршилтын үзэл баримтлалын ерөнхий ойлголт юм.

Ихэнхдээ Марковын гинжин хэлхээний онолыг танилцуулахдаа тэд өөр нэр томъёог баримталж, зарим талаар ярьдаг физик систем, энэ нь цаг хугацааны агшин бүрд аль нэг төлөвт байна: , мөн төлөвөө зөвхөн цаг хугацааны тусдаа цэгүүдэд өөрчилдөг, өөрөөр хэлбэл систем нь нэг төлөвөөс нөгөөд шилждэг (жишээлбэл, -ээс). Марковын гинжин хэлхээний хувьд аль ч муж руу явах магадлал өндөр байдаг тухайн үед тухайн систем нь тухайн үед ямар төлөвт байсанаас л хамаарах ба өмнөх мөчүүдийн төлөв байдал нь тодорхой болсон тул өөрчлөгддөггүй. Түүнчлэн, ялангуяа туршилтын дараа систем нь ижил төлөвт үлдэж болно ("төрөөс муж руу шилжих").

Үүнийг харуулахын тулд жишээг авч үзье.

Жишээ 1.Шулуун шугам дээр байрлах бөөмс хором мөчид тохиолдох санамсаргүй цохилтын нөлөөн дор энэ шулуун шугамын дагуу хөдөлж байна гэж төсөөлье. Бөөмс нь бүхэл координаттай цэгүүдэд байрлаж болно: ; Цацруулагч хана нь цэгүүдэд байрладаг. Түлхэлт бүр нь бөөмсийг хананы ойролцоо байхаас бусад тохиолдолд магадлалын дагуу баруун тийш, магадлалын дагуу зүүн тийш шилжүүлдэг. Хэрэв бөөмс нь хананд ойрхон байвал ямар ч түлхэлт нь хананы хоорондох зайд нэг нэгжийг хөдөлгөдөг. Эндээс бид бөөмийн алхаж буй энэ жишээ Марковын ердийн гинж болохыг харж байна.

Тиймээс үйл явдлуудыг системийн төлөв, тестийг төлөв байдлын өөрчлөлт гэж нэрлэдэг.

Одоо шинэ нэр томьёо ашиглан Марковын хэлхээг тодорхойлъё.

Дискрет цагийн Марковын хэлхээ нь тодорхой тогтсон хугацаанд төлөвүүд нь өөрчлөгддөг хэлхээ юм.

Марковын гинж тасралтгүй хугацааЦаг хугацааны санамсаргүй тохиолдлын аль ч үед төлөвүүд нь өөрчлөгддөг хэлхээг нэрлэдэг.

§2. Нэг төрлийн Марковын гинж. Шилжилтийн магадлал. Шилжилтийн матриц

Тодорхойлолт.Хэрэв нөхцөлт магадлал (төрөөс муж руу шилжих) туршилтын тооноос хамаарахгүй бол Марковын гинжийг нэгэн төрлийн гэж нэрлэдэг. Тиймээс энгийнээр бичихийн оронд .

Жишээ 1.Санамсаргүй алхах. Бүхэл тооны координаттай цэг дээр шулуун шугам дээр материаллаг бөөм байг. Тодорхой цаг мөчид бөөмс нь цочролыг мэдэрдэг. Түлхэлтийн нөлөөн дор бөөмс нь нэг нэгжийн магадлалтайгаар баруун тийш, магадгүй нэг нэгж зүүн тийш хөдөлдөг. Цочролын дараах бөөмсийн байрлал (координат) нь шууд өмнөх цочролын дараа тухайн бөөмс хаана байснаас хамаарах бөгөөд өмнөх бусад цочролын нөлөөн дор хэрхэн хөдөлж байгаагаас хамаарахгүй нь ойлгомжтой.

Тиймээс санамсаргүй алхалт нь салангид хугацаатай нэгэн төрлийн Марковын гинжин хэлхээний жишээ юм.

Шилжилтийн магадлал гэдэг нь тухайн төлөвөөс (ямар нэгэн туршилтын үр дүнд систем өөрийгөө олсон, ямар ч тооноос үл хамааран) дараагийн туршилтын үр дүнд систем төлөвт шилжих нөхцөлт магадлал юм.

Тиймээс тэмдэглэгээнд эхний индекс нь өмнөх төлөвийн тоог, хоёр дахь нь дараагийн төлөвийн тоог заана. Жишээлбэл, хоёр дахь төлөвөөс гурав дахь төлөв рүү шилжих магадлал.

Төлөвийн тоог хязгаартай, тэнцүү байг.

Системийн шилжилтийн матриц нь энэ системийн шилжилтийн бүх магадлалыг агуулсан матриц юм.

Матрицын мөр бүр нь үйл явдлын магадлалыг (ижил төлөвөөс аль ч боломжит төлөв рүү шилжих) агуулдаг. бүтэн бүлэг, тэгвэл эдгээр үйл явдлын магадлалын нийлбэр нэгтэй тэнцүү байна. Өөрөөр хэлбэл, шилжилтийн матрицын мөр бүрийн шилжилтийн магадлалын нийлбэр нь нэгтэй тэнцүү байна.

Гурван төлөвт байж болох системийн шилжилтийн матрицын жишээг өгье; төлөв байдлаас төлөв рүү шилжих нь нэгэн төрлийн Марковын гинжин хэлхээний схемийн дагуу явагддаг; Шилжилтийн магадлалыг матрицаар өгөв.

Хэрэв систем төлөв байдалд байсан бол нэг алхамаар төлөвийг өөрчилсний дараа 0.5 магадлалтай, 0.5 магадлалтай, 0.2 магадлалтай төлөвт шилжинэ гэдгийг эндээс харж болно. дараа нь шилжилтийн дараа энэ нь мужуудад дуусч болно; энэ нь мужаас шилжих боломжгүй. Сүүлийн мөрМатриц нь төлөвөөс аль нэгэнд шилжихийг харуулж байна боломжит мужуудижил магадлал нь 0.1.

Системийн шилжилтийн матриц дээр үндэслэн та системийн төлөвийн график гэж нэрлэгдэх боломжтой. Энэ нь хэлхээг дүрслэн харуулахад тохиромжтой. График байгуулах дарааллыг жишээн дээр авч үзье.

Жишээ 2.Өгөгдсөн шилжилтийн матрицыг ашиглан төлөвийн график байгуул.

Учир нь матриц дөрөв дэх захиалга, тэгвэл систем нь 4 боломжит төлөвтэй байна.

График нь системийн нэг төлөвөөс ижил төлөв рүү шилжих магадлалыг заагаагүй болно. Бодож байхдаа тодорхой системүүдЭхлээд төлөвийн графикийг байгуулж, дараа нь системийн нэг төлөвөөс ижил төлөв рүү шилжих магадлалыг (матрицын эгнээний элементүүдийн нийлбэр нэгтэй тэнцүү байх шаардлагад үндэслэн) тодорхойлж, дараа нь шилжилтийг байгуулах нь тохиромжтой. системийн матриц.

§3. Марковын тэгш байдал

Тодорхойлолт.Алхамуудын (туршилтын) үр дүнд систем төлөвөөс төлөв рүү шилжих магадлалыг тэмдэглэе. Жишээлбэл, хоёр дахь төлөвөөс тав дахь төлөв рүү 10 алхамаар шилжих магадлал.

Бид шилжилтийн магадлалыг олж авдаг гэдгийг онцолж байна

Шилжилтийн магадлалыг мэдэж, системээс төлөв рүү шилжих магадлалыг алхам алхмаар олоорой.

Үүний тулд бид завсрын төлөвийг (ба хооронд) авч үзэх болно. Өөрөөр хэлбэл, эхний төлөвөөс алхам алхмаар систем нь магадлал бүхий завсрын төлөвт шилжин, үүний дараа завсрын төлөвөөс үлдсэн үе шатанд магадлал бүхий эцсийн төлөвт шилжинэ гэж бид таамаглах болно.

Томъёоны дагуу бүрэн магадлал, бид авдаг

. (1)

Энэ томъёог Марковын тэгш байдал гэж нэрлэдэг.

Тайлбар.Дараах тэмдэглэгээг танилцуулъя.

– бидний сонирхож буй үйл явдал (систем эхний төлөвөөс эцсийн төлөв рүү алхам алхмаар шилжих), тиймээс, ; − таамаглалууд (систем эхний төлөвөөс завсрын төлөв рүү алхам алхмаар шилжинэ), тиймээс − таамаглал гарсан тохиолдолд үүсэх нөхцөлт магадлал (алхам алхмаар систем завсрын төлөвөөс эцсийн төлөвт шилжих болно), тиймээс,

Нийт магадлалын томъёоны дагуу,

()

Эсвэл бидний баталсан тэмдэглэгээнд

Марковын томъёо (1)-тэй давхцаж байна.

Шилжилтийн бүх магадлалыг мэддэг, өөрөөр хэлбэл, төлөвөөс төлөв рүү шилжих матрицыг нэг алхамаар мэддэг тул та төлөвөөс төлөв рүү шилжих магадлалыг хоёр үе шаттайгаар олж чадна, тиймээс шилжилтийн матриц өөрөө; мэдэгдэж байгаа матрицыг ашигласнаар та төлөвөөс төлөв рүү шилжих матрицыг гурван үе шаттайгаар олох боломжтой.

Үнэн хэрэгтээ Марковын тэгш байдлыг оруулав

,

тэмдгийн гинжин санамсаргүй магадлал

,

(2)

Тиймээс (2) томъёог ашиглан та бүх магадлалыг олж, улмаар матрицыг өөрөө олж болно. Томъёо (2)-ыг шууд ашиглах нь уйтгартай болж, матрицын тооцоолол нь зорилгодоо хурдан хүргэдэг тул би (2)-оос үүсэх харилцааг матриц хэлбэрээр бичнэ.

(1)-д оруулснаар бид мөн адил олж авна

Ерөнхийдөө

Теорем 1.Ямар ч s, t

(3)

Баталгаа. Магадлалыг тооцоод үзье нийт магадлалын томъёог ашиглан (), тавих

Тэнцүү байдлаас

Эндээс тэгшитгэлээс (4) ба

бид теоремын мэдэгдлийг олж авна.

В матрицыг тодорхойлъё матрицын тэмдэглэгээ(3) хэлбэртэй байна

Түүнээс хойш шилжилтийн магадлалын матриц хаана байна. (5)-аас дараах байдалтай байна

(6)

Матрицын онолоор олж авсан үр дүн нь (6) томъёог ашиглан тэдгээрийн зан төлөвийг тооцоолох, судлах боломжийг олгодог

Жишээ 1.Шилжилтийн матрицыг тодорхойлсон Шилжилтийн матрицыг ол

Шийдэл. Томьёог ашиглацгаая

Матрицуудыг үржүүлснээр бид эцэст нь авна:

.

§4. Суурин хуваарилалт. Хязгаарын магадлалын теорем

Цаг хугацааны дурын цэг дэх магадлалын тархалтыг нийт магадлалын томъёог ашиглан олж болно

(7)

Энэ нь цаг хугацаанаас хамаардаггүй нь харагдаж магадгүй юм. За дуудъя суурин хуваарилалтвектор , нөхцөлийг хангаж байна

шилжилтийн магадлал хаана байна.

Хэрэв Марковын хэлхээнд байгаа бол дараа нь аль нэгэнд нь

Энэ мэдэгдлийг (7) ба (8)-ын индукц дагаж мөрдөнө.

Нэгийн хязгаарлах магадлалын тухай теоремын томъёоллыг танилцуулъя чухал ангиМарковын гинж.

Теорем 1. Хэрэв зарим >0-ийн хувьд матрицын бүх элементүүд эерэг байвал дурын хувьд , for

, (9)

Хаана 0-ийн тэгш бус байдлыг хангадаг тогтмол тоотой хөдөлгөөнгүй тархалт< h <1.

, тэгвэл теоремын нөхцлийн дагуу аль ч төлөвөөс эерэг магадлал бүхий аль ч төлөвт цаг хугацааны хувьд хүрч болно. Теоремын нөхцлүүд нь тодорхой утгаараа үечилсэн гинжийг оруулаагүй болно.

Хэрэв теорем 1-ийн нөхцөл хангагдсан бол систем тодорхой төлөвт байх магадлал нь анхны тархалтын хязгаараас хамаарахгүй. Үнэн хэрэгтээ, (9) ба (7) -аас харахад аливаа анхны хуваарилалтын хувьд,

Теорем 1-ийн нөхцөл хангагдаагүй Марковын гинжин хэлхээний хэд хэдэн жишээг авч үзье. Ийм жишээнүүд жишээ гэдгийг батлахад хэцүү биш юм. Жишээн дээр шилжилтийн магадлал нь хязгаартай боловч эдгээр хязгаар нь анхны төлөвөөс хамаарна. Ялангуяа хэзээ

Бусад жишээн дээр магадлалын хүрээ байхгүй нь ойлгомжтой.

1-р жишээнд суурин тархалтыг олъё. Векторыг олох хэрэгтэй хангах нөхцөл (8):

,

;

Тиймээс, хөдөлгөөнгүй тархалт байгаа боловч бүх координат вектор эерэг биш байна.

Олон гишүүнт схемийн хувьд өгөгдсөн төрлийн үр дүнгийн тоотой тэнцүү санамсаргүй хэмжигдэхүүнүүдийг оруулсан. Марковын гинжин хэлхээнд ижил төстэй хэмжигдэхүүнүүдийг танилцуулъя. Систем цаг хугацаанд нь төлөвт орох тоог хэлье. Дараа нь системийн цохилтын давтамж төрийн . (9) томъёог ашиглан бид ойртох үед үүнийг баталж чадна. Үүнийг хийхийн тулд та Чебышевын тэгш бус байдлын асимптотик томьёог олж, ашиглах хэрэгтэй. -ийн томъёоны гарал үүслийг энд үзүүлэв. Үүнийг хэлбэрээр илэрхийлье

(10)

хаана, хэрэв, мөн өөрөөр. Учир нь

,

дараа нь математикийн хүлээлт ба томъёоны (9) өмчийг ашиглан бид олж авна

.

Теорем 1-ийн дагуу энэхүү тэгш байдлын баруун талд байгаа гурвалсан гишүүн нь нийлсэн цувааны хэсэгчилсэн нийлбэр юм. тавих , бид авдаг

Учир нь

Томъёогоор (11) тухайлбал, энэ нь дараах байдалтай байна

цагт

Та мөн ялгааг тооцоолоход ашигладаг томъёог авч болно.

§5. Марковын гинжин хэлхээнд магадлалыг хязгаарлах теоремын баталгаа

Эхлээд хоёр лемма баталъя. тавья

Лемма 1. Аливаад хязгаарлалт байдаг

Баталгаа. (3) тэгшитгэлийг ашиглан бид олж авна

Тиймээс дараалал нь монотон, хязгаарлагдмал байдаг. Энэ нь Лемма 1-ийн мэдэгдлийг илэрхийлж байна.

Лемма 2. Хэрэв теорем 2-ын нөхцөл хангагдсан бол тогтмолууд байна. тиймэрхүү

Дурын хувьд

Энд нь эерэг байгаа бүхний нийлбэр, бусад нь нийлбэр гэсэн үг. Эндээс

. (12)

Теорем 1-ийн нөхцлийн дагуу шилжилтийн магадлал бүгдэд, дараа нь аль нэгэнд

Мөн хязгаарлагдмал тооны мужуудаас болж

Одоо ялгааг тооцоолъё . (3) тэгшитгэлийг ашиглан , , бид олж авна

Эндээс бид (8)-(10) ашиглан олно

=.

Энэ хамаарлыг тэгш бус байдал (14)-тэй хослуулснаар бид леммын мэдэгдлийг олж авна.

Теоремын баталгаа руу оч. Дараалал нь монотон байдаг тул

0<. (15)

Үүнээс болон Лемма 1-ээс бид олж мэднэ

Тиймээс, та авах үед болон

Эерэг нь тэгш бус байдлаас үүдэлтэй (15). (3) тэгшитгэлийн хязгаарт хүрч бид (12) тэгшитгэлийг хангана. Теорем нь батлагдсан.

§6. Марковын гинжин хэлхээний хэрэглээ

Марковын гинж нь санамсаргүй үйл явцын онолын сайн танилцуулга болж өгдөг. Ихэнх хэрэглээнд цаг хугацааны үүрэг гүйцэтгэдэг параметрээс хамаардаг санамсаргүй хэмжигдэхүүний гэр бүлийн энгийн дарааллын онол. Энэ нь үндсэндээ үйл явцын урт хугацааны болон орон нутгийн зан үйлийг бүрэн дүрслэх зорилготой юм. Үүнтэй холбогдуулан хамгийн их судлагдсан зарим асуудлыг энд оруулав.

Брауны хөдөлгөөн ба түүний ерөнхий ойлголтууд - тархалтын процесс ба бие даасан өсөлттэй процессууд . Санамсаргүй үйл явцын онол нь магадлалын онол, операторын онол ба дифференциал тэгшитгэлийн онолын хоорондын уялдаа холбоог гүнзгийрүүлэхэд хувь нэмэр оруулсан бөгөөд энэ нь бусад зүйлсийн дунд физик болон бусад хэрэглээнд чухал ач холбогдолтой байв. Хэрэглээнд актуар (даатгалын) математик, дарааллын онол, генетик, замын хөдөлгөөний хяналт, цахилгаан хэлхээний онол, бараа материалын онол зэрэг сонирхолтой үйл явц багтана.

Мартингалес . Эдгээр процессууд нь Марковын гинжин хэлхээний хангалттай шинж чанарыг хадгалдаг бөгөөд чухал эргодик теоремууд тэдгээрийн хувьд хүчинтэй хэвээр байна. Мартингалес нь Марковын гинжин хэлхээнээс ялгаатай нь одоогийн байдал мэдэгдэж байгаа үед зөвхөн ирээдүйн математикийн хүлээлт, гэхдээ магадлалын тархалт өөрөө өнгөрсөн үеэс хамаарахгүй. Мартингалийн онол нь судалгааны чухал хэрэглүүр болохын зэрэгцээ статистикт үүсэх санамсаргүй үйл явцын онол, цөмийн задралын онол, генетик, мэдээллийн онолыг шинэ хязгаарын теоремоор баяжуулсан.

Хөдөлгөөнгүй үйл явц . Дээр дурдсанчлан хамгийн эртний мэдэгдэж буй эргодик теорем нь хөдөлгөөнгүй санамсаргүй үйл явцын хязгаарлагдмал зан үйлийг дүрсэлсэн үр дүн гэж тайлбарлаж болно. Ийм үйл явц нь түүний хангасан бүх магадлалын хуулиуд цаг хугацааны шилжилтийн хувьд өөрчлөгддөггүй шинж чанартай байдаг. Физикчдийн анх таамаглал болгон томъёолсон эргодик теорем нь тодорхой нөхцөлд чуулгын дундаж нь цаг хугацааны дундажтай давхцдаг гэсэн үгээр илэрхийлж болно. Энэ нь системийн урт хугацааны ажиглалт болон нэг системийн бие даасан олон хуулбарыг нэгэн зэрэг (мөн агшин зуур) ажигласнаар ижил мэдээллийг авч болно гэсэн үг юм. Их тооны хууль бол Бирхоффын эргодик теоремын онцгой тохиолдолоос өөр зүйл биш юм. Өргөн утгаар нь ойлгодог суурин Гауссын үйл явцын үйлдлийг интерполяци хийх, урьдчилан таамаглах нь сонгодог хамгийн бага квадратын онолын чухал ерөнхий ойлголт болж өгдөг. Хөдөлгөөнгүй үйл явцын онол нь шуугиан эсвэл санамсаргүй хөндлөнгийн оролцоотойгоор мессеж дамжуулах системийг судлах, бүтээхтэй холбоотой харилцаа холбооны онол гэх мэт олон салбарт зайлшгүй шаардлагатай судалгааны хэрэгсэл юм.

Марковын үйл явц (дараа үр дагаваргүй үйл явц) нь дарааллын системийг (QS) загварчлах, нийгэмд болж буй нийгэм, эдийн засгийн үйл явцыг удирдах стратегийг загварчлах, сонгоход асар их үүрэг гүйцэтгэдэг.

Марковын хэлхээг мөн текст үүсгэхэд ашиглаж болно. Хэд хэдэн текстийг оролт болгон нийлүүлж, дараа нь нэг үгийн дараа дараагийн үг гарах магадлал бүхий Марковын гинжийг байгуулж, энэ хэлхээнд үндэслэн үүссэн текстийг үүсгэнэ. Тоглоом нь маш хөгжилтэй болж хувирав!

Дүгнэлт

Тиймээс бид курсын ажилдаа Марковын гинжин хэлхээний тухай ярьж байсан. Бид үүнийг ямар чиглэлээр, хэрхэн ашигладаг талаар олж мэдсэн, бие даасан туршилтууд нь Марковын гинжин хэлхээнд магадлалыг хязгаарлах теоремыг баталж, Марковын ердийн ба нэгэн төрлийн гинжин хэлхээний жишээг өгч, шилжилтийн матрицыг олох боломжийг олгодог.

Марковын гинжин хэлхээний загвар нь бие даасан туршилтын дизайны шууд ерөнхий ойлголт гэдгийг бид харсан.

Ашигласан уран зохиолын жагсаалт

1. Чистяков В.П. Магадлалын онолын хичээл. 6-р хэвлэл, Илч. − Санкт-Петербург: Лан хэвлэлийн газар, 2003. − 272 х. − (Их дээд сургуулийн сурах бичиг. Тусгай зохиол).

2. Гнеденко Б.В. Магадлалын онолын хичээл.

3. Гмурман В.Э. Магадлалын онол, математик статистик.

4. Ventzel E.S. Магадлалын онол ба түүний инженерчлэлийн хэрэглээ.

5. Колмогоров А.Н., Журбенко И.Г., Прохоров А.В. Магадлалын онолын танилцуулга. − Москва-Ижевск: Компьютерийн судалгааны хүрээлэн, 2003, 188 х.

6. Katz M. Физикийн магадлал ба холбогдох асуудлууд.

Дискрет төлөв (DS) бүхий систем дэх Марковын санамсаргүй үйл явцыг математикийн тайлбарлах аргууд нь системийн төлөвөөс төлөв рүү шилжих шилжилтийн аль үе шатанд (өмнө нь мэдэгдэж байсан эсвэл санамсаргүй) тохиолдож болохоос хамаарна.
Хэрэв системийг төлөвөөс төлөвт шилжүүлэх нь урьдчилан тодорхойлсон цаг мөчид боломжтой бол бид үүнийг шийдэж байна Дискрет хугацаатай санамсаргүй Марковын процесс.Хэрэв ямар ч санамсаргүй мөчид шилжилт хийх боломжтой бол бид үүнийг шийдэж байна тасралтгүй хугацаатай санамсаргүй Марков процесс.
Физик систем байгаасай Сдотор байж болох nмужууд С 1 , С 2 , …, S n. Мужаас муж руу шилжих нь зөвхөн цаг мөчид л боломжтой байдаг т 1 , т 2 , …, tk, эдгээр мөчүүдийг цаг хугацааны алхам гэж нэрлэе. Бид систем дэх хамтарсан үйлдвэрийг авч үзэх болно Сбүхэл аргумент 1, 2, ..., функцын хувьд к, энд аргумент нь алхамын дугаар юм.
Жишээ: С 1 → С 2 → С 3 → С 2 .
Тодорхойлохыг зөвшөөрье С и (к) – дараа нь гэсэн баримтаас бүрдэх үйл явдал ксистем S төлөвт байгаа алхамууд би.
Дурын хувьд күйл явдал S 1 ( к), S 2 ( к),…, С n (к) хэлбэр үйл явдлын бүрэн бүлэгмөн байна нийцэхгүй.

Систем дэх үйл явцыг үйл явдлын гинжин хэлхээ хэлбэрээр төлөөлж болно.
Жишээ: С 1 (0) , С 2 (1) , S 3 (2) , S 5 (3) ,….
Энэ дарааллыг гэж нэрлэдэг Марковын гинж , хэрэв алхам бүрийн хувьд аль нэг төлөвөөс шилжих магадлал С иямар ч нөхцөлд Сжсистем хэзээ, хэрхэн төлөвт хүрсэнээс хамаарахгүй С и.
Ямар ч үед ямар ч үед зөвшөөрнө үү к-р шатлалын систем Саль нэг мужид байж болно С 1 , С 2 , …, S n, өөрөөр хэлбэл үйл явдлын бүрэн бүлгээс нэг үйл явдал тохиолдож болно: С 1 (к), S 2 ( к) , …, S n (к) . Эдгээр үйл явдлын магадлалыг тэмдэглэе.
П 1 (1) = П(С 1 (1)); П 2 (1) = П(С 2 (1)); …; Pn(1) = П(S n (к));
П 1 (2) = П(С 1 (2)); П 2 (2) = П(S 2 (2)); ...; Pn(2) = П(S n (2));
П 1 (к) = П(С 1 (к)); П 2 (к) = П(С 2 (к)); …; Pn(к) = П(S n (к)).
Алхам дугаар бүрийн хувьд нөхцөл хангагдсаныг харахад хялбар байдаг
П 1 (к) + П 2 (к) +…+ Pn(к) = 1.
Эдгээр магадлалыг нэрлэе төрийн магадлалТиймээс даалгавар нь иймэрхүү сонсогдох болно: системийн төлөвийн магадлалыг аль ч тохиолдолд олох к.
Жишээ.Зургаан муж улсын аль нэгэнд байж болох ямар нэгэн төрлийн тогтолцоо байг. Дараа нь түүнд тохиолдож буй үйл явцыг системийн төлөв байдлын өөрчлөлтийн график хэлбэрээр дүрсэлж болно (Зураг 7.9, А), эсвэл системийн төлөвийн график хэлбэрээр (Зураг 7.9, б).

A)

Цагаан будаа. 7.9
Мөн систем дэх үйл явцыг дараах төлөв байдлын дараалал болгон дүрсэлж болно. С 1 , С 3 , С 2 , С 2 , С 3 , С 5 , С 6 , С 2 .
төлөвийн магадлал ( к+ 1)-р алхам нь зөвхөн төлөвөөс хамаарна к-м алхам.
Аливаа алхамын хувьд кСистем аль ч төлөвөөс өөр төлөвт шилжих зарим магадлал байдаг тул эдгээр магадлалыг нэрлэе. Марковын гинжин хэлхээний шилжилтийн магадлал.
Нэг үе шаттайгаар нэг төлөвөөс нөгөөд шилжих боломжгүй бол эдгээр магадлалын зарим нь 0 байх болно.
Марковын гинжийг нэрлэдэг нэгэн төрлийн, хэрэв шилжилтийн төлөвүүд нь алхамын тооноос хамаарахгүй бол түүнийг дуудна нэг төрлийн бус.
Нэг төрлийн Марковын гинж байх ба системийг зөвшөөрөх Сбайна nболомжит мужууд: С 1 , …, S n. Нэг алхамаар өөр төлөвт шилжих магадлалыг муж бүрт мэдэгдээрэй, өөрөөр хэлбэл. П ij(аас С иВ Сжнэг алхамаар), дараа нь бид шилжилтийн магадлалыг матриц хэлбэрээр бичиж болно.

. (7.1)
Энэ матрицын диагональ дагуу систем төлөв байдлаас шилжих магадлалууд байдаг С иижил төлөвт С и.
Өмнө нь оруулсан үйл явдлуудыг ашиглах , бид шилжилтийн магадлалыг нөхцөлт магадлал гэж бичиж болно:
.
Мэдээжийн хэрэг, нэр томъёоны нийлбэр үйл явдлуудаас хойш матрицын мөр бүрт (1) нэгтэй тэнцүү байна үл нийцэх үйл явдлын бүрэн бүлгийг бүрдүүлнэ.

Марковын гинжийг авч үзэх, түүнчлэн Марковын санамсаргүй үйл явцыг шинжлэхдээ янз бүрийн төлөвийн графикуудыг ашигладаг (Зураг 7.10).

Цагаан будаа. 7.10

Энэ систем нь зургаан муж улсын аль нэгэнд байж болно П ijтөлөвөөс системийн шилжилтийн магадлал юм С имужид Сж. Энэ системийн хувьд тухайн үед систем ямар нэгэн төлөвт байсан ба түүнээс гарсан тэгшитгэлүүдийг бичнэ тгарч ирээгүй:

Ерөнхий тохиолдолд Марковын гинж нь нэг төрлийн бус, өөрөөр хэлбэл магадлал юм П ijалхам тутамд өөрчлөгддөг. Алхам бүрт шилжилтийн магадлалын матриц өгөгдсөн гэж бодъё, дараа нь системийн магадлалыг Сдээр к-дахь шат нь мужид байх болно С и, томъёог ашиглан олж болно

Шилжилтийн магадлалын матриц ба системийн анхны төлөвийг мэдсэнээр мужуудын магадлалыг олох боломжтой. ямар ч дараа к--р алхам. Цагийн эхний мөчид системийг төлөвт байлга С м. Дараа нь t = 0 байна
.
Эхний алхамын дараа магадлалыг олъё. Төрөөс С мсистем муж руу шилжих болно С 1 , С 2 гэх мэт магадлал бүхий Pm 1 , Pm 2 , …, Pmm, …, P mn. Дараа нь эхний алхамын дараа магадлал тэнцүү болно

. (7.2)
Хоёр дахь алхамын дараах төлөвийн магадлалыг олъё: . Бид таамаглал бүхий нийт магадлалын томъёог ашиглан эдгээр магадлалыг тооцоолох болно.
.
Таамаглал нь дараахь мэдэгдлүүд байх болно.

• эхний алхамын дараа систем S 1 -H 1 төлөвт байсан;
• хоёр дахь алхамын дараа систем S 2 -H 2 төлөвт байсан;
• дараа n 3-р алхамд систем S n -H n төлөвт байсан.

Хоёр дахь алхамын дараа ямар нэгэн төлөвийн магадлал:

(7.3)
Формула (7.3) нь шилжилтийн бүх магадлалыг нэгтгэдэг П ij, гэхдээ зөвхөн 0-ээс бусад зүйлийг харгалзан үзнэ. Дараа нь ямар нэгэн нөхцөл байдал үүсэх магадлал к-р алхам:

(7.4)
Тиймээс, дараа нь улсын магадлал кдах шатыг магадлалаар (7.4) давтагдах томьёогоор тодорхойлно. к - 1)-р алхам.

Даалгавар 6.Марковын гинжин хэлхээний шилжилтийн магадлалын матрицыг нэг алхамаар өгөв. Өгөгдсөн хэлхээний шилжилтийн матрицыг гурван үе шаттайгаар ол .
Шийдэл.Системийн шилжилтийн матриц нь энэ системийн шилжилтийн бүх магадлалыг агуулсан матриц юм.

Матрицын мөр бүр үйл явдлын магадлалыг (төлөвөөс шилжих) агуулна бимужид j), бүрэн бүлгийг бүрдүүлдэг тул эдгээр үйл явдлын магадлалын нийлбэр нэгтэй тэнцүү байна.

n алхмын (туршилтын) үр дүнд систем i төлөвөөс j төлөв рүү шилжих магадлалыг p ij (n) гэж тэмдэглэе. Жишээлбэл, p 25 (10) нь арван алхамаар хоёр дахь төлөвөөс тав дахь төлөвт шилжих магадлал юм. n=1-ийн хувьд бид p ij (1)=p ij шилжилтийн магадлалыг олж авна гэдгийг анхаарна уу.
Бидэнд даалгавар өгсөн: p ij шилжилтийн магадлалыг мэдэж, төлөвөөс системийн шилжилтийн p ij (n) магадлалыг ол. бимужид jтөлөө nалхам. Үүнийг хийхийн тулд бид завсрын (хооронд биТэгээд j) төлөв r. Өөрөөр хэлбэл, бид үүнийг анхны төлөвөөс авах болно битөлөө мсистем завсрын төлөвт шилжих алхамууд r p ij (n-m) магадлалтай, үүний дараа үлдсэн n-m алхамуудад r завсрын төлөвөөс p ij (n-m) магадлалтай эцсийн j төлөвт шилжинэ. Нийт магадлалын томъёог ашиглан бид дараахь зүйлийг авна.
.
Энэ томъёог Марковын тэгш байдал гэж нэрлэдэг. Энэ томьёог ашиглан та бүх магадлалыг p ij (n), улмаар P n матрицыг өөрөө олж болно. Матрицын тооцоолол нь зорилгодоо илүү хурдан хөтөлдөг тул бид үүссэн томъёоноос үүссэн матрицын хамаарлыг ерөнхий хэлбэрээр бичнэ.
Үүссэн томъёог ашиглан Марковын гинжин шилжилтийн матрицыг гурван үе шаттайгаар тооцоолъё.

Хариулт:.

Даалгавар №1. Марковын гинжин шилжилтийн магадлалын матриц нь дараах хэлбэртэй байна.
.
t=0 үеийн төлөвүүдийн тархалтыг вектороор тодорхойлно.
π 0 =(0.5; 0.2; 0.3)
Олно: a) t=1,2,3,4 момент дахь төлөвийн хуваарилалт.
в) суурин хуваарилалт.

Тодорхойлолт.Хэрэв нөхцөлт магадлал (төрөөс муж руу шилжих) туршилтын тооноос хамаарахгүй бол Марковын гинжийг нэгэн төрлийн гэж нэрлэдэг. Тийм ч учраас тэд зүгээр л оронд нь бичдэг.

Жишээ 1.Санамсаргүй алхах. Бүхэл тооны координаттай цэг дээр шулуун шугам дээр материаллаг бөөм байг. Тодорхой цаг мөчид бөөмс нь цочролыг мэдэрдэг. Түлхэлтийн нөлөөн дор бөөмс нь нэг нэгжийн магадлалтайгаар баруун тийш, магадгүй нэг нэгж зүүн тийш хөдөлдөг. Цочролын дараах бөөмсийн байрлал (координат) нь шууд өмнөх цочролын дараа тухайн бөөмс хаана байснаас хамаарах бөгөөд өмнөх бусад цочролын нөлөөн дор хэрхэн хөдөлж байгаагаас хамаарахгүй нь ойлгомжтой.

Тэгэхээр санамсаргүй алхах уу? нэгэн төрлийн салангид хугацааны Марковын гинжин хэлхээний жишээ.

Шилжилтийн магадлал гэдэг нь тухайн төлөвөөс (ямар нэгэн туршилтын үр дүнд систем өөрийгөө олсон, ямар ч тооноос үл хамааран) дараагийн туршилтын үр дүнд систем төлөвт шилжих нөхцөлт магадлал юм.

Тиймээс тэмдэглэгээнд эхний индекс нь өмнөх индексийн тоог, хоёр дахь нь? дараагийн улсын дугаар. Жишээлбэл, - хоёр дахь төлөвөөс гурав дахь төлөв рүү шилжих магадлал.

Төлөвийн тоо хязгаартай, тэнцүү байг.

Системийн шилжилтийн матриц нь энэ системийн шилжилтийн бүх магадлалыг агуулсан матриц юм.

Матрицын мөр бүр нь бүрэн бүлгийг бүрдүүлдэг үйл явдлын магадлалыг (ижил төлөвөөс аливаа боломжит төлөвт шилжих) агуулж байгаа тул эдгээр үйл явдлын магадлалын нийлбэр нэгтэй тэнцүү байна. Өөрөөр хэлбэл, шилжилтийн матрицын мөр бүрийн шилжилтийн магадлалын нийлбэр нь нэгтэй тэнцүү байна.

Гурван төлөвт байж болох системийн шилжилтийн матрицын жишээг өгье; төлөв байдлаас төлөв рүү шилжих нь нэгэн төрлийн Марковын гинжин хэлхээний схемийн дагуу явагддаг; Шилжилтийн магадлалыг матрицаар өгөв.

Хэрэв систем төлөв байдалд байсан бол нэг алхамаар төлөвийг өөрчилсний дараа 0.5 магадлалтай ижил төлөвт үлдэж, 0.5 магадлалтай ижил төлөвт үлдэж, төлөвт шилжинэ гэдгийг бид эндээс харж байна. магадлал нь 0.2, дараа нь шилжилтийн дараа тэр мужид өөрийгөө олж болно; энэ нь мужаас шилжих боломжгүй. Матрицын сүүлчийн эгнээ нь 0.1-ийн ижил магадлалтай мужаас аль нэг төлөв рүү шилжихийг харуулж байна.

Системийн шилжилтийн матриц дээр үндэслэн системийн төлөвийн график гэж нэрлэгдэх боломжтой. Энэ нь хэлхээг дүрслэн харуулахад тохиромжтой. График байгуулах дарааллыг жишээн дээр авч үзье.

Жишээ 2.Өгөгдсөн шилжилтийн матрицыг ашиглан төлөвийн график байгуул.

Учир нь Дөрөв дэх дарааллын матриц, дараа нь систем нь 4 боломжит төлөвтэй байна.

График нь системийн нэг төлөвөөс ижил төлөв рүү шилжих магадлалыг заагаагүй болно. Тодорхой системийг авч үзэхдээ эхлээд төлөвийн графикийг барьж, дараа нь системийн нэг төлөвөөс ижил төлөв рүү шилжих магадлалыг тодорхойлох нь тохиромжтой (матрицын эгнээний элементүүдийн нийлбэр нэгтэй тэнцүү байх шаардлагад үндэслэн). ), дараа нь системийн шилжилтийн матрицыг байгуулна.

Өнөөдөр би Марковын гинжтэй ажиллахад хялбар болгохын тулд хичээл бичих талаар хэлэхийг хүсч байна.

Муурны доор өгөөч.

Үндсэн мэдлэг:

Графикуудыг зэргэлдээ матриц хэлбэрээр дүрслэх, графикийн талаархи үндсэн ойлголтуудын мэдлэг. Практик хэсэгт зориулсан C++ хэлний мэдлэг.

Онол

Марковын гинжин хэлхээ гэдэг нь эцсийн буюу тоолж болох тооны үр дүн бүхий санамсаргүй үйл явдлын дараалал бөгөөд тодорхой хэлбэл, ирээдүй нь өнгөрсөн үеэс үл хамаарах шинж чанараараа тодорхойлогддог. A. A. Марковын нэрэмжит (ахлах).

Марковын гинжийг ашиглах талаар маш олон нийтлэл бичсэн боловч бид ангийг үргэлжлүүлэн хөгжүүлэх болно.

Марковын гинжин хэлхээний жишээг танд хэлье.

Ирээдүйд бид энэ схемийг жишээ болгон авч үзэх болно.

Мэдээжийн хэрэг, хэрэв А оройноос зөвхөн нэг гарч байгаа ирмэг байвал түүний жин 1-тэй тэнцүү байх болно.

Тэмдэглэлүүд

Матриц гэдэг нь Марковын гинжийг төлөөлөхөд ашигладаг чиг баримжаатай жигнэсэн графикийн зэргэлдээх матриц юм. (энэ талаар дараа нь). Энэ тохиолдолд энэ матрицыг шилжилтийн магадлалын матриц эсвэл зүгээр л шилжилтийн матриц гэж нэрлэдэг.

Марковын гинжин хэлхээний матриц дүрслэл

Би танд сануулъя:

Хязгаарлагдмал тооны оройтой n (1-ээс n хүртэл дугаарлагдсан) G графикийн зэргэлдээх матриц нь n хэмжээтэй дөрвөлжин А матриц бөгөөд aij элементийн утга нь i-р оройноос ирэх ирмэгүүдийн тоотой тэнцүү байна. графикийн j-р орой хүртэл.

Манай тохиолдолд матриц нь 10х10 хэмжээтэй байх болно, үүнийг бичье.

0 50 0 0 0 0 50 0 0 0
0 0 80 20 0 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 0 100 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 70 30 0
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 100 0 0 0 0

Санаа

Ийнхүү тоотой тэнцүү тоотой үйл явдал тохиолдох магадлал бидэнд байна багана-тэй тэнцүү тоотой үйл явдлын дараа шугамууд.

Магадлалын онолыг мэддэг хүмүүс мөр бүр нь магадлалын тархалтын функц гэдгийг тааж чадна.

Марковын гинжин хэлхээний алгоритм

Тайлбар: магадлалын тархалт тэг байвал орой нь төгсгөлтэй байна (матрицын 6-р мөрийг үзнэ үү).

Маш гоёмсог алгоритм, тийм ээ?

Хэрэгжилт

Дамжуулах алгоритмын хэрэгжилт

загвар Элемент * Марков ::Дараах(int StartElement = -1) (хэрэв (Марков ::Эхэлсэн) // хэрвээ зэргэлдээх матриц үүссэн бол ( хэрэв (StartElement == -1) // хэрэв анхдагч эхлэл элемент нь StartElement = Марков бол :: Одоогийн; // дараа нь бид үргэлжлүүлнэ (Бүтээн байгуулагч Current = 0) std::random_device rd;<>std::mt19937 gen(rd()); ::AdjacencyMatrix.at(Current).begin(), Марков ::AdjacencyMatrix.at(Current).end()); // магадлалын тархалтад тулгуурлан тоо үүсгэхийн тулд савыг эхлүүлэх int next = dicr_distr(gen); // дараагийн оройг үүсгэнэ үү (дараагийн == Марков ::size()) // генераторын нарийн шинж чанарууд, хэрэв магадлалын тархалт тэг байвал энэ нь NULL-ийн элементийн тоог буцаана; Марков ::Одоогийн = дараагийн; // одоогийн оройн өгөөжийг өөрчлөх &(Марков

::elems.at(дараагийн)); // орой дээрх утгыг буцаана ) буцаана NULL; ) Энэ алгоритм нь савны онцлогоос шалтгаалан маш энгийн харагддагсалангид_тараалт

0 50 0 0 0 0 50 0 0 0

. Энэ сав хэрхэн ажилладагийг үгээр илэрхийлэхэд маш хэцүү тул матрицынхаа 0-р эгнээг жишээ болгон авч үзье.

Генераторын үйл ажиллагааны үр дүнд тус бүрдээ 0.5 магадлал бүхий 1 эсвэл 6-г буцаана. Энэ нь хөдөлгөөн үргэлжлэх ёстой баганын дугаарыг (гинжин хэлхээний оройн тоотой тэнцүү) буцаана.

Анги ашигладаг жишээ програм:

Жишээнээс Марковын гинжин хэлхээг хийдэг программын хэрэгжилт #оруулна #include "Markov.h" #include #оруулна namespace std ашиглах; int main() (Марков< num; i++) { getline(ins, str); chain.AddElement(str); // добавляем вершину } if (chain.InitAdjacency()) // инициализируем матрицу нулями { for (int i = 0; i < chain.size(); i++) { for (int j = 0; j < chain.size(); j++) { (ins >гинж;<< "Adjacency matrix write error" << endl; } } } outs << chain.At(0) << " "; // выводим 0-ю вершину for (int i = 0; i < 20 * chain.size() - 1; i++) // генерируем 20 цепочек { string *str = chain.Next(); if (str != NULL) // если предыдущая не конечная outs << (*str).c_str() << " "; // выводим значение вершины else { outs << std::endl; // если конечная, то начинаем с начала chain.Current = 0; outs << chain.At(0) << " "; } } chain.UninitAdjacency(); // понятно } else cerr << "Can not initialize Adjacency matrix" << endl;; ins.close(); outs.close(); cin.get(); return 0; }

outs.open("out.txt"); ifstream ins;

ins.open("matrix.txt"); int тоо;

давхар Проб = 0;

(ins >> num).get(); // оройнуудын тоо string str;

хувьд (int i = 0; i

> Prob).get();

хэрэв (!chain.PushAdjacency(i, j, Prob)) // матрицыг оруулна уу ( cerr Програмын үүсгэсэн гаралтын жишээ:

Нэг төрлийн Марковын гинжин хэлхээнд байгаа системийн бүх боломжит төлөвүүд нь шилжилтийн магадлалаас бүрдэх энэхүү гинжийг тодорхойлдог стохастик матриц юм.

Хэрэв матриц нь нэгээс өөр, модуль нь нэгтэй тэнцүү шинж чанарын тоогүй бол стохастик матриц ба түүнд харгалзах нэгэн төрлийн Марковын гинжин хэлхээг регуляр гэж нэрлэнэ, хэрэв матрицын шинж чанарын тэгшитгэлийн энгийн үндэс нь нэгдмэл байвал тогтмол гэж нэрлэнэ.

Ердийн матриц нь ердийн хэлбэрээр (69) (х. 373) матрицууд нь анхдагч байдаг гэдгээрээ онцлог юм. Ердийн матрицын хувьд нэмэлт .

Нэмж дурдахад, Марковын нэгэн төрлийн гинжийг задрах, задрах, ациклик, цикл гэж нэрлэдэг бөгөөд хэрэв энэ гинжин хэлхээний хувьд стохастик матриц нь тус тус нь задрах, задрах, анхдагч, импримитив байвал.

Анхдагч стохастик матриц нь ердийн матрицын тусгай төрөл тул ациклик Марковын гинж нь ердийн гинжин хэлхээний тусгай төрөл юм.

Шилжилтийн хязгаарлах магадлал нь зөвхөн нэгэн төрлийн Марковын гинжин хэлхээнд л байдгийг бид харуулах болно.

Үнэн хэрэгтээ ердийн матрицын хамгийн бага олон гишүүнт байг. Дараа нь

Теорем 10-ын дагуу бид үүнийг таамаглаж болно

Томъёо (24) дээр үндэслэн Ч. V (хуудас 113)

(96)

Хаана нь багасгасан нэмэлт матриц ба

Хэрэв ердийн матриц бол

тиймээс (96) томъёоны баруун талд эхнийхээс бусад бүх нэр томъёо тэг рүү чиглэдэг. Иймд ердийн матрицын хувьд шилжилтийн хязгаарлах магадлалаас тогтсон матриц байдаг ба

Эсрэг нөхцөл байдал илт харагдаж байна. Хэрэв асуудал гарвал

тэгвэл матриц нь , a гэсэн шинж чанартай дугаартай байж болохгүй, учир нь хязгаар байхгүй болно [Хязгаарлалт (97") байгаа тул ижил хязгаар байх ёстой.]

Тогтмол (зөвхөн тогтмол) Марковын гинжин хэлхээнд матриц байдаг гэдгийг бид нотолсон. Энэ матрицыг (97) томъёогоор тодорхойлно.

Матрицыг шинж чанарын олон гишүүнтээр хэрхэн илэрхийлж болохыг харуулъя

болон хавсарсан матриц .

Баримтлалаас

(95), (95") ба (98)-ын дагуу дараах байдалтай байна.

Тиймээс (97) томъёог томьёогоор сольж болно

(97)

Энгийн Марковын гинжин хэлхээний хувьд энэ нь ердийн гинжин хэлхээний тодорхой төрөл учраас матриц нь байдаг бөгөөд (97), (97") аль нэг томъёогоор тодорхойлогддог. Энэ тохиолдолд томъёо (97") мөн хэлбэртэй байна.

2. Ерөнхий төрлийн ердийн гинжийг (тогтмол бус) авч үзье. Бид харгалзах матрицыг хэвийн хэлбэрээр бичнэ

(100)

Энд анхдагч стохастик матрицууд байдаг ба задрах боломжгүй матрицууд нь хамгийн их шинж чанарын тоотой байдаг. Итгэж байна

,

хэлбэрээр бичье

(101)

Гэхдээ , учир нь матрицын бүх шинж чанарын тоо нь үнэмлэхүй утгаараа нэгээс бага байна. Тийм ч учраас

(102)

Анхдагч стохастик матрицууд тул (99) ба (35) (х. 362) томъёоны дагуу матрицууд эерэг байна.

ба эдгээр матрицын аль нэг багана бүрт бүх элементүүд хоорондоо тэнцүү байна:

.

Стохастик матрицын хэвийн хэлбэр (100) нь системийн төлөвүүдийг бүлэгт хуваахтай тохирч байгааг анхаарна уу.

(104) дэх бүлэг бүр (101) дэх цувралын өөрийн бүлэгтэй тохирч байна. Л.Н.Колмогоровын нэр томъёоны дагуу системийн төлөвүүдийг чухал гэж нэрлэдэг бөгөөд үлдсэн бүлгүүдэд багтсан мужуудыг чухал бус гэж нэрлэдэг.

Матрицын (101) хэлбэрээс үзэхэд аливаа хязгаарлагдмал тооны алхмын хувьд (мөчнөөс мөч хүртэл) системийн цорын ганц боломжтой шилжилт нь a) чухал төлөвөөс нэг бүлгийн чухал төлөв рүү, б) чухал бус төлөвөөс чухал төлөв рүү, в) чухал биш төлөвөөс ижил буюу өмнөх бүлгийн чухал биш төлөв рүү.

Матрицын (102) хэлбэрээс харахад зөвхөн ямар ч төлөвөөс чухал төлөв рүү шилжих боломжтой, өөрөөр хэлбэл ямар ч чухал бус төлөвт шилжих магадлал нь алхамуудын тоогоор тэг болох хандлагатай байдаг. Тиймээс зайлшгүй төлөвүүдийг заримдаа хязгаарын төлөв гэж нэрлэдэг.

3. Томъёо (97)-аас дараах байдалтай байна.

.

Энэ нь матрицын багана бүр нь шинж чанарын дугаарын стохастик матрицын хувийн вектор болохыг харуулж байна.

Ердийн матрицын хувьд 1-ийн тоо нь шинж чанарын тэгшитгэлийн энгийн үндэс бөгөөд энэ тоо нь матрицын зөвхөн нэг (скаляр хүчин зүйл хүртэл) хувийн вектортой тохирч байна. Тиймээс матрицын аль ч баганад бүх элементүүд ижил сөрөг бус тоотой тэнцүү байна.

Тиймээс ердийн гинжин хэлхээнд шилжилтийн хязгаарлах магадлал нь анхны төлөвөөс хамаардаггүй.

Эсрэгээр, хэрэв зарим ердийн нэгэн төрлийн Марковын гинжин хэлхээнд проделийн шилжилтийн магадлал нь анхны төлөвөөс хамаардаггүй, өөрөөр хэлбэл томъёо (104) нь биелдэг бол схемд (102) матрицад шаардлагатай байдаг. Гэхдээ дараа нь гинж нь тогтмол байдаг.

Ердийн гинжин хэлхээний онцгой тохиолдол болох ациклик гинжин хэлхээний хувьд энэ нь анхдагч матриц юм. Тиймээс зарим хүмүүсийн хувьд (377-р хуудасны 8-р теоремыг үзнэ үү). Харин дараа нь .

Үүний эсрэгээр, зарим хүмүүсийн хувьд 8-р теоремын дагуу матриц нь анхдагч, тиймээс өгөгдсөн нэгэн төрлийн Марковын гинж нь цикл бус гэсэн үг юм.

Бид олж авсан үр дүнг дараах теорем хэлбэрээр томъёолно.

Теорем 11. 1. Нэг төрлийн Марковын гинжин хэлхээнд бүх хязгаарлагдмал шилжилтийн магадлалууд оршин тогтнохын тулд гинж тогтмол байх шаардлагатай бөгөөд хангалттай. Энэ тохиолдолд хязгаарлах шилжилтийн магадлалаас бүрдэх матрицыг (95) эсвэл (98) томъёогоор тодорхойлно.

2. Тогтмол нэгэн төрлийн Марковын гинжин хэлхээний хязгаарлагдмал шилжилтийн магадлал нь анхны төлөвөөс хамааралгүй байхын тулд гинж тогтмол байх шаардлагатай бөгөөд хангалттай. Энэ тохиолдолд матрицыг (99) томъёогоор тодорхойлно.

3. Тогтмол нэгэн төрлийн Марковын гинжин хэлхээний бүх хязгаарлах шилжилтийн магадлалууд тэгээс ялгаатай байхын тулд гинж нь циклик байх нь зайлшгүй бөгөөд хангалттай юм.

4. Үнэмлэхүй магадлалын багануудыг танилцуулъя

(105)

Тухайн үед систем (,) төлөвт байх магадлал хаана байна. Магадлалыг нэмэх ба үржүүлэх теоремуудыг ашиглан бид дараахь зүйлийг олно.

(,),

давхар Проб = 0;

матрицын шилжүүлсэн матриц хаана байна.

Шилжилтийн магадлалын эхний магадлал болон матриц нь мэдэгдэж байгаа бол бүх үнэмлэхүй магадлалыг (105) (106) томъёогоор тодорхойлно.

Хязгаарлах үнэмлэхүй магадлалыг танилцуулъя

Тэгш байдлын хоёр талыг (106) -ийн хязгаарт шилжүүлснээр бид дараахь зүйлийг олж авна.

Шилжилтийн хязгаарлагдмал магадлалын матриц байгаа нь хязгаарлах үнэмлэхүй магадлал байгаа гэсэн үг гэдгийг анхаарна уу. аливаа анхны магадлалын хувьд мөн эсрэгээр.

Томъёо (107) ба матрицын (102) хэлбэрээс харахад чухал биш төлөвт харгалзах хязгаарлах үнэмлэхүй магадлал нь тэгтэй тэнцүү байна.

Матрицын тэгш байдлын хоёр талыг үржүүлэх

баруун талд, бид (107)-ын тусламжтайгаар дараахийг олж авна:

өөрөөр хэлбэл ахиу үнэмлэхүй магадлалын багана нь шинж чанарын тооны матрицын хувийн вектор юм.

Хэрэв энэ Марковын гинж тогтмол бол матрицын шинж чанарын тэгшитгэлийн энгийн үндэс болно. Энэ тохиолдолд хязгаарлах үнэмлэхүй магадлалын баганыг (108)-аас онцгойлон тодорхойлно (ба -аас хойш).

Марковын ердийн хэлхээг өгье. Дараа нь (104) ба (107) -аас дараах байдалтай байна.

(109)

Энэ тохиолдолд хязгаарлах үнэмлэхүй магадлал нь анхны магадлалаас хамаарахгүй.

Үүний эсрэгээр, матрицын бүх мөрүүд ижил байх тохиолдолд (107) томьёо байгаа тохиолдолд хамаарахгүй байж болно, өөрөөр хэлбэл.

,

тиймээс (Теорем 11-ийн дагуу) энэ нь ердийн матриц юм.

Хэрэв анхдагч матриц бол , улмаар (109) -ийн хүчинд

Эсрэгээр, хэрэв бүх зүйл анхны магадлалаас хамаардаггүй бол матрицын багана бүрт бүх элементүүд ижил бөгөөд (109) дагуу байдаг бөгөөд энэ нь теорем 11-ийн дагуу энэ нь анхдагч матриц, өөрөөр хэлбэл энэ гинж гэсэн үг юм. ациклик юм.

Дээрхээс үзэхэд теорем 11-ийг дараах байдлаар томъёолж болно.

Теорем 11". 1. Аливаа анхны магадлалын хувьд нэгэн төрлийн Марковын гинжин хэлхээнд бүх хязгаарлах үнэмлэхүй магадлалууд оршин тогтнохын тулд гинж тогтмол байх шаардлагатай бөгөөд хангалттай.

2. Аливаа анхны магадлалын хувьд нэгэн төрлийн Марковын гинжин хэлхээнд байх үнэмлэхүй магадлалыг хязгаарлахын тулд эдгээр анхны магадлалаас хамаарахгүй байхын тулд хэлхээ тогтмол байх нь зайлшгүй бөгөөд хангалттай юм.

3. Нэг төрлийн Марковын гинжин хэлхээ нь аливаа анхны магадлалын эерэг хязгаарлах үнэмлэхүй магадлалтай байх ба эдгээр хязгаарлах магадлал нь анхны магадлалаас хамааралгүй байхын тулд гинж нь циклик байх нь зайлшгүй бөгөөд хангалттай юм.

5. Одоо шилжилтийн магадлалын матрицтай ерөнхий төрлийн нэгэн төрлийн Марковын гинжийг авч үзье.

Матрицын хэвийн хэлбэрийг (69) авч, (69) дахь матрицуудын үл хамаарах байдлын индексүүдээр тэмдэглэе. Бүхэл тооны хамгийн бага нийтлэг үржвэр байг. Дараа нь матриц нь модулийн хувьд нэгтэй тэнцүү шинж чанарын тоотой байдаггүй, гэхдээ нэгээс ялгаатай, өөрөөр хэлбэл энэ нь ердийн матриц юм; энэ тохиолдолд - хамгийн бага үзүүлэлт нь - зөв матриц. Бид тоог өгөгдсөн нэгэн төрлийн Марковын гинжин хэлхээний үе гэж нэрлэдэг ба... Эсрэгээр, хэрэв ба , (110) ба (110") томъёогоор тодорхойлогддог.

Чухал бус төлөвт харгалзах дундаж ахиу үнэмлэхүй магадлал үргэлж тэг байна.

Хэрэв матрицын хэвийн хэлбэр нь тоо юм бол (зөвхөн энэ тохиолдолд) дундаж хязгаарлах үнэмлэхүй магадлал нь анхны магадлалаас хамаарахгүй бөгөөд тэгшитгэлээс (111) өвөрмөц байдлаар тодорхойлогддог.