Belirtilen ayrık dağıtımdan rasgele bir sayı nasıl oluşturulur?

Question

Sonlu sayıda olası sonuç ile belirli bir dağılıma sahip olduğumuzu söylersek, bu dağılımdan rasgele bir sayı üretmek O (logn) değerinden daha hızlı olabilir, burada n sayı olası sonuçtur?

O bunu yapmak için nasıl (logn):
- (rastgele sayı i için daha az ya da buna eşit olacak Dizi [i] = Olasılık) kümülatif olasılıklı bir dizi yapmak
- rasgele sayı oluşturmak tekdüze dağılım (k ile gösterelim)
- En küçük olanı bulun, böylece k < Array [i]. İkili arama kullanılarak yapılabilir.
- i rastgele sayıdır.

Answer 1

Yürütmenin takma adı yöntemi, önceden hesaplanması gereken bazı boyuttaki yardımcı dizileri kullanarak, en kötü sürekli durumda örnek oluşturabilir. Bu yöntem, Devroye's book on sampling Bölüm 3'te açıklanmıştır ve R sample() işlevinde uygulanır. R'nin kaynak kodundan veya this thread'dan kod alabilirsiniz. Bir 1991 paper by Vose, başlatma maliyetini düşürdüğünü iddia ediyor.

Girişin tam formunu ve kaç tane rasgele sayı çizmek istediğinizi belirtmedikçe sorunuzun iyi tanımlanmadığını unutmayın. Örneğin, giriş her bir sonucun olasılığını veren bir dizi ise, o zaman algoritmanız O (log n) değildir, çünkü ilk önce giriş dizisinden O (n) zaman alan kümülatif olasılıkları hesaplamalıdır. Çok sayıda örnek çizmeyi düşünüyorsanız, tek bir örnek oluşturma maliyeti çok önemli değildir. Bunun yerine önemli olan, m sonucu üretmek için gereken toplam maliyet ve gereken en yüksek bellek. Bu bağlamda, takma ad çok iyi. Örnekleri bir kerede üretmek istiyorsanız, here numaralı O (n + m) algoritmasını kullanın ve ardından sonuçları karıştırın.