[OT] Algorithm question

[MysticZach via Digitalmars-d]

On Thursday, 4 May 2017 at 08:04:22 UTC, Timon Gehr wrote:
> 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.

Or how close it can get, depending on the range of intervals 
used. My math skill is shaky here.

Maybe there's no way to deterministically jump to every element 
of an array with equal probability of hitting any given element 
satisfying a given predicate first. It sure would be cool if 
there were.