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.
