# Questions tagged [sampling]

The sampling tag has no usage guidance.

88
questions

8
votes

1
answer

120
views

### How to sample exactly k indices given the inclusion probabilities of all indices?

Let $k<d$ two positive integers, and $\{p_i\}_{i=1}^d$ a series of probabilities, with $p_i \in (0,1)$ and $\sum_{i=1}^d p_i = k$.
We wish to sample exactly $k$ distinct indices $\mathcal{I}\...

1
vote

0
answers

18
views

### Metropolis-Hastings in mini-batch setting

I would like to ask the following question : I have seen papers such as Stochastic gradient Langevin dynamics (link) and Stochastic gradient Hamiltonian monte-carlo (link) which could be used to train ...

2
votes

1
answer

61
views

### Connection between Wassertein-2 metric and difference in variance

Given two probability densities $\mu\in\mathcal P(\mathbb R^d)$ and $\nu\in\mathcal P(\mathbb R^d)$, we define their Wasserstein-$p$ metric as
$$
W_p^p(\mu, \nu)=\inf_{\gamma\in \Gamma(\mu, \nu)}\int_{...

0
votes

0
answers

25
views

### Nonparametric sampling for conditional distribution consistency

Suppose we have two random variables $X$ and $Y$ related by the equation:
$Y=kX+Z,$
where $k$ is an unknown constant scalar, and $Z$ is a zero mean Gaussian random variable independent of $X$. The ...

0
votes

0
answers

42
views

### Function samplable from the past and Hardy spaces

What I am ultimately looking for is a $L^2$ function $f$ on the real line that can be sampled from the past, i.e. for each $x<0$ there are $L^2$ coefficients $c_n(x)$, $n\in \mathbb{N}$ such that, ...

2
votes

0
answers

48
views

### Mean and variance of Wasserstein 2-distance for sequence of normal distributions obtained from resampling

I am reading this article: The curse of recurssion. At page 8, I dont know how to calculate the mean and variance for the Wassertein distance (the relations 4 and 5), in this context the hypothesis. I ...

3
votes

0
answers

98
views

### Sampling uniformly from the convex cone

Let $n$ vectors of dimension $d$ (e.g., $n = 100$, $d = 10000$), each with infinity norm of $1$, be given. The conic combination of those $n$ vectors generates a convex cone.
How to uniformly sample ...

1
vote

0
answers

82
views

### How can one build a min-2-wise independent small sample space from min-3-wise permutations?

I have been studying a polynomial-size set of permutations from one of my lectures. The below image, taken from the lecture notes PDF, illustrates how to construct min-3-wise permutations.
My ...

3
votes

0
answers

137
views

### How to sample uniformly over a polytope knowing its vertex presentation?

Say that a convex polytope $P$ is presented as $P = \mathrm{Conv}(v_1, \dots , v_m)$.
I would like to sample over $P$, without generating the facet presentation of the polytope.
How can I do that?
I ...

1
vote

1
answer

243
views

### Question about the proof of Propp-Wilson algorithm in Olle Häggström's book

Update: Oops! This is a stupid question and should be closed. The definition of the probability space that contains events $A_i$ requires using a single random stream.
I have difficulties ...

0
votes

1
answer

121
views

### Definition of sequence sampled from a measure

Question: Exactly what does it mean for a sequence of points to be sampled from a given probability measure?
I have in mind statements such as «let the sequence $(x_k)$ be sampled with density $f$», ...

2
votes

0
answers

44
views

### When can convolutional integral operators be sampled

Consider an integral operator $F:C^{1/2}([0,T],\mathbb{R}^n)\rightarrow \mathbb{R}$ of the form
$$
f\mapsto \int_0^T f(t)^{\top}\kappa(T-t)dt,
$$
for some $\kappa\in C^{\infty}(\mathbb{R})(\mathbb{R},\...

3
votes

1
answer

334
views

### Importance resampling with exponential weighting

Suppose that we have
$$
\frac{p(x)}{q(x)} \propto \exp(\tau f(x)),
$$
where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x_i\}_{i=1}^n$ such that $n^{-1}\sum_{...

3
votes

2
answers

253
views

### Is there something like a "self-avoiding Markov chain" on a continuous space?

If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants.
However, as far as I can see they are ...

1
vote

0
answers

41
views

### Does the constrained Wasserstein barycenter admit a blue noise property?

Let $(E,d)$ be a metric space and $\nu$ be a probability measure on $\mathcal B(E)$. In this paper, it is mentioned that sampling from $\mu$ can be described as choosing $n\in\mathbb N$, $x_1,\ldots,...

7
votes

1
answer

263
views

### Square-root lattices: where do they appear?

As an experimental physicist working on crystallography I'm often dealing with the reconstruction of an object from intensity data that emerge from an imaging device. In mathematics the problem is ...

0
votes

0
answers

74
views

### Alternative to the Sampling Theorem / Invertible transform with sampling criteria

I seek a transform $T$ that operates on real-valued $x(t)$, that
Is perfectly invertible
Has discrete counterpart with continuous reconstructor
Provides conditional reconstruction guarantees
...

3
votes

0
answers

40
views

### Invertibility of the sampling matrix

Given a function $f: \mathbb{R}^2\rightarrow\mathbb{C}$ sampled as a matrix $F_{ij}$ on some ractangle $[a,b]\times[c,d]\subset\mathbb{R}^2$ with steps $\Delta x$ and $\Delta y$ as the stepsizes so ...

2
votes

1
answer

205
views

### Given iid samples from the joint distribution $P$ of pair of r.v.'s $(X,Y)$, how to get iid samples from independence coupling $P_X \otimes P_Y$?

Let $(X,Y)$ be a pair of random variables on a measure space $\mathcal T \subseteq \text{"subsets of }\mathbb R^2\text{"}$, with joint probability distribution $P$.
We don't assume $X$ and $Y$ are ...

4
votes

1
answer

186
views

### Integral of $\ln(1/|f|)$ for $f$ bandlimited

I came across the following assertion: if $f\in PW_\infty([-a,a])$, i.e. the Bernstein space of functions in $L^\infty(\mathbb{R})$ which are the Fourier transform of a distribution supported on $[-a,...

2
votes

1
answer

495
views

### Shift-invariant spaces

We can define a shift-invariant space as
$$V_{\varphi}(\mathbb{Z}):=\left\{\sum_{k\in\mathbb{Z}}c_k\varphi({\cdot}-k):(c_k)\in \ell_2\right\},$$
where convergence of the series is taken to be in $L^2(\...

5
votes

3
answers

744
views

### Probability of an edge in a random graph

Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence.
...

1
vote

0
answers

34
views

### Correlating two matrices $A,B$ with stochastic dependency structure imposed by cross-validation

Consider a labelled data set
$$D = \{(x_1, y_1),...,(x_n, y_n)\} $$
on which we want to evaluate a machine learning algorithm using $k$-fold cross validation with $m$ different random seeds. This ...

1
vote

1
answer

171
views

### Intuition of the "work" done by random variables in Monte Carlo methods (incl. MCL)

(I've tried Math SE, but have so far come up empty handed, so I'm trying my luck here.)
I would like to get a better intuitive understanding of why Monte Carlo works so well in approximating a ...

3
votes

0
answers

277
views

### Injectivity of the convolution operator $f \mapsto (k*f(s))_{s \in S}$ via sampling at $S=\alpha \mathbb Z$

Let $S \subset \mathbb R$ be a set of sampling points, say $S = \alpha \mathbb Z, \alpha >0$.
Let $k$ be some convolution kernel and $A$ the operator which maps some $f$ to the sequence
$$
Af = (k*...

5
votes

0
answers

121
views

### Which operations commute with fractional translation?

Let $\mathbf{v}$ be a real signal (i.e., an infinitely long vector).
A translation operation $T_{s}\mathbf{v}$ with integer $s$ is trivially
defined by $\forall i,s:\left(T_{s}\mathbf{v}\right)_{i}=v_{...

1
vote

1
answer

62
views

### Distribution of a two-part sampling process

I have a known distribution $f(x)$ (in fact, I can safely assume that $f(x)$ is the Maxwell-Boltzmann distribution, i.e. $f(x)\propto x^2 \exp(-x^2)$). I take $N$ samples from the distribution, but am ...

0
votes

1
answer

271
views

### Random sampling from modified Erlang distribution [closed]

I am tasked with randomly sampling from the following probability density function, which is a modified Erlang Function:
$$f(k,q,\nu)=\frac{(k q)^{k-1}}{[(k-1) !]^{v}} \quad \text { with } \quad q \...

2
votes

1
answer

77
views

### Column subset selection with least angle optimization

Given a matrix $A$ I need to select a "representative" subset of its columns so that the each non-selected column is as close as possible to a selected one.
Formally:
Given $A \in \mathbb{R}...

3
votes

1
answer

192
views

### Fast sampling of matroids

In his classic paper, Donald E. Knuth described how random matroids of fixed rank can be generated.
What is the currently the fastest (in terms of mixing behaviour) known way to sample matroids of ...

2
votes

0
answers

69
views

### Are two degree sequences compatible, for random simple graph generation?

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...

3
votes

1
answer

826
views

### Relation between signal derivative and frequency spectrum

I want to sample a signal whose derivative I know to be bounded by physical constraints. The sampling is disturbed by gaussian noise, hence I need to filter the sample with a lowpass filter.
Since I ...

1
vote

1
answer

152
views

### Sampling i.i.d. variables with restrictions

General Problem: Suppose $X_1,\ldots,X_n \sim \mathbb{P}_X^{\otimes n}$ is a finite sequence of i.i.d. (real- or integer-valued) random variables. Suppose $A\subseteq \mathbb{R}^n$ is a set of "...

6
votes

0
answers

293
views

### Probability that a random multigraph is simple

Question.
Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...

2
votes

1
answer

824
views

### Interior point of a convex polytope

Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...

0
votes

0
answers

33
views

### Condition on the point cloud matrix making the points "generic" in the uniform sense

For a matrix $X\in\mathbb{R}^{d\times n}$, what condition can I impose on $X$ to make the collection of its columns generic in the sense that they look like the result of uniformly sampling a convex ...

0
votes

1
answer

103
views

### Yates-Grundy draw-by-draw sampling inclusion probabilities

Is there an efficient algorithm to calculate the inclusion probabilities (the probability that an item will be included in a sample) in the Yates-Grundy draw-by-draw sampling?
Sampling description: ...

5
votes

2
answers

934
views

### Invariant measure vs Riemannian measure on Stiefel manifold

I'm interested in sampling uniformly from the Stiefel manifold $V(k, n)$, but while researching how to do this I came to wonder the following.
In Edelman et al. [1] there are presented two ...

1
vote

1
answer

132
views

### Random optimization problem

Let $V$ be a set of $n$-dimensional vectors such that, for each ${\bf v}\in V$ and for each index $i\in [n-1]$, we have $0\le v_{i+1}\le v_i$. Let $P(\cdot)$ be a discrete probability distribution ...

5
votes

1
answer

242
views

### What is the pdf of Laplace distribution conditioned on a plane? How can I sample from it?

Our goal is to sample from the Laplace distribution conditioned on a linear subspace. Here are the details of this problem.
Let
$$p(x) \propto \exp(-\|x\|_1/\sigma)$$
be the pdf of the Laplace ...

-2
votes

1
answer

47
views

### Using common samples to numerically estimate pairwise equality of three random variables

Let $X,Y,Z$ be three discrete random variables which I can numerically sample. I need to numerically estimate the probability that $X=Y$ and the probability that $X=Z$. I would like to know whether ...

2
votes

0
answers

111
views

### Can computers take uniform samples from a polytope?

For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$.
Suppose the plane $P \subset \mathbb R^N$ is ...

1
vote

2
answers

346
views

### Use Importance sampling for multimodal and multivariate distribution draws, how to choose proposal distribution?

I'm in trouble trying to generate samples following a particular distribution which is not numerically known perfectly. Let us consider a $R^n$ space provided with an orthonormal base $( e_{1},...,e_{...

2
votes

2
answers

100
views

### Draw samples from distribitions in the neighborhood of a fixed distribution

Disclaimer
Sorry in advance for vagueness. I'm still trying to get my ideas right on this one.
Setup
So, let $P$ be a distribution on a Euclidean space $X$ with an $\ell_p$ metric, and let $P_\...

8
votes

1
answer

401
views

### Expectation inequality for sampling without replacement

Is the following proposition correct?
$X_1, X_2, X_3$ are uniformly at random sampled from a finite set $\mathcal X$ without replacement.
$f : \mathcal X^2 \rightarrow \mathbb R_{\ge0}$ is symmetric:...

4
votes

1
answer

387
views

### Minimize the variance of a Boltzmann distribution

N.B.: Sorry for cross-posting from https://stats.stackexchange.com/posts/347804/edit (I realized it was the wrong venue for the question, but couldn't find an easy way to transfer the question here).
...

2
votes

1
answer

797
views

### Uniform sampling of random connected graph with given number of vertices/edges

I am looking for algorithms for the exact uniform sampling of connected labelled graphs with $n$ vertices and $m$ edges. By "exact" I mean that every such graph should be generated with precisely (not ...

2
votes

1
answer

72
views

### Sampling with non-uniform probabilities

Let $p_1,p_2,...,p_n$ are given probabilities. ($\sum_{i=1}^n p_i =1, p_i \geq 0 $). Is there any distribution, which picks $k\leq n$ distinct elements from $1,2,...,n$ such that $P(i \in S) = k p_i$ ...

1
vote

1
answer

127
views

### Plancharel-Pólya inequality for functions of exponential type

If $f(z)$ is an entire function of exponential type $\tau$ and $p$ a positive number such that that $$\int_{-\infty}^{+\infty}|f(x)|^pdx<\infty$$
then it can be proven that $$\int_{-\infty}^{+\...

4
votes

1
answer

254
views

### Combinatorial computational problem about 0-1 vectors and sampling algorithms

Let $M \in \{0,1\}^{m\times n}$, where $n\gg 1$ and $m\le n$. A procedure consisting of the following three steps is repeated $t\gg 1$ times:
A row $\require{amsmath} \boldsymbol{r}$ of $M$ picked in ...