从具有给定概率的阵列中随机选择而不进行替换

userInThisWorld 发表于 Dev

userInThisWorld

假设我有一个item[1,2, ...n]数组[p1,p2,....,pn]，一个probability array ，其中的n个数很大，可能达到数千个。所有概率的总和等于1。

我每次需要随机选择3个唯一的项目，一个可能性较高的项目被选择的可能性更高。
我需要进行超过2万次的选择。

我通过创建一个新的数组实现了一种工作方法，该数组包含基于项目概率的重复项。例如，如果item1，item2和item3的概率[2/n,4/n,1/n]分别为，则新数组将包含[1,1,2,2,2,2,3]。

它工作正常，但效率不高。同样，使用这种方法有可能多次选择同一项目，然后我不得不重新选择另一个耗时的项目。

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

沃尔菲

您的初始数组

 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变量，以便下次进行选择时，不会删除某些元素！甚至更好，vectorise选择循环，使x和p成N×n，从各行每次移除元素。