# Tag Info

### 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/...
• 80.2k
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 ...
• 141k

### 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 ...
• 80.2k

### Are all pseudo-random number generators ultimately periodic?

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 ...
• 270k
Accepted

### How does an operating system create entropy for random seeds?

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

### How to simulate a die given a fair coin

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 ...
• 6,519
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,...
• 141k

### 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.
• 25.1k

### Why is the Mersenne Twister regarded as good?

The initial Mersenne-Twister (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. This page lists the ...
• 427

### 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....
• 311

### 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 ...
• 473
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 ...

### 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 ...
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 ...
• 80.2k
Accepted

### What's a uniform shuffle?

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 ...
• 28.2k

### 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 ...
• 592
Accepted

### How to simulate a die given a fair coin

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$...
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$...
• 141k

### 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 ...
• 1,582
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 ...
• 141k
Accepted

### Returning a random subset with length k of N strings while only storing at most k of them

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth. Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, ...
• 141k

### Uniform sampling from a simplex

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. ...
• 1,469

### Why do we care about random Boolean SAT formula?

If your solver is efficient for random 3-SAT, it by no means entails that it is efficient for an arbitrary 3-SAT instance. Randomly generated instances are very different from instances that arise in ...
• 22.1k
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 ...
• 270k
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 ...
• 270k
Accepted

### Can someone explain LazySelect?

$\DeclareMathOperator{\rank}{rank}$Given a set $S$ of $n = 2k$ elements, the algorithm is aimed at finding the median of $S$ in linear time, with high probability. The idea is to find two elements \$a,...
• 270k
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 ...
• 198
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 ...
• 25.1k