Markov zinciri karıştırma süresi - Markov chain mixing time - Wikipedia

İçinde olasılık teorisi, karıştırma zamanı bir Markov zinciri Markov zincirinin kendi zincirine "yakın" olduğu zamandır. kararlı hal dağıtım.

Daha doğrusu, aşağıdakiler hakkında temel bir sonuçtur: Markov zincirleri sonlu durum indirgenemez periyodik olmayan bir zincirin benzersiz bir durağan dağılıma sahip olmasıdır. π ve başlangıç ​​durumuna bakılmaksızın, zaman-t zincirin dağılımı yakınsak π gibi t sonsuzluğa meyillidir. Karıştırma süresi, fikrin çeşitli biçimlendirmelerinden herhangi birini ifade eder: ne kadar büyük olmalıdır t o zamana kadart dağıtım yaklaşık π ? Bir değişken, varyasyon mesafesi karıştırma süresi, en küçük olarak tanımlanır t öyle ki olasılık ölçülerinin toplam değişim mesafesi küçük:

tüm alt kümeler için durumların ve tüm başlangıç ​​durumlarının. Bu, hangi anlamda Dave Bayer ve Persi Diaconis  (1992 ) tüfek sayısının kanıtlandı karıştırır Sıradan bir 52 kart destesini karıştırmak için gereken 7'dir. Matematik teorisi, karıştırma sürelerinin zincirin altında yatan yapının boyutunun bir fonksiyonu olarak nasıl değiştiğine odaklanır. Bir ... için -kart destesi, gerekli tüfek karıştırma sayısı arttıkça . En gelişmiş teori endişeleri rastgele algoritmalar için # P-Tamamlandı sayısı gibi algoritmik sayma problemleri grafik renklendirmeleri verilen köşe grafiği. Bu tür sorunlar, yeterince fazla sayıda renk için, Markov zinciri Monte Carlo yöntem ve karıştırma süresinin yalnızca (Jerrum 1995 ). Bu örnek ve karıştırma örneği, hızlı karıştırma özelliği, karıştırma süresinin en çok polinomik olarak hızlı artması (zincirin durum sayısı). Hızlı karıştırmayı kanıtlayan araçlar, aşağıdakilere dayalı argümanları içerir: iletkenlik ve yöntemi bağlantı. Markov zincirinin daha geniş kullanımlarında Monte Carlo yöntemi, simülasyon sonuçlarının kesin gerekçelendirilmesi, karıştırma süresine teorik bir sınır gerektirecektir ve birçok ilginç pratik durum, bu tür teorik analize direnmiştir.

Ayrıca bakınız

Referanslar

  • Aldous, David; Doldur, Jim, Tersinir Markov Zincirleri ve Grafikler Üzerinde Rastgele Yürüyüşler, dan arşivlendi orijinal 2004-09-21 tarihinde.
  • Bayer, Dave; Diaconis, Persi (1992), "Kırlangıç ​​kuyruğunu inine kadar sürüyor" (PDF), Uygulamalı Olasılık Yıllıkları, 2 (2): 294–313, doi:10.1214 / aoap / 1177005705, JSTOR  2959752, BAY  1161056.
  • Jerrum, Mark (1995), "Sayısını tahmin etmek için çok basit bir algoritma k- düşük dereceli bir grafiğin renkleri ", Rastgele Yapılar ve Algoritmalar, 7 (2): 157–165, doi:10.1002 / rsa.3240070205, BAY  1369061.
  • Levin, David A .; Peres, Yuval; Wilmer, Elizabeth L. (2009), Markov zincirleri ve karıştırma süreleri Providence, Rhode Island: Amerikan Matematik Derneği, ISBN  978-0-8218-4739-8, BAY  2466937.
  • Sinclair, Alistair (1993), Rastgele oluşturma ve sayma için algoritmalar: Markov zinciri yaklaşımı, Teorik Bilgisayar Biliminde İlerleme, Birkhäuser Boston, Inc., Boston, MA, doi:10.1007/978-1-4612-0323-0, ISBN  0-8176-3658-7, BAY  1201590.