[OT] Algorithm question

[Timon Gehr via Digitalmars-d]

On 03.05.2017 01:09, MysticZach wrote:
>
>
>> Counterexample: [1,1,1,0,0]
>>
>> Your algorithm returns 0 with probability 7/20, 1 with probability
>> 6/20 and 2 with probability 7/20.
>>
>> Note that there is a simple reason why your algorithm cannot work for
>> this case: it picks one of 20 numbers at random. The resulting
>> probability mass cannot be evenly distributed among the three
>> elements, because 20 is not divisible by 3.
>
> That's true. Two points, though: If the range of error is within
> 1/(n*(n-1)), with array length n,

It's not though. For example, [1,1,1,0,...,0] (length 29), you get 0 and 
2 each with probability 43/116, but 1 only with probability 30/116.

It might be interesting to figure out how far from uniform the 
distribution can get.

> it may be close enough for a given
> real world use case. 2. n is known to be large, which makes 1/(n*(n-1))
> even smaller.  You'd probably have to trade accuracy for performance. I
> wonder how much less performant a truly accurate algorithm would be.
> Also, whether there's a way to make an algorithm of this style
> completely accurate.

For an accurate algorithm based on (unconditional) uniformly random 
sampling, the number of outcomes from sampling needs to be divisible by 
all numbers from 1 to n. (Because each of those could conceivably be the 
number of elements satisfying the predicate.)