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
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 ...
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 ...
32
The title and the body of your question ask two different questions: how the OS creates entropy (this should really be obtains entropy), and how it generates pseudo-randomness from this entropy. I'll start by explaining the difference.
Where does randomness come from?
Random number generators (RNG) come in two types:
Pseudo-random number generators (PRNG),...
answered Aug 25 '14 at 18:17
Gilles 'SO- stop being evil'
38.9k7 gold badges103 silver badges167 bronze badges
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
What you can do, is to employ a method called rejection sampling:
Flip the coin 3 times and interpret each flip as a bit (0 or 1).
Concatenate the 3 bits, giving a binary number in $[0,7]$.
If the number is in $[1,6]$, take it as a die roll.
Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.
Since $\frac 68$ of the possible outcomes lead to ...
29
It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.
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 ...
25
Non-deterministic algorithms are very different from probabilistic algorithms.
Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. ...
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 ...
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 ...
18
The short answer is that no one knows what real randomness is, or if such a thing exists. If you want to quantify or measure the randomness of a discrete object, you would typically turn to Kolmogorov complexity. Before Kolmogorov complexity, we had no way of quantifying randomness of say a sequence of numbers without considering the process that spawned it.
...
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 ...
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 ...
17
You seem to have misunderstood what the key is.
In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver. For OTP, the key is the entire pad and, if two people wish to encrypt some message using OTP, they must ensure beforehand that they have a long enough pad to do that.
For your proposed ...
16
Random graphs with small world topology
In graphs with small world topology, nodes are highly clustered yet the path length between them is small. A topology like this can make search problems very difficult, since local decisions quickly propagate globally. In other words, shortcuts can mislead heuristics. Further is has been shown that many different ...
15
An algorithm specifies a method to get from a given input to a desired output that has a certain relation with the input. We say that this algorithm is deterministic if at any point, it is specified exactly and unambiguously what the next step in the algorithm is that must be performed as part of that method, potentially dependent on the input or the partial ...
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 ...
15
A uniform shuffle of a table $a = [a_0, ..., a_{n-1}]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible rearrangements of $n$ elements and you need to pick one of them uniformly at random.
Many methods for shuffling seem uniform to people but are not and so it is ...
14
You should be aware that there are two different definitions of nondeterminism being thrown around here.
As wikipedia defines it, pretty much "not determinism", that is, any algorithm that doesn't always have the same behavior on the same inputs. Randomized algorithms are a special case of "not deterministic" algorithms, because they fit the definition as I ...
14
In short: non-determinism means to have multiple, equally valid choices of how to continue a computation. Randomisation means to use an external source of (random) bits to guide computation.
In order to understand nondeterminism, I suggest you look at finite automata (FA). For a deterministic FA (DFA), the transition function is, well, a function. Given the ...
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 ...
13
We will show by induction that the permutation $\rho_n = (2,3,4,\ldots, n,1)$ is an example with $C(\rho_n) = 2^{n-1}$. If this is the worst case, as it is for the first few $n$ (see the notes for OEIS sequence A192053), then $m(n) \approx (2/e)^{n}$. So the normalized min, like the normalized max, is 'exponentially bad'.
The base case is easy. For 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
To have a slightly more efficient method than the one pointed out by @FrankW but using the same idea, you can flip your coin $n$ times to get a number below $2^n$. Then interpret this as a batch of $m$ die flips, where $m$ is the largest number so that $6^m < 2^n$ (as already said, equality never holds here). If you get a number greater or equal to $6^m$ ...
11
There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. ...
11
Randomness is a philosophical concept (though there are several mathematical definitions as well). There are two aspect to randomness generated by a computer, unpredictability and pseudorandomness, which correspond to two different demands from a randomness source:
Data produced by the randomness source should be unpredictable, even in principle.
Data ...
Only top voted, non community-wiki answers of a minimum length are eligible
