Skip to main content

Questions tagged [sampling]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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}\...
Daniel Soudry's user avatar
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 ...
okm02's user avatar
  • 11
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_{...
Daniel Cortild's user avatar
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 ...
ljy's user avatar
  • 63
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, ...
kaleidoscop's user avatar
  • 1,332
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 ...
Andrei Mihalcea's user avatar
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 ...
mathhamcs's user avatar
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 ...
D.S.'s user avatar
  • 45
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 ...
giulio bullsaver's user avatar
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 ...
zemora's user avatar
  • 565
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$», ...
Simon's user avatar
  • 21
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},\...
Annie's user avatar
  • 91
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_{...
Minkov's user avatar
  • 1,127
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 ...
0xbadf00d's user avatar
  • 157
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,...
0xbadf00d's user avatar
  • 157
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 ...
user avatar
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 ...
OverLordGoldDragon's user avatar
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 ...
sqrt6's user avatar
  • 61
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 ...
dohmatob's user avatar
  • 6,824
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,...
pipenauss's user avatar
  • 297
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(\...
AKG's user avatar
  • 49
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. ...
Matthieu Latapy's user avatar
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 ...
Joker123's user avatar
  • 153
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 ...
litmus's user avatar
  • 91
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*...
J. Swail's user avatar
  • 437
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_{...
Daniel Soudry's user avatar
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 ...
Kunstmord's user avatar
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 \...
Jack Rolph's user avatar
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}...
Felix Goldberg's user avatar
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 ...
Tobias Windisch's user avatar
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 ...
Matthieu Latapy's user avatar
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 ...
LucioPhys's user avatar
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 "...
Peter Wildemann's user avatar
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 ...
Matthieu Latapy's user avatar
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 ...
Davide Papapicco's user avatar
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 ...
Min Wu's user avatar
  • 461
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: ...
Josef Ondrej's user avatar
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 ...
Călin's user avatar
  • 271
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 ...
Penelope Benenati's user avatar
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 ...
BOYI's user avatar
  • 53
-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 ...
Adrian Radillo's user avatar
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 ...
Daron's user avatar
  • 1,915
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_{...
Gavroche's user avatar
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_\...
dohmatob's user avatar
  • 6,824
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:...
Rui Zhang's user avatar
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). ...
dohmatob's user avatar
  • 6,824
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 ...
Szabolcs Horvát's user avatar
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$ ...
Ethan's user avatar
  • 145
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}^{+\...
pipenauss's user avatar
  • 297
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 ...
Penelope Benenati's user avatar