6 ms·

From the abstract: "A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from unif

• gvb 13y ago
  Not all deterministic algorithms with uniform distributions are PRNGs.
  • buo 13y ago
    I know that, but that is what the first sentence in the paper's abstract is claiming. As I said, I think it's wrong.
    • paddyoloughlin 13y ago
      Breaking Bad is a TV show. American Idol is also a TV show. However, Breaking Bad is not American Idol.
    • gvb 13y ago
      A dog is a mammal, but not all mammals are dogs. The paper states "[a] pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform." You are asserting the converse, that all deterministic algorithms with uniform distributions are PRNGs.
• syzo 13y ago
  you can also check that (1,1), (1,2), (2,1), and (2,2) all happen with expected frequencies (i.e. roughly 25%), where the two numbers in the pair are just two numbers in a row in the sequence. You would have gotten 100% (1,2) and 0% for the rest, so that's suspicious. same for 3-tuples, 4-tuples, ..., and n-tuples. There's probably other, more sophisticated tests as well, but I'm not an expert.
  • buo 13y ago
    I think you missed my point, which is this: the first sentence in the paper's abstract is wrong.
    • syzo 13y ago
      My examples with pairs and n-tuples are also distributions.
      • buo 13y ago
        That's a good point, and that may well be what the authors meant. Since all PRNGs are periodic (at least all I now of), the definition eventually breaks down. I can see how it can be made to work with a bit of extra formalism, though. Thanks.
        • jameshart 13y ago
          Any finite state PRNG has to be periodic. Good luck implementing an infinite state one.
• phaemon 13y ago
  Nope, because you don't have the same number of 9s and 8s as 1s and 2s, so it's not uniform.
  • buo 13y ago
    I don't think you're correct. A discrete distribution can be defined for any number of values. Linux, which is the subject of the paper, uses a discrete distribution too.
    • phaemon 13y ago
      Ok, that's fine, you just want to use 1s and 2s (though it would have been more obvious if you'd just used 0s and 1s :) ). In that case, you don't have as many 11s and 22s as 12s and 21s (I'm ignoring the commas since they're irrelevant).
      • deleted 13y ago
        [deleted]
• mcherm 13y ago
  No, your sequence IS distinguishable from a uniform sequence. At least it is if I understand what you mean by "...". If you mean that it generates 1,2,1,2,1,2,1 and then after that generates a mix of different values that include all possible values in approximately equal frequency, then you may have a fairly good PRNG. If you mean that it produces 1,2,1,2,1,2,1 and then after that it continues to alternate between 2 and 1, then this is easily distinguished from uniform.
  • buo 13y ago
    But I never said it was indistinguishable. What I'm saying is that the definition in the first sentence of the paper is wrong or, at least, incomplete.
    • jerf 13y ago
      "whose distribution is indistinguishable from uniform" Emphasis mine. Distribution here is not its English meaning, it is referring to the statistical term. Thus, it is talking about numbers "drawn from the uniform distribution", not "uniform numbers". A PRNG drawing from the uniform distribution may produce that sequence (for any set that includes 1 and 2), but a PRNG that only produced that sequence would certainly not be drawing from the uniform distribution.
    • moocowduckquack 13y ago
      Perhaps you don't understand the terms in context. If you looked at the distribution of your example, it would have two big spikes in it, at numbers one and two.
  • pmelendez 13y ago
    >"No, your sequence IS distinguishable from a uniform sequence." No, it is not distinguishable. The definition according to wikipedia: The discrete uniform distribution is a symmetric probability distribution whereby a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n. So the distribution is indeed uniform but it fails in being random.
• andrewcooke 13y ago
  you're quoting the first sentence from the abstract in isolation; there's a lot more detail in the paper. in particular the define the notion of epsilon-closeness (section 2) for any distinguisher (which could include one that detects repeated patterns).
  • buo 13y ago
    My intention is not to criticize the paper, which I don't even claim to understand. I just thought the authors definition of a PNRG is wrong (or at least incomplete) and that caught my attention. If I'm wrong, I hope somebody will set me right.
    • andrewcooke 13y ago
      i just did. (1) an abstract is just a sketch of the entire paper contents. (2) in section 2 of the paper they give a more precise meaning to indistinguishable which allows you to use any function you can think of to detect non-uniformity (roughly - there are details like it's a limit as you go to large sequences, so that any finite random pattern becomes progressively less likely, etc etc). so you can cover the case you are worried about by using a test that looks for repeated patterns of values. [more generally, even with hn as it is these days, if you're asking for clarification rather than raising an objection, then you should probably prefix your comment with something like "i don't understand the paper, can someone please understand why...".]
      • buo 13y ago
        Thanks.
      • pmelendez 13y ago
        >"(1) an abstract is just a sketch of the entire paper contents." That is not an excuse for containing a bogus definition without a warning, especially in the abstract which is the first thing that you read to tell if the paper is interesting enough to look it in depth.
• manulp 13y ago
  This sequence is trivially distinguishable from something uniform.
• deutronium 13y ago
  Using ent, and 0's and 1's (instead of 1's and 2's). (By this I mean a pattern of 0,1,0,1 bits etc. - 4248759 bytes worth in this case) Below is the output from ent: ---------------------------- Entropy = 0.000000 bits per byte. Optimum compression would reduce the size of this 4248759 byte file by 100 percent. Chi square distribution for 4248759 samples is 1083433545.00, and randomly would exceed this value less than 0.01 percent of the times. Arithmetic mean value of data bytes is 170.0000 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is undefined (all values equal!).
• bmm6o 13y ago
  I don't think people understand what your point is. What do you think is missing from the sentence? An explicit mention of independence? Why do you think 1,2,1,2,1,2,... is indistinguishable from uniform? In another response you said > But I never said it was indistinguishable which is confusing in context. What properties do yo claim your sequence has?
  • buo 13y ago
    I'm sorry for being unclear. The authors define a a PRNG as a sequence such that, if you find its distribution (histogram), it resembles the uniform distribution (all values appear the same number of times). In 1,2,1,2,1,2,..., all values appear the same number of times and its histogram is uniform. However, it is not random. It is clearly not random -- so it is distinguishable from a uniform "true random" sequence, which was my point. However, as was explained to me by another commenter, what I missed is that you may group a number of consecutive numbers together and find the histogram of that, and, in that case, my sequence fails to have a uniform histogram. So, at this point I'm willing to accept that the author's definition is correct and I just had a hole in my understanding.
    • bqe 13y ago
      Are you missing the point of a limit? As t->inf, if we counted all of the 1's and all of the 2's and all of the 3's, etc. and there were no 3's, it's not random according to this definition or any definition I'm aware of.
      • pmelendez 13y ago
        I guess he is restricting the domain to [1,2] in which case 1,2,1,2,1,2... is as "random" as 1,2,2,2,1,2,1,1 ... I guess what is bothering him is the lack of entropy in the sequence.
    • bmm6o 13y ago
      I guess I could see your interpretation, but it requires that you ignore all of the context of the paper. For instance, you take distribution to equal histogram. This may make sense in some contexts, but here it's absolutely not true; the values are supposed to be taken independently from some probability distribution. Pro tip: if you think you've spotted a major problem in the first line of an abstract, maybe give the author the benefit of the doubt. Especially if you're not familiar with the field.
• mistercow 13y ago
  I am not terribly good with statistical terminology, but I don't think that the definition you're assuming for "uniform distribution" is the one in general use. Once you know a[n], a[n+1] will follow a delta distribution, not a uniform distribution.
• akjj 13y ago
  Clearly, a PRNG is a subtle concept and it's common for abstracts to not be completely precise. In context, it's clear to me that by "uniform" they mean "a random process which generates numbers independently from a uniform distribution." Your process is generating numbers uniformly, but successive outputs are definitely not independent. One reason why I feel your interpretation is strained is that the phrasing makes "uniform" sound like a single process. You seem to be reading it as "numbers which are distributed uniformly," but the word indistinguishable really suggests that it's more than just the distribution that matters.
• betterunix 13y ago
  The sequence 1,2,1,2,1,2,1... is not indistinguishable from a uniform sequence, at least in the context of cryptography. With high probability, an algorithm that checks if all the even indexed inputs are 1 and all the odd indexed inputs are 2 will distinguish that sequence from a uniform random sequence (this is easy to see, as the probability of a sequence of that form being generated by repeatedly tossing a fair coin is very small).
• tiagobraw 13y ago
  why not 4, 4, 4, 4, 4,... ;) obligatory: http://xkcd.com/221/ http://xkcd.com/221/
  • poizan42 13y ago
    Or: http://dilbert.com/strips/comic/2001-10-25/ http://dilbert.com/strips/comic/2001-10-25/