On Tuesday, 2 May 2017 at 23:09:54 UTC, MysticZach wrote:
> On Tuesday, 2 May 2017 at 21:00:36 UTC, Timon Gehr wrote:
>> On 02.05.2017 22:42, MysticZach wrote:
>>> On Tuesday, 2 May 2017 at 13:44:03 UTC, MysticZach wrote:
>>>    for (;;) {
>>>       if (P(a[i]))
>>>          return i;
>>>       ++count;
>>>       if (count == length)
>>>          return -1;
>>>       i += hop;
>>>       if (i < length)
>>>          continue;
>>>       if (i < skipLength)
>>>          i += hop;
>>
>> (I guess this should be 'while'.)
>
> skipLength is determined modulo hop, thus it can't be more than one hop away.

Actually, I did botch the implementation. The hopping interval must be based on the prime rather than on n. But you could still short circuit the while loop, I think. `if (prime - n > hop) { skipLength = n + ((prime - n) % hop); }

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.)

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.

On Thursday, 4 May 2017 at 13:19:43 UTC, MysticZach wrote:
> On Thursday, 4 May 2017 at 08:04:22 UTC, Timon Gehr wrote:
>> On 03.05.2017 01:09, MysticZach wrote:
>>> 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.

Within a small range of error, I mean.

On Thu, May 04, 2017 at 01:19:43PM +0000, MysticZach via Digitalmars-d wrote: [...]
> 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.

Of course there is.  The random permutation approach works. In this case, the data itself is not allowed to be permuted, but equivalent semantics can be obtained by permuting an array of indices into the data. But the challenge is how efficiently you can generate a random permutation so that the cost of generating one doesn't outweigh the O(n) linear scan algorithm.

I'm surprised there are no (known) incremental algorithms for generating
a random permutation of 0..n that requires less than O(n) space.


T

-- 
Life is complex. It consists of real and imaginary parts. -- YHL

On Friday, 12 May 2017 at 18:43:53 UTC, H. S. Teoh wrote:
> I'm surprised there are no (known) incremental algorithms for generating
> a random permutation of 0..n that requires less than O(n) space.

I've told you all you need to know...