Hey wouldn't {0000 through 1111} automatically contain every combination of {00 through 11} exactly twice?
I mean if you didn't overlap the bits.
I'm not sure what you mean exactly. The bitstream of 2^4*4 = 64 bits that goes like 00000001 ... 1111 obviously contains '00' more than twice, so perhaps I'm not understanding what you mean by overlapping the bits. That said, I think that you understand what is meant by the importance of balanced relative frequency.
I was just trying to figure out if generating some number random bits at a time that iterates through every possible sequence of a small number of bits, or if it might distribute the odds improperly. So if I generated 8 bit numbers I could place them into a stream and pull out 7 bit numbers and they would still be equally distributed inherently.
Doesn't matter so much now though - looking at NIST I'm working at imitating a long series of coin tosses instead of imitating something like a dice roll.
I have a question also!
How do I find the probably of a given distribution of runs?
Shouldn't each run is twice as common as a run one bit longer than it?
I think I know how to find the probability of any run in any stream - (a-b)/(2^b) where a is total length and b is run length, right?
I'm deriving a list of all of the runs and trying to catch distributions with bad p values. I'm trying to make sure that the bits imitate random coin tosses via run frequency.
So you should see 16 1bit runs,8 2bit runs,4 3bit runs, 2 4bit runs, and 1 5bit run in a sequence of 61 bits.
But when I get 15,9,3,1,1,1 how do I check if that's a really rare case?
God I really have to read that NIST documentation again...
Second Question!
If I test for p-values = 1 in 2^16 wouldn't that limit my legitimate randomness to 2^16 even if my period was much, much higher?
Because everything rarer than 1 in 2^16 wouldn't exist so everything more common than 1 in 2^16 would have to repeat, right?
Maybe with some offset like +1 version of the old sequence.
Or am I totally out to lunch on this one?
I'm just thinking how random could dice be if one only used rolls totaling 6, 7, or 8?
Because this is what I think of when I picture chopping the ends off of the Gaussian distribution.
I guess you could have every order of every type of 6, 7, and 8. And every repeat. Is that what happens?
Third Question!
If I had a sequence that I knew wasn't random, and I took every other bit out so that the new sequence was half as many bits as the original - if I did that could I still see the same patterns that were in the original non random sequence, or would it drastically reduce the odds of me catching a problem?
[size=1]Currently my PRNG simulates a crooked old man with gambling problems giving his associate a mean look and then flipping a coin while [size=1]Saturn[size=1] is in [size=1]Leo[size=1] over and over until I generate the right number of bits, but i have to say it runs kind of slow. And I think there's correlation between how often my jokes are bad and how often heads (1) comes up - which is currently every time.
Do you often think about how one measure gives no confidence in a statistic (ie. it's not really a statistic), two measures gives ultra low confidence, and a trillion trillion measures can give pretty great confidence?
Do you often think about how combinations and permutations can be enumerated?
Do you often think about how the sequence "[eqn]0 \rightarrow 1 \rightarrow 2 \rightarrow 3[/eqn]" is a cyclical orbit of period four if you repeat it over and over again? Do you often think about how this sequence is different from the sequence "[eqn]3 \rightarrow 2 \rightarrow 1 \rightarrow 0[/eqn]" and the sequence "[eqn]1 \rightarrow 2 \rightarrow 0 \rightarrow 3[/eqn]", etc? Do you often think about how each of these sequences can be identified by its own unique identifier, say, [eqn]S0,\;S1,\;S2,[/eqn] etc, and how the sequence of sequences that starts with "[eqn]S0 \rightarrow S1 \rightarrow S2 \rightarrow[/eqn] etc" is different from the sequence of sequences that starts with "[eqn]S2 \rightarrow S1 \rightarrow S0 \rightarrow[/eqn] etc", etc, and if you fully expand any one of these sequences of sequences and use it as a cyclical orbit by repeating it over and over, the cyclical orbit has a period greater than four even though you only have four basic symbols to work with? Do you often think of about how each of these sequences of sequences can be identified by its own unique identifier... blah blah blah... and so on and so forth, until the cows come home and you end up with the possibility of cyclical orbits of gargantuan period even though you only have four basic symbols to work with?
Do you often think about how the algorithm followed by a particular PRNG is constant/static? Do you often think about how when this constant algorithm spits out a particular sequence of numbers (ie. 2372829, then 96) that the constant algorithm often spits out a different sequence (ie. 2372829, then 723788) when the seed is different? Do you often think about how the hidden variables inside of the PRNG are responsible for this, and how they are initialized by the seed? Do you often think of the output of the PRNG as a sequence of positions on the number line (ie. position 2372829, then position 723788) and that this motion from position to position is affected by the positions of the hidden variables on the number line, and those hidden variable positions are often affected by their own positions and the position of the output, and how it's somewhat, kinda, loosely like a giant many-body physics simulation akin to real "orbits" where the laws of motion are the PRNG's constant algorithm? Do you often think about how Mersenne Twister is somewhat, kinda, loosely like a giant physics simulation with roughly 600+ bodies / hidden variables where the motion is very complicated and practically unpredictable (but not quite truly unpredictable, hence only pseudo-random, plus the hidden bodies / variables are only moved every 600+ rounds or so instead of every round, etc) to those who do not have access to the seed / hidden variable positions?
My terminology may not be perfect, but hopefully you get the basic idea.
If I had a sequence that I knew wasn't random, and I took every other bit out so that the new sequence was half as many bits as the original - if I did that could I still see the same patterns that were in the original non random sequence, or would it drastically reduce the odds of me catching a problem?
I can easily answer this one: After you take every other bit out the resulting sequence could be anything. It could be completely random or it could be completely deterministic, or anything in between.
Example: Consider a long sequence with the structure 0r0r0r0r0r0r0r0r0r0r0r..., where `r' represents a random bit. This sequence is obviously not random, since you can predict the correct value of the bit half of the time. If you take out the `r's you are left with a completely deterministic sequence, but if you take out the `0's you are left with a completely random sequence.
Consider a long sequence with the structure 0r0r0r0r0r0r0r0r0r0r0r..., where `r' represents a random bit. This sequence is obviously not random, since you can predict the correct value of the bit half of the time. If you take out the `r's you are left with a completely deterministic sequence, but if you take out the `0's you are left with a completely random sequence.
If I had intended on looking at both the rs and the 0s, just separately, could I catch every pattern? Because I want to make sure every nth bit passes the chi square and others. That not only is abababab random but aaaa and bbbb are random as well. This is because I plan to use as few bits as I need when I call the PRNG so it'll be more like a linear feedback shift register than one that generates a block of bits at random. It seems like a good idea to check these things. The only reason I'm asking is to see if I should check for patterns like aabbbaabbb and ababbababb. But maybe I'm reading too much into it.
Anyway, it'll be a while before I finish the code for the testing suite but if anyone's interested in peeking at it later on that'd be cool.
Anyway thanks again ya'll.
And Taby, funny you should mention that I was just looking to see if I could use the n-body problem as a PRNG lol. Or it's kind of like the good old pendulum on a pendulum trick so maybe that would be easier to compute. Oh, and strange attractors, right? Maybe xor a few together lol. Or xor the cube with every rotation of it and use a diagonal line of 8 bits. Inside a cube with relatively prime side lengths, and then you could take 8 points in a line - bounce around in a few of those and xor the results.
Might sound overly complicated but a simple abstraction seems apparent and might actually come up with something decently random. Maybe. I think it would apply to CSPRNG more because no one expected strange attractors to exhibit complex behavior.
[color=#ff0000]Oh and here's a god awful LCG I invented - one of many experiments:
n[sub]+1[/sub] = n*5 +1 mod 2^32
for which I use
(unchecked) n[sub]+1[/sub] = n + n<<2 +1
but I'm sure a compiler would optimize to that for you lol.
Has full period length, but is probably far from random and definitely not CSPRNG caliber.
And if you want to play with LCGs a bit, I'm pretty sure the 5 can be any prime number except 2 and done with bitshifting relatively fast and the 1 can be any odd number - maybe.
[color=#0000ff]But I have been thinking about using two LFSRs in conjuction with a LCG - not by xoring the bits like KISS or something, but by plugging in the LFSR results as the basis of the LCG
n[sub]+1[/sub] = n *a +b mod2^32
a is like a 6 bit LFSR, maybe + some number.
b is like a 26 bit LFSR, maybe + 2^6 or 2^6-1.
If the periods of each were relatively prime, they should have the maximum period. And I don't think the occasional non odd multiplier would cause a shortened period.
Might have a period as high as 2^63 or something. Computation wouldn't be too much and it might be cryptographically strong.
What do you guys think?
And Taby, funny you should mention that I was just looking to see if I could use the n-body problem as a PRNG lol. Or it's kind of like the good old pendulum on a pendulum trick so maybe that would be easier to compute. Oh, and strange attractors, right? Maybe xor a few together lol. Or xor the cube with every rotation of it and use a diagonal line of 8 bits. Inside a cube with relatively prime side lengths, and then you could take 8 points in a line - bounce around in a few of those and xor the results.
Nah, it doesn't follow a uniform distribution but some weird chaotic distribution (which makes it unusable for most purposes). Interesting idea though - there may exist a straightforward mapping between a specific chaotic distribution and the uniform distribution, but as far as I know none exists.
Note that chaotic systems are not exactly cheap to compute though, the pendulum on a pendulum system requires fourth order numerical integration (lots of floating-point operations). Another issue is portability - since chaotic systems are extremely sensitive on the initial conditions, two systems which handle floating-point computations differently (which is very common) will not produce the same output. This doesn't happen with integer-based algorithms since integer computation is very well defined.
“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”
Not to be huge stickler on details, but there are chaotic PRNGs that use integers entirely, of both full-blown n-body interaction type (ie. O(n^2) time complexity) and limited interaction type (ie. O(n) time complexity). A couple of integer-based chaotic PRNGs that I looked at were Trident and Trifork, which are kind of in-between O(n^2) and O(n). As for other chaotic PRNGs, I'm generally not a huge fan of those that simply XOR the results from a couple of single variable chaotic maps (ie. two logistic maps which are used to generate two bits that are subsequently XORed, where for each r = 4 is a constant, and x is a variable). Multiple variable maps are the only way to go, as far as I'm concerned. I'm also of the opinion that simply XORing like this should never be used as a security measure, since it's just security by obscurity, and that's not really security.
Of course, it's by definition true that a chaotic PRNG based on real numbers will behave differently even when switching between single and double precision.
Anyway, I'm not sure what's meant by "weird chaotic distribution", as if that automatically implies non-uniformity by default. I was under the impression that if a system is ergodic, it covers the phase space uniformly, by definition. I could be wrong. But yes, speaking of phase space, there are situations in a full-blown n-body simulation where temporary co-orbits are formed, and so patterns in the traversal of the phase space do pop up. Patterns in the traversal of the phase space are not a problem inherent to just chaotic PRNGs, but all PRNGS. It's part of the reason why they're only pseudo-random. Anyway, I got rid of that problem by using a forward-looking predictor-corrector that skips to a different part of the phase space several rounds before the co-orbits even form. Mind you, the PRNG was only a toy, not meant for cryptographic use by any means, and I guess you could say that I was excluding small parts of the phase space by choice. That said, the phase space was separate from the space representing the numbers being put out, so the skipping of parts of the phase space was not exactly the same thing as skipping parts of the output range.
Anyway, I'm not sure what's meant by "weird chaotic distribution", as if that automatically implies non-uniformity by default.[/quote]
I am not well-versed in the intricacies of real-valued PRNG's, so I cannot really say much there. But consider that while an ergodic system assures that the whole phase space will ultimately be traversed, it says nothing about *how* it is traversed - this is directly tied to the concept of variance, and a uniform distribution does have a well-defined variance. If your ergodic chaotic PRNG spends 90% of its time in 1% of its phase space, then quickly sweeps through the remaining 99% before resuming oscillation, then it does traverse the whole phase space, but is most definitely not uniformily distributed. I suppose some constructions can be designed to exactly match the variance of a uniform distribution, though. In the limit, sure, it is, but if I recall correctly the convergence time is absurdly high (exponential in the internal state size, iirc).
But I am not very familiar with those notions so don't quote me too much on it - I am more familiar with cryptography and number theory.
“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”
I think you know what you're talking about, and I'm pretty sure that what you're saying does apply to a whole lot of strange attractors even in the presence of full-blown chaos. That said, do consider that a gas in thermal equilibrium is chaotic and that such a gas was the very type of system that was used as the basis for statistical mechanics, information theory, etc, which are just fancy frameworks for studying the uniform / equi-distribution in question. Of course the phase space is not totally "uniform" at all times otherwise temperature would be a meaningless concept in general, so I probably mixed up state space and phase space there (dumb, I know). I admit that I could also be misinterpreting the ergodic hypothesis, and I apologize for that in advance if I am (I probably am), but I just don't think that it's so cut and dry as to say chaos cannot give the uniform distribution in question. That said, I am not very familiar with any mathematics (jack of all trades, master of none), and when I say "I could be wrong", it should be taken as meaning "I generally yearn for enlightenment, and if I'm wrong, please let me know because I will be thankful".
There's also a nice (if obvious) theorem, one of my favorites as it is extremely applicable and very simple to understand.
If you have a bijective function [eqn]f: \mathbb{S} \rightarrow \mathbb{S}[/eqn] on a finite set [eqn]\mathbb{S}[/eqn], then given any initial state [eqn]\lambda_0[/eqn], the periodic sequence [eqn]\lambda_{n + 1} = f(\lambda_n)[/eqn] will always include [eqn]\lambda_0[/eqn].
The proof is straightforward, here's a sketch leaving out the details - if the sequence did not include [eqn]\lambda_0[/eqn], then it must have reached a cycle at some point later in the sequence, [eqn]\lambda_p[/eqn], which implies that [eqn]f^{-1} (\lambda_p) = \lambda_{p - 1}[/eqn] must have been the previous term in the sequence. This implies that [eqn]f^{-1} (\lambda_{p - 1}) = \lambda_{p - 2}[/eqn] must have been in the sequence too, all the way down to [eqn]\lambda_0[/eqn]. Therefore [eqn]\lambda_0[/eqn] is in the sequence - we have reached a logical contradiction indicating the initial assumptions cannot be true, therefore the sequence must include [eqn]\lambda_0[/eqn].
Note that if the function [eqn]f[/eqn] is not bijective (i.e. cannot be inverted over [eqn]\mathbb{S}[/eqn]), then [eqn]f^{-1}[/eqn] is undefined and the theorem does not hold. However, a subtle point - it doesn't matter whether [eqn]f^{-1}[/eqn] can be feasibly computed or not - as long as it exists, the theorem holds (this is an important consideration in number-theoretic cryptography, as it comes up in the study of one-way functions, and notably trapdoor functions).
Here is an example: let [eqn]f(x) = (3x + 1) \mod 11[/eqn] - this is invertible because 3 is not divisible by 11 (so the inverse of 3 modulo 11 is defined). Let us choose some starting value, say [eqn]x = 3[/eqn]. Then we get the sequence 10, 9, 6, 8, and finally 3 again. Let's try with [eqn]x = 7[/eqn], we get 0, 1, 4, 2, and then 7 again. And finally, with [eqn]x = 5[/eqn], we just get 5 back again immediately. So there are three "loops" for this PRNG: we have 10, 9, 6, 8, 3, and we have 0, 1, 4, 2, 7, and then we have 5. So if we picked [eqn]x = 4[/eqn] as a starting value instead, we would have gotten 4, 2, 7, 0, 1.
Now if we tried with a non-invertible PRNG, say [eqn]f(x) = (4x + 2) \mod 16[/eqn] (4 and 16 are not coprime, so the inverse of 4 modulo 16 does not exist, the function cannot be inverted). Let's choose a starting value [eqn]x = 8[/eqn]. We get 2, 10, 10, 10... see what happened? The sequence collapsed into a tiny cycle of a single value. Note that it is possible for a non-invertible PRNG to still come up with the same initial state, purely by chance - the theorem above simply states that it must, if the mapping function is invertible.
This has applications in PRNG design and testing. If you design a feedback PRNG (which feeds on its output to produce more pseudorandom data, like linear congruential generators do), and if the PRNG's mapping function is invertible, you will always end up reaching the initial state again, regardless of the state you chose - this is interesting because it means you will never reach "dead ends" where the PRNG goes, 71, 45, 19, 41, 31, 19, 18, 19, 18, 19, ... and it also implies that if you wish to evaluate the PRNG's period empirically,you don't need to use a specialized cycle-finding algorithm - you only store the value you started with and stop when you reach it again! You just saved lots of work by simply observing your mapping is invertible.
Of course, this says nothing about how long the period actually is - many such cycles can coexist in the PRNG's domain (an extreme example is a PRNG with a mapping function that goes "add one if the state is odd, subtract one if the state is even" - clearly this is invertible, but the maximum period length is two, as the PRNG would go 44, 43, 44, 43, or 61, 62, 61, 62, ...). However a good way to ensure the PRNG has maximal period is to drop the feedback construction completely and instead build a random permutation. If you have an invertible function [eqn]f: \mathbb{S} \rightarrow \mathbb{S}[/eqn], then instead of the sequence above you output [eqn]f(0)[/eqn], [eqn]f(1)[/eqn], [eqn]f(2)[/eqn], ... traversing the full set [eqn]\mathbb{S}[/eqn]. Since [eqn]f[/eqn] is a bijection, the output is a bijection of [eqn]\mathbb{S}[/eqn]. If [eqn]f[/eqn] has good mixing properties, the result is a pseudorandom permutation of [eqn]\mathbb{S}[/eqn]. And if [eqn]\mathbb{S}[/eqn] is large enough, the bias due to the fact that it is impossible to get the same number out more than once converges to zero.
More specifically, if the PRNG's internal state is [eqn]n[/eqn] bits large, then in a truly random sequence of [eqn]n[/eqn]-bit integers, you would need a sequence of [eqn]2^\frac{n}{2}[/eqn] integers to have a 50% chance of a number coming up twice (birthday paradox) - this gives a distinguishing attack on the PRNG (i.e. differentiate it from a truly random output). Now let [eqn]n = 256[/eqn] (very modest size, many generators have [eqn]n[/eqn] in the four digits and some are extremely fast) - you would require [eqn]2^{128}[/eqn] integers to observe the bias. This is infeasible - problem solved.
An interesting way to get this working is to use a block cipher, which is by definition invertible (and also, conveniently parameterizable with a key, which can be treated as the PRNG's seed). Voila! You have a cryptographically secure pseudorandom number generator (or not - there are some gotchas to be aware of - for instance, this kind of construction delegates all of its security and quality properties to the underlying block cipher, this can also be an advantage since you can "plug in" well-reviewed algorithms and easily replace them when a weakness is found).
I don't know, I find it fascinating how you can start with such a simple observation and, with some work, draw such wide-ranging implications from it. We know so little...
A word of warning about PRNG testing - be careful with large internal states. As a rule of thumb, the bigger the internal state, the easier it is to produce a theoretically biased PRNG yet not realize it because of the sheer size of the internal state. A PRNG with a 4096-bit internal state can have an impossibly large bias reducing its entropy to, say, 128 bits, however it is still infeasible to actually observe the bias - too many bits. So it looks OK, but it really isn't, and you have no empirical way of knowing if your PRNG behaves well other than that flaw. This is why I prefer working with very small internal states (256 bits), it makes it easier to spot any blatant error. Also, if you make your PRNG's word size a parameter (allowing it to work on bytes, words, longwords, 64-bit integers, etc...), you can test for bias using a small internal state, and then extend the PRNG to a large internal state for real world use, with the advantage that most of the theoretical and empirical analysis carries over (but this is, by far, easier said than done).
Anyway this is more of an inspirational post, to give some more keywords and insight into pseudorandom number theory. I hope it will be found useful.
“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”
