Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sampling]

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

3
votes
2answers
95 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 ...
0
votes
0answers
25 views

How to randomly sample a social graph to find paths between at least 20% of profiles?

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...
2
votes
2answers
31 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
55 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
29 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
180 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
25 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 ...
0
votes
0answers
17 views

Hidden Markov Model with likelihood sampling method

I have a revision question for an exam which I'm unsure about. The question includes Hidden Markov Model which I'm well aware of, but I'm just not sure how to use the weighted sampling method in this ...
1
vote
1answer
38 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
95 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
20 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
50 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
35 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 ...
0
votes
0answers
45 views

Time-decaying sum sketch

At the Data Mining course at school i've received the following question regarding sketching: Consider a stream of events with timestamps: $t_1<t_2<\ldots$ We are interested in ...
1
vote
1answer
36 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 ...
4
votes
3answers
845 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
32 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
191 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
46 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 ...
2
votes
3answers
318 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
59 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
25 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
58 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 ...
3
votes
1answer
384 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
24 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 ...
-3
votes
1answer
154 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 ...
4
votes
1answer
82 views

Uniformly sampling from cycles of a graph

I was wondering if, given an arbitrary cycle basis (that's complete, e.g. every cycle in the graph can be expressed as the $\mathbb{Z}/2\mathbb{Z}$ sum of elements from the basis) of some graph $G$, ...
1
vote
0answers
74 views

Uniform sampling from general simplex with a twist [closed]

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange. Given $a_1,\dots,a_D$ (all strictly positive), I want to draw points uniformly from ...
0
votes
0answers
151 views

Uniform generation of random bipartite bi-regular graphs?

I want an algorithm that takes the following Input: $M,N,k,d$ positive integers such that $kM = dN$. and produces the following Output: Random bipartite graph, with $M$ vertices all of degree $k$ ...
1
vote
1answer
94 views

How broken is LCG in the case of partial output?

Suppose we have a linear congruential generator defined by $X_{n+1} = (a X_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X_0$. However, if we can ...
6
votes
3answers
193 views

Efficiently generating a uniformly random list of unique integers in a range

The problem: To generate a list of size $n$, Containing unique integers, Sampled uniformly in the range $\left[0,m\right)$, In $O(n)$ time, except that: Assuming $m$ is bounded by some word-size, $\...
0
votes
2answers
82 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 ...
6
votes
3answers
214 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 ...
1
vote
0answers
215 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 ...
31
votes
3answers
9k views

Why is the Mersenne Twister regarded as good?

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list ...
4
votes
1answer
255 views

Choosing a random bit from a bitmap

Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so. I have quite a large bitmap (~100 Million bits) (e.g. ...
4
votes
3answers
3k views

What's a uniform shuffle?

What does it mean exactly a "uniform shuffle" algorithm ? Is this method considered a uniform shuffle ? ...
2
votes
2answers
86 views

How to sample random game input that looks similar to human control?

What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this ...
2
votes
0answers
232 views

Sampling random graphs with Eulerian paths

How to generate random graphs with eulerian Paths? Its well known that there is a eulerian path if the number of nodes with odd degree is exactly 2 or zero. I'm interested in an algorithm to make ...
3
votes
2answers
121 views

Generating graphs such as found on Sedgewick's Algorithms book on the MST chapters

I always wondered what the algorithm might be to generate graphs such as those found on Sedgewick's algorithms books (consider the picture on the left): Could any one point me to the name (or ...
1
vote
0answers
353 views

Non-Uniform Random Number Generation, from Uniform Random Number Generater [closed]

The project I am currently working on (in C#) requires generating random integer between 0 and Int64.MaxValue. I have access to a Uniform RNG, which for pseudo-code purposes in the question, I will ...
1
vote
1answer
66 views

How to simulate this randomized “finite” sum? [closed]

Consider the the Geometric Brownian motion $\qquad dX_t=\mu X_t dt+\sigma X_t dW_t$, with $X_0=1$, $\mu=0.2$, and $\sigma=0.30$. for each $n=1,2,3,..$ let $h_n=1/n$, and let $X^n_n$ be the final ...
5
votes
0answers
66 views

Uniform Sampling on Intersection of Faces of Simplices [closed]

I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{...
5
votes
1answer
92 views

Delaunay Triangulation on Convex Polytopes — Uniform Sampling

My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts: ...
0
votes
1answer
133 views

Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...
1
vote
1answer
44 views

How to get samples of different paths?

Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed). Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B. I ...
3
votes
0answers
204 views

permutations sampling by probability matrix

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = \...
0
votes
1answer
44 views

Estimate distribution of a composite variable

Suppose I have N sets of numbers (10 numbers per set) {a1, ....., a10}. I form a sum by taking one number at random from each set. SUM = num from set 1 +......+ num from set N. If I do this a large ...
6
votes
1answer
673 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 ...
13
votes
2answers
618 views

Efficient algorithm to generate two diffuse, deranged permutations of a multiset at random

Background $\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{...