# Questions tagged [sampling]

The sampling tag has no usage guidance.

60
questions

**1**

vote

**1**answer

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

**3**

votes

**0**answers

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

**0**

votes

**0**answers

20 views

### Algorithm for sampling stratification-constrained permutations

Let $\mathcal{X}$ be some base space, and let $\mathbf{S} =S_1, \ldots, S_N$ be a cover (not a partition, i.e. they can overlap) of $\mathcal{X}$. I will refer to the $S_i$ as strata, and to the cover ...

**1**

vote

**1**answer

70 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

28 views

### Keeping track of the variance of a Metropolis-Hastings estimator

Let $(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces, $p,q$ be probability densities on $(E,\mathcal E,\lambda)$, and $\varphi:E'\to E$ be bijective and $(\mathcal E',\...

**0**

votes

**0**answers

28 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

35 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

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

**0**

votes

**0**answers

75 views

### Minimizing weighted variance subject to constraints

Let $X$ be a random variable that is uniformly distributed on the
set $\Theta\equiv\left\{ 0,\frac{1}{n},\frac{2}{n},...,\frac{n-1}{n},1\right\} $ for some large $n$.
Suppose that the set $\Theta$ is ...

**1**

vote

**1**answer

115 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

108 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

44 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

166 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

85 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

264 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

334 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

216 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

63 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

108 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

241 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

117 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

485 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

739 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

40 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

129 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

172 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

99 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

122 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

610 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

219 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

148 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

44 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

226 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

701 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

147 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

82 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

194 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

153 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

206 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

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

**1**

vote

**0**answers

74 views

### Stochastic process inference from partial observations

Consider a set $U$. My signal is a piece-wise constant "function"
$Sig: t \mapsto s$, i.e. the signal at time $t$ equals to some subset
$s \subset U$. One can see $Sig(t)$ as a stochastic process.
...

**1**

vote

**1**answer

419 views

### Discretizing a cosine function?

I'd like to start by noting that for some fixed natural $N$ basis functions for my system will be generated by $f(k,x)$ as defined and explained here or in numerous other sources:
$$f(k,x) = \sqrt2 \...

**1**

vote

**3**answers

299 views

### A sampling and learning question

Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button.
We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to ...

**0**

votes

**1**answer

559 views

### transform a polynomial into another one upto a constant

I have a polynomial $p(x)=a_Nx^N+a_{N-1}x^{N-1}+\dots+a_0$. I want to convert this into another polynomial of same order, say $b_Ny^N+b_{N-1}y^{N-1}+\dots+b_0$. Is it possible to find a transformation ...

**3**

votes

**2**answers

1k views

### Sampling without replacement until hitting a subset

I randomly sample uniformly from $ \{1,..,N \}$ without replacement until drawing a number $ \leq k$. Denote the expected number of draws by $R(N,k)$. I want a good approximation for $\sum_{k=1}^N R(...

**3**

votes

**1**answer

421 views

### When can you describe a population and its component subpopulations with the same parametric family of distributions?

I believe that it is often the case that you are trying to select the best probability distribution to use to describe some phenomenon you are studying, and you have data not only for a population, ...