# Questions tagged [sampling]

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

83 questions
Filter by
Sorted by
Tagged with
0answers
35 views

### Quota sampling participants

We need to select participants, based on the quotas provided. For example: exactly 15 men exactly 15 women exactly 10 young exactly 10 middle aged exactly 10 old exactly 10 poor exactly 10 middle ...
1answer
32 views

### Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as ...
0answers
58 views

### Peculiar MCMC sampling problem

I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
1answer
68 views

### Generate random matrix and its inverse

I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that ...
0answers
12 views

### Raters and subsampling

In order to select questions for an online contest, we get contributors to submit potential questions that they write themselves. Then, out of, say 100 submitted questions, we have to rate them and ...
1answer
39 views

### Sampling in large graph using simple random walk

I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, we don’t know the size of the network). However crawling is supported, i.e, ...
1answer
46 views

### Sampling numbers from a weighted set that sum to constant value

So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
2answers
90 views

### Efficient n-choose-k random sampling

Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)? I have read this question but it asks for generations of all combinations, not ...
0answers
61 views

### Complexity of generating non-uniform random variates

What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) ...
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 ...
3answers
2k 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 ...
2answers
129 views

### Efficiently shuffling items in $N$ buckets using $O(N)$ space

I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows: We have $N$ buckets, $B_1$ through $B_N$. Each bucket $B_i$ maps to a ...
2answers
57 views

### Nyquist theorem, sample meaning

Given that this wave was sampled at a sampling frequency f: Why does the wave sampled at a sampling frequency 3f/2 look like this? What does 3f/2 mean? Does it mean that we sample every 2 waves 3 ...
1answer
55 views

### Sample K representative frames within a video

I have an image-based processing module that takes photos for some computer vision processing. I have many videos, but I need to sample representative frames as its inputs, preferably those frames ...
1answer
193 views

### Proof Knuth S algortihm correctness

In the programming pearls book by Jon Bentley, there is a section about the problem of finding a random set of m integers from range 0 to n-1 integers. To do so they use Knuth's algorithm given by the ...
2answers
70 views

2answers
88 views

### Random sampling of tuples

When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may ...
1answer
756 views

### Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
3answers
244 views

### Is there a random shuffle algorithm using only true /false?

Is there a way to randomly shuffle an array using only a source of random boolean values? SO to clarify, shuffle using true /false only, and not integers or decimals. For this question, I'm ...
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 ...
0answers
232 views

### Linear regression - iterative approach

I have a single output variable $y$ and a number of inputs $x_1$, $x_2$, etc. These are time series. Each $x_i$ explains the changes in $y$ in specific circumstances, and the goal is to have a linear ...