Skip to main content
Share Your Experience: Take the 2024 Developer Survey
101 votes

Is von Neumann's randomness in sin quote no longer applicable?

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/...
David Richerby's user avatar
78 votes
Accepted

Is von Neumann's randomness in sin quote no longer applicable?

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 ...
D.W.'s user avatar
  • 161k
49 votes

Can we generate random numbers using irrational numbers like π and e?

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 ...
David Richerby's user avatar
28 votes
Accepted

Simulating a probability of 1 of 2^N with less than N random bits

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,...
D.W.'s user avatar
  • 161k
28 votes

Can we generate random numbers using irrational numbers like π and e?

It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.
gnasher729's user avatar
  • 30.4k
21 votes

Why is the Mersenne Twister regarded as good?

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 ...
Pierre L'Ecuyer's user avatar
21 votes

Is von Neumann's randomness in sin quote no longer applicable?

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....
bmm6o's user avatar
  • 311
18 votes

Is von Neumann's randomness in sin quote no longer applicable?

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 ...
maaartinus's user avatar
18 votes
Accepted

Can we generate random numbers using irrational numbers like π and e?

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 ...
Dmitry Grigoryev's user avatar
17 votes
Accepted

Problem with the pseudo random number generator One-Time-Pad

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 ...
David Richerby's user avatar
16 votes

pick K random integers without repetition

Ṃųỻịgǻňạcểơửṩ mentioned that this is the reservoir problem. The reservoir sampling problem, though, is explicitly a very strict requirement for a streaming algorithm, i.e. it works in just one pass ...
Theo H's user avatar
  • 321
15 votes

Is von Neumann's randomness in sin quote no longer applicable?

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 ...
Warbo's user avatar
  • 622
12 votes
Accepted

Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$...
D.W.'s user avatar
  • 161k
12 votes
Accepted

Is there a linear-time algorithm for randomly sampling weighted combinations?

There is a very simple $O(n \log k)$ algorithm described in Weighted random sampling with a reservoir by Pavlos S. Efraimidis and Paul G. Spirakis, which can be summarized as: Associate a value $r_i^{...
orlp's user avatar
  • 13.6k
11 votes
Accepted

Why is the Mersenne Twister regarded as good?

A recent paper by Vigna starts with an explanation of the history of Mersenne-Twister (MT), and why it has prevailed so far. The original paper about the Mersenne Twister was published by Makoto ...
jherek's user avatar
  • 228
11 votes

Problem with the pseudo random number generator One-Time-Pad

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator No, no and once again no. I'm concerned that this is what you're being taught. The absolutely fundamental ...
Paul Uszak's user avatar
  • 1,602
10 votes
Accepted

How best to statistically verify random numbers?

You can't. Randomness is a property of the source, not a property of the values you get from that source. In other words, randomness is a statement about the probability distribution, not about some ...
D.W.'s user avatar
  • 161k
9 votes
Accepted

Why is randomness a problem? (i.e. why do we care about derandomization?)

Complexity theory is a mathematical theory which aims at addressing one shortcoming of computability theory, namely, it takes into account the use of resources. While it is true that in its early days ...
Yuval Filmus's user avatar
8 votes
Accepted

Time complexity of this while loop

Worst case, if the second call to rand() returns 0 and the first call doesn't, you get a floating point division by zero, and if you are using standard IEEE 754 arithmetic, the result is +infinity. In ...
gnasher729's user avatar
  • 30.4k
8 votes

Shuffling a list while keeping order relative to related elements

Your problem can be phrased as generating a random linear extension of a partial order. The partial order in your phrase is generated by your constraints. There is a classical algorithm of Matthews ...
Yuval Filmus's user avatar
8 votes
Accepted

What makes a pseudorandom generator, a high quality one?

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 ...
Yuval Filmus's user avatar
7 votes

Generate string with large Kolmogrov complexity

No. This is basically Chaitin's incompleteness theorem. Roughly, the theorem says that there exists a concrete constant $C$ (which is a function of your consistent set of axioms) for which no fixed ...
Yonatan N's user avatar
  • 499
7 votes

How to select a binary tree node uniformly at random

The algorithm works just fine. Note that each node's size field tells you the total number of nodes in the subtree rooted at that node. Throughout this answer, I'm ...
David Richerby's user avatar
7 votes

Problem with the pseudo random number generator One-Time-Pad

A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish ...
Ariel's user avatar
  • 13.4k
7 votes

Is von Neumann's randomness in sin quote no longer applicable?

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 ...
Pharap's user avatar
  • 301
7 votes

Can we generate random numbers using irrational numbers like π and e?

(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 ...
Ayrat's user avatar
  • 1,075
6 votes

Are all pseudo-random number generators ultimately periodic?

Simple example of pseudo-random sequence that is not periodic: concatenate together the binary representations of all positive integers, in order: ...
Don Hatch's user avatar
  • 209
6 votes

Achieving Randomness

There are two types of answers: Practical: You are looking for good stream ciphers. Several exist, though we don't know for sure that they are secure. Theoretical: You are looking for ...
Yuval Filmus's user avatar
6 votes

Time complexity of this while loop

This answer refers to a version of the question in which $x$ is sampled by dividing two random numbers. As mentioned by Rick Decker's answer, given $x$, we can approximate the running time by $O(\max(...
Yuval Filmus's user avatar
6 votes
Accepted

How could you characterize "true randomness" of a finite sequence?

Answer to original question: Your question is based on some faulty premises and misunderstandings. A word/string is neither computable nor uncomputable. Rather, we apply uncomputability to ...
D.W.'s user avatar
  • 161k

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