Questions tagged [sampling]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...