Select 从具有给定概率的数组中随机抽取，无需替换

Question

假设我有一个项目数组 [1,2, ...n] 和一个概率数组 [p1,p2,....,pn]，其中 n 是一个非常大的数字，可能达到数千。所有概率之和等于1.

我每次需要随机select3个独特的物品，概率高的物品被selected的几率更高。
我需要做select离子超过2万次。

我已经实现了一种工作方法，方法是创建一个新数组，其中包含根据概率重复的项目。例如，如果 item1、item2 和 item3 的概率分别为 [2/n,4/n,1/n]，则新数组将包含 [1,1,2,2,2,2,3].

它工作正常但效率不高。另外，使用这种方法有可能 select 多次使用同一个项目，然后我必须重新 select 另一个消耗时间的项目。

MATLAB 中是否有用于此目的的有效方法或内置函数？

Answer 1

你的初始数组

 x = [1, 2, 3];   % 1:n, where n = 3
 p = [2, 4, 1]/7; % probabilities of choosing each element

您可以使用以下方法以给定的概率选择一个元素：

 r = rand; % get random number in range (0,1)
 xi = x(find(cumsum(p) >= r, 1)); % Get x where cumulative probability >= random number

你想选择不放回，所以我们每次循环去掉元素

k = 2;           % number of choices
r = rand(k,1);   % random numbers
xi = zeros(k,1); % output choices
for ii = 1:k     % choices loop
    % Choose x with probability of each element contained in p
    idx = find(cumsum(p) >= r(ii), 1);
    xi(ii) = x(idx);
    % Remove item from lists
    x(idx) = []; p(idx) = [];
    % Rescale probabilities
    p = p/sum(p);
end

使用此方法，重复的 x 个条目将被视为独立的，相对于它们自己指定的 p 个值。

注意：如果你想做这个选择 N 次然后使用一些临时的 x 和 p 变量，这样下次你做选择时你没有删除了一些元素！或者更好的是，将选择循环矢量化并将 x 和 p 变为 N×n，每次从每一行中删除一个元素。

Answer 2

如果您将函数 datasample 与可选参数 Weights 一起使用，然后将其与权重数组一起使用，则函数 datasample 会执行您的要求。

注：datasample使用旧函数histc生成样本，推荐使用新函数histcounts。如果你想要更高的效率，这只是一个问题。引用文档：

histc is not recommended. Use HISTCOUNTS instead.

Select 从具有给定概率的数组中随机抽取，无需替换

Select randomly from array with given probabilites without replacement

random

matlab

probability