Jump vs. seed

[tuom....@gmail.com]

Hi!

If I understand correctly, the purpose of a jump function is to divide the continuum of starting points into known chunks so that parallel generators generate non-overlapping sequences of values, correct? For example, for 256-bits state generator, the jump (or long jump) create 128-bits (192-bits) chunks.

If I seed the (256-bits) generator with SplitMix using just one 64-bits number (generating 4 values with it), how well does it distribute the starting points of the generator? I mean, after how many steps at minimum would two parallel generators start to overlap?

On one hand, I would say that if the 64-bits seed "spreads" over 256-bits state, then it should be pretty well-spaced out, so for most practical usage it could be used instead of jump function as one would expect the starting points are pretty far apart. On the other hand, perhaps birthday paradox brings some two starting points too close to each other?

Thank you for any feedback!

[Sebastiano Vigna]

> On 29 May 2020, at 08:38, tuom....@gmail.com wrote:
>
> Hi!

>
> If I seed the (256-bits) generator with SplitMix using just one 64-bits number (generating 4 values with it), how well does it distribute the starting points of the generator? I mean, after how many steps at minimum would two parallel generators start to overlap?

There's no way to know analytically. If you assume that they spread randomly, as you say, you can use the formula here:

https://www.sciencedirect.com/science/article/abs/pii/S0020019020300260

The formula is exact and complicated, but you can use the upper bound n²L/P, where L is the length of the sequences, n the number of sequences and P the period. If you use 2^64 sequences of length 2^64, the probability of overlap is 2^-64. I'd say your safe (under the assumption, unprovable, that the initialization generated by SplitMix "looks random").

Ciao,

seba