Java 中的加权随机概率

Question

我有一个适应度值（百分比）列表，它们按降序排列：

List<Double> fitnesses = new ArrayList<Double>();

我想从这些 Doubles 中选择一个，它极有可能是第一个，然后降低每个项目的可能性，直到最后一个接近 0% 的机会成为最后一个项目列表。

我该如何实现这一目标？

感谢您的任何建议。

Answer 1

如果你想 select "one of these Doubles, with an extreme likelihood of it being the first one, then decreasing likelihood for each item, until the final one is close to 0% chance of it being the final item in the list" 那么你似乎想要一个指数概率函数。 (p = x²).

但是，只有编写解决方案并尝试过后，您才会知道自己是否选择了正确的函数，如果它不适合您的需求，那么您将需要选择其他概率函数，例如正弦函数(p = sin( x * PI/2 )) 或反比 (p = 1/x).

因此，重要的是根据概率函数为select编写一个项目的算法，这样您就可以尝试任何您喜欢的概率函数。

所以，这是一种方法。

注意以下几点：

我将 10 作为随机数生成器的种子，以便始终产生相同的结果。删除播种以在每个运行.
我正在为您的 "percentages" 使用 Integer 的列表以避免混淆。一旦您了解其工作原理，请随意替换为 Double 的列表。
我提供了一些样本概率函数。试试看它们产生的分布。

玩得开心！

import java.util.*;

public final class Scratch3
{
    private Scratch3()
    {
    }

    interface ProbabilityFunction<T>
    {
        double getProbability( double x );
    }

    private static double exponential2( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return StrictMath.pow( x, 2 );
    }

    private static double exponential3( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return StrictMath.pow( x, 3 );
    }

    private static double inverse( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return 1/x;
    }

    private static double identity( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return x;
    }

    @SuppressWarnings( { "UnsecureRandomNumberGeneration", "ConstantNamingConvention" } )
    private static final Random randomNumberGenerator = new Random( 10 );

    private static <T> T select( List<T> values, ProbabilityFunction<T> probabilityFunction )
    {
        double x = randomNumberGenerator.nextDouble();
        double p = probabilityFunction.getProbability( x );
        int i = (int)( p * values.size() );
        return values.get( i );
    }

    public static void main( String[] args )
    {
        List<Integer> values = Arrays.asList( 10, 11, 12, 13, 14, 15 );
        Map<Integer,Integer> counts = new HashMap<>();
        for( int i = 0;  i < 10000;  i++ )
        {
            int value = select( values, Scratch3::exponential3 );
            counts.merge( value, 1, ( a, b ) -> a + b );
        }
        for( int value : values )
            System.out.println( value + ": " + counts.get( value ) );
    }
}

Answer 2

这是另一种方法，它使您能够近似任意权重分布。

传递给WeightedIndexPicker的数组表示应该分配给每个索引的"buckets"（>0）个数。在你的情况下，这些将是下降的，但它们不一定是。当你需要一个索引时，选择一个介于 0 和桶总数之间的随机数和 return 与该桶关联的索引。

我使用了 int 权重数组，因为它更易于可视化，并且避免了与浮点数相关的舍入误差。

import java.util.Random;

public class WeightedIndexPicker
{   
    private int total;
    private int[] counts;
    private Random rand;

    public WeightedIndexPicker(int[] weights)
    {
        rand = new Random();

        counts = weights.clone();       
        for(int i=1; i<counts.length; i++)
        {
            counts[i] += counts[i-1];
        }
        total = counts[counts.length-1];
    }

    public int nextIndex()
    {
        int idx = 0;
        int pick = rand.nextInt(total);
        while(pick >= counts[idx]) idx++;
        return idx;
    }

    public static void main(String[] args)
    {
        int[] dist = {1000, 100, 10, 1};

        WeightedIndexPicker wip = new WeightedIndexPicker(dist);        
        int idx = wip.nextIndex();

        System.out.println(idx);
    }
}

Answer 3

我认为您不需要所有这些代码来回答您的问题，因为您的问题似乎更多地是关于数学而不是代码。例如，使用 apache 公共数学库获取分布很容易：

ExponentialDistribution dist = new ExponentialDistribution(1);
// getting a sample (aka index into the list) is easy
dist.sample();
// lot's of extra code to display the distribution.
int NUM_BUCKETS = 100;
int NUM_SAMPLES = 1000000;

DoubleStream.of(dist.sample(NUM_SAMPLES))
    .map(s->((long)s*NUM_BUCKETS)/NUM_BUCKETS)
    .boxed()
    .collect(groupingBy(identity(), TreeMap::new, counting()))
    .forEach((k,v)->System.out.println(k.longValue() + " -> " + v));

但是，正如您所说，数学库中有这么多 种可能的分布。如果您正在为特定目的编写代码，那么最终用户可能希望您解释为什么选择特定的发行版以及为什么按照您的方式为该发行版设置参数。这是一道数学题，应该在数学论坛上提问。

Java 中的加权随机概率

Weighted-random probability in Java

java

probability