Markov zincirinin geçiş durumlarının matrisi. Markov zincirleri

1. matris P2 devrenin durumdan geçişi Ben bir durumda J ikide
adım;

2. Şu andaki durumlara göre olasılık dağılımı T=2;

3. şu anda olma olasılığı T=1 devrenin durumu olacaktır A2;

4. sabit dağıtım.

Çözüm. Ayrık bir Markov zinciri için eğer homojen ise aşağıdaki ilişki doğrudur:

burada P1 bir adımdaki geçiş olasılıklarının matrisidir;
Рn - n adım için geçiş olasılıkları matrisi;

1. P2 geçiş matrisini iki adımda bulun

Durumlar üzerindeki olasılık dağılımının açık olmasına izin verin S inci adım vektör tarafından belirlenir
.
Matris bilmek Pn n adımda geçiş, durumlar üzerindeki olasılık dağılımını belirleyebiliriz (S+N)-inci adım . (5)

2. Sistemin o andaki durumları üzerindeki olasılık dağılımını bulalım. T=2. (5)'i koyalım S=0 ve N=2. Daha sonra .

Alacağız.

3. Sistemin o andaki durumları üzerindeki olasılık dağılımını bulalım. T=1.

(5)'i koyalım S=0 ve N=1 ise .
Şu anda bunun olasılığını nasıl görebiliriz? T=1 devrenin durumu olacaktır A2,eşit p2(1)=0,69.
Durumlar üzerindeki olasılık dağılımı, adımdan adıma değişmiyorsa durağan olarak adlandırılır;
Daha sonra (5) numaralı ilişkiden N=1 elde ederiz

4. Durağan dağılımı bulalım. =2 olduğundan =(р1; р2) elde ederiz. Sistemi yazalım doğrusal denklemler(6) içinde koordinat formu

Son koşula normalizasyon denir. Sistem (6)'da bir denklem her zaman diğerlerinin doğrusal birleşimidir. Bu nedenle üzeri çizilebilir. Sistemin ilk denklemini ve normalizasyon denklemini birlikte çözelim. 0.6'mız var p1=0,3p2 yani p2=2p1. Daha sonra p1+2p1=1 veya , yani . Buradan, .
Cevap:
1) belirli bir Markov zinciri için iki adımlı geçiş matrisi şu şekildedir: ;
2) şu andaki durumlara göre olasılık dağılımı T=2 eşittir ;
3) şu anda olma olasılığı T=1 devrenin durumu olacaktır A2, eşittir p2(T)=0,69;
4) sabit dağılım şu şekildedir:

Verilen matris sürekli bir Markov zincirinin geçiş yoğunlukları. Λ matrisine karşılık gelen etiketli bir durum grafiği oluşturun; bir sistem oluştur diferansiyel denklemler Durum olasılıkları için Kolmogorov; Sınırlayıcı olasılık dağılımını bulun. Çözüm. Sonlu sayıda duruma sahip homojen Markov zinciri A1, A2,…A geçiş yoğunlukları matrisi ile karakterize edilir ,

Nerede - Markov zincirinin durumdan geçiş yoğunluğu Аi bir durumda Aj; рij(Δt)-Geçiş olasılığı Ai→Aj zaman aralığı başına Δ T.

Sistemin durumdan duruma geçişleri, üzerinde yoğunluklara karşılık gelen yayların işaretlendiği etiketli bir durum grafiği kullanılarak uygun şekilde belirtilir. λ ben>0. Belirli bir geçiş yoğunluğu matrisi için etiketli bir durum grafiği oluşturalım

Olasılıkların bir vektörü olsun RJ(T),
J=1, 2,…,, sistem şu durumda AJşu anda T.

Açıkçası 0≤ RJ(T)≤1 ve . Daha sonra, skaler bir argümanın vektör fonksiyonunun diferansiyel kuralına göre şunu elde ederiz: . Olasılıklar RJ(T) Kolmogorov diferansiyel denklemleri (SDEK) sistemini karşılar; matris formu benziyor. (7)

İlk anda sistem durumdaysa Aj, o zaman SDUK başlangıç ​​koşulları altında çözülmelidir
RBen(0)=1, рj(0)=0, j≠i,j=1, 2,…,. (8)
SDUK kümesi (7) ve başlangıç ​​koşulları(8) homojen bir Markov zincirini benzersiz bir şekilde tanımlar: sürekli zaman ve sınırlı sayıda durum.
Belirli bir Markov zinciri için bir SDEK oluşturalım. =3 olduğuna göre J=1, 2, 3.

(7) numaralı ilişkiden şunu elde ederiz:

.
Buradan sahip olacağız

Son koşula normalizasyon denir.
Durumlar üzerindeki olasılık dağılımına denir sabit eğer zamanla değişmezse, yani Rj=yapı, J=1,2,…,. Buradan .

Daha sonra SDUK (7)'den durağan dağılımı bulmak için bir sistem elde ederiz.
(9)
Bu sorun için SDUK'tan alacağız

Elde ettiğimiz normalizasyon koşulundan 3р2+р2+р2=1 veya . Bu nedenle limit dağılımı şu şekildedir:
Şu kuralı kullanırsak, bu sonucun doğrudan etiketli durum grafiğinden elde edilebileceğini unutmayın: durağan bir dağılım için, ürünlerin toplamı λ jipi, j≠Ben, gelen oklar için Ben-th durumu çarpımların toplamına eşittir λ jipi, j≠Ben, dahil olan oklar için Ben-th durumu. Gerçekten mi,

Ortaya çıkan sistemin SDUK kullanılarak derlenen sisteme eşdeğer olduğu açıktır. Bu nedenle aynı çözüme sahiptir.
Cevap: Durağan dağılım şu şekildedir:

Tanım. Koşullu olasılık (durumdan duruma geçiş) deneme sayısına bağlı değilse, Markov zincirine homojen denir. Bu yüzden onun yerine sadece yazıyorlar.

Örnek 1. Rastgele yürüyüş. Koordinatı tam sayı olan bir noktada düz bir çizgi üzerinde maddi bir parçacık olsun. Belirli anlarda parçacık şoklara maruz kalır. Bir itmenin etkisi altında parçacık bir birim sağa ve bir birim sola olasılıkla hareket eder. Bir parçacığın bir şoktan sonraki konumunun (koordinatının), parçacığın hemen önceki şoktan sonra nerede olduğuna bağlı olduğu ve önceki diğer şokların etkisi altında nasıl hareket ettiğine bağlı olmadığı açıktır.

Yani rastgele bir yürüyüş mü? Homojen ayrık zamanlı Markov zincirinin bir örneği.

Geçiş olasılığı, sistemin bir sonraki test sonucunda (hangi sayıda olursa olsun bazı testlerin sonucunda sistemin kendisini bulduğu durumdan) duruma geçmesinin koşullu olasılığıdır.

Dolayısıyla gösterimde ilk indeks bir öncekinin sayısını, ikincisi ise? sonraki durum numarası. Örneğin, ikinci durumdan üçüncü duruma geçiş olasılığı.

Durumların sayısı sonlu ve eşit olsun.

Bir sistemin geçiş matrisi, bu sistemin tüm geçiş olasılıklarını içeren bir matristir:

Matrisin her satırı olayların (aynı durumdan herhangi bir olası duruma geçiş) olasılıklarını içerdiğinden, tam grup ise bu olayların olasılıklarının toplamı bire eşittir. Başka bir deyişle geçiş matrisinin her satırının geçiş olasılıklarının toplamı bire eşittir:

Üç durumda olabilen bir sistemin geçiş matrisine örnek verelim; durumdan duruma geçiş, homojen bir Markov zinciri şemasına göre gerçekleşir; geçiş olasılıkları matris tarafından verilmektedir:

Burada görüyoruz ki sistem bir durumdaysa, bir adımda durumu değiştirdikten sonra 0,5 olasılıkla aynı durumda kalacak, 0,5 olasılıkla aynı durumda kalacak, bir duruma geçecektir. 0,2 olasılıkla geçişten sonra kendini eyaletlerde bulabilir; bir durumdan diğerine geçemez. Son satır Matris bize bir durumdan olası durumların herhangi birine aynı olasılıkla 0,1 ile gidileceğini gösterir.

Sistemin geçiş matrisine dayanarak, sistemin durum grafiği olarak adlandırılan grafiğini oluşturabilirsiniz; buna etiketli durum grafiği de denir. Bu, devrenin görsel temsili için uygundur. Bir örnek kullanarak grafik oluşturma sırasına bakalım.

Örnek 2. Belirli bir geçiş matrisini kullanarak bir durum grafiği oluşturun.

Çünkü matris dördüncü sıra, buna göre sistemin 4 olası durumu vardır.

Grafik, sistemin bir durumdan aynı duruma geçiş olasılığını göstermez. Düşünürken özel sistemlerİlk önce bir durum grafiği oluşturmak, ardından sistemin bir durumdan aynı duruma geçiş olasılığını belirlemek (matris satırlarının öğelerinin toplamının bire eşit olması gerekliliğine dayanarak) ve ardından bir geçiş oluşturmak uygundur. sistemin matrisi.

Bu makale soyut nitelikte olup, burada verilenlere dayanarak yazılmıştır. kaynakların sonu, yer yer alıntılananlar.

Markov zincirleri teorisine giriş

Markov zinciri böyle bir dizidir rastgele olaylar Her bir olayın olasılığının yalnızca sürecin içinde bulunduğu duruma bağlı olduğu şimdiki an ve daha önceki durumlardan bağımsızdır.

1. Nihai ayrık devre şu şekilde belirlenir:
2. bir dizi durum S = (s 1, …, s n), olay rastgele bir denemenin sonucu olarak bir durumdan diğerine geçiştir vektör başlangıç ​​olasılıkları
3. (başlangıç ​​dağılımı) p (0) = ( p (0) (1),…, p (0) (n)) t = 0 başlangıç ​​zamanında sürecin şu şekilde olma olasılığını belirler: p (0) (i) ben durumunda geçiş olasılıkları matrisi P = ( p i j), süreç geçiş olasılığını karakterize eden mevcut durum

si i'den sonraki s j durumuna, bir durumdan geçiş olasılıklarının toplamı 1'e eşitken:

∑ j =1… n p ben j = 1

S = (S 1, ..., S 5) durum kümesine sahip bir geçiş olasılıkları matrisi örneği, p (0) = (1, 0, 0, 0, 0) başlangıç ​​olasılıklarının bir vektörü:

Başlangıç ​​olasılıkları vektörünü ve geçiş matrisini kullanarak, sürecin n zamanında i durumunda olacağını gösteren p(n)(i) olasılıklarından oluşan bir vektör olan stokastik vektör p(n)'yi hesaplayabiliriz. Aşağıdaki formülü kullanarak p(n) değerini elde edebilirsiniz:

P(n) = p(0)×Pn
N büyüdükçe p (n) vektörleri bazı durumlarda stabilize olur - zincirin sabit dağılımı olarak adlandırılabilecek belirli bir olasılık vektörüne ρ yakınlaşırlar. Durağanlık, p (0) = ρ alarak herhangi bir n için p (n) = ρ elde etmemiz gerçeğinde ortaya çıkar.
En basit kriter
Durağan bir dağılıma yakınsamayı garanti eden şuna benzer: P geçiş olasılıkları matrisinin tüm elemanları pozitifse, o zaman n sonsuza doğru yöneldikçe, p(n) vektörü ρ vektörüne doğru yönelir, bu da tek çözümdür form sistemine p × P = p. n P n matrisinin tüm elemanları pozitifse, o zaman p (n) vektörü hala kararlı olacaktır.
Bu ifadelerin kanıtları ayrıntılı olarak sunulmaktadır.

Markov zinciri, köşeleri zincirin durumlarına ve yaylar da aralarındaki geçişlere karşılık gelen bir geçiş grafiği olarak gösterilir. si ve sj köşelerini birleştiren yayın (i, j) ağırlığı şu şekilde olacaktır: olasılığa eşit pi (j) birinci durumdan ikinci duruma geçiş.

Yukarıda gösterilen matrise karşılık gelen grafik:

Markov zincirlerinin durumlarının sınıflandırılması Markov zincirlerini değerlendirirken sistemin kısa bir süre içindeki davranışı ilgimizi çekebilir. Bu durumda mutlak olasılıklar önceki bölümdeki formüller kullanılarak hesaplanır. Ancak sistemin davranışını incelemek daha önemlidir. geniş aralık
geçiş sayısının sonsuza doğru gittiği zamandır.
Daha sonra, sistemin uzun vadedeki davranışını incelemek için gerekli olan Markov zincirlerinin durumlarının tanımları tanıtılmaktadır. Markov zincirleri bir durumdan diğerine geçiş olasılığına göre sınıflandırılır. Geçiş grafiğinin sıra diyagramının çıkmaz köşelerine karşılık gelen bir Markov zincirinin durum gruplarına (geçiş grafiğinin köşelerinin alt kümeleri), zincirin ergodik sınıfları denir.

Yukarıda gösterilen grafiği dikkate alırsak, M 2 = ( S 1 , S 2 , S 3 , S4). Ergodik sınıflarda yer alan durumlara temel, geri kalanlara ise gerekli olmayan denir (her ne kadar bu tür isimler sağduyu). Soğurucu durum s i ergodik sınıfın özel bir durumudur. Daha sonra böyle bir duruma gelindiğinde süreç duracaktır. S i için p ii = 1 doğru olacaktır, yani. geçiş grafiğinde ondan yalnızca bir kenar çıkacaktır - bir döngü., varyanslar ve gerekiyorsa dağılımlar. Gelecekte bu istatistikleri kullanarak program kodunu optimize edebilirsiniz; programın kritik kısımlarını hızlandırmak için düşük seviyeli yöntemler kullanın. Bu yönteme kod profili oluşturma adı verilir.

Örneğin Dijkstra'nın algoritmasında aşağıdaki devre durumları mevcuttur:

• köşe (v), öncelik kuyruğundan yeni bir köşeyi kaldırın, yalnızca b durumuna gidin;
• başlangıç ​​(b), zayıflama prosedürü için giden yayları arama döngüsünün başlangıcı;
• analiz (a), bir sonraki yayın analizi, a, d veya e'ye olası geçiş;
• azalma (d), grafiğin bazı köşe noktalarına ilişkin tahminin azaltılması, a'ya doğru hareket edilmesi;
• son (e), döngünün tamamlanması, bir sonraki köşeye geçilmesi.

Geriye köşeler arasındaki geçiş olasılıklarını ayarlamak kalır ve köşeler arasındaki geçişlerin süresini, çeşitli durumlara girme olasılıklarını ve sürecin diğer ortalama özelliklerini inceleyebilirsiniz.

Benzer şekilde, sistem kaynaklarına program tarafından belirlenen sırayla erişilmesiyle ilgili hesaplama süreci, durumları sistem kaynaklarının (işlemci, bellek ve çevresel aygıtlar geçişi) kullanımına karşılık gelen emici bir Markov zinciri ile temsil edilebilir; olasılıklar çeşitli kaynaklara erişim sırasını yansıtır. Bu sayede hesaplama süreci, özelliklerinin analizine uygun bir biçimde sunulmaktadır.

Herhangi bir S j durumuna diğer herhangi bir S i durumundan sonlu sayıda geçişle ulaşılabiliyorsa Markov zincirine indirgenemez zincir denir. Bu durumda devrenin tüm durumlarının iletişim halinde olduğu söylenir ve geçiş grafiği güçlü bağlantının bir bileşenidir.
sürecin Sj durumlarında olma olasılığı, j = 1,…, n, sürecin her bir durumda harcadığı zamanın oranı.

İndirgenemez devreler sistem güvenilirliğinin modelleri olarak kullanılır. Gerçekten de, bir sürecin sıklıkla kullandığı bir kaynak arızalanırsa tüm sistemin işlevselliği riske girecektir.

Bu durumda, bu kadar kritik bir kaynağın kopyalanması, arızaların önlenmesine yardımcı olabilir.

Bu durumda, servis verilebilir ve arızalı ekipmanın bileşiminde farklılık gösteren sistemin durumları, devre durumları, aralarındaki geçişler arızalarla ilişkili ve cihazların restorasyonu ve aralarındaki bağlantılardaki değişiklikler olarak yorumlanır. sistemin çalışabilirliği. İndirgenemez bir devrenin özelliklerinin tahminleri, sistemin bir bütün olarak davranışının güvenilirliği hakkında fikir verir. Ayrıca bu tür devreler, işleme için gönderilen cihazlar ve görevler arasındaki etkileşim modelleri olabilir. Kullanım örnekleri

2 β 1 - α - 2 β 3 β

1 - α - 3 β
4β
1 - 4β
Benzersiz bir ergodik sınıfa sahip olduğu ve bu nedenle olasılık vektörleri sınıfındaki p × P = p sisteminin sahip olduğu not edilebilir.
tek çözüm

. Bu çözümü bulmamızı sağlayan sistemin denklemlerini yazalım:

P 0 (1 - α) + p 1 β = p 0 ,
p 0 α + p 1 (1 - α - β) + p 2 2 β = p 1,
p 1 α + p 2 (1 - α - 2 β) + p 3 3 β = p 2,
p 2 α + p 3 (1 - α - 3 β) + p 4 4 β = p 3,

p 3 α + p 4 (1 - 4 β) = p 4 .

Bundan şunu elde ederiz (γ = α / β ile):

Artık πi olasılıkları kümesi, sabit modda sistemin i bloklarını meşgul edeceği bilinmektedir. Bu durumda, p 4 = C γ 4/4 süresinin bir bölümünde sistemdeki tüm bloklar dolu olur, sistem isteklere yanıt vermez. Elde edilen sonuçlar herhangi bir sayıda blok için geçerlidir. Artık bunlardan yararlanabilirsiniz: Ek cihazların maliyetlerini ve sistemin tamamen dolu olduğu süredeki azalmayı karşılaştırabilirsiniz.
Bu örnek hakkında daha fazlasını şuradan okuyabilirsiniz.

Sonlu ve sonsuz sayıda aşamaya sahip karar verme süreçleri

Birkaç geçiş olasılığı matrisinin olduğu bir süreci düşünün. Zamanın her anı için şu veya bu matrisin seçimi verdiğimiz karara bağlıdır. Yukarıdaki örnek aşağıdaki örnek kullanılarak anlaşılabilir. Bahçıvan, toprak analizi sonucunda durumunu üç sayıdan biriyle değerlendirir: (1) - iyi, (2) - tatmin edici veya (3) - kötü. Bahçıvan aynı zamanda toprağın bu yılki verimliliğinin yalnızca bir önceki yıldaki durumuna bağlı olduğunu fark etti. Bu nedenle toprak geçişi olasılığı olmadan

dış etkiler

Gübre maliyetine ve toprak kalitesine bağlı olarak gelir fonksiyonlarını belirleyen R1 ve R2 matrislerini tanıtalım: R1 R2 Son olarak bahçıvan ortalama beklenen getiriyi maksimuma çıkarmak için hangi stratejiyi seçeceği sorunuyla karşı karşıya kalır.İki tür problem düşünülebilir: sonlu ve sonsuz sayı aşamalar.

Bahçıvan N yıl sonra mesleğini bırakma niyetinde olsun.

Şimdi bizim görevimiz bahçıvan için en uygun davranış stratejisini, yani gelirini maksimuma çıkaracak stratejiyi belirlemektir. Sorunumuzdaki aşama sayısının sınırlılığı, bahçıvanın N + 1 yılda (N dahil tüm yıllar onun için önemlidir) tarım arazisine ne olacağını umursamaması gerçeğinde ortaya çıkmaktadır. Artık bu durumda strateji arama probleminin dinamik programlama problemine dönüştüğünü görebiliriz. Eğer i durum numarasından başlayarak n'den N'ye kadar olan aşamalar için alınabilecek maksimum ortalama beklenen geliri f n (i) ile belirtirsek, o zaman f n (i)'yi f n + sayılarına bağlayan bir yineleme ilişkisi türetmek kolaydır. 1 (j)
F n (i) = maksimum k (∑ j =1 m p ij k [ r ij k + f n +1 (j)]), n = 1, 2, …, N
Burada k kullanılan stratejinin sayısıdır. Bu denklem, toplam gelir r ij k + f n +1 (j), n aşamasındaki i durumundan n +1 aşamasındaki j durumuna pi ij k olasılığı ile geçişin bir sonucu olarak elde edildiği gerçeğine dayanmaktadır. Artık optimal çözüm, fn(i)'nin azalan yönde (n = N ...1) sıralı olarak hesaplanmasıyla bulunabilir.

Aynı zamanda, problem ifadesine başlangıç ​​olasılıklarının bir vektörünü dahil etmek, problemin çözümünü zorlaştırmayacaktır.

Bu örnek 'da da tartışıldı.. Ancak bu şekilde ilerlemek imkansızdır çünkü metnin anlamsal yükünün yüksek dereceli Markov zincirlerindeki büyümesi, metnin benzersizliğinin azalmasından çok daha yavaş gerçekleşir. Ve örneğin otuzuncu dereceden Markov zincirleri üzerine inşa edilmiş bir metin yine de insanların ilgisini çekecek kadar anlamlı olmayacak, ancak zaten oldukça benzer olacaktır. orijinal metinÜstelik böyle bir devredeki durumların sayısı şaşırtıcı olacaktır.
Bu teknoloji artık internette web sayfası içeriği oluşturmak için (maalesef) çok yaygın olarak kullanılıyor. Web sitelerine gelen trafiği artırmak ve sıralamasını yükseltmek isteyenler arama motorları, sayfalarına mümkün olduğunca çok şey koymaya çalışın anahtar kelimeler Aramak için. Ancak arama motorları, gerçek metni tutarsız bir anahtar kelime karmaşasından ayırt edebilen algoritmalar kullanır. Daha sonra arama motorlarını kandırmak için Markov zincirine dayalı bir oluşturucu tarafından oluşturulan metinleri kullanırlar. Elbette var olumlu örnekler Markov zincirlerinin metinle çalışmak için kullanılması; yazarlığın belirlenmesinde ve metinlerin orijinalliğinin analiz edilmesinde kullanılır.

Markov zincirleri ve piyangolar

Bazı durumlarda olasılıksal modelÇeşitli piyangolardaki sayıları tahmin etmek için kullanılır. Görünen o ki, farklı dolaşımların sırasını modellemek için Markov zincirlerini kullanmanın bir anlamı yok. Çekilişte toplara ne olduğu bir sonraki çekilişin sonuçlarını hiçbir şekilde etkilemeyecektir, çünkü çekilişten sonra toplar toplanır ve bir sonraki çekilişte toplar piyango tepsisine yerleştirilir. sabit sıra. Bu durumda geçmiş dolaşımla bağlantı kopar. Başka bir şey de, bir çekilişte düşen topların sırasıdır. gözlemlenen aynı olaya karşılık gelen durumlar. Bu nedenle, yalnızca bu tür durum grupları arasında bir geçiş olasılıkları matrisi oluşturabiliriz. Bu olasılıklar farklı durumlar arasındaki geçiş olasılıklarının ortalamasıdır. ayrı eyaletler Bu elbette Markov zinciri modelinin sayısal piyangolara uygulanmasının verimliliğini azaltır.
Bu duruma benzer bir model sinir ağı hava durumu tahminleri, döviz fiyatları ve geçmiş verilerin mevcut olduğu diğer sistemlerle bağlantılı olarak kullanılabilir ve yeni alınan bilgiler gelecekte kullanılabilir. İyi kullanım bu durumda, sistemin yalnızca tezahürleri bilindiğinde, ancak iç (gizli) durumlar bilinmediğinde, Vikikitap'ta ayrıntılı olarak tartışılan gizli Markov modelleri (gizli Markov modelleri) uygulanabilir.

Edebiyat

1. Romanovski I.V.
2. Ayrık analiz: Öğrenciler için bir ders kitabı, 3. baskı. - St. Petersburg: Nevsky Lehçesi; BHV Petersburg, 2003. Taha, Hamdy A. Yöneylem Araştırmasına Giriş, 6. baskı.
3. - M.:
4. Yayınevi

Williams, 2001.

1. Werner M. Kodlamanın temelleri. Üniversiteler için ders kitabı.
2. - M .: Tekhnosfer, 2004.

Belyaev A., Gavrilov M., Masalskikh A., Medvinsky M. Markov süreçleri, 2004. Görselleştiriciler Alekseev V. Markov karar verme süreçleri, 2002. Belyaev A. Markov zincirleri, 2002. Yöntemler
matematiksel açıklamalar Markoviyen rastgele süreçler ayrık durumları olan bir sistemde (DS), sistemin durumdan duruma geçişlerinin zaman içinde hangi noktalarda (önceden bilinen veya rastgele) meydana gelebileceğine bağlıdır. Bir sistemin bir durumdan duruma geçişi önceden belirlenmiş anlarda mümkünse, söz konusu olan şeyle ilgileniyoruz ayrık zamanlı rastgele Markov süreci.
Geçiş herhangi bir zamanda mümkünse rastgele an S zaman, o zaman uğraşıyoruz N sürekli zamanlı rastgele Markov süreci. S 1 , S 2 , …, Olsun fiziksel sistem T 1 , T 2 , …, , içinde olabilecek eyaletler S Sn . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür teşekkürler
, bu anları zaman adımları olarak adlandıralım. Sistemde ortak girişimi dikkate alacağız S 1 → S 2 → S 3 → S 2 .
1, 2, … tamsayı argümanının bir fonksiyonu olarak k (burada argüman adım numarasıdır.Örnek: . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür atamayı kabul edelim ben.
k . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür) – sonrasında oluşan bir olay burada argüman adım numarasıdır. sistemin S durumunda olduğu adımlar burada argüman adım numarasıdır. Ben Herhangi biri için (burada argüman adım numarasıdır. olaylar S 1 ( ) , S 2 () ,…, S N

) biçim
tam bir etkinlik grubu S 1 (0) , S ve onlar
Bu dizi denir Markov zinciri , eğer her adım için herhangi bir durumdan geçiş olasılığı varsa k her koşulda S j sistemin duruma ne zaman ve nasıl ulaştığına bağlı değildir k.
Herhangi bir zamanda herhangi bir zamanda izin ver . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür-inci adım sistemi S eyaletlerden birinde olabilir S 1 , S 2 , …, Olsun, yani tam bir olay grubundan bir olay meydana gelebilir: S 1 (burada argüman adım numarasıdır. sistemin S durumunda olduğu adımlar burada argüman adım numarasıdır.) , …, Olsun (burada argüman adım numarasıdır.). Bu olayların olasılıklarını gösterelim:
P 1 (1) = P(S 1 (1)); P 2 (1) = P(S 2 (1)); …; Pn(1) = P(Olsun (burada argüman adım numarasıdır.));
P 1 (2) = P(S 1 (2)); P 2 (2) = P(S2(2)); ...; Pn(2) = P(Olsun (2));
P 1 (. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür) = P(S 1 (. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür)); P 2 (. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür) = P(S 2 (. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür)); …; Pn(. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür) = P(Olsun (. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür)).
Her adım numarası için koşulun karşılandığını görmek kolaydır
P 1 (. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür) + P 2 (. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür) +…+ Pn(. Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür) = 1.
Bu olasılıklara diyelim durum olasılıkları Bu nedenle görev şu şekilde görünecektir: herhangi bir durum için sistem durumlarının olasılıklarını bulun . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür.
Örnek. Altı durumdan herhangi birinde olabilecek bir tür sistem olsun. daha sonra içinde meydana gelen süreçler, sistemin durumundaki değişikliklerin bir grafiği olarak gösterilebilir (Şekil 7.9, A) veya bir sistem durumu grafiği biçiminde (Şekil 7.9, B).

A)

Pirinç. 7.9
Ayrıca sistemdeki süreçler bir dizi durum olarak gösterilebilir: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Durum olasılığı ( . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür+ 1)inci adım yalnızca şu anki duruma bağlıdır k- adım.
Herhangi bir adım için . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür sistemin herhangi bir durumdan başka bir duruma geçmesinin bazı olasılıkları vardır, bunlara olasılıklar diyelim Markov zincirinin geçiş olasılıkları.
Bir durumdan diğerine geçiş tek adımda mümkün değilse bu olasılıklardan bazıları 0 olacaktır.
Markov zinciri denir homojen geçiş durumları adım numarasına bağlı değilse, aksi takdirde denir heterojen.
Homojen bir Markov zinciri olsun ve sistem S sahip olmak N olası durumlar: S 1 , …, Olsun. Her durum için bir adımda başka bir duruma geçme olasılığı bilinsin, yani. P ij(itibaren k V S j tek adımda) geçiş olasılıklarını bir matris olarak yazabiliriz.

. (7.1)
Bu matrisin köşegeni boyunca sistemin durumdan geçiş olasılıkları vardır. k aynı durumda k.
Daha önce girilen etkinlikleri kullanma geçiş olasılıklarını koşullu olasılıklar olarak yazabiliriz:
.
Açıkçası terimlerin toplamı olaylar olduğundan matrisin her satırındaki (1) bire eşittir tam bir uyumsuz olaylar grubu oluşturur.

Markov zincirlerini değerlendirirken ve Markov rastgele sürecini analiz ederken çeşitli durum grafikleri kullanılır (Şekil 7.10).

Pirinç. 7.10

Bu sistem altı durumdan herhangi birinde olabilir. P ij sistemin durumdan geçiş olasılığıdır k bir durumda S j. Bu sistem için sistemin belirli bir durumda olduğu ve zaman içinde bu durumun dışında olduğu denklemlerini yazıyoruz. Tçıkmadı:

İÇİNDE genel durum Markov zinciri homojen değildir, yani olasılık P ij adımdan adıma değişir. Her adımda bir geçiş olasılıkları matrisinin verildiğini varsayalım, o zaman sistemin olasılığı S Açık . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür-th adım eyalette olacak k formülü kullanılarak bulunabilir

Geçiş olasılıkları matrisi ve sistemin başlangıç ​​durumu bilindiğinde, durumların olasılıkları bulunabilir. herhangi birinden sonra . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür-inci adım. Zamanın ilk anında sistemin bu durumda olmasına izin verin Sm. O zaman t = 0 için
.
İlk adımdan sonra olasılıkları bulalım. Devletten Sm sistem durumlara girecek S 1 , S 2 vb. olasılıklarla Öğleden sonra 1 , Öğleden sonra 2 , …, Pmm, …, P mn. O zaman ilk adımdan sonra olasılıklar eşit olacaktır

. (7.2)
İkinci adımdan sonraki durumun olasılıklarını bulalım: . Bu olasılıkları aşağıdaki formülü kullanarak hesaplayacağız: tam olasılık hipotezlerle:
.
Hipotezler aşağıdaki ifadeler olacaktır:

• ilk adımdan sonra sistem S1-H1 durumundaydı;
• ikinci adımdan sonra sistem S2-H2 durumundaydı;
• sonrasında N Adımın sonunda sistem S n -H n durumundaydı.

İkinci adımdan sonra herhangi bir durumun olasılığı:

(7.3)
Formül (7.3) tüm geçiş olasılıklarını özetler P ij, ancak yalnızca sıfır olmayanlar dikkate alınır. Sonrasında herhangi bir koşulun olasılığı . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür-inci adım:

(7.4)
Böylece, bir durumun olasılığı . Bir durumdan diğerine geçişler yalnızca belirli anlarda mümkündür adım, yinelenen formül (7.4) ile olasılıklar ( k- 1) adım.

Görev 6. Bir Markov zinciri için tek adımda geçiş olasılıklarının bir matrisi verilmiştir. Belirli bir devrenin geçiş matrisini üç adımda bulun .
Çözüm. Bir sistemin geçiş matrisi, bu sistemin tüm geçiş olasılıklarını içeren bir matristir:

Matrisin her satırı olayların olasılıklarını içerir (durumdan geçiş Ben bir durumda J), tam bir grup oluşturur, dolayısıyla bu olayların olasılıklarının toplamı bire eşittir:

Sistemin n adım (test) sonucunda i durumundan j durumuna geçme olasılığını pi j (n) ile gösterelim. Örneğin p 25(10), ikinci durumdan beşinci duruma on adımda geçiş olasılığıdır. n=1 için pi j (1)=pi j geçiş olasılıklarını elde ettiğimize dikkat edin.
Bize bir görev veriliyor: geçiş olasılıklarını pij bilmek, sistemin durumdan geçiş olasılıklarını pij(n) bulmak Ben bir durumda J için N adımlar. Bunu yapmak için bir ara madde (arasında) tanıtıyoruz. Ben Ve J) durum R. Başka bir deyişle, başlangıç ​​durumundan itibaren bunu varsayacağız. Ben için M sistemin ara duruma geçeceği adımlar R pi j (n-m) olasılığı ile, bundan sonra kalanlar için n-m adım r ara durumundan p ij (n-m) olasılığıyla j son durumuna gidecektir. Toplam olasılık formülünü kullanarak şunu elde ederiz:
.
Bu formüle Markov eşitliği denir. Bu formülü kullanarak tüm pi j (n) olasılıklarını ve dolayısıyla P n matrisinin kendisini bulabilirsiniz. Matris hesabı hedefe daha hızlı ulaştırdığından, elde edilen formülden elde edilen matris ilişkisini genel formda yazıyoruz.
Ortaya çıkan formülü kullanarak Markov zincirinin geçiş matrisini üç adımda hesaplayalım:

Cevap:.

Görev No.1. Markov zinciri geçiş olasılığı matrisi şu şekildedir:
.
t=0 anındaki durumlar üzerindeki dağılım, vektör tarafından belirlenir:
π 0 =(0,5; 0,2; 0,3)
Bulmak: a) t=1,2,3,4 anlarında duruma göre dağılım.
c) sabit dağıtım.

Markov Zinciri ölçülebilir uzayda tanımlanan ayrık zamanlı bir Markov sürecidir.

giriiş

Markov rastgele süreçleri, adını ilk kez rastgele değişkenlerin olasılıksal bağlantısı üzerine çalışmaya başlayan ve "olasılık dinamiği" olarak adlandırılabilecek bir teori yaratan seçkin Rus matematikçi A.A. Markov'dan (1856-1922) almıştır.

İÇİNDE diğer temel bilgiler bu teori ilk temeldi genel teori rastgele süreçlerin yanı sıra bu kadar önemli uygulamalı bilimler, difüzyon süreçleri teorisi, güvenilirlik teorisi, teori olarak sıraya girme vesaire. Günümüzde Markov süreçleri teorisi ve uygulamaları çeşitli alanlarda yaygın olarak kullanılmaktadır.

Matematiksel aparatın karşılaştırmalı basitliği ve netliği nedeniyle elde edilen çözümlerin yüksek güvenilirliği ve doğruluğu, özel ilgi Markov süreçleri yöneylem araştırması ve optimal karar verme teorisi ile ilgilenen uzmanlardan alınmıştır.

Basit örnek: yazı tura atmak

Açıklama vermeden önce genel şema, hadi dönelim basit örnek. Diyelim ki hakkında konuşuyoruz bir para atma oyununda art arda yazı tura atılması hakkında; t = 0, 1, ... gibi zamanın koşullu anlarında bir para atılıyor ve her adımda oyuncu aynı 1/2 olasılıkla ±1 kazanabiliyor, dolayısıyla t zamanındaki toplam kazancı şu şekildedir: rastgele değişkenξ(t) ile olası değerler j = 0, ±1, ...

ξ(t) = k olması koşuluyla, bir sonraki adımda kazanç zaten ξ(t+1) = k ± 1'e eşit olacaktır. belirtilen değerler j = k ± 1, eşit olasılıkla 1/2.

Geleneksel olarak burada karşılık gelen olasılıkla ξ(t) = k durumundan ξ(t+1) = k ± 1 durumuna bir geçişin meydana geldiğini söyleyebiliriz.

Formüller ve tanımlar

Bu örneği genelleştirirsek, t = 0, 1, ... ayrık zamanı boyunca durumdan duruma rastgele geçen, sayılabilir sayıda olası "faz" durumuna sahip bir "sistem" hayal edebiliriz.

Rastgele geçişler zincirinin bir sonucu olarak ξ(t)'nin t zamanındaki konumu olsun

ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Her şeyi resmi olarak belirtelim olası durumlar tamsayılar i = 0, ±1, ... Bilinen bir ξ(t) = k durumu için, bir sonraki adımda sistemin koşullu olasılıkla ξ(t+1) = j durumuna gittiğini varsayalım.

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

geçmişteki davranışından bağımsız olarak, daha doğrusu, t anına kadar olan geçiş zincirinden (1) bağımsız olarak:

Hepsi için P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) t, k, j... (3) - Markov'un mülkü.

Bu olasılıksal şemaya denir sayılabilir sayıda duruma sahip homojen Markov zinciri- homojenliği (2)'de tanımlananların olmasıdır. geçiş olasılıkları p kj, ∑ j p kj = 1, k = 0, ±1, ..., zamana bağlı değildir, yani. P(ξ(t+1) = j|ξ(t) = k) = P ij - geçiş olasılığı matrisi bir adımda n'ye bağlı değildir.

Açıkça görülüyor ki P ij - kare matris negatif olmayan öğeler ve satırlar arasındaki birim toplamları ile.

Böyle bir matrise (sonlu veya sonsuz) stokastik matris adı verilir. Herhangi bir stokastik matris, geçiş olasılıklarının bir matrisi olarak hizmet edebilir.

Uygulamada: ekipmanların ilçelere teslimi

Belirli bir şirketin Moskova'da ekipman teslim ettiğini varsayalım: kuzey bölgesi(A ile gösterilir), güney (B) ve orta (C). Şirketin bu bölgelere hizmet veren bir kurye ekibi bulunmaktadır. Kuryenin bir sonraki teslimatı yapmak için halihazırda kendisine daha yakın olan bölgeye gittiği açıktır. Aşağıdakiler istatistiksel olarak belirlendi:

1) A'ya teslimattan sonra, bir sonraki teslimat A'da 30 vakada, B'de 30 vakada ve C'de 40 vakada gerçekleştirilir;

2) B'ye teslimattan sonra, bir sonraki teslimat A'da 40 vakada, B'de 40 vakada ve C'de 20 vakada gerçekleştirilir;

3) C'ye teslimattan sonra, bir sonraki teslimat A'da 50 vakada, B'de 30 vakada ve C'de 20 vakada gerçekleştirilir.

Böylece bir sonraki teslimat bölgesi yalnızca bir önceki teslimata göre belirlenir.

Geçiş olasılığı matrisi şöyle görünecektir:

Örneğin p 12 = 0,4, B alanına teslimattan sonra bir sonraki teslimatın A alanına yapılma olasılığıdır.

Her teslimatın ardından bir sonraki bölgeye hareketin 15 dakika sürdüğünü varsayalım. Daha sonra istatistiklere göre 15 dakika sonra A'da bulunan kuryelerin %30'u A'da, %30'u B'de ve %40'ı C'de olacak.

Bir sonraki anda kuryelerin her biri mutlaka bölgelerden birinde olacağından sütunların toplamı 1'e eşittir. Ve olasılıklarla uğraştığımız için matrisin her elemanı 0'dır.<р ij <1.

Bu modeli Markov zinciri olarak yorumlamamızı sağlayan en önemli durum kuryenin t+1 anındaki konumunun aşağıdakilere bağlı olmasıdır. sadece t zamanındaki konumdan.

Şimdi basit bir soru soralım: Eğer kurye C'den başlıyorsa, iki teslimat yaptıktan sonra B'de olma olasılığı nedir? 2 adımda B'ye nasıl ulaşabilirsiniz? Yani, 2 adımda C'den B'ye giden birkaç yol vardır:

1) önce C'den C'ye ve sonra C'den B'ye;

2) C-->B ve B-->B;

3) C-->A ve A-->B.

Çarpma kuralı göz önüne alındığında bağımsız olaylarİstenilen olasılığın şuna eşit olduğunu buluruz:

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

Sayısal değerlerin değiştirilmesi:

P = 0,5*0,3 + 0,3*0,4 + 0,2*0,3 = 0,33

Elde edilen sonuç, kuryenin C'den çalışmaya başlaması durumunda 100 vakadan 33'ünde iki teslimattan sonra B'de olacağını göstermektedir.

Açıkçası hesaplamalar basit, ancak 5 veya 15 doğumdan sonra olasılığı belirlemeniz gerekiyorsa, oldukça fazla zaman alabilir.

Bu tür olasılıkları hesaplamanın daha basit bir yolunu gösterelim. Geçiş olasılıklarını elde etmek için çeşitli koşullar 2 adımda P matrisinin karesini alırız:

O halde (2, 3) elemanı, yukarıda başka bir şekilde elde edilen, C'den B'ye 2 adımda geçiş olasılığıdır. P2 matrisindeki elemanların da 0 ile 1 arasında değiştiğini ve sütunların toplamının 1 olduğunu unutmayın.

O. C'den B'ye geçiş olasılıklarını 3 adımda belirlemeniz gerekiyorsa:

1 yol. 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, burada p(CA) - 2 adımda C'den A'ya geçiş olasılığı (yani bu, P2 matrisinin (1, 3) öğesidir).

Yöntem 2. P3 matrisini hesaplayın:

7. kuvvete geçiş olasılıkları matrisi şöyle görünecektir:

Her satırın öğelerinin bazı sayılara eğilimli olduğunu fark etmek kolaydır. Bu şunu gösteriyor ki, yeterince sonra büyük miktar Teslimatta kuryenin hangi ilçede çalışmaya başladığı önemli değildir. O. hafta sonunda yaklaşık %38,9'u A'da, %33,3'ü B'de ve %27,8'i C'de olacak.

Geçiş olasılığı matrisinin tüm elemanları (0, 1) aralığına aitse, bu tür bir yakınsamanın meydana gelmesi garanti edilir.