# Questions tagged [sampling]

The tag has no usage guidance.

12 questions
Filter by
Sorted by
Tagged with
375 views

### Finding uniformly random perfect matching of a graph

Problem: Suppose that we have a graph $G$ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly ...
• 121
174 views

### Number of random bits necessary to approximate an arbitrary distribution

Given a discrete distribution $X$ and $\varepsilon\in(0,1)$, consider the minimal $m\in\mathbb{N}$ such that $\mathbf{SD}(f(U^m),X)\leq\varepsilon$, for some (the best, possibly inefficient) ...
• 179
136 views

### Consistent Sampling a Random Walk

Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid. I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
• 958
146 views

### Complexity of sampling a clique uniformly at random

Let $G$ be an undirected graph, and let $C_1, ..., C_M$ denote all possible cliques in $G$. What is known on the complexity of sampling a clique uniformly at random. That is, returning clique $C_i$ ...
• 1,153
141 views

• 4,041