# Tag Info

100

If you're using some hardware source of entropy/randomness, you're not "attempting to generate randomness by deterministic means" (my emphasis). If you're not using any hardware source of entropy/randomness, then a more powerful computer just means you can commit more sins per second.

75

Just because you can't see a pattern doesn't mean that no pattern exists. Just because a compression algorithm can't find a pattern doesn't mean that no pattern exists. Compression algorithms are not silver bullets that can magically measure the true entropy of a source; all they give you is an upper bound on the amount of entropy. (Similarly, the NIST ...

47

For any reasonable definition of perfect, the mechanism you describe is not a perfect random number generator. Non-repeating isn't enough. The decimal number $0.101001000100001\dots$ is non-repeating but it's a terrible generator of random digits, since the answer is "always" zero, occasionally one, and never anything else. We don't actually know if every ...

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 ...

31

Let us first assume that you want to sample within x + y + z = 1 0 ≤ x ≤ 1 0 ≤ y ≤ 1 0 ≤ z ≤ 1 This doesn't make quite a difference, since the sample point will still lie in your requested area with high probability. Now you are left with sampling a point from a simplex. In the 3d example you get a 2d simplex (triangle) realized in 3d. How to pick a ...

29

It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.

20

I've always understood the quote to mean that a deterministic algorithm has a fixed amount of entropy, and although the output can appear "random" it can't contain more entropy than the inputs provide. From this perspective, we see that your algorithm smuggles in entropy via System.nanoTime() - most definitions of a "deterministic" algorithm would disallow ...

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

Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. When you interpret "living in a state of sin" as "doing a nonsense", than it's perfectly right. What you did is using a rather slow method System.nanoTime() to generate rather weak randomness. You measured some ... entropy rate of ~5.3 bits/...

18

The most obvious disadvantage is the unnecessary complexity of PRNG algorithms based on irrational numbers. They require much more computations per generated digit than, say, an LCG; and this complexity typically grows as you go further in the sequence. Calculating 256 bits of π at the two-quadrillionth bit took 23 days on 1000 computers (back in 2010) - a ...

15

Computers Being Really Random: True randomness is impossible for Turing Machines in a theoretical sense, and most computers can't generate truly random output. Therefore, some modern computers include hardware that allows the computer to access an outside source which will hopefully include some randomness. One example of how this can be accomplished is ...

14

I thought I'd chime in on the meaning of "random". Most answers here are talking about the output of random processes, compared to the output of deterministic processes. That's a perfectly good meaning of "random", but it's not the only one. One problem with the output of random processes is that they're hard to distinguish from the outputs of deterministic ...

9

Triangulate the polygon Determine in which of the triangles the point should lie (weights triangle areas) Sample the point in the triangle as explained in this post

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

Quick answer: If the run time of your algorithm to pick a random number is not random you could get a pattern of times which is not random. As an example. Suppose the function to read the time is triggered by an event, and the event is timed to the clock, now your functions based on the clock. If the run time of your algorithm is faster than the precision ...

8

This is to add to the existing answers. Devroye is an excellent reference for questions of this sort. Chap.7 gives the algorithms needed to generate uniform order statistics, which the OP is after. For generating uniform order statistics, sorting $n$ samples of $[0,1]$ will do. This approach takes $O(n \log n)$ time. A quicker way ( available in the book) ...

8

(updated after many people pointed out that random number generator is not the same thing as a single normal sequence) If you ask whether you can get a normal sequence out of $\pi$ (i.e., all numbers appear uniformly), then there are several answers on mathoverflow. For example, the answer about Distribution of the digits of Pi says: ...it is believed ...

7

Nobody mentioned this, so let me formally prove that if $D$ is a domain whose size is not a power of two, then finitely many fair coin tosses aren't enough to generate a uniformly random member of $D$. Suppose you use $k$ coins to generate a member of $D$. For each $d \in D$, the probability that your algorithm generated $d$ is of the form $A/2^k$ for some ...

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). ... 7 Compression isn't an accurate test of randomness, and nor is looking at an image and saying "that looks random". Randomness is tested by empirical methods. There are in fact suites of specially designed software/algorithms for testing randomness, for example TestU01 and the Diehard tests. Furthermore, your image is in fact a 1D string of number mapped onto ... 6 Yes. Use a block cipher with a small block size. This is extremely efficient and requires extremely little state. A block cipher is a map$E : K \times X \to X$such that, for every$k \in K$,$E(k,\cdot)$is a permutation on$X$(a bijective function$X\to X$). Moreover, if$k$is chosen uniformly at random, then$E(k,\cdot)$acts in a way that is ... 6 Yes, there are. Consider the recurrence$a_{n+1}=(7a_n/4 + 1/2) - (5a_n/4 + 1/2)(-1)^{a_n}$where$a_0$is a given integer value. It is well known that this gives the Collatz sequence. There is no "known" closed form solution to the recurrence (and if you find it, you would be quite famous in mathematical circles). Furthermore, it is also well known that ... 6 Shannon's source coding theorem shows that, in some exact sense, you need$\log N/\log R$samples (on average) of the type$[0,\ldots,R-1]$to generate a random number of the type$[0,\ldots,N-1]$. More accurately, Shannon gives an (inefficient) algorithm that given$m$samples of the first type, outputs$m(\log N/\log R - \epsilon)$samples of the second ... 5 Actually, no, rejection sampling is far from the only way of proceeding. Unfortunately, considering that computers store all information as bits, and thus can only manipulate random bits of information, any algorithm to draw a uniform random variable of range$N$will be infinite, if the binary base development of$N$is infinite. This theorem is a ... 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 integrate the PDF to a CDF F(x), then uniformly generate a random number x between 0 and 1 and choose a y such that F(y)=x as your sample. This is more or less difficult, depending on your PDF. Some PDFs have analytical solutions, others need numerical methods. For some distribution Rejection sampling works well, some distributions can be sampled ... 5 You are confusing the concept of random numbers from "numbers that appear to be random." To understand von Neumann's quote, we have to understand what it means to "generate random numbers." Warbo's answer links an excellent XKCD to this end: When we talk about random numbers, we're not talking about the values themselves. Obviously a 4 is no more random ... 5 Suppose the alphabet is$\{a,b\}$, and you have one forbidden word,$aa$. Suppose we are trying to generate a word of length 3. The first two letters will be distributed uniformly over$ab,ba,bb$. Hence the first letter has the following distribution:$a$with probability$1/3$,$b$with probability$2/3$. In contrast, the allowable words are$\$ aba,abb,bab,...

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