Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
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, ...
Dotman's user avatar
  • 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$ (...
hedgehog0's user avatar
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 ...
user2316602's user avatar
3 votes
0 answers
44 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 ...
Erel Segal-Halevi's user avatar
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 ...
Helen Grey's user avatar
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 ...
Joseph Turian's user avatar
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 ...
Rishabh Kothary's user avatar
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 ...
dev's user avatar
  • 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 ...
Amin's user avatar
  • 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/...
Segun Ojo's user avatar
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 ...
Xinyu Mao's user avatar
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 ...
Null_Space's user avatar
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....
Ninja Chris's user avatar
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{ ...
dohmatob's user avatar
  • 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]...
Samuel Schlesinger's user avatar
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 ...
learning_tcs's user avatar
3 votes
1 answer
180 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 ...
actcon's user avatar
  • 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 ...
XYZ's user avatar
  • 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 ...
dohmatob's user avatar
  • 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 ...
dohmatob's user avatar
  • 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 $...
Command Master's user avatar
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^...
SagarM's user avatar
  • 706
1 vote
0 answers
315 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 ...
user65914's user avatar
7 votes
2 answers
328 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 ...
Etsch's user avatar
  • 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 ...
wanderer's user avatar
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 ...
Jnov's user avatar
  • 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 ...
Peter O.'s user avatar
  • 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 (...
Peter O.'s user avatar
  • 191
0 votes
1 answer
99 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$-...
user1246462's user avatar
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 ...
R B's user avatar
  • 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 ...
Nav89's user avatar
  • 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, ...
AngryLion's user avatar
  • 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$ (...
Annonymous's user avatar
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 ...
MikeG's user avatar
  • 113
4 votes
1 answer
160 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,\...
user332582's user avatar
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 ...
user152789811's user avatar
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 ...
fgrieu's user avatar
  • 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 ...
Bader Abu Radi's user avatar
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 ...
zfkmz's user avatar
  • 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 ...
SSS's user avatar
  • 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 ...
listener's user avatar
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 ...
Alexander Chervov's user avatar
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 ...
Geoffrey Irving's user avatar
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 ...
phipsgabler's user avatar
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 ...
Simd's user avatar
  • 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\...
Sudipta Roy's user avatar
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 ...
Annonymous's user avatar
-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 (...
sn3jd3r's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
Cyriac Antony's user avatar

1
2 3 4 5