On the numerical analysis of infinite multi-dimensional Markov chains

Birden fazla alt sistemden oluşan ve Markov özelliğine sahip bir sistemi çok boyutlu bir Markov zinciri olarak göstermek mümkündür. Bu Markov zincirinin ulaşılabilir durum uzayı, genellikle çarpım durum uzayının bir öz alt kümesidir. Böyle bir Markov zincirine karşı gelen matrisin sıkıştırılmış olarak saklanması ve Kronecker işlemlerin etkili bir şekilde gerçekleştirilebilmesi, ulaşılabilir durum uzayının alt sistem durum uzaylarının alt kümelerinin Kartezyen çarpımlarının birleşimi olarak yazılmasını gerektirir. Bu çalışmada ilk olarak, üç veya daha fazla boyutlu bir sistemin ulaşılabilir durum uzayının en az sayıda alt sistem durum uzaylarının alt kümelerinin Kartezyen çarpımlarına bölümleme probleminin, NP-tam bir problem olduğunu gösteriyoruz. Bu problemi çözmek için, eniyi çözümü bulması kesin olmayan, biri birleştirme ve diğeri geliştirme temelli olmak üzere iki algoritma öneriyoruz. Literatürde yer alan ve rasgele olarak oluşturulmuş örneklerle yaptığımız deneyler, geliştirme temelli algoritmanın daha çok zaman ve bellek gerektirdiğini, ancak neredeyse her zaman daha az sayıda bölümleme bulabildiğini gösteriyor. Markov zincirine karşılık gelen matris, Kronecker çarpımları kullanılarak sıkıştırılmış olarak gösterildiğinde, çözümleme yöntemleri vektör-Kronecker terim çarpımının üzerine bina edilir. Kronecker terimlerdeki çarpan matrisler yoğun olduğunda, karma algoritması vektör-Kronecker terim çarpımını etkili bir şekilde hesaplayabilir. çarpan matrisler seyrek olduğunda ise, Markov zincirine karşılık gelen matrisin sıfırdan farklı elemanlarını çarpım esnasında oluşturup vektörde karşılık gelen elemanlarla çarpmak daha etkili olabilmektedir. Karma algoritmasını, Kronecker terimin çarpan matrislerindeki tamamı sıfır olan satır ve sütünları gözardı edecek şekilde değiştirmeyi öneriyoruz. Bu değişiklik, sonucu sıfır olan kayan noktalı sayı işlemlerinin gerçekleştirilmemesini sağlıyor. çok sayıda modelde, değiştirilmiş karma algoritması pek çok kayan noktalı sayı işleminden kaçınılmasını sağlıyor. Yine bazı modellerde, değiştirilmiş karma algoritmasının sıfırdan farklı elemenları çarpım esnasında oluşturan algoritmaya kıyasla daha az kayan noktalı sayı işlemi ve bellek gerektiriyor. Markov zincirine karşılık gelen matris, Kronecker çarpımları kullanılarak sıkıştırılmış olarak gösterilse bile, işlemler için gereken bellek miktarı ulaşılabilir durum uzayının büyüklüğüyle doğru orantılı olarak değişmektedir. özellikle boyut sayısı arttığında, bu daha büyük bir sorun oluşturmaktadır. Hiyerarşik Tucker ayrıştırması kullanarak, çözüm vektörlerinin görece sıkıştırılmış olarak tutulup, temel vektör-Kronecker terim çarpma işlemlerinin görece etkili olarak gerçekleştirilebildiğini gösteriyoruz. Sürekli zamanlı bir Markov zinciri olarak modellenmiş bir rassal kimyasal sistemin zamana bağlı değişimi kimyasal ana denklemi olarak da bilinen bir adi diferansiyel denklem sistemi olarak tanımlanabilir. Kimyasal ana denklemi, zamanı ayrıklaştırarak ve sayılabilir sonsuz durum uzayınının kesilerek elde edilmiş doğrusal sistemin çözülmesiyle çözümlenebilir. Durum uzayının ihmal edilebilir az sayıda durum içererek, kesilmiş durum uzayı dışında az miktarda olasılık kitlesi kalacak şekilde kesilmesi ise apaçık değildir. Hiyerarşik Tucker ayrıştırması kullanarak adi diferansiyel denklem çözücüsünün ihtiyaç duyduğu bellek miktarını azaltılabileceğini gösteriyoruz. Ayrıca, sonsuz durum uzayını kesmek için tahmin vektörlerini kullanan yenilikçi bir yöntem öneriyoruz. Sayısal deneyler uyarlamalı kesim stratejilerinin zaman ve bellek ihtiyacını, sabit kesim stratejilerine kıyasla ciddi olarak azalttığını gösteriyor. Son olarak, birden fazla sınıfa ait müşteri kabul eden, müşterilerin sınıfa bağımlı Markov varış sürecine göre geldikleri ve çok sayıda sunucusu olan bir yeniden denemeli kuyruk sistemini ele alıyoruz. Ele aldığımız sistemde, servis zamanlarınının sınıfa bağımlı evre-tipli, yeniden deneme zamanlarının ise çevrimsiz sınıfa bağımlı evre-tipli dağılım gösterdiklerini farz ediyoruz. Bu sistemin ölçümkallığının gerek ve yeter koşulunu ise sürüklenme fonksiyonlarına dayanan ölçütler kullanarak elde ediyoruz. Sonsuz durum uzayını uygun bir şekilde seçilmiş Lyapunov fonksiyonu kullanarak kesiyoruz. Elde ettiğimiz kesilmiş modeli ise çok boyutlu bir Markov zincir olarak tanımlayıp bu zincire karşılık gelen matrisin Kronecker temelli sayısal çözümlemesini gerçekleştiriyoruz.