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
3
votes
0
answers
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 ...
- 31
0
votes
0
answers
30
views
Chernoff bounds using importance sampling identity
How to use importance sampling identity to obtain the Chernoff bounds as given below?
Let X have moment generating function $\phi(t)= E[e^{tX}]$. Then, for any c > 0 ,
$P[X\geq c ]\leq e^{-tc} \phi(...
1
vote
2
answers
112
views
Sampling from bins with ratio preservation
I have sequence of integers $a_1, a_2, .., a_n$,
let $S_a = \sum_{i=1}^{N}{a_i}$,
for any $k \in (0; 1)$ I need an algorthim to that maps every $a_i$ into another integer $b_i$ with 2 requirements:
$...
- 287
0
votes
0
answers
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
1
answer
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) ...
- 13
1
vote
1
answer
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$...
- 123
8
votes
3
answers
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 ...
- 183
1
vote
1
answer
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, ...
- 111
1
vote
1
answer
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 ...
- 23
1
vote
2
answers
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 ...
- 11
0
votes
0
answers
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 ...
- 101
0
votes
1
answer
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 ...
- 3
1
vote
0
answers
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 ...
- 403
4
votes
0
answers
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 ...
- 5,730
3
votes
1
answer
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,...
- 531
1
vote
2
answers
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 ...
- 190
0
votes
1
answer
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 ...
- 250
2
votes
1
answer
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 ...
- 121
1
vote
1
answer
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)$ ...
- 12.7k
2
votes
1
answer
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 ...
- 31
0
votes
1
answer
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 ...
- 147
3
votes
1
answer
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 ...
- 12.7k
2
votes
0
answers
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 ...
- 119
4
votes
2
answers
88
views
If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?
As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\...
- 2,372
3
votes
0
answers
37
views
How to generate a uniform random sample of unique vertex pairings from a undirected graph under constraint?
I'm working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random ...
- 31
3
votes
1
answer
141
views
How to uniformly sample a sorted simplex
I am looking for an algorithm to uniformly generate a descending 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 ...
- 133
2
votes
1
answer
64
views
How to implement random sampling with continuous variables?
How functions like rnorm in R (and similar functions) create a random sample ? If I want to implement one algorithm to simulate this procedure what can I do? When you have the pdf or pmf of a ...
1
vote
1
answer
32
views
Sampling of subsets with repeat
Given a string S of length n and a positive integer k <= n, we want to randomly, and with equal probability, choose a string from the set of all strings of length k that may be formed with a subset ...
- 13
3
votes
0
answers
54
views
Random linear arrangement of a tree with constrained edge lengths
Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the ...
- 131
2
votes
1
answer
60
views
Set which is easy to sample, but difficult to sample from its complement
Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\...
- 23
6
votes
1
answer
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 ...
- 200
1
vote
0
answers
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 ...
- 111
4
votes
0
answers
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 ...
- 41
2
votes
1
answer
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 ...
D.W.♦
- 156k
1
vote
0
answers
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 ...
0
votes
1
answer
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 ...
- 161
2
votes
1
answer
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, ...
- 31
3
votes
1
answer
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 ...
3
votes
3
answers
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 ...
- 31
4
votes
1
answer
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) ...
- 451
3
votes
2
answers
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 ...
- 254
2
votes
2
answers
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 ...
- 23
4
votes
2
answers
154
views
Fast sampling from discrete space
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...
- 41
0
votes
0
answers
120
views
L1 sampling for sampling edges of a graph
I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone ...
- 1
3
votes
1
answer
938
views
How to use Latin hypercube sampling with fixed points?
I use Latin hypercube sampling to select what point to evaluate my function. As evaluations take a lot of time, I want to limit the time by adding already evaluated points.
I thought about taking the ...
- 131
0
votes
1
answer
212
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 ...
- 131
1
vote
1
answer
219
views
Uniform sampling with constraints
Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the ...
- 13
1
vote
0
answers
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 ...
- 11
0
votes
1
answer
30
views
Testing two distributions, both accept null hypothesis
I have a sample that is collected to verify the accuracy of a new random number generator.
Applying the goodness of fit test to check if this sample comes from the Standard Normal Distribution and ...
- 23
2
votes
2
answers
108
views
Limit repetitions in randomized list with each unique element occurring n times
I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row.
So with elements [0,1,2] n = ...
- 21