For example, let's say there is a array of items each equally likely to be chosen, and the output of this random function will tell which item to be chosen, but I want the function to be split into multiple steps so that along each step the list of potential items is narrowed in giving better insight on the result probabilities.

Here's a step by step example of how it might work:

Step 1: Every item is 1/1000 chance.

Step 2: Random subset of half the original set is removed, so each remaining item is 1/500 now.

Step 3: Repeat step 2 until narrowed down to a single item.

The requirements I'd like for the algorithm is < O(n) time complexity and at each step the distribution is still uniformly random.

Initially I though to have an algorithm which:

1. Start with variables min and max describing the current range of values left.
2. Shrink the range by generating random float number between [-1, 1] which is applied to the range to shrink it proportionally. If random number is negative then lower the max, otherwise raise the min. So 50% of the time it is shifting the min up, and shifting the max down, and the range is shrinking by a factor between [0,1].
3. Repeat 2. until range converges on a single number.

But I noticed this doesn't have a uniform distribution, and instead it is more common for the chosen result to be closer to starting min and max values. So to fix this I think one could add a preliminary step where the starting range is offset by another random value. But this would only fix in making the starting distribution uniformly random, and it still doesn't fit my requirement of making it uniformly random at every step.

The naive solution is to generate random numbers and remove those from the list until at each step, but that is a O(n) solution so I hope there is something better.

CodePudding user response：

You just have to apply Bayes' Theorem.

If you randomly remove a portion p of the remaining possibilities, the remaining items have their probabilities multiplied by 1/(1-p). So in your step 2, the probabilities change by an amount corresponding to how much the range changed. And not by a fixed factor.

CodePudding user response：

This problem has some very simple answers so maybe that is why people seemed confused.

One solution is to generate a random number between [0,n] where n is the number of items in the current set, and instead of just removing it, you remove a range of items around that point.

Solution two is a bit more complicated but has the property of preserving set order location such that the resulting set is just a spliced section of the original set, wheras the first solution's resulting set could be made of up multiple sections of the original set. The method here is as described initially in my post, but you also apply the random offset during each turn, not just once at the beginning.