# Questions tagged [sampling]

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

114 questions
Filter by
Sorted by
Tagged with
40 views

### Constrained random sampling by inequalities

Assume I have $n$ random variables $x$ which need to obey a set of inequality constraints that are linear and can be written as $Ax \leq 0$. Is there a method to sample effectively from these for ...
30 views

18 views

### What is the advantage of every Bayes Nets Sampling algorithm?

I have studied four Bayes Nets Sampling algorithms for calculating the probabilities, including: $1. Prior Sampling$ $2. Rejection Sampling$ $3. Likelihood Weighting$ $4. Gibbs Sampling$ And my ...
1 vote
28 views

### How to generate spatial scale-free nwtworks?

I want to generate spatial scale-free networks for my project. Are there any python libraries that enable it? I read about the BA model (https://www.science.org/doi/pdf/10.1126/science.286.5439.509) ...
1 vote
122 views

### Faster Algorithm for sampling a point from the array

Let $M$ be a collection of elements given in the form of the array such that membership of any element can be done in $O(1)$ time. Which means elements of array $M$ are $\{1,2,\cdots,n\}$ such that $1$...
1k views

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

Let's say we want to find the smallest positive integer x for which some property A holds. We know that such an integer exists. However, we have no knowledge about the scale of x (i.e. x could be 7 or ...
1 vote
43 views

### Naïve array sampling algorithm: the possibility of a item being chosen and its time complexity

This naïve sampling algorithm I am talking about is fairly simple: create a set for storing chosen items first, randomly select an item from the array, and examminate if it is in the set. If it isn't, ...
1 vote
100 views

### Sample a set of N numbers without replacement, each element taken from N different weighted sets

Here's my problem: I have $N$ sets of integers $S_i$ where $|S_i| = n_i \forall i \in [1,N]$ each with non-uniform weights $W_i = \{w_{i,1}, ..., w_{i,n_i}\}$ such that $\sum_{j}{w_{i,j}} = 1$. I want ...
1 vote
97 views

### Weighted sample of ~k elements from array in O(n) time?

I have an array $a$ with $n$ elements, all of which have an associated weight. For example: $a = \{ (A,2), (B,5), (C,9), ..., (Z,1) \}$, such that element $A$ has weight $w_A=2$, element $B$ has ...
52 views

### Resampling an array of objects

Context I have an array of objects (or a list of dictionaries), sorted in order based on a property of each object, say, time. In JSON, it would look something ...
65 views

### Efficient random sampling from large discrete distribution

I have a random variable $X$ that can take finite values in $\{X_1, ..., X_n\}$ with probabilities $\{p_1,..., p_n\}$. Is there a computationally efficient way to sample a number from this set? My ...
1 vote
37 views

### How to sample the most unique vectors from a very large set efficiently?

While this question already exists and does talk about a heuristic with the Farthest Point First technique, I would like to approach the problem in a more efficient way. I do agree that this is an NP ...
80 views

### How to sample a perfect partition uniformly at random?

I would like to sample $n$ integers (of some fixed length, say $k$ bits) uniformly at random, and have them partitioned into two sets of equal sum. Since finding such a perfect partition (even if it ...
71 views

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

Given alphabet $\{0,1\}$, we want to uniformly sample $x,y \in \{0,1\}^n$ such that $ed(x,y)=k$, where $ed$ denotes the Levenstein distance, i.e., the minimum number of edit operations (insert, delete,...
1 vote
114 views

### Probability that two specific elements are in uniformly random sample

Consider the sampling algorithm as described here section 2.2 specifically Algorithm 2.4. Essentially we are given a stream of $N$ elements and wish to maintain a uniformly random sample, $S$, of size ...
377 views

### How to sample Bivariate Normal Distribution with Accept reject method

I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods: Prior Sampling Gibbs Sampling Rejection Sampling I have done the first two samplings and ...
181 views

### Algorithm to sample high-dimensional parameter space of expensive cost function

I am looking for recommendations for algorithms (apparently this is the right SO site for that) that efficiently scan the high-dimensional parameter space of a cost function that is very expensive to ...
1 vote
50 views

### Selecting random element from complement of set

Let $[n] = \{1, 2, \dots, n\}$. Suppose we have a subset $S$ of $[n]$ of size $k$. Can we sample one element uniformly at random from $[n] \setminus S$ in $O(k)$ time? It's okay to use $O(n)$ ...
644 views

### Is there an algorithm for random sampling from a priority queue with probability proportional to priority?

Suppose I want to randomly sample from a large set of items, each of which has a "score". I want my probability of sampling to be proportional to the score. One simple way to achieve this ...
17 views

### Is reservoir sampling unnecessary if you know the length of the stream of integers?

I think I understand Reservoir Sampling. If you have a large stream of integers then it allows you to get a sample of size k from that stream without putting it all in memory. My question is what if ...
72 views

### Sampling from specific random distribution on sets

I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $[0, n)$ (without replacement) such that the elements within each ...
53 views

### Integer sampling with exponentially decreasing probability

Given a probability $p$ and an integer $N$, I would like to generate a sample $S$ of the population $P=\{0,1,...,N\}$ such that integer $m\in P$ is sampled with probability $p^m$. It is trivial to do ...
88 views

375 views

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

Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word? For short output strings ...
1 vote
37 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 ...
67 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 ...
400 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 ...
1 vote
17 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 ...
97 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 ...
76 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, ...
268 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 ...
4k 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 ...
460 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) ...
242 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 ...
240 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 ...
154 views

1 vote
921 views

### Backward mapping with bilinear sampler

I have some experiences with Convolutional Neural Networks before. I have a question regarding the Bilinear Sampler used in "Unsupervised Monocular Depth Estimation With Left-Right Consistency" (the ...