23 votes

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 ...
rurban's user avatar
  • 457
20 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
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
9 votes
Accepted

Efficient sampling from all positive integers to find the largest integer below a transition for f(n)

The normal approach is to evaluate $f(1)$, $f(2)$, $f(4)$, $f(8)$, $f(16)$, $f(32)$, $f(64)$, etc., until you find the first power of two for which $f(2^k)=\text{true}$ (and thus $f(2^{k-1})=\text{...
D.W.'s user avatar
  • 159k
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

Efficient sampling from all positive integers to find the largest integer below a transition for f(n)

If you want the exact value of x, you’d find an interval of width 2^k containing x, then k steps of binary search at a cost of roughly x^2 find x. Total cost about x^2 log x. If you want a rough ...
gnasher729's user avatar
5 votes
Accepted

Sampling a uniform distribution of fixed size strings containing no forbidden substrings

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

Efficiently generating a uniformly random list of unique integers in a range

Make a binary tree/trie, starting with nothing in the trie Pick a uniform random number over $\left[0,m\right)$ Pad the number to $|m|$ bits, adding leading zeros if necessary Insert the number into ...
Realz Slaw's user avatar
  • 6,191
4 votes

Efficiently generating a uniformly random list of unique integers in a range

Another approach is to use format-preserving encryption (e.g., a Feistel cipher) to build a pseudorandom permutation on the domain $\{0,1,\dots,m-1\}$, then encrypt the sequence $0,1,\dots,n-1$ and ...
D.W.'s user avatar
  • 159k
4 votes
Accepted

Efficiently generating a uniformly random list of unique integers in a range

Here is a solution in $O(n\log n)$ (with high probability). We consider two cases: $n\log n \geq m$ and $n\log n \leq m$. In the first case, we choose a random permutation of $[0,m)$ and take only the ...
Yuval Filmus's user avatar
4 votes
Accepted

Sampling from a set of numbers with a fixed sum

You can bound the variance as follows. Let $b_i$ be an indicator variable signaling that $x_i$ was chosen. You are interested in $y = \sum_i b_i x_i$. We have $$ \mathbb{E}[(b_ix_i)^2] = \frac{x_i^2}{\...
Yuval Filmus's user avatar
4 votes

Complexity of generating non-uniform random variates

The binomial, negative binomial, and hypergeometric distributions are discrete distributions. Knuth and Yao (1976) gave complexity results for discrete distributions in general. Given a stream of i.i....
Peter O.'s user avatar
  • 171
4 votes

Efficient n-choose-k random sampling

Here is the simplest algorithm, which is efficient when $k$ is much smaller than $n$ relatively. Input: two positive integers $n$ and $k$ with $k\le n$ Output: a random permutation of $k$ integers ...
John L.'s user avatar
  • 39k
4 votes
Accepted

A data structure for an allocation-free dynamic sample rate buffer

The best name I can think of is derandomized or deterministic reservoir sampling. I don't know of any ready-made implementations.
orlp's user avatar
  • 13.4k
3 votes
Accepted

Why do we need Gibbs sampling (and MCMC)?

The approach you described sounds like the common algorithms for sampling. If by reasonable distribution, you mean a smallish finite discrete distribution, then see the following references for how to ...
eyeApps LLC's user avatar
3 votes

Why do we need Gibbs sampling (and MCMC)?

It's not "essentially $O(1)$" to draw objects from a set with non-uniform probability: your bucketing scheme takes more than constant time. Further, sampling from a Markov chain allows you to sample ...
David Richerby's user avatar
3 votes
Accepted

Proof Knuth S algortihm correctness

I have finally succeeded in proving Knuth's algorithm S. Let's state it first: Knuth's algorithm S takes a sample of $M$ elements from $N$ inputs, N is not known until the end of inputing. A uniform ...
Petar Mihalj's user avatar
3 votes

Sampling perfect matching uniformly at random

If you assume that your graph is planar, then there is a polynomial time procedure for this sampling problem. First, the problem of counting the number of perfect matchings is in P for planar graphs. ...
Elle Najt's user avatar
  • 374
3 votes

Sample K representative frames within a video

The question misses a lot of detail, so I will try to make an educated guess. I don't know of any specific algorithm for the task you are trying to achieve, but the first step towards your solution ...
João Gueifão's user avatar
3 votes

Generate random matrix and its inverse

Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states: We can uniformly generate a matrix and its inverse in time $2M(n) +...
orlp's user avatar
  • 13.4k
3 votes

If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?

Theorem: For any given $A$, either there are good algorithms to sample every subset of $A$, or what you're describing is impossible. Proof (perhaps slightly informal): Suppose there are some "...
Сергей Макеев's user avatar
3 votes

Uniformly sample $x,y\in\{0,1\}^n$ with Levenstein distance $k$

There are two considerations: running time, and correctness. Running time: When $k < (n-1)/\lg(4n)$, heuristically I expect the running time of your algorithm to be fine and I'd guess you won't ...
D.W.'s user avatar
  • 159k
2 votes

Why is the Mersenne Twister regarded as good?

I produced now a simple overview of most of the known RNG's, with its speed and quality, based on improved dieharder tests. https://rurban.github.io/dieharder/QUALITY.html For TestU01 and PractRand ...
rurban's user avatar
  • 457
2 votes

Uniform sampling from a simplex

One other possibility is to use the Dirichlet distribution using the SciPy module. Essentially, if we set $\alpha=(1,\dots,1)^\top$, then the probability density is effectively uniform on a $n$-...
Alma Rahat's user avatar
2 votes

How to simulate a die given a fair coin

I came across this thread looking to validate if the solution I came up with with when my kids wanted to play a game requiring a die but one could not be found. Take three coins and write numbers like ...
JP Duffy's user avatar
  • 121
2 votes
Accepted

Uniformly sampling from cycles of a graph

Exponential-time algorithm One (slow) approach is to rejection sampling. Let $c_1,\dots,c_k$ be the cycle basis. Then we obtain an isomorphism $\varphi : (\mathbb{Z}/2\mathbb{Z})^k \to \mathcal{E}$,...
D.W.'s user avatar
  • 159k
2 votes

Uniform generation of random bipartite bi-regular graphs?

The problem of generating random $d$-regular graphs uniformly at random has been extensively studied. Some of the proposed algorithms are quite sophisticated. In general, the problem becomes more ...
Zur Luria's user avatar
  • 349
2 votes
Accepted

How broken is LCG in the case of partial output?

Yes, there are techniques based on lattice reduction that are faster than brute force. See, e.g., https://crypto.stackexchange.com/a/20714/351, especially the first 3 papers cited there. One can ...
D.W.'s user avatar
  • 159k

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