45

You've got a brilliant new compression scheme, eh? Alrighty, then... ♫ Let's all play, the entropy game ♫ Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ...


45

Sure, you can combine PRNGs like this, if you want, assuming they are seeded independently. However, it will be slower and it probably won't solve the most pressing problems that people have. In practice, if you have a requirement for a very high-quality PRNG, you use a well-vetted cryptographic-strength PRNG and you seed it with true entropy. If you do ...


39

All pseudorandom generators that don't rely on outside randomness and use a bounded amount of memory are necessarily ultimately periodic since they have finite state. You can think of them as huge deterministic finite automata which have special "output" states in which they give their output. All finite automata are eventually periodic, and so all ...


28

Wow, great question! Let me try to explain the resolution. It'll take three distinct steps. The first thing to note is that the entropy is focused more on the average number of bits needed per draw, not the maximum number of bits needed. With your sampling procedure, the maximum number of random bits needed per draw is $N$ bits, but the average number of ...


22

There are $2^N-1$ binary strings of length less than $N$, and $2^N$ binary strings of length exactly $N$. This means that whatever your compression algorithm is, there must be some string which it can't compress at all, just because the mapping from original string to compressed string must be injective (one-to-one). This is the driving force behind many ...


19

In fact, something of a breakthrough has just been announced by doing precisely this. University of Texas computer science professor David Zuckerman and PhD student Eshan Chattopadhyay found that a "high-quality" random number could be generated by combining two "low-quality" random sources. Here's their paper: Explicit Two-Source Extractors and Resilient ...


18

MT was regarded as good for some years, until it was found out to be pretty bad with the more advanced TestU01 BigCrush tests and better PRNGs. The table at pcg-random.org e.g. gives a good overview of features of some of the most used PRNGs, where the only "good" feature of the Mersenne Twister is the huge period, $2^{219937}$ and the possibility to use a ...


13

If the state of the PRNG is finite, then it has a finite period. (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite. For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.) In practice, worrying about the period of the ...


13

I am the Editor who accepted the MT paper in ACM TOMS back in 1998 and I am also the designer of TestU01. I do not use MT, but mostly MRG32k3a, MRG31k3p, and LRSR113. To know more about these, about MT, and about what else there is, you can look at the following papers: F. Panneton, P. L'Ecuyer, and M. Matsumoto, ``Improved Long-Period Generators Based on ...


12

What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern. This is known as enumerative coding, and it's one of the oldest deployed compression algorithms. Probably the simplest algorithm is from Thomas Cover. It's based on the simple observation that if you have a word that is $n$ bits long,...


10

There's no single method to determine the type of the PRNG. Indeed, for a cryptographic-strength PRNG you can't distinguish its output from truly random, so you can't determine the type of such PRNGs solely by looking at their output. Instead, for each of the schemes that you list, there is a way to recover the seed and predict future bits from its output. ...


9

Suppose that $X_1,\ldots,X_n$ is a pseudorandom binary sequence. That is, each $X_i$ is a random variable supported on $\{0,1\}$, and the variables $X_1,\ldots,X_n$ are not necessarily independent. We can think of this sequence being generated in the following way: first we sample a uniformly random key $K$, and then use some function $f(K)$ to generate the ...


9

There are several criteria for the quality of a PRNG: How fast it is. This includes how fast it is to setup it, and how fast it is to produce a single bit (amortized). How difficult it is to guess the next bit given all previous bits. How difficult it is to distinguish between output of the PRNG and truly random bits. The last two criteria are strongly ...


8

The feedback polynomial is $x^7 + x^6 + x^5 + x^1 + 1$ and can be computed using the Berlekamp-Massey algorithm.


7

Imagine that your seed $s$ has length $k$. Your PRNG is a deterministic function of the seed, so it outputs at most $2^k$ different sequences of length $n$. There are $2^n$ of these, so your scheme isn't going to work unless it falls back on just sending the whole $n$-bit string when there is no corresponding $s$. (As another answer noted, this will ...


7

PRNGs are state-machines. If they're based only in internal input (in contrast to Poker Stars RNG which is a combination of hardware and software, seeding itself continuously from... sound samples) you'll get (C, S1,...) where C is the current (or previous) value and S1,... could be a set of states: If there are possible N values (since the memory is ...


7

There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated numbers is to mask the true state. Here's how it works. You take your $b$-bit number $x_t$ to be the true state at time $t$, but the number your RNG generates is $...


7

IIRC (and this is from memory), the 1955 Rand bestseller A Million Random Digits did something like this. Before computers were cheap, people picked random numbers out of this book. The authors generated random bits with electronic noise, but that turned out to be biassed (it's hard to make a flipflop spent exactly equal times on the flip and the flop). ...


6

Actually, bruteforce should work just fine. You can quickly find a set of taps that doesn't have a full period, then find a value that's not in the period. Here's what I'd do: Randomly pick a set of taps (a feedback polynomial). Verify whether this has a single full period of size $2^{32}-1$, as follows. Randomly pick a starting state $s_0$ (not the all-...


6

Simple example of pseudo-random sequence that is not periodic: concatenate together the binary representations of all positive integers, in order: 110111001011101111000... (Prepend a "." and it's called the binary Champernowne constant.) Of course this isn't very high quality as far as pseudo-random sequences go, but it demonstrates that it's possible ...


6

Check out [1] and the discussion in Section 4, Random Automata Generation. The paper benchmarks different DFA minimization algorithms. A uniform random generator is used that produces canonical string representations of complete DFAs with $n$ states and $k$ symbols. They also discuss other methods. [1] Almeida, M., Moreira, N., & Reis, R. (2007). On the ...


6

Somewhat like sorting algorithms in this regard, there is no "one size fits all" PRNG. Different ones are used for different purposes and there is a wide variety of design criteria and uses. It is possible to misapply PRNGs, such as using one for cryptography that it is not designed for. Wikipedia's entry on Mersenne Twister also mentions that it was not ...


6

There is a comprehensive and excellent answer in this earlier “Cryptanalysis of Linear Feedback Shift Registers” question. Alternatively, if you know the order of the recurrence is $n$, you can solve a linear system of the form $$ \left( \begin{array}{lllll} z_i & z_{i+1} & \cdots & z_{i+n-1} \\ z_{i+1} & z_{i+2} & \cdots & z_{i+n} \...


6

The standard notion of pseudorandomness is about a process. You can say that the process (the pseudorandom generator) is pseudorandom, or not. The notion of pseudorandomness of a single string is not defined; that's not something you can talk about. Kolmogorov randomness is a property of a bit-string. You can say that a particular bit-string (sequence) ...


5

This website provides the answer: A xorshift* generator with an n-bit state space is $n/64$-dimensionally equidistributed: every $n/64$-tuple of consecutive 64-bit values appears exactly once in the output, except for the zero tuple (and this is the best possible for 64-bit values). A xorshift+ generator is however only $(n/64 − 1)$-dimensionally ...


5

Your definition of pseudorandomness is misleading. A better definition would start with a function with "expansion", and then state then it is indistinguishable from random. In your case, the function is "expanding" since it takes $n$ bits and outputs $n+1$ bits. However, the $n+1$ bits it produces don't look random. Can you tell why?


5

Let's start with some background. The context is derandomization: Given a randomized algorithm, is there an equivalent deterministic algorithm? Let's consider a randomized algorithm for some decision problem. The algorithm makes use of some random bits $r_1,\ldots,r_n$. In practice, we run this algorithm by using an "informal" pseudorandom number ...


5

I'll give this a shot, since I'm sufficiently disturbed by the advice given in some of the other answers. Let $\vec{X},\vec{Y}$ be infinite bit sequences generated by two RNGs (not necessarily PRNGs which are deterministic once initial state is known), and we're considering the possibility of using the sequence $\vec{X} \oplus \vec{Y}$ with the hope of ...


5

You can generate any distribution by using a standard PRNG to choose $X$ uniformly from the interval $[0,1]$ and then returning $F^{-1}(X)$, where $F$ is the cumulative distribution function of the distribution you're interested in. For the Gaussian distribution, though, it's usually better to use Box–Muller or ziggurat.


5

There is no such test. All automated tests for examining the randomness of a PRNG have limitations. If you read some papers in the literature that propose PRNGs, you might notice that they do more than just run an automated test against their scheme. Of course you can always write up anything at any time. For the research community to find it interesting,...


Only top voted, non community-wiki answers of a minimum length are eligible