Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have an application that wants controllable random functions from $\mathbb{Z}^2$ and $\mathbb{Z}^3$ to $2^{32}$ , where by controllable I basically mean seedable by some parameters (say, on the order of 3 to 5 32-bit integers) such that the same seeds will always produce the same functions. The most obvious way of doing this (for the two-dimensional case, say) would seem to be computing the value at some point $(x,y)$ by using $x$, $y$, and the seed parameters as seeds for something like an LFSR generator or a Mersenne Twister, then running the RNG for some fixed number of steps and taking the resultant value as the value of the function at that point.

My question is, how can I be certain that this procedure won't keep too much correlation between adjacent 'seed points', and is there either a straightforward analysis or even just some general guideline for how many iterations would be necessary to eliminate that correlation? My first back-of-the-envelope guess would be that each iteration roughly doubles the decorrelation between given seed values, so that 32 iterations would be necessary to achieve the requisite decorrelation over a range of $2^{32}$ values (and in practice I'd probably double it to 64 iterations), but that's strictly a guess and any proper analysis would be welcome!

Edited for clarification: To further outline the issue, I may be sampling this random function $f$ (for some given seed parameters) at arbitrary values, and need those samples to be identical between passes; so for instance, if a first application computes $f(0, 0)$, $f(437, 61)$, $f(-23, 129)$, and then $f(5,3)$, and a second (potentially concurrent) application computes $f(1,0)$ and then $f(5,3)$, both passes need to find the same value of $f$ at $(5,3)$. I may also be sampling $f$ at arbitrary points, so I'd like the evaluation to take constant time (and in particular, evaluating $f(x,y)$ shouldn't take time linear in $x+y$).

share|improve this question
    
Just so I understand your question correctly: you have an integer lattice/grid, and you want to associate with each point in the grid a pseudorandom number? Why would you have to cycle the PRNG for each point in the grid? That sounds like an excellent way to easily exhaust the period of your PRNG if your grid is fine enough. –  J. M. Aug 5 '10 at 1:19
    
I may be sampling the grid at random positions (so I don't want to pre-compute and store all the values for the grid) but want to avoid potential correlation between adjacent points. –  Steven Stadnicki Aug 5 '10 at 3:36
1  
I'm missing your point: if you're Monte Carlo sampling your grid anyway, why is it so important that separate instances of the sampling should associate the exact same pseudorandom number to the exact same grid point? You shouldn't have to worry about correlation if your PRNG has a sufficiently long period anyway. –  J. M. Aug 6 '10 at 0:36

2 Answers 2

up vote 1 down vote accepted

Note that when an LFSR is used to generate a sequence of +1 / -1 values, the correlation between that sequence and any time-shifted version of that sequence is near zero: (sum from i = 0 to N-1 of a[i]a[i+k]) is either N if k is a multiple of N, or -1 otherwise.

The initial state of an LFSR has a one-to-one mapping to the time shift -- this is analogous to a discrete logarithm problem in Galois fields; given a time shift k, it's easy to find the initial state of an LFSR (O(log(k), I think, as it's just computing exponentiation in the appropriate Galois field), but given the initial state of an LFSR, it's hard to find the time shift k in anything shorter than O(k). So your PRNG could be an LFSR with very long period e.g. 64 bits or greater, and the "seed" could be a time shift used to derive a different initial state.

As far as 2- or 3- or k-dimensional mapping, interleave the bits of the coordinates, and use a hash function to map those bits to an integer for use in deriving LFSR seeds.

I'm not sure what kind of correlation you're looking to avoid between functions. (e.g. correlation in a statistical sense, or cryptographic independence e.g. one PRNG cannot be used to predict future output of another).

share|improve this answer
    
could anyone help me convert the sum formula to jsmath or tex or whatever we use on this website? –  Jason S Aug 5 '10 at 11:37
    
If I understand your suggestion right, then the problem with using X/Y for shift values is that it makes the generation of values f(x,y) take time linear in x+y - I'd like it to be constant for any given x/y. I'll clarify the question above. –  Steven Stadnicki Aug 5 '10 at 17:55
    
? why linear in x+y? Read again. Timeshifts can be precomputed as exponentiation in Galois fields. –  Jason S Aug 6 '10 at 13:03
    
...and do you want it to be a large constant time or a small constant time? (how fast does each # have to be, compared to, say, MD5 calculation?) –  Jason S Aug 6 '10 at 13:04

This does not strictly answer your question, but might be too long for a comment. =)

I believe you should rethink your approach. Most random number generators are designed to be seeded once, and than return a sequence of "random" numbers, as close to independent and uniformly distributed as possible. I don't think that there are many results about the correlation of the 64th sequence element for different seeds.

Also, (at least in the implementations I know) the period of the algorithm is a lot longer than the number of possible seeds. If you have to reuse seeds in your case, you could introduce correlations that are avoidable.

Instead of precomputing the entire grid, you could get a random value just-in-time and store it for future reference, saving memory if you don't access every node.

share|improve this answer
    
The problem is that I'd like to use the same random function for different runs where it won't always get sampled in the same order; e.g., if pass 1 samples my random f(x,y) at (100, 10), (-20, 5), and (5, 3), it should get the same result for f(5,3) as a second run that samples f at (0, 0) and (50, 20), then (5, 3) - and because runs may happen in arbitrary order or even in parallel, I can't cache values. I'll try and clarify the Q above. –  Steven Stadnicki Aug 5 '10 at 17:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.