Rastgele gerçek polinomların en büyük kökünün karmaşık sayıdan çok gerçek sayı olma olasılığı daha yüksek

 (mathoverflow.net)
1 puan yazan GN⁺ 2024-05-12 | 1 yorum | WhatsApp'ta paylaş
  • Katsayıları bağımsız düzgün dağılımlı gerçek sayılar olan rastgele bir polinomda toplam gerçek kök sayısı yaklaşık 2log n/π ile sınırlı kalsa da, deneylerde mutlak değeri en büyük/en küçük kökün gerçek olma olasılığının daha yüksek olduğu görülüyor
  • Derece başına 10^5 Monte Carlo simülasyonunda bu olasılık n büyüdükçe 1/2 civarına doğru düşüyor; normal dağılımlı katsayılar (-1,1) aralığına ölçeklendiğinde de benzer gözlem korunuyor
  • Bir yanıt, sonlu derecedeki uç kök probleminin rastgele kuvvet serisi P(x)=a₀+a₁x+a₂x²+… için en küçük kökün gerçek olup olmadığını sorma problemine yakınsadığını düşünüyor
  • Dağılıma bağlı olarak limit değer değişebilir: düzgün dağılım [-1,1] için yaklaşık %51, standart normal dağılım için yaklaşık %52, varyansı 1/k! olan normal dağılım için %62, ±1 ayrık dağılımı için ise %40’ların başı gibi görünüyor
  • Yanıtlayan kişi “1/2’ye yakınsar” yorumuna kuşkuyla yaklaşıyor; derece 200 ve 300’ü karşılaştıran 40 bin deneyde en küçük kökün gerçek olup olmadığı tümünde korunduğu için limitin %50’den büyük olma ihtimalini güçlü görüyor

Problem kurgusu: Gerçek kökler az, ama uç kökler gerçek tarafa kayıyor

  • Gerçek katsayılı rastgele polinomlarda tüm kökler içinde gerçek köklerin sayısı karmaşık köklere göre çok daha azdır
    • Katsayılar bağımsız olarak (-1,1) düzgün dağılımından geliyorsa, n dereceli bir polinomun gerçek kök sayısı asimptotik olarak 2log n/π + o(1) olur
    • Karmaşık kök sayısı yaklaşık n - 2log n/π olur
    • Bağlantılı makaleye göre başka katsayı dağılımlarında da benzer asimptotik formül geçerlidir
  • Burada “en büyük kök” ve “en küçük kök” sırasıyla mutlak değeri en büyük kök ve mutlak değeri en küçük kök anlamına gelir
  • Gerçek kökler çok daha azsa uç köklerin de karmaşık olması beklenebilir; ancak soruyu soran kişinin deney verileri ters yönde bir tablo gösteriyor

Monte Carlo gözlemi ve açık soru

  • Gözlenen verinin özü üç noktadan oluşuyor
    • En büyük kökün veya en küçük kökün gerçek olma olasılığı, karmaşık olma olasılığından büyük
    • Bu olasılık n büyüdükçe 1/2 civarındaki bir değere düşüyor gibi görünüyor
    • Her n değeri için 10^5 Monte Carlo simülasyonu yapılmış
  • Katsayılar düzgün dağılım yerine ortalaması 0, standart sapması 1 olan normal dağılımdan seçilip (-1,1) aralığına ölçeklendiğinde de aynı gözlemin ve limit olasılığının korunduğu belirtiliyor
  • Soru iki noktaya indirgeniyor
    • En büyük kök ve en küçük kök neden gerçek tarafa kayıyor?
    • Derece n için ilgili olasılık n→∞ iken 1/2 civarında bir değere yakınsıyor mu?
  • Gözlenen yanlılık koşullu olasılıkla şöyle ifade ediliyor
    • P(L|R)=P(S|R)≈π/(4log n)
    • P(L|C)=P(S|C)≈π/(2nπ-4log n)

Güncelleme: Alt sınır ispatı ve n=1000 ek deneyi

  • Bağlantılı Math StackExchange yazısında, en büyük kökün gerçek olma olasılığının en az şu değer olduğu kanıtlanıyor
    • (23-16√2)/6 ≈ %6,2
  • 11 Mayıs 2024 güncellemesine, derece n=1000 polinomlar için neredeyse 60.000 deneyin sonucu eklenmiş
    • n≤125 için gözlenen grafiklerle tutarlı sonuçlar ortaya çıkmış
    • Deneme sayısı arttıkça en büyük kökün gerçek olma olasılığının azalma eğilimi gösterdiği ve 1/2’ye yakınsama ihtimali olduğu yazıyor

Yanıt: Rastgele kuvvet serisinin en küçük köküne bağlanıyor

  • Math StackExchange ve Thurston, Selberg, and random polynomials Part II blog yazısına dayanarak, uygun katsayı dağılımlarında sonlu derecedeki limitin rastgele kuvvet serisinin en küçük kökü problemine uzandığı belirtiliyor
    • P(x)=a₀+a₁x+a₂x²+…
    • Sonlu derecede en küçük kökün gerçek olma olasılığının limiti, bu rastgele kuvvet serisinin en küçük kökünün gerçek olma olasılığı olur
  • Rouché teoremi kullanılırsa bu olasılığın 0’dan büyük ve 1’den küçük olduğu kolayca gösterilebilir deniyor
  • Limit değer, aᵢ katsayılarının dağılımına göre değişebilir
    • aᵢ [-1,1] düzgün dağılımlıysa yaklaşık %51
    • Ortalama 0, varyans 1 olan Gaussian ise yaklaşık %52
    • Gaussian olup varyansı 1/k! ise yaklaşık %62
    • 1 ve -1 ayrık dağılımı ise %40’ların başı gibi görünüyor
  • Dolayısıyla “makul tüm durumlarda %50’den büyüktür” demektense, modele bağlı olarak %50’den büyük veya küçük olabilir demek daha doğru

Gerçek kökler az olsa da uç kökleri kaplayabilmelerinin nedeni

  • Birçok modelde kökler birim disk çevresinde toplanma, açı dağılımı ise düzgünleşme eğilimindedir; çok yerel ölçekte kökler arasında itilme (repulsion) oluşur
  • Karmaşık kökler birim diskin çevresine yayılabilir; fakat gerçek kökler arasındaki itilmenin gerçek kökleri daha küçük veya daha büyük olmaya “zorladığı” düşünülüyor
  • Bu bakış açısına göre toplam gerçek kök sayısı logaritmik seviyede olsa bile, en küçük kökü veya en büyük kökü almak için yeterince çok gerçek kök olabilir
  • Geriye kalan görev, Monte Carlo ile kolayca hesaplanan değerleri nasıl titiz sayısal tahminlere dönüştüreceğimizdir

Rouché teoremiyle titiz tahmin üretme fikri

  • Düzgün dağılım aᵢ∈[-1,1] varsayılarak, düşük dereceli polinomların katsayı uzayını küçük kutulara bölme yöntemi öneriliyor
    • Örnek olarak derece 100’den küçük polinomlarda her aᵢ değerini aynı uzunlukta 1000 aralığa bölme yöntemi anılıyor
    • Yanıtta bunun sonuçta 100^1000 polinom verdiği yazıyor
  • Monte Carlo açısından bakıldığında çoğu polinomun aşağıdaki iki kümeye ayrılabileceği bekleniyor
    • En küçük kökü gerçek olan ve mutlak değeri 9/10’dan küçük olanlar
    • En küçük iki kökü karmaşık eşlenik çift olan ve mutlak değerleri 9/10’dan küçük olanlar
  • Her iki durumda da yalnızca ilgili kökü içeren disk sınırında |P| > (9/10)^100 gösterilirse, Rouché teoremi ile en küçük kökün niteliğinin korunduğu garanti edilebilir
  • Bu yöntemin teorik bir engeli yok; ancak pratik hesaplama miktarı çok büyük olabilir, bu yüzden derece 10’dan küçük ve 10^10 polinom seviyesinde hesaplama ya da daha verimli bir bölme gerekebilir

1/2’ye yakınsama yorumuna itiraz ve ek hesaplama

  • Yanıtlayan kişi, soruyu soranın “muhtemelen 1/2’ye yakınsar” yorumunu ikna edici bulmuyor; başka doğal ve simetrik modellerin 1/2’ye yakınsamamasını buna karşı kanıt olarak gösteriyor
  • Derece 500 olan 1000 rastgele polinom üretilip en küçük kökün mutlak değeri kontrol edildiğinde, tüm durumlarda mutlak değer 0,91’den küçük çıkmış
    • Bu rastgele kuvvet serisine genişletildiğinde, |z|<0.91 diski içinde fonksiyon değişiminin 10^-20 mertebesinde veya daha küçük olduğu yazıyor
    • Rouché teoreminin uygulanamaması için en küçük kökün veya karmaşık eşlenik çiftin, mutlak değer bakımından bir sonraki köke aşırı derecede yakın olması gerekir
  • Daha iyi yakınsama oranı tahmini için şu deney öneriliyor
    • Derece 500 olan 50.000 rastgele polinom hesaplamak
    • Aynı başlangıç terimlerini koruyarak derece 1000’e genişletilmiş 50.000 polinom hesaplamak
    • İki derecede en küçük kökün gerçek olup olmadığını ve derece artırıldığında bu niteliğin ne sıklıkla değiştiğini kontrol etmek
  • Yanıtlayanın sezgisi, derece 500’den 1000’e geçerken değişen durumların çok nadir olacağı yönünde
    • İki değer de %51 civarındaysa ve değişme oranı %1’den çok daha küçükse, limitin %50’den kesin olarak büyük olduğuna işaret sayılabilir

Gerçek karşılaştırma deneyi: Derece 200 ve 300

  • Büyük dereceli hesaplamalar uzun sürdüğü için gerçek karşılaştırma derece 200 ve 300 ile yapılmış
  • 40.000 polinom çalıştırma sonucu:
    • Derece 200 polinomların 20.287’sinde en küçük kök gerçekti
    • Bu polinomlar derece 300’e genişletildiğinde tüm durumlarda aynı özellik korundu
  • Bu sonuç, derece 200, 300 ve 1000 için beklenen değerlerin sonsuz derece beklenen değerine şimdiden çok yakın olabileceğini düşündürüyor
  • Hesaplanan değer yaklaşık %50,7; soruyu soranın hesaplaması da benzer şekilde %50,7 düzeyinde olduğundan, limitin 1/2’den büyük olduğu yönünde kanıt olarak sunuluyor
  • Yanıtlayan kişi “limit %50’den büyük” olduğundan emin olduğunu söylüyor ve yanlış olduğunu kanıtlayan kişiye 100 dolar vereceğini ekliyor

Kesilmiş kuvvet serisinin hızlı kararlılığı

  • Ek kanıt olarak, rastgele kuvvet serisi P(x)=Σaᵢxᶦ için kesilmiş polinom Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦ üzerinde, k=1’den 1000’e kadar en küçük kökün gerçek mi karmaşık mı olduğunun ne zaman kararlı hâle geldiği kontrol ediliyor
  • 200 rastgele polinomda kararlılığın başlangıç noktası çoğunlukla çok küçüktü
    • Birçoğu k=1 veya k=2’de zaten kararlı hâle geldi
    • Listelenen değerlerin en büyüğü 22
  • Bu sonuç da sonlu derece deneylerinin sonsuz derece limitine hızla yaklaşabileceği değerlendirmesini destekliyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-05-12
Hacker News yorumları

  • Rastlantı düzeyi ile 1/φ arasında olması gerçekten ilginç
    Bağlantısı verilen MSE yazısında en büyük kökün gerçek olma olasılığının en az %6,2 olduğu artık kanıtlandı; hatta 1/φ’nin 1/10’undan bile fazla. Asal sayılar ile φ arasındaki bağlantının doğal olduğunu düşünüyorum. Asal sayılar, sıkça yanlış anlaşıldığı gibi rastgele değildir; önceki asal sayılardan özyinelemeli olarak ortaya çıkarlar, çünkü önceki asal sayıların katlarının dolduramadığı “boşluklar”dır. Bu yüzden e ya da φ gibi bir doğal büyüme örüntüsünün belirmesini beklemek makul. Hakikat ve güzellik gibi çok temel büyüklüklerin örüntüsü

    • Asal sayılarda e’nin ortaya çıkma biçimi, büyüyen aralıklardan oluşan kümelerin boyut ortalamasında görülebilir; örneğin (2,3,5)(7,11)(13,17)... ya da azalmayan aralıklardan oluşan (2,3,5,7,11)(13,17)(19,23,29)... gibi
      Bu, asal sayıların kendi özelliğinden ziyade büyümenin bir özelliği ve rastgele sayı kümelerinde daha iyi uyuyor
    • Güzel. φ her zaman bir şeyler çok sıkışık biçimde bir araya geldiğinde ortaya çıkıyor gibi

  • Aklıma hemen iki soru geliyor

    1. Burada rastgele ne demek? Sayısal deney yapılmış gibi görünüyor; sınırlı bir kümede tekdüze tamsayı katsayılar kullanılmış olmasına benziyor ve bu durumda sonuçlar epey değişebilir
    2. Her zaman gerçek kök garanti eden tek derecelere mi, çift derecelere mi, yoksa ikisine birden mi bakıldığını merak ediyorum
      Bu ilginç yazıyı küçümsemek istemiyorum
    • Tanımda kullanıldığı üzere dağılım, (-1,1) aralığında bağımsız tekdüze katsayı dağılımı
    • Doğru. Asıl problem ifadesi paradoksal. Sonsuz bir kümeden tekdüze örnekleme yapılamaz. Orijinal yazının sınırlı rastgele kayan nokta sayıları kullandığını düşünüyorum
      Ancak sorunun önemli kısmı, gerçek sayılar üzerindeki olası herhangi bir dağılım için de sorulabilir

  • Bununla sayısal deney yapmak isterseniz, R’de bu amaç için yerleşik destek var
    plot(polyroot(runif(101,-1,1)))
    Bu şekilde 100. dereceden bir polinomun kök görselleştirmesini görebilirsiniz

  • “Katsayıların bağımsız ve (−1,1) aralığında tekdüze rastgele olduğu varsayılır. Aksi halde her katsayı, mutlak değeri en büyük katsayıya bölünerek (−1,1) aralığına ölçeklenebilir.”
    Sezgim doğru mu bilmiyorum ama böyle bölüp ölçekleyince, en büyük katsayı dışındaki katsayıların dağılımı tekdüze olmayan dağılım hâline gelmez mi?

    • Önemli olan, bir polinomu sabitle çarpmanın kökleri değiştirmemesidir
    • Doğru ama tek bir gerçek sayıyı tekdüze dağılımdan rastgele seçemezsiniz. Bir yerlerde taviz vermek gerekir
    1. derece ve üzeri polinomlar için formül yok; peki gerçek kök ile gerçek sayı + epsilon*i nasıl ayırt ediliyor?
    • Budan teoremi https://en.wikipedia.org/wiki/Budan%27s_theorem kullanılırsa (r - ɛ, r + ɛ] aralığında tam olarak bir gerçek kök mü, yoksa tam olarak 0 kök mü olduğunu doğrulamak mümkün
      Tahmin değeri r herhangi bir kökün ɛ yakınındaysa, kesin değeri bilmeden de gerçek kök ile karmaşık kök ayırt edilebilir. Elbette Budan teoreminin yanıt veremediği durumlar da var. Örneğin o aralıkta iki ya da daha fazla kök varsa en açık şekilde başarısız olur
    • Yüksek dereceli polinomların kökleri için kesin bir formülün imkânsız olması, bu polinomların kök dağılımını öğrenme ihtimalini ortadan kaldırmaz. Soru belirli bir polinom hakkında değil, dağılım hakkında olduğu için Abel teoremi bir engel değildir
      Örneğin a_i katsayıları bağımsız ve aynı dağılımlı Bernoulli rastgele değişkenleri olan a_n x^n + ... + a_0 polinomunu düşünürsek, derece n büyük olsa bile (>4) bu tür bir polinomun x = 0 noktasında gerçek köke sahip olma olasılığının 1/2 olduğunu rahatlıkla söyleyebiliriz. Bağlantı verilen soruda da benzer ama daha incelikli bir mantık işliyor
    • Tamsayı katsayılı bir polinomsa en büyük kök ve en küçük kök, katsayıların mutlak değerlerinin maksimumunun bir kuvveti biçiminde üstten sınırlandırılabilir. Kökün sahip olabileceği en küçük sanal kısım için de benzer bir sınır olmalı
      Katsayılar gerçek sayılarsa formül olsa bile yardımcı olmaz. Bir sayının 0’a eşit olup olmadığını belirleyememe sorunu aynen kalır. Örneğin ikinci derece formülde diskriminant -epsilon olabilir; epsilon 0 ise sanal kök yoktur, 0 değilse sanal kök vardır
    • Burada türevin kullanılabileceğini düşünüyorum. x+iy ve x-iy karmaşık köklerse ve y çok küçükse, x’teki türev de küçük olmalı. y=0 ise çift katlı kök olur, dolayısıyla p'(x)=0 olur
      Bu nedenle p'(x) 0’dan yeterince uzaksa tekil gerçek kök sayılabilir. Ayrıca rastgele katsayılarda çift katlı kökün fiilen ortaya çıkmayacağını düşünüyorum
    • Tahmin, sayısal hesaplamaya değil akıl yürütmeye dayanıyor. Örneğin gerçek değerli bir polinom karmaşık eşleniğe göre kararlı olduğundan, karmaşık bir kökü varsa eşleniği de mutlaka köktür. Dolayısıyla birbirinden farklı üç kökü olan bir polinomda bunlardan biri mutlaka gerçek kök olmalıdır. Bu tür akıl yürütmeyle kökün saf gerçek mi yoksa karmaşık mı olduğu anlaşılabilir
      Formül konusuna gelince, 5. derece ve üzeri için genel bir formül yoktur. Genel formül yalnızca 4. derece ve altındaki polinomlar için vardır
      Elbette belirli yüksek dereceli polinom türleri için özel formüller olabilir. Ama genel 5. derece ve üzeri için yoktur; bu da klasik olarak zaten kanıtlanmıştır

  • Konudan biraz sapıyor ama böyle matematik yazılarını okumak her zaman keyifli
    Üniversitede matematiği gerçekten seviyordum; bilgisayar bilimi okudum ama hocaların aldığı keyif bana hep ilham verirdi. Daha fazla öğrenmek, matematikle problem çözmeye biraz dalmak istiyorum. Muhtemelen sayısal analiz tarafına yönelebilirim
    Ancak mezun olalı 2 yıl oldu ve o zamandan beri pek uğraşmadığım için epey yeniden öğrenmem gerekecek gibi. Nereden başlamanın iyi olacağını, ilginç konular bulabileceğim yerler olup olmadığını merak ediyorum. Sayısal analiz değil ama lisans döneminde epey Project Euler problemi çözmüştüm; buna benzer başka şeyler var mı? Her türlü fikre açığım
    Yoksa önce ders kitaplarındaki tüm problemleri yeniden mi çözmeliyim? ;-)

  • Bu tür matematiği bilmediğim için mi bilmiyorum
    Kafamda “rastgele” bir polinom alıp yalnızca en büyük iki köke bakıyorum. Sonra iki yansımayı düşünüyorum: eğrinin altı/üstüne göre yansıma ve x eksenine göre yansıma. Bu en üstteki iki kök dejenere değilse, yansımayla elde edilen dört eğri kombinasyonundan ikisi en büyük reel köke, ikisi de en büyük sanal köke sahip gibi geliyor. Dejenereyse en büyük kök reeldir
    Bu yüzden (1) en büyük kökün reel olduğu durumların sanal olduğu durumlardan daha fazla olduğu ve (2) dejenere olmayan en büyük köke sahip eğriler dejenere olanlardan sonsuz derecede daha fazla olduğu için bu “üstünlüğün” yok olacak kadar küçük olduğu sonucuna varırdım
    Terminolojiyi neredeyse hiç bilmediğim belli oluyordur. Muhtemelen rastgele katsayıların tekdüzeliğinin uzayda tekdüze dağılıma yol açmadığı noktasını kaçırıyorum. Ya da yansımam koşullardan birini, örneğin reel katsayı koşulunu bozuyor olabilir. Ya da düpedüz yanlış olabilirim

    • Yansımadan ne kastettiğini tam anlayamadım. p(x) polinomunun grafiğini x eksenine göre yansıtmak, p(x)i p(-x)e çevirmek demektir. “Eğrinin altı/üstüne göre yansıma” ne demek? y eksenine göre yansıma mı? O zaman p(x)in -p(x)e dönüşmesi demek
    • Eğrinin altı/üstüne göre yansıma ne anlama geliyor?
      Kombinasyon derken muhtemelen (polinom + yansıtılmış polinom)/2 almak mı kastediliyor?

  • Reel olanın daha olası görünmesinin neden sezgiye aykırı olduğunu pek anlamıyorum
    Bir aralıktaki tekdüze rastgele reel katsayılar yerine, kompleks düzlemde orijin merkezli bir diskten tekdüze rastgele kökler seçip polinom oluştursaydık, reel katsayılı bir polinom elde etme olasılığı neredeyse hiç olmazdı. Tersine, rastgele kökler reelse polinom mutlaka reel katsayılara sahip olur. Dolayısıyla önsel olarak hiçbir cevap şaşırtıcı değil; reel olanın daha makul görünmesi bana biraz daha sezgisel geliyor. Elbette bu zorunlu değil

    • n dereceli bir polinomun n kökü vardır. Buna hem reel kökler hem kompleks kökler dahildir. Rastgele bir polinomda bunların kabaca log(n) tanesi reel kök, n - log(n) tanesi reel olmayan köktür
      n büyüdükçe log(n), n'ye göre çok küçük kalır; bu yüzden vakaların yarısından fazlasında en büyük kökün o çok az sayıdaki reel kökten biri olması oldukça şaşırtıcıdır

  • Buradaki bağlantıları takip ederken Boris Hanin'in yanıtlarından biri, bir süredir aklımda olan bir soruyu çözmüş gibi görünüyor

  • Bu arada rastgele polinom derken reel katsayılı mı, yoksa kompleks katsayılı mı merak ediyorum

    • Kompleks katsayılara izin verilirse dağılım kompleks düzlemde dönme simetrik olur. Bu yüzden herhangi bir kökün reel eksen üzerinde olma olasılığı, orijinden geçen başka herhangi bir doğru üzerinde olma olasılığından daha büyük değildir. En büyük kökü reel olan polinomlar neredeyse ortadan kaybolur
    • Soruda açıkça reel katsayılar deniyor. Deneysel olarak tekdüze dağılımda [-1, 1] aralığından rastgele katsayılar seçilmiş ve bir tür ölçeklenmiş normal dağılım da test edilmiş gibi görünüyor
    • Sorunun ilk satırında “real” yazıyor