Creating samples from a well-specified population using a probabilistic method and/or producing random numbers from a specified distribution.
1
vote
1answer
44 views
How to sample uniformly from a stream of elements, some of which are unsuited?
I get values $x_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x_t) >T$. Consider the following simple algorithm.
...
7
votes
1answer
59 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 ...
1
vote
2answers
132 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 ...
6
votes
1answer
100 views
Algorithms for graph generation using given properties
There may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g., clustering coefficient, average shortest path length, degree distribution, etc).
My ...
1
vote
1answer
46 views
Stochastical algorithm
We have a stochastic random source. This gives the bit $0$ (or $1$) with probability $1/2$.
We want to generate a uniform distribution on the set S = $\{0, 1,..., n-1\}$.
Which algorithm gives with ...
3
votes
2answers
116 views
Construction of binary random variable
We throw two coins in a row and thus get the event space $\{ZZ, WW, ZW, WZ\}$.
Each of the 4 elementary events has a probability $1/4$.
how can I construct 3 binary random variable $x_1$, $x_2$, ...
7
votes
2answers
278 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 ...
12
votes
3answers
235 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.
...
