Stationary distributions and convergence rates for the edge flipping process

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2021

Tezin Dili: İngilizce

Öğrenci: YUNUS EMRE DEMİRCİ

Danışman: ÜMİT IŞLAK

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Kenar çevirme süreci, bir çizgenin tüm olası renk desenleri kümesi üzerinde rastgele bir yürüyüştür. Seçilen kenarın iki uç düğümü her seferinde aynı renkle renklendirilir. Bu renk p olasılıkla mavi ve 1-p olasılıkla kırmızıdır. Düğüm çevirme sürecinde kenarlar yerine düğümleri seçiyoruz. Seçilen düğümün tüm komşuları ve kendisi aynı renkle renklendirilir. Bu rastgele yürüyüşün özdeğerleri, çizgenin köşelerinin tüm alt kümeleri tarafından indekslenir. Bu indeksleme sayesinde özdeğerler ve bunun sonucunda da üzerinde çalıştığımız çizge sınıflarındaki yakınsama hızları hakkında bilgi sahibi olduk. Tam çift parçalı çizge ve tırtıl ağacı gibi bazı basit çizge sınıflarında bu rastgele yürüyüşün bir süre sonra nereye yakınsadığı ile ilgili sonuçlar elde ettik. Genel olarak şu iki soruya cevap arıyoruz: nereye yakınsar ve ne kadar hızlı gerçekleşir.