ELDEN ELE KARIŞTIRMA DESTEYİ NE ZAMAN UNUTUR?

Kart karıştırmak, olasılık kuramındaki temel bir sorunun somut bir hâlidir: rastgele bir süreç başladığı yeri unutmak için ne kadar zamana ihtiyaç duyar? Yeni açılmış bir deste sıralıdır. Her karıştırma onu biraz daha karıştırır; ta ki orijinal sıranın hiçbir izi saptanamayana dek.

Matematikçiler iki yanıt düzeyini birbirinden ayırır. Karışma süresi (mixing time) büyüklük mertebesini verir. Cutoff (eşik) çok daha fazlasını söyler: kesin bir anın çevresinde deste, “açıkça karışmamış” durumdan “tamamen karışmış” duruma neredeyse bir anda geçer. Karıştırmayı bundan biraz kısa tutarsanız hâlâ fark edebilirsiniz; biraz uzun tutarsanız edemezsiniz.

Bir matematikçinin gözünden karıştırma

Elden ele karıştırmada desteyi bir elinizde tutar ve küçük kart paketlerini diğer elinize bırakırsınız. Makale bunu şöyle modelliyor: komşu kartlar arasındaki n − 1 boşluğun her biri p olasılıkla bağımsız olarak kesiliyor ve ortaya çıkan paketlerin sırası tersine çevriliyor. Destenin bir kez baştan sona geçilmesi bir karıştırma sayılıyor.

Makaleye göre önceki çalışmalar büyüklük mertebesini zaten belirlemişti. Pemantle karışma süresini n² ile n² log n arasına sıkıştırdı; Jonasson ardından doğru mertebenin n² log n olduğunu gösterdi. Ama tam sabit ve keskin bir eşiğin gerçekleşip gerçekleşmediği açık kaldı: Diaconis ve Pal, 2022’de elden ele karıştırma eşiğini açık problemler arasında saymıştı.

Sonuç

Yunjiang Jiang eşiğin var olduğunu kanıtlıyor ve yerini belirliyor.

Teorem. Sabit bir kesme olasılığı p için elden ele karıştırma, birinci mertebede,

p² / (2(1 − p)π²) × n² log n

karıştırmada karışır. Biraz öncesinde deste rastgelelikten uzak kalır; biraz sonrasında rastgeleliğe yakındır.

p = 1/2 için — boşlukların ortalama yarısında kesme — formül n² log n / (4π²) hâline gelir.

Kanıt nasıl işliyor

Kanıtın birbirinden bağımsız üç parçası var.

1. Alt sınır tek bir kartı izliyor. Kartın konumu dikkat çekici derecede temiz bir biçimde evriliyor: kosinüs biçimli kesin desenler, sonlu bir deste için bile bilinen bir hızla sönümleniyor. Tüm deste üzerinden toplandığında, başlangıç sırasının saptanabilir bir izini öngörülen ana kadar koruyorlar.
2. Üst sınır, yalnızca iki kartın yer değiştirmesiyle farklılaşan iki desteyi karşılaştırıyor. Aynı rastgele kesmelerle çalıştırıldığında fark, komşu hâline gelip birleşebilene dek deste içinde dolaşan iki işaretli konum gibi davranıyor. Bunun gerçekleşme hızı alt sınırla örtüşüyor.
3. Karıştırmayla ilgisi olmayan, permütasyonlara ilişkin statik bir eşitsizlik, bu karşılaştırmayı tüm desteye dair bir ifadeye dönüştürüyor. Bu, makalenin en teknik kısmı; kartların bloklara nasıl dağıldığını sayan tablolar üzerinde özyinelemeyle kuruluyor.

Makale ayrıca düzensizliği ölçmenin bir başka yolu olan göreli entropi için de, tam yerini belirlemeden, bir eşik kanıtlıyor.

Formül gerçek bir deste hakkında ne söylüyor

52 kartlık bir desteyi p = 1/2 ile formüle yerleştirmek 52² × ln 52 / (4π²), yani yaklaşık 270 karıştırma veriyor. Bu bizim kendi hesabımız, makaledeki bir rakam değil ve kaba bir gösterge olarak okunmalı: teorem çok büyük destelerin davranışını tanımlıyor ve düzeltme terimi nicelendirilmemiş. Karşılaştırma için makale, Bayer ve Diaconis’in riffle karıştırma için belirlediği (3/2) log₂ n ölçeğine atıf yapıyor — 52 kart için yaklaşık 8,6, aynı çekinceyle. n² log n ile log n arasındaki uçurum, elden ele karıştırmayı bu kadar yavaş kılan şey.

Birinci mertebe, idealleştirilmiş eller

Sonuç birinci mertebeden: geçiş penceresinin genişliğini ya da tam biçimini vermiyor. Kesme olasılığı sabit tutuluyor ve kesmelerin bağımsız olduğu varsayılıyor; bu, gerçek ellerin bir idealleştirmesi. Yazar bir dipnotta, yapay zekâ sistemi GPT-6 Astra’nın “argümanların geliştirilmesinde, hesapların denetlenmesinde ve anlatımın hazırlanmasında kullanıldığını” ve matematiksel içerikten yazarın sorumlu olduğunu belirtiyor. Makale bir ön baskıdır.