Questions tagged [pr.probability]
Questions in probability theory
244
questions
2
votes
1
answer
187
views
Additive chernoff bound
From wikipedia,
Additive form (absolute error)
The following theorem is due to Wassily Hoeffding and hence is called the Chernoff-Hoeffding theorem.
Chernoff-Hoeffding theorem.
Suppose $X_1, \ldots, ...
- 109
0
votes
0
answers
46
views
Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?
The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here:
Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$:
If $x \in L$ (...
2
votes
0
answers
53
views
Approximately sampling from a discrete unimodal distribution with large support
I have an algorithmic problem and I am curious if a solution is known in the literature, because I cannot find it. I came up with an algorithm of my own, but would be curious if something is known.
I ...
- 630
3
votes
0
answers
46
views
Approximate decomposition of a many-to-one assignment
Suppose we have $n$ items and $n$ agents and we want to assign one item to each agent. We have a probability matrix $P$ such that $p_{i,j}$ is the probability that agent $i$ gets item $j$. If $\sum_j ...
- 2,078
0
votes
0
answers
42
views
Speed networking algorithm
I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
- 101
1
vote
0
answers
21
views
Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG
I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over ...
- 111
0
votes
1
answer
168
views
An additive combinatoric probability question
Let $A,B \subset [d]$, where $[d] = \{0,...,d \}$, such that $A\cap B = \phi$ and $|A| = |B| = \frac{d+1}{2}$. I was studying the size of $|(2A \cup 2B) \triangle (A+B)|$, where $\triangle$ is the ...
0
votes
0
answers
53
views
Non regular distribution in [0,1] examples
We say a distribution is regular is its associated virtual function \psi(x) = x - (1-F(x))/f(x) is monotone non decreasing. Here F and f are CDF and PDF for the distribution.
How do I construct an ...
- 11
0
votes
0
answers
51
views
Is there any bound on the convergence rate of actions in bandit literature?
In classical bandit problems where there are $K$ arms and we should decide which arm to pull at each period, the main issue is to design an algorithm that minimizes the regret and we find a bound on ...
- 61
0
votes
0
answers
41
views
Proof that Sufficiency and Caliberation by group are equivalent notions
I am currently reading through the Fairness and Machine Learning book and I have a problem understanding the proof of Proposition 1 in Chapter 3 (titled Classification) (https://fairmlbook.org/...
2
votes
1
answer
280
views
Chernoff bound for weighted sums of Bernoulli random variables
I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest.
Let $X_1, \dots, X_n$ be independent random varibles such that each $X_i$ is a ...
- 23
1
vote
1
answer
81
views
A bound that follows from submodularity
I am studying Lemma 1 of this paper: The Adaptive Complexity of Maximizing a Submodular Function. The proof appears on page 11.
I got stuck on this inequality:
where $f$ is a monotone submodular set ...
- 113
0
votes
0
answers
62
views
How do I calculate the information content of a mass spectrum?
Ions in a mass spectrum are represented using two independent values for the mass-to-charge ratio [m/z] of the ion and it's relative abundance. Here's an example for caffeine from HMDB: https://hmdb....
- 101
1
vote
0
answers
28
views
Generalization bound for margin / ramp loss which is not vacuous when margin tends to zero, but recovers usual generalization bound for 0-1 loss
For any $t \ge 0$, consider the ramp loss function $\phi_t:\mathbb R \to [0,1]$ defined by
$$
\phi_t(z) = \begin{cases}0,&\mbox{ if }z \ge t,\\
1-z/t,&\mbox{ if }z \in (0,t),\\
1,&\mbox{ ...
- 291
1
vote
0
answers
46
views
Will the maximum entropy joint distribution given a known set of marginal distributions have the maximum plausible support?
Define $[n] = \{1, 2, ..., n\}$. Given a distribution $P : \{0, 1\}^{[n]} \rightarrow [0, 1]$ and a subset $S \subseteq [n]$, we can define the $S$-marginal of $P$, $P_S : \{0, 1\}^S \rightarrow [0, 1]...
- 1,572
1
vote
0
answers
85
views
Generalizing Fano's inequality
Fano's inequality says the following:
Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
- 11
3
votes
1
answer
181
views
Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support
Say we have a black-box access to a distribution $\mathcal{D}$ with finite support $\{1,2,...,n\}$ with probability mass function $i \mapsto p_i$. How many samples of $\mathcal{D}$ are needed to learn ...
- 33
1
vote
2
answers
138
views
How to find the size of an ϵ-net of a vector space?
Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and ...
- 113
0
votes
0
answers
31
views
Minimax computation for classification problems with smooth densities functions
Fix $d=1$, $r \in (0,\infty)$ and a neigborhood $\Omega$ of $0$ in $\mathbb R^d$ and let and let $W^{1,\infty}(r)$ be the Sobolev ball continuously differentiable functions $f:\mathbb R^d \to \mathbb ...
- 291
2
votes
1
answer
206
views
Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$
$\DeclareMathOperator\sg{sg}\DeclareMathOperator\VCdim{VCdim}$
Let $X$ be a measurable space and given a measurable function $f:X \to \mathbb R$, recall that the subgraph of $f$, denoted $\sg(f)$ is ...
- 291
3
votes
0
answers
107
views
Outputting true with probabiltiy $P(A|B)$ given $P(B), P(B|A)$, and a function which returns true with probability $P(A)$
I have a black-box function which returns true with probability $ P(A) $, that I don't know how to calculate.
I receive evidence B, and I want to create a function which returns true with probability $...
- 464
3
votes
3
answers
502
views
Evaluating asymptotic probabilities of First Order Logic Formulas?
0-1 Laws in first order logic state that the probability of a FOL sentence $\Phi$, defined as follows:
$$P(\Phi) = \frac{|\{\omega \in \Omega^{n}:\omega \models \Phi\}|}{|\Omega^{n}|} $$
where $\Omega^...
- 706
1
vote
0
answers
320
views
Can I estimate the probability of a given output of the diffusion model?
I have a pretrained Grad-TTS (https://arxiv.org/abs/2105.06337) denoising diffusion model that predicts a spectrogram (an array of numerical values) $Y$ from input text $X$. If I have a text $X_0$ and ...
- 11
7
votes
2
answers
329
views
Isolation Lemma over finite fields
i couldn't find the answer to the following question:
The Isolation Lemma of Mulmuley, Vazirani and Vazirani uses the weight function $w:[n] \rightarrow [m]$ and assigns a subset $S \subseteq [n]$ the ...
- 615
4
votes
0
answers
243
views
Maximize the mutual information between 2 discrete random variables
I have two random variables $X$ and $Y$. $X$ follows Poisson-Binomial distribution with parameters $\{q_1, \ldots, q_k\}$. Thus, $X$ can take values in the set $\{0,1,\ldots,k\}$.
$Y$ is a binary ...
- 99
3
votes
1
answer
201
views
Proof and interpretation of the No Free Lunch theorem in data privacy
This question relates to a supposed counterexample to the No Free Lunch theorem governing data privacy mechanisms, as stated by Kifer et al (Section 2.1).
Colloquially, the theorem states that no ...
- 39
7
votes
0
answers
210
views
From coin flips to algebraic functions via pushdown automata
Background
We're given a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads ...
- 191
7
votes
0
answers
148
views
Probability distributions generated by pushdown automata
Background
This question is about generating random variates, in the form of their binary expansions, on restricted computing models. Specifically, the computing model is based on pushdown automata (...
- 191
0
votes
1
answer
102
views
Differential privacy definition: subset of range of values vs. equals a value in the range
Consider only $\epsilon$-differential privacy. The textbook definition for this is:
Definition 1: "A randomized algorithm $\mathcal{M}$ with domain $\mathbb{N}^{|\chi|}$ is $\epsilon$-...
- 87
8
votes
0
answers
151
views
What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)
Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$.
The Entropy-Constrained Quantization problem asks what is the best ...
- 9,438
9
votes
0
answers
160
views
"Looking for help understanding a proof by Gossner (1998)."
Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
- 209
1
vote
1
answer
186
views
Young Diagrams and distinguishing between two distributions
Introduction:
The reference for everything is this paper.
The Robinson–Schensted–Knuth (RSK) algorithm is a well-known
combinatorial algorithm with diverse applications throughout
mathematics, ...
- 173
1
vote
0
answers
232
views
Converse form of Chernoff bound
Suppose $X_1,\ldots,X_n$ are i.i.d. random variables, all with mean $p$, and we have the statement that $\Pr\left[\sum_i X_i\geq 0.8n\right]\geq 0.9$, can we use this to conclude anything about $p$ (...
- 251
6
votes
5
answers
441
views
Relationship between Random Graph Theory and TCS
Sorry for this large and vague question. I am a new grad probability student recently interested in random graph theory(RG). I heard from someone in math department that RG has close relationship to ...
- 113
4
votes
1
answer
161
views
What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?
The following result is adapted from Anthony and Bartlett, 1999 (Theorem 4.9).
Theorem There exist positive constants $m_0 \le 400$, $c_1 \le 8$, $c_2 \le 41$, $c_3 \ge 1/576$ such that, if $(\Omega,\...
- 143
1
vote
0
answers
73
views
Prune length distribution of random binary tree
Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...
2
votes
0
answers
165
views
Theorem on non-decreasing probability of success of an algorithm
Question: What's a standard name/framework for the following, or some variant?
Stated briefly for a probabilistic algorithm: define $p_n$ as the conditional probability of success of a fork of the ...
- 109
3
votes
1
answer
103
views
Conditioning Probability on a Language With Measure 0
Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...
- 257
4
votes
0
answers
152
views
Are there any known Chernoff/Hoeffding bounds for the case of "almost independence"?
The usual statement of a Hoeffding bound (e.g. https://sites.math.washington.edu/~morrow/335_17/ineq.pdf) requires independent random variables.
My question is: Do there exist bounds similar to ...
- 187
1
vote
1
answer
215
views
Effect of self loops on mixing time?
Consider 2 graphs G1 and G2.
G1: Any non-regular graph.
G2: Same graph but with added self-loops such that degree of each node is the same (either some $\Delta$, or maximum '$n$', where $n$ is the ...
- 33
0
votes
0
answers
64
views
Rademacher complexity of k-fold maxima of hyperplanes
Aryeh Kontorovich wrote a technical report on 'Rademacher complexity of k-fold maxima of hyperplanes.' But its link (https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf) is not accessible ...
- 9
3
votes
0
answers
253
views
Power law for degree distribution of random KNN graphs?
Setup Sample random points from say standard Gaussian (or uniform) distribution in $R^{d}$ for some "d"
and consider a KNN (K-nearest neigbour) graph for some K.
Look at the degree ...
2
votes
0
answers
133
views
Can a tractable sequence distribution prefer satisfying to unsatisfying assignments?
Let $p(x)$ be a Boolean circuit on $n$ bits $x \in \{0,1\}^n$. Consider a program that computes a probability distribution over all sequences $x$, autoregressively factored as
$$\pi(x | p) = \prod_{0 ...
- 3,243
6
votes
0
answers
122
views
Is there a known notion of "stochastic dependent pair"?
I came upon this when thinking about the semantics of probabilistic programs. Say you have a generative model
N ~ Poisson()
for n = 1:N
X[i] ~ Normal()
Then the ...
- 229
5
votes
1
answer
185
views
Complexity of finding the most likely edge
Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.
Now consider the following random process. First sample a uniformly random ...
- 3,950
-1
votes
1
answer
108
views
Required sample size to hit certain subset of a ground set
Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N_1,\cdots,N_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\...
- 265
0
votes
0
answers
47
views
understanding generalized coupon collector for distributions or learning mixture of distribution
Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
- 251
-1
votes
1
answer
66
views
Notation in proof for Asymptotic Equipartition Property
In the following lecture notes chapter 3, page 12-13, they state the following
We begin by introducting some important notation:
- For a set $\mathcal{S},|\mathcal{S}|$ denotes its cardinality (...
- 133
3
votes
1
answer
196
views
Binary search on coin heads probability
Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function. I want to find the smallest $x$ such that $f(x) \ge 1/2$.
If I had a way to compute $f(x)$ given $x$, I could simply use ...
- 11.7k
13
votes
3
answers
2k
views
"Almost all objects have property P" vs. "It is easy to test whether an object has property P"
I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable".
My guess ...
- 1,723