Sözde Rastgele Sayı Üreteçleri
Sözde rastgele sayı üreteci, bir başlangıç tohumundan (seed) yola çıkarak, birim aralıktaki tekdüze dağılımdan bağımsız çekilişleri taklit eden uzun, tekrarlanabilir bir sayı dizisi üreten deterministik bir tekrarlamadır.
Tanım
Sözde rastgele sayı üreteci, bir durum (state), durumu ilerleten bir geçiş fonksiyonu ve her durumu bir sayıya eşleyen bir çıktı fonksiyonu ile tanımlanan bir algoritmadır; bu algoritma, tekdüze rastgele sayılardan istatistiksel olarak ayırt edilemez olması amaçlanan periyodik bir dizi üretmektedir.
Kapsam
Bu konu, tekdüze üreteçlerin (doğrusal uyumlu, gecikmeli-Fibonacci, genelleştirilmiş geri beslemeli kaydırma yazmacı ve birleşik üreteçler) yapısını, periyot uzunluğu ve kafes veya eşdağılım davranışı gibi kalitelerini belirleyen yapısal özelliklerini ve bunları doğrulamak için kullanılan ampirik ve teorik testleri kapsamaktadır. Kriptografik olarak güvenli üreteçler, yalnızca zıt bir tasarım hedefi olarak belirtilmektedir.
Temel sorular
- Hangi tekrarlamalar uzun periyotlar ve iyi yüksek boyutlu tekdüzelik sağlamaktadır?
- Bir üretecin kalitesi, kafes yapısı ve eşdağılımı ile nasıl ölçülmektedir?
- Hangi ampirik test bataryaları rastgelelikten sapmaları tespit etmektedir?
- Üreteçler, periyodu uzatmak ve istatistiksel özellikleri iyileştirmek için nasıl tohumlanmakta (seeded) ve birleştirilmektedir?
Anahtar kavramlar
- Tohum (Seed) ve durum (state)
- Periyot uzunluğu
- Eşdağılım
- Kafes yapısı
- Spektral test
- Birleşik üreteçler
Temel kuramlar
- Doğrusal tekrarlamalı üreteçler
- Doğrusal uyumlu ve kaydırma yazmacı tekrarlamaları, bir tam sayı durumunu modüler aritmetik ile ilerletmektedir; bunların periyotları ve ardışık çıktıların kafes yapısı, çarpanın ve modülün sayı teorik özellikleriyle belirlenmektedir.
- Eşdağılım ve Mersenne Twister
- Bükülmüş genelleştirilmiş geri beslemeli kaydırma yazmaçlarına dayalı üreteçler, birçok boyutta muazzam periyotlar ve kanıtlanabilir eşdağılım sağlamakta, bu da onları istatistiksel simülasyonlar için yaygın olarak benimsenen bir varsayılan haline getirmektedir.
Klinik önem
Bir istatistiksel paketteki varsayılan üreteç, ürettiği her simülasyon, bootstrap ve Monte Carlo sonucunun tekrarlanabilirliğini ve geçerliliğini belirlemektedir; periyot ve eşdağılımı anlamak, uygulayıcıların gizli düzenlilikleri yüksek boyutlu simülasyonları bozabilecek üreteçlerden kaçınmasına yardımcı olmaktadır.
Tarihçe
Lehmer, 1949'da doğrusal uyumlu yöntemi önermiştir; daha sonraki analizler, kötü seçilmiş parametrelerin kafes kusurlarını ortaya çıkarmış, bu da spektral testi, birleşik üreteçleri ve nihayetinde 1998'deki Mersenne Twister gibi uzun periyotlu eşdağılımlı tasarımları teşvik etmiştir.
Öne çıkan isimler
- Donald Knuth
- Pierre L'Ecuyer
- Makoto Matsumoto
- Derrick Henry Lehmer
İlgili konular
Temel eserler
- knuth1997
- matsumoto1998
Sıkça sorulan sorular
- Bir sözde rastgele üreteci diğerinden daha iyi yapan nedir?
- İyi bir üreteç çok uzun bir periyoda sahiptir, çıktılarını birçok boyutta bile tekdüze dağıtır, standart istatistiksel test bataryalarını geçer ve hızlı ve tekrarlanabilir özelliktedir. Kötü üreteçler kısa periyotlara veya simülasyonları yanlı hale getirebilecek görünür kafes desenlerine sahip olabilmektedir.
- Tohum (seed) neden önemlidir?
- Tohum, başlangıç durumunu sabitlemektedir, bu nedenle tüm dizi onun tarafından belirlenmektedir. Tohumu kaydetmek, bir simülasyonu tam olarak tekrarlanabilir kılarken, tohumları dikkatsizce seçmek paralel çalıştırmalar arasında çakışan veya ilişkili akışlara neden olabilmektedir.