Questions tagged [sampling]
The sampling tag has no summary.
90 questions
0 votes
1 answer
67 views
How to uniformly sample from a nonlinearly transformed simplex?
Let $S = \{ w \in \mathbb{R}^3 : w_1 + w_2 + w_3 = 1,; w_i \ge 0 \}$ be the standard 2-simplex. Consider the transformation $$ T(w_1, w_2, w_3) = (w_1, w_2^p, w_3), $$ not followed by a ...
15 votes
0 answers
287 views
Sampling from the uniform distribution on preorderings on n objects
Let $n$ be a natural number, and $\mathscr{P}$ be the set of all preorderings (i.e., reflexive and transitive relations) on $\{1,\ldots,n\}$. (Equivalently, we can defined $\mathscr{P}$ as the set of ...
- 38k
1 vote
1 answer
92 views
How to study the convergence of the sample mode for arbitrary probability spaces
(This is not the problem I actually care about, but an analogy with similar issues to the problem I'm actually considering.) Consider a probability space with i.i.d. random variables $X_i$ producing ...
- 297
9 votes
1 answer
218 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}\...
- 978
2 votes
0 answers
37 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 ...
- 21
3 votes
1 answer
135 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_{...
- 133
0 votes
0 answers
43 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 ...
- 63
0 votes
0 answers
81 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, ...
- 1,362
2 votes
0 answers
149 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
153 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 ...
- 31
3 votes
0 answers
196 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,473
1 vote
1 answer
323 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 ...
- 673
0 votes
1 answer
156 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$», ...
- 21
2 votes
0 answers
61 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},\...
- 91
3 votes
1 answer
376 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_{...
- 1,127
3 votes
2 answers
358 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 ...
- 249
1 vote
0 answers
62 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,...
- 249
7 votes
1 answer
334 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 ...
user491917
0 votes
0 answers
118 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
55 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 ...
- 61
2 votes
1 answer
276 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 ...
- 7,033
4 votes
1 answer
223 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,...
- 319
2 votes
1 answer
687 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(\...
- 49
5 votes
3 answers
1k 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,534
1 vote
0 answers
44 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 ...
- 153
1 vote
1 answer
220 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 ...
- 91
3 votes
0 answers
309 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*...
- 66
5 votes
0 answers
139 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_{...
- 978
1 vote
1 answer
99 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 ...
- 13
0 votes
1 answer
322 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 \...
- 111
2 votes
1 answer
129 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}...
- 7,082
3 votes
1 answer
260 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 ...
- 268
2 votes
0 answers
93 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 ...
- 1,534
3 votes
1 answer
1k 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 ...
- 33
2 votes
1 answer
211 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 "...
- 381
6 votes
0 answers
372 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 ...
- 1,534
2 votes
1 answer
959 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
54 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 ...
- 461
0 votes
1 answer
191 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: ...
- 21
6 votes
2 answers
1k 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 ...
- 281
1 vote
1 answer
156 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 ...
- 1,707
5 votes
1 answer
298 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 ...
- 53
-2 votes
1 answer
61 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
123 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 ...
- 2,035
1 vote
2 answers
445 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_{...
- 11
2 votes
2 answers
136 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_\...
- 7,033
8 votes
1 answer
469 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:...
- 83
4 votes
1 answer
423 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). ...
- 7,033
3 votes
1 answer
1k 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 ...
- 931
2 votes
1 answer
94 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$ ...
- 145