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 ...
43
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 ...
31
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'
37.6k7 gold badges101 silver badges166 bronze badges
30
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 ...
24
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
First, let us make two maybe obvious, but important assumptions:
_.random_item can choose the last position.
_.random_item chooses every position with probability $\frac{1}{n+1}$.
In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here:
For the singleton list there is only one possibility, so it is ...
21
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
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/...
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 ...
17
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 ...
16
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 ...
15
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
Generating the exact uniform distribution of all sudoku puzzles can be done that way: you can just randomly generate a 9x9 grid and then only keep it if it is a correct sudoku grid, otherwise retry.
This brute-force approach guarantees you a uniform distribution but is clearly not efficient, since you can multiply the probability of the grid to be correct ...
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 ...
14
What you're looking for is based on Rejection sampling or the accept-reject method (note that the Wiki page is a bit technical).
This method is useful in these kinds of situations: you want to pick some random object from a set (a random integer in the set $[a,b]$ in your case), but you don't know how to do that, but you can pick some random object from a ...
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
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
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
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
Yes and no, depending on what you mean by “the only way”. Yes, in that there is no method that is guaranteed to terminate, the best you can do (for generic values of $N$ and $R$) is an algorithm that terminates with probability 1. No, in that you can make the “waste” as small as you like.
Why guaranteed termination is impossible in general
Suppose that you ...
answered Jul 4 '12 at 23:18
Gilles 'SO- stop being evil'
37.6k7 gold badges101 silver badges166 bronze badges
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
