Questions tagged [sampling]

Creating samples from a well-specified population using a probabilistic method and/or producing random numbers from a specified distribution.

Filter by
Sorted by
Tagged with
20
votes
3answers
2k views

Is rejection sampling the only way to get a truly uniform distribution of random numbers?

Suppose that we have a random generator that outputs numbers in the range $[0..R-1]$ with uniform distribution and we need to generate random numbers in the range $[0..N-1]$ with uniform distribution. ...
26
votes
4answers
8k views

Uniform sampling from a simplex

I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should ...
20
votes
9answers
15k views

How to simulate a die given a fair coin

Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate ...
37
votes
3answers
13k views

Why is the Mersenne Twister regarded as good?

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list ...
14
votes
2answers
841 views

Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ ...
6
votes
3answers
203 views

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

The problem: To generate a list of size $n$, Containing unique integers, Sampled uniformly in the range $\left[0,m\right)$, In $O(n)$ time, except that: Assuming $m$ is bounded by some word-size, $\...
11
votes
1answer
6k views

Generate scale-free networks with power-law degree distributions using Barabasi-Albert

I'm trying to reproduce the synthetic networks (graphs) described in some papers. It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree ...
5
votes
3answers
3k views

What's a uniform shuffle?

What does it mean exactly a "uniform shuffle" algorithm ? Is this method considered a uniform shuffle ? ...
2
votes
3answers
1k views

Best random permutation employing only one random number

The ideal random permutation algorithm of Fisher and Yates (Algorithm P in Knuth vol.2) for a sequence of $n$ objects requires $n-1$ random numbers. In some card games one first does a "cut" and ...
13
votes
2answers
982 views

Sampling perfect matching uniformly at random

Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am ...
5
votes
1answer
97 views

Delaunay Triangulation on Convex Polytopes — Uniform Sampling

My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts: ...
0
votes
1answer
156 views

Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...