# Questions tagged [sampling]

The sampling tag has no usage guidance.

65
questions

**0**

votes

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**4**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**2**answers

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 ...