Markov Zinciri

Vikipedi, özgür ansiklopedi

Bu sayfa, başka dilde bir Vikipedi'den çevrilmektedir.
Siz de yardım etmek istiyorsanız ya da çeviri yarıda kalmışsa, çalışmaya katılan kişilerle iletişime geçip, sayfanın durumunu onlara sorabilirsiniz.
Sayfanın geçmişine baktığınızda, sayfa üzerinde çalışma yapanları görebilirsiniz.

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.

[değiştir] Tanımı

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, X₁, X₂, X₃, ... 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).\,$

X_i'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.

[değiştir] Çeşitlemeleri

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 (X_n)den yeni bir (Y_n) zincirinin şöyle kurulması mümkündür: Y_n sıralamalı m-boyutlu X değerlerinden şöyle kurulsun:

Y_n = (X_n, X_n−1, ..., X_n−m+1)

O zaman Y_n, durum uzayı S^m olan ve klasik Markov özelliği bulunan bir Markov zinciri olur.

[değiştir] Örnek

[değiştir] Markov zincirlerinin özellikleri

[değiştir] İndirgenebilirlik

[değiştir] Dönemsellik

[değiştir] Tekrarlama

Eger i durumdan basladigimiz bilindigi halde, i durmuna hicbir zaman donme imkâni yaratmayan bir sifira esit olamayan olasilik bulunuyorsa i durumu gecis durum olarak nitelendirilir. Daha matimatik bicimle ve notasyonla bir rassal degisken olan T_i i durumuna ilk geri donus zamani (vurma zamani) olsun; yani

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

Bu halde i durumu gecisli olmasi icin ancak ve ancak

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

olmalidir. Eger bir durum i gecisli degilse (yani 1 olasilkla bir sonlu olan vurma zamanina sahipse), o halde i durumu yinelenen veya israrli durum olarak adlandirilir. Vurma zamani sonlu olmakla beraber bir sonlu beklenen degeri bulunmasi gerekmez. M_i beklenen geri donus zamani yani

$M_i = E[T_i].\,$

olsun. O halde eger M_i sonlu ise i durumu da pozitif yinelenen olur; aksi halde i durumu sifir yinelenen olacaktir; bu durumlara ayni sirayla sifir-olmayan israrli veya sifir israrli durum adlarida verilir.

Bir durumun yinelenen olmasi ancak ve sadece ancak

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

ifadesi gercekse ortaya cikacagi isbatlanamistir.

Eger durum i yi girdikten sonra hicbir zaman o durumdan cikmak mumkun degilse, i durumu yutan durum olarak adlandirilir. Bu halde i durumu yutan durum olamasi icin ancak ve sadece ancak su kosulu saglamasi gerekir:

p i i = 1

and

p i j = 0

for $i \not= j.$

[değiştir] Ergodiklik

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

[değiştir] Tersinebilir Markov zincirleri

[değiştir] Bernoulli şeması

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

[değiştir] Uygulamalar

[değiştir] Fizik

[değiştir] Sınama

[değiştir] Kuyruk kuramı

[değiştir] İnternet uygulamaları

[değiştir] İstatistik

[değiştir] İktisat

[değiştir] Matematiksel biyoloji

??????

[değiştir] Müzik

[değiştir] Beyzbol

[değiştir] Markov parodi üreticileri

[değiştir] Tarihçe

[değiştir] İçsel kaynaklar

[değiştir] Referanslar

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.

Classical Text in Translation: A. A. Markov, An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains, trans. David Link. Science in Context 19.4 (2006): 591-600. Online: http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=637500

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.

S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability. London: Springer-Verlag, 1993. ISBN 0-387-19832-6. online: http://decision.csl.uiuc.edu/~meyn/pages/book.html . Second edition to appear, Cambridge University Press, 2009.

S. P. Meyn. Control Techniques for Complex Networks. Cambridge University Press, 2007. ISBN: 9780521884419. Appendix contains abridged Meyn & Tweedie. online: http://decision.csl.uiuc.edu/~meyn/pages/CTCN/CTCN.html

Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). 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 ed.). 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.

[değiştir] Dışsal kaynaklar

(pdf) Markov Chains chapter in American Mathematical Society's introductory probability book
Generates random parodies in the style of another body of text using a Markov chain algorithm
A generator that uses Markov Chains to create random words
Markov Chains
Şablon:Planetmath reference
Chapter 5: Markov Chain Models
Generating Text (About generating random text using a Markov chain.)
The World's Largest Matrix Computation (Google's PageRank as the stationary distribution of a random walk through the Web.)
Dissociated Press in Emacs approximates a Markov process
Markov Chain Example
Markov Chains for Search Engines
Steganography proof-of-concept using Markov Chains.
n^th order Markov Chain implementation in Ruby
Baseball Run Modeler using Markov Chains
Theory of Markov chains in baseball
Sequential analysis software for generating visual representations of probability models