Questions tagged [sampling]
The sampling tag has no usage guidance.
65
questions
0
votes
0answers
33 views
Weighted random sampling notation [closed]
I'm a computer scientist, not a mathematician, so please excuse the lack of mathematical rigor.
I'm currently writing a paper where I would like to express the following using equations:
I have a ...
1
vote
1answer
53 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 ...
1
vote
1answer
45 views
Random sampling from modified Erlang distribution
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 \...
1
vote
1answer
54 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}...
2
votes
1answer
102 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 ...
0
votes
0answers
23 views
sampling the distribution W, the mapping of k ordered observations to N distributions
we have a set of N ordered distributions.
also, we have K<N samples from those distributions, without replacement, ordered according to the original set (we can imagine someone samples a ...
2
votes
0answers
48 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 ...
0
votes
0answers
58 views
Anti-concentration of measure: Slud's inequality for finite populations
Suppose that I have Bernoulli trials with unknown bias $p$. I need $\Omega(\frac{\log 1/\delta}{\epsilon^2})$ samples for the average of the samples to estimate $p$ within $\epsilon$ error with ...
3
votes
1answer
127 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
1answer
109 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 "...
5
votes
0answers
214 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
vote
1answer
215 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
0answers
29 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
0answers
40 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: ...
3
votes
2answers
316 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
1answer
120 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
1answer
141 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
1answer
45 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
0answers
104 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 ...
0
votes
2answers
199 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
2answers
86 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
1answer
274 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
1answer
341 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).
...
1
vote
1answer
291 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
1answer
64 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
1answer
112 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
1answer
245 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 ...
1
vote
1answer
123 views
Sampling set: relatively dense and uniformly discrete
The Paley-Wiener space of a domain $\Omega\subset\mathbb{R}^d$ is the set $$PW_\Omega:=\{f\in L^2(\mathbb{R}^d):\text{supp}\widehat{f}\subset\Omega\}.$$
We say that a discrete set $\Lambda\subset\...
6
votes
1answer
529 views
Randomly covering a sphere
Let $S$ be the $n$-dimensional unit sphere in the Euclidean space. Further,
let $X_1,\ldots,X_k$ and $Y_1,\ldots,Y_m$ be iid $S$-valued random variables with common (unknown) distribution $\mu$. With $...
4
votes
1answer
870 views
How to measure distribution of high-dimensional data
I have to methods of projecting random samples in $\mathbb{R}^n$ onto a manifold defined by $C(q)=0$, which is a lower-dimensional subset. Now, samples in $\mathbb{R}^n$ are uniformly distributed. ...
1
vote
0answers
41 views
RMHMC sampling in non-parametric setup
The aim is to sample distributions using Fisher information (as mass matrix in Hamiltonian MCMC sampling). Details can be found in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.580&...
0
votes
0answers
161 views
Expected value of parametrized Gibbs distribution w.r.t another probability distribution
Let $\mu$ be a compactly supported probability measure on a finite-dimensional euclidean space (for simplicity) $\mathbb E$, and suppose $\mu$ has density. For a random point $x \sim \mu$,
consider ...
1
vote
1answer
177 views
How to sample a path between 2 states in a Markov chain
Given an ergodic Markov chain and 2 states $x$ and $y$, how may one algorithmically sample a path (of finite length) $x =: s_0 \rightarrow s_1 \rightarrow \ldots \rightarrow s_T = y$ between $x$ and $...
1
vote
1answer
103 views
Bounding function by random sampling
Let $f(x): \mathbf{C} \to \mathbf{C}$ be a complex valued polynomial of degree $n$, and suppose that for a random point $z$ sampled uniformly from the unit disk $|z|\leq 1$ we have
$$\mathbf{P}_{z}( |...
0
votes
1answer
124 views
Efficiently Sampling of Multivariate Distributions in the Vicinity of a Manifold
I am given a multivariate distribution, that maps each point of $\mathbb{R}^n$ to its probability of being drawn as sample and, the convolution $\mathcal{S_r}\times\mathcal{M}$ of a manifold $\mathcal{...
3
votes
1answer
727 views
Sampling from a particular multivariate probability distribution
Given $3$ real variables $x_1, x_2, x_3 \equiv \bf{x}$, consider their probability density function (PDF)
\begin{equation}
P({\bf x}) = C \, p(x_1) \cdots p(x_3) \exp[f({\bf x})],
\end{equation}
where ...
1
vote
0answers
57 views
2-step sampling from a conditional density
The setting is as follows:
We are given two random variables $X : \Omega \to \mathbb{R}$ and $\Theta : \Omega \to T$ for some 'parameter space' $T \subset \mathbb{R}$, and
1) we know the density of $...
3
votes
2answers
220 views
Sampling Theorem for non-bandlimited Functions
The classical Shannon sampling theorem states that
a bandlimited function with $\mbox{supp } \hat f\subset [-1/2,1/2]$ can be uniquely determined by its samples $(f(i))_{i\in \mathbb{Z}}$ (The symbol $...
1
vote
0answers
62 views
Simulate a graph from a certain distribution
I am wondering if anyone can indicate whether the following is a solved problem. I don't care about time of the algorithm currently.
Consider a general probability distribution F on simple graphs ...
6
votes
1answer
160 views
Sample integer points of cross-polytope uniformly
For $r,d\in\mathbb{N}$, let
$$C_{r,d}=\{x\in\mathbb{Z}^d: \|x\|_1\le r\}\subset\mathbb{Z}^d$$
be the set of integer points of the $d$-dimensional cross-polytope with radius $r$.
What is (...
0
votes
0answers
46 views
Efficient sampling from a polytope with large number of contraints [duplicate]
As far as I know, the most popular way to sample from a polytope (in H-representation)
\begin{equation}
\mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\}
\end{equation}
...
8
votes
4answers
276 views
Uniform Sampling Subject to Linear Equalities and Non-Negativity Constraint
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{...
3
votes
1answer
778 views
Sampling point uniformly at random satisfying equality constraints
First of all, I apologize in advance if the question has already been asked in some way on this site and/or if there is a widely known solution to this problem.
The description of my problem is ...
2
votes
0answers
151 views
Probabilities involving Beurling density
I am interested in calculating probabilities involving Beurling densities. Since it's likely probabilists are not familiar with the definitions, I give them below.
Definitions.
A metric space is ...
2
votes
1answer
83 views
Estimating mean and variance of a distribution based on error-prone estimates of its cdf
Suppose I have some random variable $X$ taking values in $[a, b]$ with unknown distribution (I am happy to assume the distribution is smooth, though it would be nice to not have to).
I have a ...
5
votes
1answer
195 views
Exactly sampling from a distribution with access to the probabilities only
There is a discrete distribution where integers, $k$, from $1$ to $n$ occur with probability $p_{k}$, all $p_{k}$ are unknown.
Rather than having access to the distribution we have access to $n$ ...
0
votes
1answer
158 views
Monte Carlo estimator with autocorrelated samples
Given an integration problem $I=\int{f(x)dx}$, we can construct an ordinary Monte Carlo estimator as
$E[I]=\sum\limits_i\frac{f(x_i)}{p(x_i)}$
where the samples $x_i$ are usually i.i.d. and drawn ...
3
votes
2answers
2k views
Approximating Probability Distribution by Sampling
Consider a discrete probability distribution over $n$ events. Assume that the probabilistic kernel is a black box, that is, we can only sample from it without knowing anything about the type or ...
6
votes
0answers
214 views
Sampling from a Convex Body with Many Extremal Points
Let $p_{1}, \ldots, p_{N}$ be a collection of points in $\mathbb{R}^{n}$. I would like to sample uniformly from the convex hull of these $N$ points in an `efficienct' way. In my setting, I have $n$ ...
1
vote
2answers
241 views
Sampling uniformly from all possible line segments of a given length that fit inside a container
Consider that task of randomly placing a line segment of some length $L$ near a plane s.t. a point $p$ at the center of the line segment is at most a distance $H$ from the plane and intersections ...
