Ayrık Zamanlı Markov Zincirleri
Ayrık zamanlı bir Markov zinciri, sayılabilir bir durum kümesi arasında tam sayı zamanlarında hareket eder ve bir sonraki durumunu yalnızca mevcut duruma bağlı olan olasılıklardan seçer; bu olasılıklar bir geçiş matrisinde yoğun bir şekilde kodlanmıştır.
Tanım
Ayrık zamanlı bir Markov zinciri, sayılabilir bir kümedeki rastgele durumların bir dizisidir; öyle ki bir sonraki durumun olasılığı yalnızca mevcut duruma bağlıdır ve bu tek adımlı olasılıklar bir geçiş matrisinde toplanmıştır.
Kapsam
Bu konu, geçiş matrislerini ve Chapman-Kolmogorov denklemlerini, güçlü Markov özelliğini, durumların iletişim sınıflarına ve geçici (transient), sıfır-tekrarlayan (null-recurrent) ve pozitif-tekrarlayan (positive-recurrent) olarak sınıflandırılmasını, periyodikliği, ilk adım analiziyle hesaplanan isabet olasılıklarını ve beklenen isabet sürelerini ve tam sayı kafesindeki rastgele yürüyüşler için tekrarlama ikiliğini kapsamaktadır.
Temel sorular
- Bir geçiş matrisi, bir zincirin birçok adım üzerindeki dinamiklerini nasıl kodlar?
- Durumlar, iletişim yapılarına ve tekrarlamalarına göre nasıl sınıflandırılır?
- İsabet olasılıkları ve beklenen isabet süreleri nasıl hesaplanır?
- Hangi rastgele yürüyüşler başlangıç noktalarına kesinlikle döner ve hangileri sonsuzluğa kaçar?
Anahtar kavramlar
- geçiş matrisi
- Chapman-Kolmogorov denklemleri
- iletişim sınıfları
- tekrarlama ve geçicilik
- isabet süreleri
Temel kuramlar
- Güçlü Markov özelliği
- Markov özelliği, durma zamanları olarak adlandırılan uygun rastgele zamanlarda geçerliliğini korumaktadır; bu nedenle bir zincir, bu tür bir zamanda bulunduğu durumdan yeniden başlamaktadır ve bu, dönüşleri, sapmaları ve isabet sürelerini analiz etmek için anahtar bir araçtır.
- Tekrarlama ikiliği
- Her durum ya tekrarlayıcıdır (sonsuz kez ziyaret edilme olasılığı bir olan) ya da geçicidir (yalnızca sonlu sayıda ziyaret edilen); basit simetrik rastgele yürüyüş için bu, boyuta bağlıdır; bir ve iki boyutta tekrarlama, üç ve daha yüksek boyutlarda ise geçicilik görülmektedir.
Klinik önem
Ayrık zamanlı Markov zincirleri, masa oyunlarını, envanter ve kuyruk sistemlerini, PageRank zinciri aracılığıyla web navigasyonunu ve genetik ve ekolojik süksesyonu modellemektedir; isabet süresi ve tekrarlama kuramları, bir sistemin hedef duruma ulaşmasının veya referans bir duruma dönmesinin ne kadar süreceği hakkında pratik soruları yanıtlamaktadır.
Tarihçe
Markov, bu zincirleri 1906'da tanıtmış ve bağımlı değişkenler için büyük sayılar yasasının geçerli olduğunu göstermek amacıyla bunları bir Puşkin şiirindeki sesli ve sessiz harf dizisine uygulamıştır. Polya'nın 1921'deki rastgele yürüyüşler analizi, onun etkisini taşıyan boyuta bağlı tekrarlama ikiliğini ortaya koymuştur.
Öne çıkan isimler
- Andrey Markov
- George Polya
- Joseph L. Doob
İlgili konular
Temel eserler
- norris1997
Sıkça sorulan sorular
- Tekrarlayıcı bir durum ile geçici bir durum arasındaki fark nedir?
- Tekrarlayıcı bir durum, zincirin kesinlikle geri döneceği ve dolayısıyla sonsuz kez ziyaret edeceği bir durumken, geçici bir durum, zincir tamamen uzaklaşmadan önce yalnızca sonlu sayıda ziyaret edilen bir durumdur.
- Basit rastgele yürüyüş neden düşük boyutlarda tekrarlayıcıyken yüksek boyutlarda değildir?
- Bir ve iki boyutta yürüyüş, başlangıç noktasına bir olasılıkla geri dönmektedir, ancak üç boyuttan itibaren kaçmak için yeterli alan bulunduğundan, yürüyüş yalnızca sonlu sayıda geri döner ve geçicidir; bu, Polya'nın klasik sonucudur.