Markov zinciri - Markov chain

Durumları E ve A olarak etiketlenmiş, iki durumlu bir Markov sürecini temsil eden bir diyagram. Her sayı, Markov sürecinin okla gösterilen yönde bir durumdan başka bir duruma geçme olasılığını temsil eder. Örneğin, Markov süreci A durumundaysa, E durumuna geçme olasılığı 0,4, A durumunda kalma olasılığı 0,6'dır.

Bir Markov zinciri veya Markov süreci , her bir olayın olasılığının yalnızca önceki olayda elde edilen duruma bağlı olduğu olası olaylar dizisini tanımlayan stokastik bir modeldir . Bir sayılabilir sonsuz dizisi, ayrı zaman basamaklarında de bu zincir hareket durumu içinde, bir verir ayrık zaman Markov zinciri (DTMC). Bir sürekli zaman süreci olarak adlandırılan sürekli-zaman Markov zinciri (CTMC). Adını Rus matematikçi Andrey Markov'dan almıştır .

Markov zincirleri gibi birçok uygulamalara sahip istatistiksel modeller böyle okuyan olarak gerçek dünya süreçlerinin, seyir kontrol sistemleri içinde motorlu araçlar , kuyruklar ve havaalanı, döviz gelen müşterilerin hatlarının döviz kurları ve hayvan popülasyon dinamikleri.

Markov süreçleri, karmaşık olasılık dağılımlarından örneklemeyi simüle etmek için kullanılan ve Bayes istatistikleri , termodinamik , istatistiksel mekanik , fizik , kimya , ekonomi , finans , sinyal alanlarında uygulama bulan Markov zinciri Monte Carlo olarak bilinen genel stokastik simülasyon yöntemlerinin temelidir. işleme , bilgi teorisi ve konuşma işleme .

Markovian ve Markov sıfatları , bir Markov süreci ile ilgili bir şeyi tanımlamak için kullanılır.

Tanıtım

Rus matematikçi Andrey Markov

Tanım

Bir Markov süreci, Markov özelliğini (bazen " hafızasızlık " olarak nitelendirilen) karşılayan stokastik bir süreçtir . Daha basit bir ifadeyle, yalnızca mevcut durumuna dayanarak gelecekteki sonuçlara ilişkin tahminlerin yapılabileceği ve - en önemlisi - bu tür tahminlerin, sürecin tam geçmişi bilinerek yapılabilecekler kadar iyi olduğu bir süreçtir. Diğer bir deyişle, şartlı sistemin mevcut durumuna, gelecekteki ve geçmişteki durumları vardır bağımsız .

Bir Markov zinciri, ayrı bir durum uzayına veya ayrı bir dizin kümesine (genellikle zamanı temsil eder) sahip olan bir Markov süreci türüdür , ancak bir Markov zincirinin kesin tanımı değişir. Örneğin, bir Markov zincirini ayrık veya sürekli zamanda sayılabilir bir durum uzayıyla (dolayısıyla zamanın doğasından bağımsız olarak) bir Markov süreci olarak tanımlamak yaygındır, ancak bir Markov zincirini ayrık zamana sahip olarak tanımlamak da yaygındır. sayılabilir veya sürekli durum uzayında (böylece durum uzayından bağımsız olarak).

Markov zincirlerinin türleri

Sistemin durum uzayı ve zaman parametre indeksinin belirtilmesi gerekir. Aşağıdaki tablo, farklı durum uzayı genelliği seviyeleri ve ayrık zaman v. sürekli zaman için Markov süreçlerinin farklı örneklerine genel bir bakış sunar:

sayılabilir durum uzayı Sürekli veya genel durum uzayı
ayrık zamanlı (ayrık zamanlı) Sayılabilir veya sonlu bir durum uzayında Markov zinciri Ölçülebilir bir durum uzayında Markov zinciri (örneğin, Harris zinciri )
sürekli-zaman Sürekli zamanlı Markov süreci veya Markov atlama süreci Markov özelliğine sahip herhangi bir sürekli stokastik süreç (örneğin, Wiener süreci )

Markov süreçlerinin özel durumlarını ifade eden bazı terimlerin kullanımı konusunda literatürde kesin bir anlaşma bulunmadığına dikkat edin. Genellikle "Markov zinciri" terimi, ayrık zamanlı bir Markov zinciri (DTMC) olan ayrık zamanlı bir süreç için ayrılmıştır , ancak birkaç yazar "Markov süreci" terimini sürekli zamanı belirtmek için kullanır. Markov zinciri (CTMC) açıkça belirtilmeden. Ek olarak, Markov süreçlerinin bu şekilde anılan ancak bu dört kategoriden herhangi birine dahil olmayan başka uzantıları da vardır (bakınız Markov modeli ). Ayrıca, zaman endeksinin mutlaka gerçek değerli olması gerekmez; durum uzayında olduğu gibi, diğer matematiksel yapılarla indeks kümeleri arasında hareket eden düşünülebilir süreçler vardır. Genel durum uzayı sürekli-zamanlı Markov zincirinin belirlenmiş bir terimi olmayacak derecede genel olduğuna dikkat edin.

Zaman parametresi genellikle ayrık olsa da , bir Markov zincirinin durum uzayı üzerinde genel olarak üzerinde anlaşmaya varılmış herhangi bir kısıtlamaya sahip değildir: terim, keyfi bir durum uzayındaki bir sürece atıfta bulunabilir. Bununla birlikte, Markov zincirlerinin birçok uygulaması, daha basit bir istatistiksel analize sahip olan sonlu veya sayılabilir sonsuz durum uzaylarını kullanır . Zaman-endeksi ve durum-uzay parametrelerinin yanı sıra, birçok başka varyasyon, uzantı ve genelleme vardır (bkz. Varyasyonlar ). Basit olması için, bu makalenin çoğu, aksi belirtilmedikçe, ayrık zaman, ayrık durum-uzay durumu üzerinde yoğunlaşmaktadır.

geçişler

Sistemin durum değişikliklerine geçişler denir. Çeşitli durum değişiklikleriyle ilişkili olasılıklara geçiş olasılıkları denir. Süreç, bir durum uzayı, belirli geçişlerin olasılıklarını tanımlayan bir geçiş matrisi ve durum uzayı boyunca bir başlangıç ​​durumu (veya başlangıç ​​dağılımı) ile karakterize edilir. Geleneksel olarak, tüm olası durumların ve geçişlerin sürecin tanımına dahil edildiğini varsayıyoruz, bu nedenle her zaman bir sonraki durum vardır ve süreç sona ermez.

Ayrık zamanlı rastgele süreç, her adımda belirli bir durumda olan bir sistemi içerir ve durum adımlar arasında rastgele değişir. Adımlar genellikle zaman içindeki anlar olarak düşünülür, ancak aynı derecede iyi bir şekilde fiziksel mesafeye veya başka herhangi bir ayrık ölçüme atıfta bulunabilirler. Resmi olarak, adımlar tamsayılar veya doğal sayılardır ve rastgele süreç, bunların durumlarla eşlenmesidir. Markov özelliği , bir sonraki adımda (ve aslında tüm gelecekteki adımlarda) sistem için koşullu olasılık dağılımının , ayrıca sistemin önceki adımlardaki durumuna değil, yalnızca sistemin mevcut durumuna bağlı olduğunu belirtir.

Sistem rastgele değiştiği için, gelecekte belirli bir noktada bir Markov zincirinin durumunu kesin olarak tahmin etmek genellikle imkansızdır. Ancak, sistemin geleceğinin istatistiksel özellikleri tahmin edilebilir. Birçok uygulamada önemli olan bu istatistiksel özelliklerdir.

Tarih

Markov, 20. yüzyılın başlarında Markov süreçlerini inceledi ve konuyla ilgili ilk makalesini 1906'da yayınladı. Sürekli zamandaki Markov süreçleri, 20. yüzyılın başlarında Poisson süreci biçiminde Andrey Markov'un çalışmasından çok önce keşfedildi . Markov, bağımsız rasgele dizilerin bir uzantısını incelemekle ilgilendi, bunun nedeni, zayıf büyük sayılar yasasının geçerli olması için bağımsızlığın gerekli olduğunu iddia eden Pavel Nekrasov ile bir anlaşmazlıktı . Markov zincirleri üzerine 1906'da yayınlanan ilk makalesinde Markov, belirli koşullar altında Markov zincirinin ortalama sonuçlarının sabit bir değer vektörüne yakınsayacağını gösterdi, böylece bağımsızlık varsayımı olmadan zayıf bir büyük sayılar kanunu kanıtladı. genellikle bu tür matematiksel yasaların geçerli olması için bir gereklilik olarak kabul edilir. Markov daha sonra Alexander Pushkin tarafından yazılan Eugene Onegin'deki sesli harflerin dağılımını incelemek için Markov zincirlerini kullandı ve bu tür zincirler için merkezi bir limit teoremi kanıtladı .

1912'de Henri Poincare , kart karıştırmayı incelemek amacıyla sonlu gruplar üzerinde Markov zincirleri üzerinde çalıştı . Markov zincirlerinin diğer erken kullanımları arasında 1907'de Paul ve Tatyana Ehrenfest tarafından tanıtılan bir difüzyon modeli ve Markov'un çalışmasından önce 1873'te Francis Galton ve Henry William Watson tarafından tanıtılan bir dallanma süreci yer alır . Galton ve Watson'ın çalışmasından sonra, daha sonra dallanma süreçlerinin bağımsız olarak keşfedildiği ve yaklaşık otuz yıl önce Irénée-Jules Bienaymé tarafından incelendiği ortaya çıktı . 1928'den itibaren Maurice Fréchet , Markov zincirleriyle ilgilenmeye başladı ve sonunda 1938'de Markov zincirleri hakkında ayrıntılı bir çalışma yayınlamasıyla sonuçlandı.

Andrei Kolmogorov , 1931 tarihli bir makalede, sürekli zamanlı Markov süreçlerinin erken teorisinin büyük bir bölümünü geliştirdi. Kolmogorov kısmen Louis Bachelier'in 1900'deki borsadaki dalgalanmalar üzerine çalışmasından ve Norbert Wiener'in Einstein'ın Brownian hareket modeli üzerine çalışmasından ilham aldı . Difüzyon süreçleri olarak bilinen belirli bir dizi Markov sürecini tanıttı ve inceledi ve burada süreçleri tanımlayan bir dizi diferansiyel denklem elde etti. Kolmogorov'un çalışmasından bağımsız olarak, Sydney Chapman , Brownian hareketini incelerken, 1928 tarihli bir makalesinde, şimdi Chapman-Kolmogorov denklemi olarak adlandırılan bir denklemi Kolmogorov'dan matematiksel olarak daha az titiz bir şekilde türetti. Diferansiyel denklemler artık Kolmogorov denklemleri veya Kolmogorov-Chapman denklemleri olarak adlandırılmaktadır. Markov süreçlerinin temellerine önemli ölçüde katkıda bulunan diğer matematikçiler arasında 1930'larda başlayan William Feller ve daha sonra 1950'lerde başlayan Eugene Dynkin bulunmaktadır .

Örnekler

Tamsayılara dayalı rastgele yürüyüşler ve kumarbazın mahvolması sorunu Markov süreçlerine örnektir. Bu süreçlerin bazı varyasyonları, yüzlerce yıl önce bağımsız değişkenler bağlamında incelenmiştir. Markov süreçlerinin iki önemli örneği , Brownian hareket süreci olarak da bilinen Wiener süreci ve stokastik süreçler teorisinde en önemli ve merkezi stokastik süreçler olarak kabul edilen Poisson sürecidir . Bu iki süreç, sürekli zamanda Markov süreçleridir, tamsayılar üzerinde rastgele yürüyüşler ve kumarbazın mahvolması problemi, ayrık zamanda Markov süreçlerine örnektir.

Ünlü bir Markov zinciri, sözde "sarhoşun yürüyüşü"dür, sayı doğrusu üzerinde rastgele bir yürüyüştür ve her adımda konumun eşit olasılıkla +1 veya -1 ile değişebildiği. Herhangi bir konumdan sonraki veya önceki tam sayıya iki olası geçiş vardır. Geçiş olasılıkları, pozisyona nasıl ulaşıldığına değil, sadece mevcut pozisyona bağlıdır. Örneğin, 5'ten 4'e ve 5'ten 6'ya geçiş olasılıklarının her ikisi de 0,5'tir ve 5'ten tüm diğer geçiş olasılıkları 0'dır. Bu olasılıklar, sistemin daha önce 4 veya 6'da olup olmamasından bağımsızdır.

Sadece üzüm, peynir ya da marulla beslenen ve beslenme alışkanlıkları aşağıdaki kurallara uygun bir canlının beslenme alışkanlıkları bir başka örnektir:

Markov-peynir-lettuce-grapes.svg
  • Günde tam olarak bir kez yiyor.
  • Bugün peynir yerse, yarın marul veya üzüm yeme olasılığı eşittir.
  • Bugün üzüm yerse yarın 1/10 olasılıkla üzüm, 4/10 olasılıkla peynir ve 5/10 olasılıkla marul yiyecektir.
  • Bugün marul yerse, yarın 4/10 olasılıkla üzüm veya 6/10 olasılıkla peynir yer. Yarın yine marul yemeyecek.

Bu yaratığın yeme alışkanlıkları bir Markov zinciri ile modellenebilir, çünkü yarınki seçimi dün ya da geçmişte ne yediğine değil, yalnızca bugün ne yediğine bağlıdır. Hesaplanabilecek bir istatistiksel özellik, yaratığın üzüm yiyeceği günlerin uzun bir süre boyunca beklenen yüzdesidir.

Bir dizi bağımsız olay (örneğin, bir dizi yazı tura), bir Markov zincirinin resmi tanımını karşılar. Bununla birlikte, teori genellikle yalnızca bir sonraki adımın olasılık dağılımı önemsiz olmayan bir şekilde mevcut duruma bağlı olduğunda uygulanır.

Markov olmayan bir örnek

Beş çeyrek (her biri 25¢ değerinde), beş onluk (her biri 10¢ değerinde) ve beş nikel (her biri 5¢ değerinde) içeren bir bozuk para cüzdanı olduğunu ve birer birer paraların keseden rastgele çekildiğini ve bir masaya koyun. Eğer sonra masaya yerleştirildiğinde paralar toplam değerini temsil eder , n ile çeker , daha sonra sırası olan olmayan Markov proses.

Durumun neden böyle olduğunu anlamak için, ilk altı çekilişte beş nikelin ve bir çeyreğin tamamının çekildiğini varsayalım. Böylece . Sadece değil, önceki değerleri de bilirsek, o zaman hangi paraların çekildiğini belirleyebiliriz ve bir sonraki madeni paranın bir nikel olmayacağını biliriz; yani bunu 1 olasılıkla belirleyebiliriz . Ama eğer daha önceki değerleri bilmiyorsak, o zaman sadece değere dayanarak dört kuruş ve iki nikel çektiğimizi tahmin edebiliriz, bu durumda kesinlikle başka bir nikel çekmek mümkün olurdu. sonraki. Bu nedenle, hakkındaki tahminlerimiz , değer öncesi bilgi birikimimizden etkilenir .

Ancak bu senaryoyu bir Markov süreci olarak modellemek mümkündür. Tablodaki madeni paraların toplam değerini temsil edecek şekilde tanımlamak yerine , tablodaki çeşitli madeni para türlerinin sayısını temsil edecek şekilde tanımlayabiliriz . Örneğin, 6 bire bir çekilişten sonra masada bir çeyrek, sıfır kuruş ve beş nikel olduğu durumu temsil etmek için tanımlanabilir. Bu yeni model 216 olası durumla temsil edilecektir (yani, üç jeton türünün her birinde 6 çekilişin sonunda masada sıfır ila beş jeton olabileceğinden, 6x6x6 durumları). İlk çekilişin durumla sonuçlandığını varsayalım . Şimdi elde etme olasılığı şunlara bağlıdır ; örneğin, devlet mümkün değildir. İkinci çekilişten sonra, üçüncü çekiliş şu ana kadar hangi madeni paraların çekildiğine bağlıdır, ancak artık yalnızca ilk durum için çekilen madeni paralara bağlı değildir (çünkü senaryoya muhtemel olarak önemli bilgiler eklenmiştir). Bu şekilde, devletin olasılığı yalnızca devletin sonucuna bağlıdır .

Resmi tanımlama

Ayrık zamanlı Markov zinciri

Ayrık zamanlı bir Markov zinciri, Markov özelliğine sahip X 1 , X 2 , X 3 , ... rasgele değişkenlerin bir dizisidir , yani bir sonraki duruma geçme olasılığı önceki duruma değil, yalnızca mevcut duruma bağlıdır. devletler:

her iki koşullu olasılık da iyi tanımlanmışsa, yani

Olası değerleri X i , bir formu sayılabilir grubu S zincirinin durum boşluğu olarak adlandırılır.

Varyasyonlar

  • Zaman-homojen Markov zincirleri süreçlerdir.
    Herkes için n . Geçişin olasılığı n'den bağımsızdır .
  • Durağan Markov zincirleri süreçlerdir.
    tüm n ve k için . Her durağan zincirin zaman-homojen olduğu Bayes kuralı ile kanıtlanabilir.
    Zamana homojen bir Markov zincirinin durağan olması için gerekli ve yeterli koşul, dağılımının Markov zincirinin durağan bir dağılımı olmasıdır.
  • m'nin sonlu olduğu hafızalı bir Markov zinciri (veya m mertebesinde bir Markov zinciri ) , tatmin edici bir süreçtir.
    Başka bir deyişle, gelecekteki durum geçmiş m durumlarına bağlıdır . Bir zincir oluşturmak mümkündür gelen düzenli durum alanı olarak alarak 'klasik' Markov özelliğine sahip,
    m arasında -tuples X , yani değerleri .

Sürekli zamanlı Markov zinciri

Sürekli-zamanlı bir Markov zinciri ( X t ) t  ≥ 0 , sonlu veya sayılabilir bir durum uzayı S , boyutları durum uzayına eşit olan bir geçiş oranı matrisi Q ve durum uzayında tanımlanan ilk olasılık dağılımı ile tanımlanır. İçin i  ≠  j , elemanlar q ij negatif olmayan ve durumundan işlem geçişleri oranını tanımlamak i durumu için j . q ii öğeleri , bir (ayrık) Markov zincirindeki bir olasılık geçiş matrisinin satır toplamlarının tümü bire eşitken, geçiş oranı matrisinin her satırının toplamı sıfır olacak şekilde seçilir.

Sürecin üç eşdeğer tanımı vardır.

sonsuz küçük tanım

Sürekli zamanlı Markov zinciri, geçiş oranları, i ve j durumları arasındaki geçiş olasılıklarının zamana göre türevleri ile karakterize edilir.

Izin süre içinde işleminin durumunu tanımlayan rasgele değişken olması t , ye işlem bir halde olduğu varsayılmaktadır i süre içinde t . O halde bilmek , önceki değerlerden bağımsızdır ve tüm j ve tüm t için h → 0 olarak ,

,

burada bir Kronecker'in ö kullanılarak küçük-o gösterimde . Geçiş ne kadar hızlı ölçüm olarak görülebilir i için j olur.

Atlama zinciri/tutma süresi tanımı

Bir ayrık zamanlı Markov zinciri tanımlar , Y , n açıklamak için , n değişkenleri işlemin inci atlama ve S 1 , S 2 , S 3 durumlarının her birinde tutma zamanlarına açıklamak için ..., S ı oranı ile üslü dağılımı aşağıdaki gibidir parametre - q Y ben Y ben .

Geçiş olasılığı tanımı

Herhangi bir değer için n = 0, 1, 2, 3, ... ve bu n değerine kadar indekslenen zamanlar : t 0 , t 1 , t 2 , ... ve bu zamanlarda kaydedilen tüm durumlar i 0 , i 1 , ben 2 , ben 3 , ... bu tutar

burada p ij çözeltisi olan ileri denklem (bir birinci dereceden diferansiyel denklem )

başlangıç ​​koşulu ile P(0) birim matrisidir .

sonlu durum uzayı

Durum uzayı sonlu ise, geçiş olasılık dağılımı , P'nin ( i , j )'inci elemanı şuna eşit olacak şekilde , geçiş matrisi adı verilen bir matris ile temsil edilebilir .

P'nin her satırı bire eşit olduğundan ve tüm elemanlar negatif olmadığından, P bir sağ stokastik matristir .

Özvektörler ve basitlerle durağan dağılım ilişkisi

Durağan bir dağılım π , girişleri negatif olmayan ve toplamı 1'e eşit olan bir (satır) vektörüdür, üzerindeki P geçiş matrisinin işlemiyle değişmez ve bu nedenle şu şekilde tanımlanır:

Bu tanımı bir özvektörünkiyle karşılaştırarak , iki kavramın birbiriyle ilişkili olduğunu ve

Normalize (olup , bir sol özvektörün) birden fazla e geçiş matris P , bir ile özdeğer birden fazla ünite özvektör daha sonra karşılık gelen sabit durumlarının ağırlıklı toplamı da sabit bir durumudur varsa 1. arasında. Ancak bir Markov zinciri için, genellikle bazı ilk dağılımlar için dağılım dizisinin sınırı olan durağan bir durumla daha fazla ilgilenilir.

Durağan bir dağılımın değerleri, P'nin durum uzayı ile ilişkilidir ve özvektörleri, göreceli oranları korunur. π'nin bileşenleri pozitif olduğundan ve toplamlarının birlik olduğu kısıtlaması yeniden yazılabilir, çünkü π'nin tüm bileşenleri 1 olan bir vektörle nokta çarpımının bir olduğunu ve π'nin bir simpleks üzerinde olduğunu görüyoruz .

Sonlu durum uzayına sahip zaman-homojen Markov zinciri

Markov zinciri zaman homojen ise, geçiş matrisi P , böylece her adımdan sonra aynı k -adımlı geçiş olasılığı aşağıdaki gibi hesaplanabilir: k geçiş matrisin inci güç, p k .

Markov zinciri indirgenemez ve periyodik olmayan ise, benzersiz bir durağan dağılım π vardır . Ek olarak, bu durumda P k , her satırın durağan dağılımı π olan bir birinci sıra matrisine yakınsar :

burada 1 , tüm girişleri 1'e eşit olan sütun vektörüdür. Bu, Perron–Frobenius teoremi tarafından belirtilir . Her ne şekilde olursa olsun bulunursa, aşağıda açıklanacağı gibi, söz konusu Markov zincirinin durağan dağılımı herhangi bir başlangıç ​​dağılımı için kolaylıkla belirlenebilir.

Bazı stokastik matrisler P için , bu örnekte gösterildiği gibi durağan dağılım varken sınır mevcut değildir:

(Bu örnek, periyodik bir Markov zincirini göstermektedir.)

Dikkate alınması gereken çok sayıda farklı özel durum olduğundan, varsa bu sınırı bulma süreci uzun bir iş olabilir. Ancak, bu sınırı bulmaya yardımcı olabilecek birçok teknik vardır. Let P bir olması , n x n matrisini ve tanımlamak

her zaman doğrudur

Çıkarma Q verimleri daha sonra her iki taraftan ve çarpanlara

burada I , n olan birim matris boyutu , n ve 0 n , n ise sıfır matrisi büyüklüğü n x n . Stokastik matrislerin çarpılması her zaman başka bir stokastik matris verir, bu nedenle Q bir stokastik matris olmalıdır (yukarıdaki tanıma bakın). Yukarıda matris denklemi ve aslında kullanımı bazen yeterli S çözmek için bir stokastik matris Q . Satır her toplamı olması da dahil olmak üzere P vardır, 1 , n + 1 belirlemek için denklem n hesaplama açısından daha kolay ise, bir yandan, bir seçer bir sıra çok bilinmeyenler, Q ve bir tarafından elemanların her biri ikame , ve diğerinde 0 vektöründeki karşılık gelen öğeyi (aynı sütundaki) değiştirir ve sonraki sol- bu ikinci vektörü dönüştürülmüş eski matrisin tersiyle çarparak Q'yu bulur .

İşte bunu yapmanın bir yöntemi: ilk önce, en sağdaki sütunu tüm 1'lerle değiştirilen A matrisini döndürmek için f ( A ) işlevini tanımlayın . [ f ( PI n )] -1 varsa, o zaman

Açıklayın: Orijinal matris denklemi, n×n değişkenli bir n×n doğrusal denklem sistemine eşdeğerdir . Ve Q'nun her satırının toplamı 1 olan bir doğru stokastik matris olduğu gerçeğinden n tane daha lineer denklem vardır . Dolayısıyla, n× için çözmek için (n×n+n) denklemlerinin herhangi bir n×n bağımsız lineer denklemine ihtiyaç duyar. n değişkenler. Bu örnekte, “Q çarpımının (P-In) en sağdaki sütunu”ndaki n denklemi, n adet stokastik denklemle değiştirilmiştir.

Önceden gereken bir şey varsa yani P bir eleman olan P i , i 1'e eşit olduğu bir ana köşegen ve i inci satır ve sütun aksi 0 ile 'doldurulmaktadır, sonra sıra veya sütun daha sonra tüm değişmeden kalır güçler P k . Dolayısıyla, I inci satır ve sütun Q ile aynı konumlarda 1 ve 0 olacaktır P .

Sabit dağılıma yakınsama hızı

Daha önce belirtildiği gibi, denklemden (varsa) durağan (veya kararlı durum) dağılımı π , satır stokastik matris P'nin bir sol özvektörüdür . Daha sonra, P'nin köşegenleştirilebilir olduğu veya eşdeğer olarak P'nin lineer olarak bağımsız n özvektöre sahip olduğu varsayılarak , yakınsama hızı aşağıdaki gibi detaylandırılır. (Non-köşegenleştirilebilir için, olduğu, kusurlu matrisler , bir başlayabilir Ürdün normal formda bir P ve benzer bir şekilde argümanlar biraz daha karmaşıktır dizi devam edin.

Let U her sütun bir sol özvektördür özvektörler matrisi (her biri 1'e eşit L2 normu olan normalize) olmak P ve izin Σ sol özdeğerler köşegen matris P olan, Σ (= diag λ 1 , λ 2 , λ 3 ,..., λ n ). Daha sonra özbileşim tarafından

Özdeğerler şu şekilde numaralandırılsın:

Yana P bir satır stokastik matristir konusu olduğu zaman özel bir sabit dağılımı, en büyük öz ve karşılık gelen bir özvektör (başka olduğu için çok özel ise, en büyük sol özdeğer 1'dir π üzerinde sabit dağıtım denklemi çözer). Let u ı olması ı arasında inci kolon U , bir matris, u ı sol özvektördür P X karşılık gelen i . Ayrıca x , geçerli bir olasılık dağılımını temsil eden bir uzunluk n satır vektörü olsun; özvektörler u i yaydığı için yazabiliriz

x'i sağdan P ile çarparsak ve bu işleme sonuçlarla devam edersek, sonunda durağan π dağılımını elde ederiz . Başka bir deyişle, π = u benxPP ... P = xP k as k → ∞. Bunun anlamı

Yana π = u 1 , π ( k ) yaklaşımlar TT olarak k sırasına göre bir hız ile ∞ iken → λ 2 / λ 1 katlanarak. Bunun nedeni, şu nedenle λ 2 / λ 1 baskın bir terimdir. Oran ne kadar küçük olursa, yakınsama o kadar hızlı olur. Durum dağılımındaki rastgele gürültü π aynı zamanda durağan dağılıma olan bu yakınsamayı da hızlandırabilir.

Genel durum uzayı

Harris zincirleri

Sonlu durum uzaylı Markov zincirleri için birçok sonuç Harris zincirleri aracılığıyla sayılamayan durum uzaylı zincirlere genelleştirilebilir .

Markov zinciri Monte Carlo yöntemlerinde Markov zincirlerinin kullanımı, sürecin sürekli bir durum uzayını takip ettiği durumları kapsar.

Yerel olarak etkileşen Markov zincirleri

Evrimi diğer Markov zincirlerinin durumunu dikkate alan bir Markov zincirleri koleksiyonunu ele almak, yerel olarak etkileşimli Markov zincirleri kavramıyla ilgilidir . Bu durum uzayının (Kartezyen-) bir çarpım formuna sahip olduğu duruma karşılık gelir. Bkz. etkileşimli parçacık sistemi ve stokastik hücresel otomatlar (olasılıksal hücresel otomatlar). Bakınız örneğin Markov Süreçlerinin Etkileşimi veya

Özellikler

İki durum, pozitif olasılığa sahip bir dizi geçişle birbirinden erişilebilirse, birbirleriyle iletişim kurar. Bu, bir dizi iletişim sınıfı veren bir denklik ilişkisidir. Sınıftan ayrılma olasılığı sıfır ise bir sınıf kapanır. Durum uzayı olan haberleşen bir sınıf varsa, bir Markov zinciri indirgenemez.

Bir durum i süreye sahip olmadığını olan büyük ortak böleni hangi geçişlerin sayısı ı başlayarak ulaşılabilir i . Yani:

Bir durum I söylenir, eğer geçici olabilir başlangıcı i , zincir geri asla sıfır olmayan bir ihtimali vardır i . Diğer türlü tekrarlanır. Tekrarlayan bir durum i için , ortalama vuruş süresi şu şekilde tanımlanır:

Devlet i ise pozitif tekrarlayan olduğunu sonlu ve aksi tekrarlamış BOŞ. Periyodiklik, geçicilik, yineleme ve pozitif ve boş yineleme sınıf özellikleridir - yani, bir durum bu özelliğe sahipse, iletişim sınıfındaki tüm durumlar bu özelliğe sahiptir.

Durumdan giden geçişler yoksa, i durumuna soğurucu denir.

ergodiklik

Bir durum i , periyodik olmayan ve pozitif tekrarlayan ise ergodik olduğu söylenir . Başka bir deyişle, bir i durumu , yineleniyorsa, 1 periyoduna sahipse ve sonlu ortalama yinelenme süresine sahipse ergodiktir. Eğer indirgenemez bir Markov zincirindeki tüm durumlar ergodik ise, o zaman zincirin ergodik olduğu söylenir.

Bir sonlu durum indirgenemez Markov zincirinin, eğer aperiyodik bir duruma sahipse ergodik olduğu gösterilebilir. Bir değer olup olmadığını Daha genel olarak, bir Markov zinciri ergodik olan N herhangi bir durum daha az adım, herhangi bir sayıda başka duruma ulaşılabilir ya da bir dizi eşit olabilir öyle ki , N . Tüm geçişlerin sıfırdan farklı bir olasılığa sahip olduğu tam bağlantılı bir geçiş matrisi durumunda, bu koşul  N  = 1 ile sağlanır.

Birden fazla durumu ve durum başına sadece bir giden geçişi olan bir Markov zinciri ya indirgenemez ya da periyodik değildir, dolayısıyla ergodik olamaz.

Markov temsilleri

Bazı durumlarda, görünüşte Markovyen olmayan süreçler, 'mevcut' ve 'gelecek' durumları kavramını genişleterek inşa edilen Markovyen temsillere sahip olabilir. Örneğin, X Markovyen olmayan bir süreç olsun. Ardından , Y'nin her durumu , X'in durumlarının bir zaman aralığını temsil edecek şekilde bir Y süreci tanımlayın . Matematiksel olarak, bu şu şekli alır:

Eğer Y Markov özelliğine sahiptir, o zaman bir Markov temsilidir X .

Markovyen temsili olan Markovyen olmayan bir sürece bir örnek, birden büyük düzenin otoregresif bir zaman serisidir .

vuruş süreleri

Vuruş süresi, zincir belirli bir duruma veya durumlar kümesine ulaşana kadar belirli bir durum kümesinde başlayan zamandır. Böyle bir zaman periyodunun dağılımı, bir faz tipi dağılımına sahiptir. Bu tür en basit dağılım, üstel olarak dağıtılmış tek bir geçiştir.

Beklenen vuruş süreleri

A  ⊆  S durumlarının bir alt kümesi için , çarpma sürelerinin k A vektörü (burada öğe , zincirin A kümesindeki durumlardan birine girdiği i durumundan başlayarak , beklenen değeri temsil eder )

Zamanın tersine çevrilmesi

Bir CTMC X t için , zamanı tersine çevrilmiş süreç olarak tanımlanır . By Kelly'nin lemmasının bu süreç ileri süreç olarak aynı durağan dağılıma sahiptir.

Tersine çevrilen süreç ileri süreçle aynıysa, bir zincirin tersine çevrilebilir olduğu söylenir. Kolmogorov'un kriteri , bir sürecin tersinir olması için gerekli ve yeterli koşulun, kapalı bir döngü etrafındaki geçiş oranlarının çarpımının her iki yönde de aynı olması gerektiğini belirtir.

Gömülü Markov zinciri

Bulmak için bir yöntem, sabit olasılık dağılımını , π bir bölgesinin ergodik sürekli zaman Markov zinciri, Q , ilk bulgu onun tarafından gömülü Markov zincir (EMC) . Açıkça söylemek gerekirse, EMC, bazen atlama işlemi olarak adlandırılan düzenli bir ayrık zamanlı Markov zinciridir . EMC'nin tek adımlı geçiş olasılığı matrisinin her bir öğesi, S , s ij ile gösterilir ve i durumundan j durumuna geçişin koşullu olasılığını temsil eder . Bu koşullu olasılıklar şu şekilde bulunabilir:

Bundan, S şu şekilde yazılabilir:

burada I olan birim matris tanılama ( S ) 'dir diyagonal matris seçerek oluşan ana çapını matrisi Q ve sıfıra diğer ayar elemanları.

Sabit olasılık dağılımı vektör bulmak için, sonraki bulmalıyız şekilde

ile bir sıra vektörü olarak, tüm elemanlar olarak bu şekilde daha büyük 0 ve vardır , bu kaynaktan = 1, π olarak bulunabilir

( Q periyodik olmasa bile S periyodik olabilir . π bulunduğunda, bir birim vektöre normalize edilmelidir .)

Sürekli-zamanlı bir Markov zincirinden türetilebilecek bir başka ayrık-zamanlı süreç, bir δ-iskeletidir - X ( t ) δ zaman aralıklarında gözlemlenerek oluşturulan (ayrık-zamanlı) Markov zinciri . Rastgele değişkenler X (0),  X (δ),  X (2δ), ..., δ-iskeleti tarafından ziyaret edilen durumların sırasını verir.

Markov zincirlerinin özel türleri

Markov modeli

Markov modelleri, değişen sistemleri modellemek için kullanılır. Markov zincirlerini her ardışık durumun gözlemlenebilir olup olmamasına ve sistemin yapılan gözlemlere göre ayarlanıp ayarlanmayacağına bağlı olarak genelleştiren 4 ana model türü vardır:

Sistem durumu tamamen gözlemlenebilir Sistem durumu kısmen gözlemlenebilir
Sistem özerk Markov zinciri Gizli Markov modeli
Sistem kontrol ediliyor Markov karar süreci Kısmen gözlemlenebilir Markov karar süreci

Bernoulli şeması

Bir Bernoulli şeması , geçiş olasılığı matrisinin aynı satırlara sahip olduğu bir Markov zincirinin özel bir durumudur; bu, bir sonraki durumun mevcut durumdan bile bağımsız olduğu anlamına gelir (geçmiş durumlardan bağımsız olmasının yanı sıra). Yalnızca iki olası durumu olan bir Bernoulli şeması, Bernoulli süreci olarak bilinir .

Bununla birlikte, Ornstein izomorfizm teoremi ile her aperiyodik ve indirgenemez Markov zincirinin bir Bernoulli şemasına göre izomorf olduğuna dikkat edin; bu nedenle, Markov zincirlerinin Bernoulli şemalarının "özel bir durumu" olduğu da aynı şekilde iddia edilebilir. İzomorfizm genellikle karmaşık bir yeniden kodlama gerektirir. İzomorfizm teoremi biraz daha güçlüdür: herhangi bir durağan stokastik sürecin bir Bernoulli şemasına göre izomorf olduğunu belirtir ; Markov zinciri böyle bir örnektir.

Sonlu tipte alt vardiya

Markov matrisi, sonlu bir grafiğin komşuluk matrisi ile değiştirildiğinde, ortaya çıkan kayma, bir topolojik Markov zinciri veya sonlu tipte bir alt kaydırma terimidir . Bitişiklik matrisi ile uyumlu bir Markov matrisi daha sonra alt kaydırma üzerinde bir ölçü sağlayabilir . Birçok kaotik dinamik sistem , topolojik Markov zincirlerine eş biçimlidir; örnekleri arasında diffeomorphisms arasında kapalı manifoldlar , Prouhet-Thue-Morse sistemi , Chacon sistemi , Sofic sistemleri , bağlam içermeyen sistemler ve blok kodlama sistemleri .

Uygulamalar

Araştırmalar, Markov zincirlerinin fizik, kimya, biyoloji, tıp, müzik, oyun teorisi ve spor gibi çok çeşitli konularda uygulama ve yararlılığını bildirmiştir.

Fizik

Markov sistemleri termodinamikte ve istatistiksel mekanikte , sistemin bilinmeyen veya modellenmemiş ayrıntılarını temsil etmek için olasılıklar kullanıldığında, dinamiklerin zamanla değişmediği varsayılabilirse ve halihazırda dahil edilmeyen ilgili hiçbir geçmişin dikkate alınmasına gerek olmadığında yaygın olarak görünür. devlet açıklamasında. Örneğin, bir termodinamik durum, elde edilmesi zor veya pahalı olan bir olasılık dağılımı altında çalışır. Bu nedenle, Markov Zinciri Monte Carlo yöntemi, bir dizi nesne üzerindeki niteliklerin olasılık dağılımını yaklaşık olarak tahmin etmek için bir kara kutudan rastgele örnekler çekmek için kullanılabilir.

Kuantum mekaniğinin yol integral formülasyonundaki yollar Markov zincirleridir.

Kafes QCD simülasyonlarında Markov zincirleri kullanılır .

Kimya

Michaelis-Menten kinetiği . Enzim (E) bir substratı (S) bağlar ve bir ürün (P) üretir. Her reaksiyon bir Markov zincirinde bir durum geçişidir.

Bir reaksiyon ağı, çoklu reaksiyonları ve kimyasal türleri içeren bir kimyasal sistemdir. Bu tür ağların en basit stokastik modelleri, sistemi, her türün molekül sayısı olan ve zincirin olası geçişleri olarak modellenen reaksiyonlarla birlikte sürekli bir zaman Markov zinciri olarak ele alır. Markov zincirleri ve sürekli zamanlı Markov süreçleri, fiziksel sistemler Markov özelliğine çok yakın olduğunda kimyada faydalıdır. Örneğin, A durumundaki çözeltide, her biri belirli bir ortalama hızla B durumuna kimyasal reaksiyona girebilen çok sayıda n molekül düşünün . Belki molekül bir enzimdir ve durumlar nasıl katlandığına atıfta bulunur. Herhangi bir tek enzimin durumu bir Markov zincirini takip eder ve moleküller esasen birbirinden bağımsız olduğundan, bir anda A veya B durumundaki moleküllerin sayısı, belirli bir molekülün o durumda olma olasılığının n katıdır.

Enzim aktivitesinin klasik modeli, Michaelis-Menten kinetiği , her zaman adımında reaksiyonun bir yönde ilerlediği bir Markov zinciri olarak görülebilir. Michaelis-Menten oldukça basit olsa da, çok daha karmaşık reaksiyon ağları Markov zincirleriyle modellenebilir.

Bir Markov zincirine dayanan bir algoritma, kimyasalların silico'daki parça bazlı büyümesini ilaçlar veya doğal ürünler gibi istenen bir bileşik sınıfına odaklamak için de kullanıldı . Bir molekül büyüdükçe, "mevcut" durum olarak ortaya çıkan molekülden bir parça seçilir. Geçmişinin farkında değildir (yani, kendisine zaten bağlı olanın farkında değildir). Daha sonra, kendisine bir parça eklendiğinde bir sonraki duruma geçer. Geçiş olasılıkları, otantik bileşik sınıflarının veri tabanları üzerinde eğitilir.

Ayrıca kopolimerlerin büyümesi (ve bileşimi) Markov zincirleri kullanılarak modellenebilir. Büyüyen polimer zincirini oluşturan monomerlerin reaktivite oranlarına dayanarak, zincirin bileşimi hesaplanabilir (örneğin, monomerlerin dönüşümlü bir şekilde mi yoksa aynı monomerin uzun serilerinde mi eklenme eğiliminde olduğu). Sterik etkiler nedeniyle , ikinci derece Markov etkileri de bazı polimer zincirlerinin büyümesinde rol oynayabilir.

Benzer şekilde, bazı epitaksiyel üst örgü oksit malzemelerinin kristalleşmesinin ve büyümesinin Markov zincirleri tarafından doğru bir şekilde tanımlanabileceği öne sürülmüştür .

Biyoloji

Markov zincirleri biyolojinin çeşitli alanlarında kullanılmaktadır. Önemli örnekler şunları içerir:

Test yapmak

Birkaç teorisyen, bir " Markov battaniyesi " oluşturmak için Markov zincirlerini birleştirme , bu zincirleri birkaç özyinelemeli katmanda ("wafering") düzenleme ve daha verimli test setleri üretme yöntemi olan Markov zinciri istatistiksel testi (MCST) fikrini önerdi. - kapsamlı testlerin yerine geçer. MCST'lerin geçici durum tabanlı ağlarda da kullanımları vardır; Chilukuri ve diğerlerinin "Nesne Algılama ve İzleme Uygulamaları ile Kanıt Füzyonu için Geçici Belirsizlik Akıl Yürütme Ağları" (ScienceDirect) başlıklı makalesi, MCST'leri daha geniş bir uygulama yelpazesine uygulamak için bir arka plan ve vaka çalışması sunar.

Güneş ışınımı değişkenliği

Güneş ışınımı değişkenlik değerlendirmeleri, güneş enerjisi uygulamaları için faydalıdır . Zaman içinde herhangi bir konumdaki güneş ışınımı değişkenliği, esas olarak güneşin gökyüzü kubbesi boyunca izlediği yolun belirleyici değişkenliğinin ve bulutluluktaki değişkenliğin bir sonucudur. Dünya yüzeyindeki erişilebilir güneş ışınımının değişkenliği, Markov zincirleri kullanılarak modellenmiştir, ayrıca iki durumlu bir Markov zinciri olarak iki açık ve bulutluluk durumunun modellenmesi de dahildir.

Konuşma tanıma

Gizli Markov modelleri , çoğu modern otomatik konuşma tanıma sisteminin temelidir .

bilgi teorisi

Markov zincirleri bilgi işleme boyunca kullanılır. Claude Shannon'un tek bir adımda bilgi teorisi alanını yaratan ünlü 1948 tarihli A Mathematical Theory of Communication adlı makalesi , İngiliz dilinin Markov modellemesi aracılığıyla entropi kavramını tanıtarak açılıyor . Bu tür idealize edilmiş modeller, sistemlerin istatistiksel düzenliliklerinin çoğunu yakalayabilir. Sistemin tam yapısını mükemmel bir şekilde tanımlamadan bile, bu tür sinyal modelleri, aritmetik kodlama gibi entropi kodlama teknikleri aracılığıyla çok etkili veri sıkıştırmayı mümkün kılabilir . Ayrıca etkili durum tahmini ve örüntü tanımaya da izin verirler . Markov zincirleri de pekiştirmeli öğrenmede önemli bir rol oynar .

Markov zincirleri, telefon ağları ( hata düzeltme için Viterbi algoritmasını kullanan ), konuşma tanıma ve biyoinformatik (yeniden düzenleme tespiti gibi ) gibi çeşitli alanlarda önemli bir araç olan gizli Markov modellerinin de temelidir .

Lzma kayıpsız veri sıkıştırma algoritması ile Markov zincirlerini bir arada Lempel-Ziv sıkıştırma çok yüksek sıkıştırma oranlarına ulaşmak için.

kuyruk teorisi

Markov zincirleri, kuyrukların analitik olarak ele alınmasının temelidir ( kuyruk teorisi ). Agner Krarup Erlang konuyu 1917'de başlattı. Bu, mesajların genellikle sınırlı kaynaklar (bant genişliği gibi) için rekabet etmesi gereken telekomünikasyon ağlarının performansını optimize etmede onları kritik hale getiriyor.

Çok sayıda kuyruk modeli, sürekli zamanlı Markov zincirlerini kullanır. Örneğin, bir M / M / 1 sıra yukarı doğru geçişler negatif olmayan tam bir CTMC olan i için i  + 1 oranında meydana λ bir uygun Poisson sürecine geçişleri ise gelen ve iş varış tarif i için i  - 1 ( i  > 1 için) μ oranında meydana gelir (iş hizmet süreleri katlanarak dağıtılır) ve kuyruktan tamamlanan hizmetleri (kalkışlar) tanımlar.

İnternet uygulamaları

PageRank algoritmasını M, veya geçiş olasılığı ile temsil eden bir durum diyagramı .

PageRank tarafından kullanılan bir web sayfasının Google bir Markov zinciri tarafından tanımlanır. Tüm (bilinen) web sayfalarında aşağıdaki Markov zincirinde durağan dağılımda sayfada olma olasılığıdır . Eğer bilinen web sayfalarının sayısı ve sayfa vardır buna bağlantıları o zaman geçiş olasılığa sahiptir ve bağlı tüm sayfalar için sıkı bağlantısı olmayan tüm sayfalar için. Parametre yaklaşık 0.15 olarak alınmıştır.

Markov modelleri, kullanıcıların web gezinme davranışlarını analiz etmek için de kullanılmıştır. Belirli bir web sitesinde bir kullanıcının web bağlantısı geçişi, birinci veya ikinci dereceden Markov modelleri kullanılarak modellenebilir ve gelecekteki gezinme ile ilgili tahminlerde bulunmak ve web sayfasını bireysel bir kullanıcı için kişiselleştirmek için kullanılabilir.

İstatistik

Markov zinciri yöntemleri, Markov zinciri Monte Carlo (MCMC) adı verilen bir süreç aracılığıyla, çok karmaşık istenen olasılık dağılımlarını doğru bir şekilde yansıtmak için rasgele sayı dizileri üretmek için de çok önemli hale geldi. Son yıllarda bu, Bayesian çıkarım yöntemlerinin uygulanabilirliğinde devrim yaratmış, çok çeşitli sonsal dağılımların simüle edilmesine ve parametrelerinin sayısal olarak bulunmasına izin vermiştir.

Ekonomi ve finans

Markov zincirleri, finans ve ekonomide, gelir dağılımı, firmaların büyüklük dağılımı, varlık fiyatları ve piyasa çöküşleri dahil olmak üzere çeşitli farklı fenomenleri modellemek için kullanılır. DG Champernowne , 1953'te gelir dağılımının bir Markov zinciri modeli oluşturdu. Herbert A. Simon ve ortak yazar Charles Bonini, firma büyüklüklerinin durağan bir Yule dağılımını türetmek için bir Markov zincir modeli kullandı. Louis Bachelier , hisse senedi fiyatlarının rastgele bir yürüyüş izlediğini ilk gözlemleyen kişi oldu. Rastgele yürüyüş daha sonra etkin piyasa hipotezinin lehine bir kanıt olarak görüldü ve rastgele yürüyüş modelleri 1960'ların literatüründe popülerdi. İş çevrimlerinin rejim değiştiren modelleri, yüksek ve düşük GSYİH büyümesi (veya alternatif olarak ekonomik genişlemeler ve durgunluklar) arasındaki geçişleri modellemek için bir Markov zinciri kullanan James D. Hamilton (1989) tarafından popülerleştirildi . Daha yeni bir örnek, Laurent E. Calvet ve Adlai J. Fisher'ın Markov anahtarlamalı multifraktal modelidir , bu model daha önceki rejim değiştirme modellerinin rahatlığına dayanmaktadır. Varlık getirilerinin oynaklık düzeyini yönlendirmek için keyfi olarak büyük bir Markov zinciri kullanır.

Dinamik makroekonomi, Markov zincirlerini yoğun olarak kullanır. Bir örnek, genel bir denge ortamında öz sermaye (hisse senedi) fiyatlarını dışsal olarak modellemek için Markov zincirlerini kullanmaktır .

Kredi derecelendirme kuruluşları , farklı kredi notlarına sahip tahviller için geçiş olasılıklarının yıllık tablolarını üretir.

Sosyal Bilimler

Markov zincirleri genellikle , mevcut yapısal konfigürasyonların gelecekteki sonuçları koşullandırdığı yola bağlı argümanları tanımlamak için kullanılır . Bir örnek başlangıçta nedeniyle fikrinin yeniden formüle edilmiş halidir Karl Marx 'ın Das Kapital bağlama, ekonomik gelişme yükselişi için kapitalizm . Mevcut araştırmalarda, bir ülkenin belirli bir ekonomik kalkınma düzeyine bir kez nasıl ulaştığını, orta sınıfın büyüklüğü , kentsel yerleşimin kırsal yerleşime oranı gibi yapısal faktörlerin konfigürasyonunu modellemek için bir Markov zinciri kullanmak yaygındır. bir siyasi seferberlik vb geçiş olasılığının daha yüksek üretecektir otoriter için demokratik rejime .

Oyunlar

Markov zincirleri birçok şans oyununu modellemek için kullanılabilir. Örneğin, çocuk oyunları Snakes and Ladders ve " Hi Ho! Cherry-O " tam olarak Markov zincirleriyle temsil edilmektedir. Her turda, oyuncu belirli bir durumda (belirli bir karede) başlar ve oradan belirli diğer durumlara (kareler) hareket etme olasılığı sabittir.

Müzik

Markov zincirleri algoritmik müzik kompozisyonunda , özellikle Csound , Max ve SuperCollider gibi yazılımlarda kullanılır . Birinci dereceden bir zincirde, sistemin durumları nota veya perde değerleri haline gelir ve her nota için bir olasılık vektörü oluşturulur ve bir geçiş olasılık matrisi tamamlanır (aşağıya bakınız). MIDI nota değerleri, frekans ( Hz ) veya diğer herhangi bir istenen metrik olabilen geçiş matrisi ağırlıklarına dayalı olarak çıktı nota değerleri üretmek için bir algoritma oluşturulur .

1. dereceden matris
Not A C E
A 0.1 0.6 0,3
C 0.25 0.05 0.7
E 0.7 0,3 0
2. dereceden matris
Notlar A NS G
AA 0.18 0.6 0.22
AD 0,5 0,5 0
AG 0.15 0.75 0.1
DD 0 0 1
DA 0.25 0 0.75
Genel Müdürlük 0.9 0.1 0
İyi oyun 0,4 0,4 0,2
GA 0,5 0.25 0.25
GD 1 0 0

İkinci dereceden bir Markov zinciri , ikinci tabloda belirtildiği gibi , mevcut durum ve ayrıca önceki durum dikkate alınarak tanıtılabilir . Daha yüksek, n, zaman zaman diğer desenler ve dizileri içine 'kopma' ise inci dereceden zincirleri, hep birlikte "grubu", özellikle notlar eğilimindedir. Bu üst düzey zincirler , birinci dereceden bir sistem tarafından üretilen 'amaçsız gezinme' yerine , bir cümle yapısı duygusuyla sonuçlar üretme eğilimindedir .

Markov zincirleri, Xenakis'in Analogique A ve B'de olduğu gibi yapısal olarak kullanılabilir. Markov zincirleri, müzik girdisine etkileşimli olarak tepki vermek için bir Markov modeli kullanan sistemlerde de kullanılır.

Genellikle müzik sistemlerinin ürettikleri sonlu uzunluktaki diziler üzerinde belirli kontrol kısıtlamaları zorlaması gerekir, ancak kontrol kısıtlamaları Markov modelleriyle uyumlu değildir, çünkü bunlar Markov'un sınırlı hafıza hipotezini ihlal eden uzun menzilli bağımlılıkları indükler. Bu sınırlamanın üstesinden gelmek için yeni bir yaklaşım önerilmiştir.

Beyzbol

Markov zincir modelleri, 1960'dan beri gelişmiş beyzbol analizlerinde kullanılmaktadır, ancak kullanımları hala nadirdir. Bir beyzbol oyununun her yarım vuruşu, koşucu ve çıkış sayısı dikkate alındığında Markov zincir durumuna uyar. Herhangi bir at-bat sırasında, 24 olası çıkış sayısı ve koşucuların konumu kombinasyonu vardır. Mark Pankin, Markov zincir modellerinin hem bireysel oyuncular hem de bir takım için oluşturulan koşuları değerlendirmek için kullanılabileceğini gösteriyor. Ayrıca çeşitli stratejiler ve oyun koşulları hakkında da tartışıyor: Markov zincir modellerinin, kiraz kuşu ve taban çalma gibi oyun durumlarının istatistiklerini analiz etmek için nasıl kullanıldığını ve çimde ve AstroTurf'te oynarken farklılıklar .

Markov metin üreteçleri

Markov süreçleri, örnek bir belge verilen yüzeysel olarak gerçek görünümlü metin oluşturmak için de kullanılabilir . Markov süreçleri eğlence "çeşitli kullanılan parodi jeneratör " yazılım (bkz ayrışmış basın Jeff Harrison, Mark V. Shaney ve Academias Nötronyum ). RiTa Toolkit dahil olmak üzere Markov zincirlerini kullanan çeşitli açık kaynaklı metin oluşturma kitaplıkları mevcuttur .

Olasılıksal tahmin

Markov zincirleri, çeşitli alanlarda tahmin yapmak için kullanılmıştır: örneğin, fiyat trendleri, rüzgar enerjisi ve güneş ışınımı. Markov zinciri tahmin modelleri, zaman serilerinin ayrıklaştırılmasından, dalgacıklarla birleştirilmiş gizli Markov modellerine ve Markov zincir karışım dağıtım modeline (MCM) kadar çeşitli ayarları kullanır.

Ayrıca bakınız

Notlar

Referanslar

  • AA Markov (1906) "Rasprostranenie zakona bol'shih keski ve velichiny, zavisyaschie uyuşturucu ve uyuşturucu". İzvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete , 2-ya seriya, tom 15, s. 135–156.
  • AA Markov (1971). "Olasılık teorisinin limit teoremlerinin bir zincire bağlı değişkenlerin toplamına genişletilmesi". Ek B'de yeniden basılmıştır: R. Howard. Dinamik Olasılık Sistemleri, cilt 1: Markov Zincirleri . John Wiley ve Oğulları.
  • Çeviride Klasik Metin: Markov, AA (2006). Bağlantı, David tarafından çevrildi. "Zincirlerdeki Örneklerin Bağlantısına İlişkin Metin Eugene Onegin'in İstatistiksel Araştırma Örneği" . Bağlamda Bilim . 19 (4): 591–600. doi : 10.1017/s0269889706001074 . S2CID  144854176 .
  • Leo Breiman (1992) [1968] Olasılık . Addison-Wesley tarafından yayınlanan orijinal baskı; Society for Industrial and Applied Mathematics ISBN  0-89871-296-3 tarafından yeniden basılmıştır . (Bkz. Bölüm 7)
  • JL Doob (1953) Stokastik Süreçler . New York: John Wiley ve Oğulları ISBN  0-471-52369-0 .
  • SP Meyn ve RL Tweedie (1993) Markov Zincirleri ve Stokastik Kararlılık . Londra: Springer-Verlag ISBN  0-387-19832-6 . çevrimiçi: MCSS . İkinci baskı, Cambridge University Press, 2009.
  • SP Meyn. Karmaşık Ağlar İçin Kontrol Teknikleri . Cambridge University Press, 2007. ISBN  978-0-521-88441-9 . Ek, kısaltılmış Meyn & Tweedie'yi içerir. çevrimiçi: [1]
  • Booth, Taylor L. (1967). Sıralı Makineler ve Otomatlar Teorisi (1. baskı). New York, NY: John Wiley and Sons, Inc. Library of Congress Card Katalog Numarası 67-25924.] Hem teorik bilgisayar bilimcileri hem de elektrik mühendisleri için yazılmış, uzmanlara yönelik kapsamlı, geniş kapsamlı kitap. Durum minimizasyon teknikleri, FSM'ler, Turing makineleri, Markov süreçleri ve karar verilemezliğin ayrıntılı açıklamaları ile. Markov süreçlerinin mükemmel işlenmesi s. 449ff. Z-dönüşümlerini, D dönüşümlerini kendi bağlamlarında tartışır.
  • Kemeny, John G.; Hazleton Mirkil; J. Laurie Snell; Gerald L. Thompson (1959). Sonlu Matematiksel Yapılar (1. baskı). Englewood Cliffs, NJ: Prentice-Hall, Inc. Kongre Kartı Katalog Numarası 59-12841 Kütüphanesi.Klasik metin. bkz. Bölüm 6 Sonlu Markov Zincirleri, s. 384ff.
  • John G. Kemeny ve J. Laurie Snell (1960) Sonlu Markov Zincirleri , D. van Nostrand Company ISBN  0-442-04328-7
  • E. Nummelin. "Genel indirgenemez Markov zincirleri ve negatif olmayan operatörler". Cambridge University Press, 1984, 2004. ISBN  0-521-60494-X
  • Seneta, E. Negatif olmayan matrisler ve Markov zincirleri . 2. devir ed., 1981, XVI, 288 s., İstatistikte Softcover Springer Serisi. (İlk olarak Allen & Unwin Ltd. tarafından yayınlanmıştır, Londra, 1973) ISBN  978-0-387-29765-1
  • Kishor S. Trivedi , Güvenilirlik, Kuyruklama ve Bilgisayar Bilimi Uygulamaları ile Olasılık ve İstatistik , John Wiley & Sons, Inc. New York, 2002. ISBN  0-471-33341-7 .
  • KS Trivedi ve RASahner, SHARPE yirmi iki yaşında , cilt. 36, hayır. 4, s. 52–57, ACM SIGMETRICS Performans Değerlendirme İncelemesi, 2009.
  • RA Sahner, KS Trivedi ve A. Puliafito, Bilgisayar sistemlerinin performans ve güvenilirlik analizi: SHARPE yazılım paketini kullanan örnek tabanlı bir yaklaşım , Kluwer Academic Publishers, 1996. ISBN  0-7923-9650-2 .
  • G. Bolch, S. Greiner, H. de Meer ve KS Trivedi, Kuyruk Ağları ve Markov Zincirleri , John Wiley, 2. baskı, 2006. ISBN  978-0-7923-9650-5 .

Dış bağlantılar