Questions tagged [sampling]

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

Filter by
Sorted by
Tagged with
4
votes
0answers
46 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 ...
3
votes
1answer
54 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
2answers
38 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 ...
0
votes
1answer
17 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 ...
0
votes
0answers
15 views

Sampling data following some arbitrary normal distributions

Let say I have a matrix $D_{N \times 3}$ which its columns are $x, y, z$ and assume that assume that $N$ is a huge number and all $x, y, z$ are sampled from 3 different uniform distributions. Now, I ...
2
votes
1answer
52 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
1answer
27 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)$ ...
1
vote
1answer
83 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 ...
0
votes
1answer
12 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 ...
3
votes
1answer
60 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 ...
2
votes
0answers
37 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 ...
4
votes
2answers
79 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 $\...
3
votes
0answers
23 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 ...
3
votes
1answer
63 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 ...
2
votes
1answer
16 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
1answer
21 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 ...
3
votes
0answers
45 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 ...
2
votes
1answer
50 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 $\...
6
votes
1answer
281 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
0answers
36 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 ...
4
votes
0answers
64 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 ...
2
votes
1answer
194 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
0answers
13 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
1answer
77 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 ...
2
votes
1answer
56 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, ...
3
votes
1answer
151 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
3answers
2k 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 ...
3
votes
1answer
191 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) ...
3
votes
2answers
154 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 ...
2
votes
2answers
128 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 ...
4
votes
2answers
108 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=...
0
votes
0answers
67 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 ...
3
votes
1answer
742 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 ...
0
votes
1answer
188 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 ...
1
vote
1answer
127 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 ...
1
vote
0answers
722 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 ...
0
votes
1answer
28 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 ...
2
votes
2answers
56 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 = ...
2
votes
0answers
37 views

Constrained selection of a random sample from a set of items with multiple attributes

Suppose I have a collection of N items, each of which has A different attributes, a1, a2, ..., aA. Attribute ai can take on Vi different possible (discrete) values, distributed across the population ...
1
vote
1answer
46 views

Randomly choose a line - algorithm

We have a large file that can't fit into internal memory. How do we randomly pick one line so that each line has the same probability to be picked? And how do we randomly pick such n lines so that ...
6
votes
3answers
2k views

How to select a binary tree node uniformly at random

The exercise I'm trying to solve is You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method ...
1
vote
0answers
102 views

What is the relationship between entropy rate and quantization?

I have a totally random source of signal data that looks like a typical normal distribution. I've included an image as I like pictures:- The source has a mean of 0, and a standard deviation of 1. ...
5
votes
1answer
374 views

Bilinear Interpolation

I am trying to implement bilinear interpolation as described in the paper Spatial Tranformer Networks by Jaderberg et. al (see link to paper). They describe bilinear interpolation in Equation 5 as: $$...
1
vote
0answers
62 views

Strength-based player cards sampling [closed]

Let's say we have a card game, like poker. Inputs are board cards and an array of cards strength(that is calculated based on the board cards and game rules). For example for 3 ranks(A, K, Q) /2 suits(...
2
votes
3answers
504 views

Why do we need Gibbs sampling (and MCMC)?

I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$. Maybe my alternative suggestion would sound somewhat naive (even ...
2
votes
1answer
70 views

Finding the (probable) maximum of a large set of integers *without* iterating over all of the values

As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers. Importantly, I do not have direct access to the full list of integers, but I do have a ...
2
votes
1answer
32 views

Sampling among constrained partitions

I'm working on a clustering problem and want to sample partitions (possible clustering solutions) among a set of constrained ones. Here is the problem: I have a set of objects $O=\{o_1,\ldots,o_n\}$ ...
3
votes
1answer
78 views

Sampling from a set of numbers with a fixed sum

Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen ...
2
votes
1answer
732 views

Randomly select a uniform subsample from a nonuniform dataset

I have a dataset of events with timestamps spanning several months. The event rate is "bursty", i.e. there are periods of much higher and lower rate than the average. I would like to randomly select ...
1
vote
1answer
26 views

What do the terms 'Sample' and 'Sampling' mean in the discussion of Pattern Recognition and Machine Learning?

The tag sampling tells me that, Creating samples from a well-specified population using a probabilistic method and/or producing random numbers from a specified distribution. Now, the question ...