MARKOV ZANJIRLI MONTE-KARLO USULLARI KONVERGENSIYASINING ALGORITMIK TAHLILI VA MA’LUMOTLAR TUZILMALARI BILAN BOG‘LIQLIGI
Ключевые слова:
Markov zanjirli Monte-Karlo, geometrik ergodiklik, spektral tirqish, aralashish vaqti, konduktans, ma’lumotlar tuzilmalari, Fenwick daraxti, alias usuli, samarali tanlanma hajmi, hisoblash murakkabligiАннотация
Maqolada Markov zanjirli Monte-Karlo (MZMK) usullarining konvergensiya nazariyasi
hisoblash murakkabligi, ergodiklik, spektral tirqish va aralashish vaqti kabi tavsiflar grafning bog‘langanligi,
kengaytiruvchanligi va algoritm iteratsiyalari soni bilan bir qiymatli mos kelishi ko‘rsatilgan. Algoritmning
to‘liq hisoblash narxini uch mustaqil ko‘paytuvchiga – integral avtokorrelyatsiya vaqti, bitta qadamning amal
narxi va zarur samarali tanlanma hajmiga – ajratuvchi model taklif etilib, isbotlangan. Model asosida
ma’lumotlar tuzilmasini tanlash konvergensiya tezligiga emas, balki narx ko‘paytuvchisiga ta’sir qilishi
asoslangan. Xulosalar 2D Izing modeli va Metropolis algoritmi ustidagi eksperimentlarda tasdiqlangan:
inkremental hisoblash 110 baravar, Fenwick daraxti esa 140 baravar tezlanish bergan.
