Markov zinciri

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Matematikte, Markov Zinciri (Andrey Markov'un adına atfen), Markov özelliğine sahip bir stokastik süreçtir. Markov özelliğine sahip olmak, mevcut durum verildiğinde, gelecek durumların geçmiş durumlardan bağımsız olması anlamına gelir. Bir başka deyişle, mevcut durumun açıklaması, sürecin gelecekteki evrimini etkileyecebilecek tüm bilgiyi kapsar. Gelecek durumlara belirli bir şekilde değil, olasılıksal bir süreçle ulaşılacaktır.

Her bir anda sistem belirli bir olasılık dağılımına bağlı olarak kendi durumunundan başka bir duruma geçebilir yahut aynı durumda kalabilir. Durumda olan değişiklikler geçiş olarak bilinir ve çeşitli durum değişmeleriyle ilişkili olasılıklar da geçiş olasılıkları olarak adlandırılır.

Markov zincirine bir örnek basit rastgele yürüyüş olur. Basit rastgele yürüyüş için durum uzayı bir gösterim üstünde bir grup köşeler halindedir. Geçiş aşamaları ise (yürüyüşün geçmişinde ne olmuş olursa olsun) cari köşeden herhangi bir komşu köşeye gitmeyi kapsar. Cari köşeden herhangi bir komşu köşeye gitme olasılığı hep aynı olup birbirine eşittir.


Tanımı[değiştir | kaynağı değiştir]

Markov zincir Markov özelliğini taşıyan, yani mevcut durum verilmiş olursa geçmiş ve gelecek durumların bağımsız olduğu, ardıardına gelen, X1, X2, X3, ... ile ifade edilen, bir seri rassal değişkendir. Matematiksel biçimle

\Pr(X_{n+1}=x|X_n=x_n, \ldots, X_1=x_1) = \Pr(X_{n+1}=x|X_n=x_n).\,

Xi'in mümkün değerleri, S olarak ifade edilen ve zincirin durum uzayı adı verilen sayılabilir bir set oluşturur.

Çok kere Markov zincirleri bir yönlendirilmiş gösterim ile tanımlanmaktadır ve bu gösterimde kenar doğrular bir durumdan diğer bir duruma geçiş olasılıkları ile tanıtılmaktadır.


Çeşitlemeleri[değiştir | kaynağı değiştir]

Sürekli-zaman Markov sürecinin sürekli bir endeksi bulunur.

Zaman içinde homojen Markov zincirleri zamana göre homojen olan geçiş olasılıkları bulunan Markov zincirleridir ve tüm n değerleri için

\Pr(X_{n+1}=x|X_n=y) = \Pr(X_{n}=x|X_{n-1}=y)\,

olan süreçlerdir.

m sonlu bir sayı ise, bir m dereceli bir Markov zinciri (yani m bellekli bir Markov zinciri) için tum n değerleri için şu ifadeler verilebilir:

\Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots , X_{1}=x_{1})
  = \Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots, X_{n-m}=x_{n-m})

'Klasik' Markov özelliği olan (Xn)den yeni bir (Yn) zincirinin şöyle kurulması mümkündür: Yn sıralamalı m-boyutlu X değerlerinden şöyle kurulsun:

Yn = (Xn, Xn-1, ..., Xn-m+1)

O zaman Yn, durum uzayı Sm olan ve klasik Markov özelliği bulunan bir Markov zinciri olur.

Örnek[değiştir | kaynağı değiştir]

Markov zincirlerinin özellikleri[değiştir | kaynağı değiştir]

İndirgenebilirlik[değiştir | kaynağı değiştir]

Dönemsellik[değiştir | kaynağı değiştir]

Tekrarlama[değiştir | kaynağı değiştir]

Eğer i durumdan başladığımız bilindiği halde, i durmuna hiçbir zaman dönme imkanı yaratmayan bir sıfıra eşit olamayan olasılık bulunuyorsa i durumu geçiş durum olarak nitelendirilir. Daha matematik biçimle ve notasyonla bir rassal değişken olan Ti i durumuna ilk geri dönüş zamanı (vurma zamanı') olsun; yani

 T_i = \inf \{ n: X_n = i | X_0 = i\}

Bu halde i durumu geçişli olması için ancak ve ancak

 \Pr(T_i = {\infty}) > 0.

olmalıdır. Eğer bir durum i geçişli değilse (yani 1 olasılıkla bir sonlu olan vurma zamanına sahipse), o halde i durumu yinelenen veya ısrarlı durum olarak adlandırılır. Vurma zamanı sonlu olmakla beraber bir sonlu beklenen değeri bulunması gerekmez. Mi beklenen geri dönüş zamanı, yani

 M_i = E[T_i].\,

olsun. O halde eğer Mi sonlu ise i durumu da pozitif yinelenen olur; aksi halde i durumu sıfır yinelenen olacaktır; bu durumlara aynı sırayla sıfır olmayan ısrarlı veya sıfır ısrarlı durum adları da verilir.

Bir durumun yinelenen olması ancak ve sadece ancak

\sum_{n=0}^{\infty} p_{ii}^{(n)} = \infty

ifadesi gerçekse ortaya çıkacağı ispatlanamıştır.

Eger durum i yi girdikten sonra hiçbir zaman o durumdan çıkmak mümkün değilse, i durumu yutan durum olarak adlandırılır. Bu halde i durumu yutan durum olaması icin ancak ve sadece ancak şu koşulu sağlaması gerekir;

 p_{ii} = 1 and  p_{ij} = 0 for i \not= j.

Ergodiklik[değiştir | kaynağı değiştir]

Sonlu durum uzayında Markov zincirleri[değiştir | kaynağı değiştir]

Tersinebilir Markov zincirleri[değiştir | kaynağı değiştir]

Bernoulli şeması[değiştir | kaynağı değiştir]

Genel durum uzayında Markov zincirleri[değiştir | kaynağı değiştir]

Uygulamalar[değiştir | kaynağı değiştir]

Fizik[değiştir | kaynağı değiştir]

Sınama[değiştir | kaynağı değiştir]

Kuyruk kuramı[değiştir | kaynağı değiştir]

İnternet uygulamaları[değiştir | kaynağı değiştir]

Google'in kullandığı internet sayfalarının PageRank'i Markov zinciri ile tanımlanmaktadır.[1] Markov zincirinde durağan dağılımda tüm bilinen internet sayfaları arasından i sayfasında bulunma olasılığıdir. Eğer N bilinen internet sayfaları ise ve i sayfası k i bağlantısına sahip işe, o zaman bağlantılı olduğu tüm sayfalar için \frac{1-q}{k i} + \frac{q}{N} ve bağlantısı olmadığı tüm sayfalar için \frac{q}{N} geçiş olasılığına sahiptir. q parametresi yaklaşık 0.15 olarak alınmıştır.

Markov modelleri aynı zamanda kullanıcıların internet gezinti davranışlarını analiz etmek için de kullanılmıştır. Bir kullanıcının bir internet sayfasından web bağlantısı ile geçişi, birincil ya da ikincil Markov modelleri ile modellenebilir ve gelecekteki hareketleri öngörmede ve dolayısıyla internet sayfasını kullanıcı için kiselleştirmede kullanılabilir.

İstatistik[değiştir | kaynağı değiştir]

İktisat[değiştir | kaynağı değiştir]

Matematiksel biyoloji[değiştir | kaynağı değiştir]

Müzik[değiştir | kaynağı değiştir]

Beyzbol[değiştir | kaynağı değiştir]

Markov parodi üreticileri[değiştir | kaynağı değiştir]

Tarihçe[değiştir | kaynağı değiştir]

Ayrıca bakınız[değiştir | kaynağı değiştir]

Kaynakça[değiştir | kaynağı değiştir]

  • A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135–156, 1906.
  • A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". Yeni basım Appendiks B: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
  • Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. (See Chapter 7.)
  • J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.
  • Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st bas.). New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924.  Extensive, wide-ranging book meant for specialists, written for both theoretical computer scientists as well as electrical engineers. With detailed explanations of state minimization techniques, FSMs, Turing machines, Markov processes, and undecidability. Excellent treatment of Markov processes pp. 449ff. Discusses Z-transforms, D transforms in their context.
  • Kemeny, John G.; Hazleton Mirkil, J. Laurie Snell, Gerald L. Thompson (1959). Finite Mathematical Structures (1st bas.). Englewood Cliffs, N.J.: Prentice-Hall, Inc.. Library of Congress Card Catalog Number 59-12841.  Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.

Dış bağlantılar[değiştir | kaynağı değiştir]