Questions tagged [sampling]
Creating samples from a well-specified population using a probabilistic method and/or producing random numbers from a specified distribution.
118 questions
0 votes
1 answer
67 views
Efficient algorithm for generating a random number in [1, 50000] with 40% probability for a fixed value (12345) and uniform distribution elsewhere?
Consider an algorithm that generates random numbers in the range [1, 50000] with the following distribution: The specific value 12345 should have a 40% probability of being selected The remaining 60% ...
0 votes
1 answer
105 views
What are typical real-world applications of enumeration or random order enumeration algorithms?
I'm currently studying enumeration algorithms and random order enumeration algorithms (enumeration results in random order) and trying to understand their downstream applications in real-world ...
1 vote
1 answer
91 views
Efficiently sampling $k$ elements from the powerset while avoiding space blow up
Is there a way that I can space efficiently sample $k$ elements from $\mathcal{P}(\{1,2,\ldots, n\})$ without replacement? For instance, the naive approach would be as follows in Python: ...
- 349
1 vote
1 answer
64 views
Best internal representation of a random variable to enable iterative sampling and interpolation/regression
Let $[0,100]$ denote the interval of real numbers between $0$ and $100$. Given a function $f:[0,100]^n \rightarrow \mathbb{R}^+$, I want to implement the following simple algorithm to search for the ...
- 113
3 votes
1 answer
202 views
A data structure for an allocation-free dynamic sample rate buffer
I'm looking for a data structure that would allow storing samples (in O(1)) from a data stream in a fixed-size buffer while the stream length isn't known in advance. Once the buffer size is exhausted ...
- 133
3 votes
0 answers
82 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 ...
- 61
1 vote
0 answers
71 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(...
- 153
1 vote
2 answers
156 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: $...
- 297
1 vote
1 answer
72 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
209 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$...
- 163
8 votes
3 answers
2k 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
72 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
2 votes
1 answer
143 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
164 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
77 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