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

learn more… | top users | synonyms

3
votes
2answers
295 views

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

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, ...
2
votes
0answers
26 views

Sampling a Large Undirected Graph

I'm working with a very large undirected graph (a social network from a telecomunication company). I'm applying a clustering algorithm on this graph to find it’s most relevant communities. The ...
4
votes
1answer
361 views

Is this method really uniformly random?

I have a list and want to select a random item from the list. An algorithm which is said to be random: When you see the first item in the list, you set it as the selected item. When you see ...
0
votes
0answers
11 views

Representative tree from sets of decision trees

I built a set of samples from an imbalanced dataset with two classes through the undersampling technique. Now, from that set of decision trees I would like to choose one representative tree. Is there ...
4
votes
2answers
71 views

Generation of random binary trees

Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that? I attempted to do as follows: ...
4
votes
2answers
78 views

Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random, The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of ...
11
votes
2answers
206 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$ ...
0
votes
0answers
51 views

Find stationary distribution of markov chain

There is a markov chain on the states $\Phi = \{0,1,2\dots n\}$. I am also given the probabilities. E.g., the probability of going from i to i+1 is 1/2, going from i to state 0 = 1/2, and finally ...
7
votes
3answers
214 views

Random sampling in a polygon

I would like to sample a uniformly random point in a polygon... If sample a large number they'd be equally likely to fall into two regions if they have the same area. This would be quite simple if ...
1
vote
2answers
249 views

Generate random numbers from an interval with holes

Given a set $S$ of $k$ numbers in $[0, N)$. The task is to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$. Edit - Also given an API to generate random numbers between ...
1
vote
1answer
67 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
121 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
207 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
397 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
48 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
170 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$, ...
11
votes
2answers
962 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 ...
13
votes
3answers
482 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. ...