從離散分佈生成隨機數的算法？

設計一種快速算法反覆產生從離散分佈數：給定陣列的[]非負實數其總和爲1，其目標是爲i的概率返回指數[I]從離散分佈生成隨機數的算法？

我在一本在線算法書「Java編程入門」第4.2章：排序和搜索（http://introcs.cs.princeton.edu/java/42sort/）中發現了這個問題。

提示說：

形成陣列S []累積總和，使得S [i]爲的[]中的第i個元素的總和。現在，生成0到1之間的隨機實數r，並使用二分查找返回s [i]≤s [i + 1]的索引i。

我一些如何我無法理解的暗示，因此無法找到解決方案..

2012-04-08 learner

到目前爲止，您嘗試過哪些方法無效？請發佈您的代碼並解釋它如何不如預期的那樣工作，並且有人會很樂意幫助您瞭解如何解決此問題。不過，我們不只是爲你做你的工作 - 你需要做一些工作，先嚐試自己解決問題。 :) – 2012-04-08 16:28:25

可能重複[數據結構爲加載骰子？]（http://stackoverflow.com/questions/5027757/data-structure-for-loaded-dice） – templatetypedef 2012-04-08 16:35:59

呃，因爲'a []'是非負的，'s [i] <= s [i + 1]'對於所有'i'都是真實的。提示看起來不對。我認爲這意味着你必須返回第一個'i'，使得[s]> = r'。 – IVlad 2012-04-08 16:36:10

有很多方法來回答這個問題。 This article描述了許多方法，其優點，缺點和運行時間。它以一個算法爲結束，該算法需要O（n）預處理時間，然後在時間O（1）中生成數字。

您正在尋找的特定方法在「輪盤選擇」下進行了介紹。

希望這會有所幫助！

來源

2012-04-08 16:31:46 templatetypedef

這是來自wakkerbot/megalhal的片段。這裏的權重是（無符號）整數，它們的和在節點 - >子節點中。爲了獲得最大速度，孩子們按降序排列（或多或少）。（權重預計將有冪律狀分佈，只有少數高權重和許多較小的）

/* 
    *   Choose a symbol at random from this context. 
    *   weighted by ->thevalue 
    */ 
    credit = urnd(node->childsum); 
    for(cidx=0; 1; cidx = (cidx+1) % node->branch) { 
     symbol = node->children[cidx].ptr->symbol; 
     if (credit < node->children[cidx].ptr->thevalue) break; 
     /* 20120203 if (node->children[cidx].ptr->thevalue == 0) credit--; */ 
     credit -= node->children[cidx].ptr->thevalue; 
    } 
done: 
    // fprintf(stderr, "{+%u}", symbol); 
    return symbol;

來源

2012-04-08 16:49:27 wildplasser

根據不同的粒度，你可以創建100，1000或10000元的指數。假定一個分佈（A，B，C，d）其中p =（10％，20％，30％，40％），我們創建了一個地圖：

val prob = Map ('a' -> 10, 'b' -> 20, 'c' -> 30, 'd' -> 40) 
val index = (for (e <- prob; 
    i <- (1 to e._2)) yield e._1).toList 

index: List[Char] = List(a, a, a, a, a, a, a, a, a, a, 
b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, 
c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, 
d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d)

我們現在可以選擇所需概率的元素非常快：

val x = index (random.nextInt (100))

X現在是由40％d，由10％等。設置簡單，訪問速度快。

數字甚至都不需要總結到100，但你必須一次計算的範圍內，則：

val max = prob.map (_._2).sum 
val x = index (random.nextInt (max))

來源

2012-04-08 17:35:46

下面是一個Python算法，實現了「輪盤賭」技術。沒有圖表就很難解釋。通過templatetypedef鏈接到的文章應該很好。另外請注意，這個算法實際上並不需要權重被歸一化（它們不需要總和爲1），但是這仍然有效。

import random 

trials = 50 
selected_indices = [] 

# weights on each index 
distrib = [0.1, 0.4, 0.2, 0.3] 

index = random.randrange(0, len(distrib) - 1) 
max_weight = max(distrib) 
B = 0 
# generate 'trials' random indices 
for i in range (trials): 

    # increase B by a factor which is 
    # guaranteed to be much larger than our largest weight 
    B = B + random.uniform(0, 2 * max_weight) 

    # continue stepping through wheel until B lands 'within' a weight 
    while(B > distrib[index]): 
     B = B - distrib[index] 
     index = (index + 1) % len(distrib) 
    selected_indices.append(index) 

print("Randomly selected indices from {0} trials".format(trials)) 
print(selected_indices)

來源

2012-04-08 19:45:59

從離散分佈生成隨機數的算法？

回答

相關問題