Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
3 votes
1 answer
144 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 ...
user avatar
  • 33
1 vote
2 answers
108 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 ...
user avatar
  • 113
0 votes
0 answers
24 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 ...
user avatar
  • 217
0 votes
0 answers
53 views

Does the the equivalence of Total variation distance formulas assumes that the two distributions are symmetrical?

Does the the equivalence of Total variation distance formulas presented here(https://ece.iisc.ac.in/~parimal/2019/statphy/lecture-14.pdf) assumes that the two distributions are symmetrical ?
user avatar
  • 1
2 votes
1 answer
185 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 ...
user avatar
  • 217
3 votes
0 answers
104 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 $...
user avatar
3 votes
3 answers
471 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^...
user avatar
  • 684
0 votes
0 answers
17 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 ...
user avatar
7 votes
2 answers
297 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 ...
user avatar
  • 615
4 votes
0 answers
201 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 ...
user avatar
3 votes
1 answer
166 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 ...
user avatar
  • 39
4 votes
0 answers
110 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 ...
user avatar
  • 211
7 votes
0 answers
132 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 (...
user avatar
  • 211
0 votes
1 answer
80 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$-...
user avatar
8 votes
0 answers
146 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 ...
user avatar
  • 9,378
8 votes
0 answers
157 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 ...
user avatar
  • 199
1 vote
1 answer
178 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, ...
user avatar
  • 153
1 vote
0 answers
169 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$ (...
user avatar
0 votes
0 answers
102 views

Using the probabilistic method to fill the gaps in a proof of set disjointness

In the 2-party $k$-sparse set disjointness problem, we have a set $U$ of size $n$ and there are two parties: Alice, who gets a set $X \subseteq U$ and Bob who gets a string $Y \subseteq U$, and it ...
user avatar
  • 51
0 votes
0 answers
105 views

Does this sum-product algorithm make more sense?

Recall the belief propagation "sum-product" algorithm (from wikipedia): $\forall x_v\in Dom(v),\;$ $\mu_{v \to a} (x_v) = \prod_{a^* \in N(v)\setminus\{a\} } \mu_{a^* \to v} (x_v)$ $ \mu_{...
user avatar
  • 129
6 votes
5 answers
350 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 ...
user avatar
  • 113
4 votes
1 answer
130 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,\...
user avatar
1 vote
0 answers
54 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 ...
user avatar
2 votes
0 answers
148 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 ...
user avatar
  • 109
3 votes
1 answer
100 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 ...
user avatar
4 votes
0 answers
123 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 ...
user avatar
  • 187
1 vote
1 answer
176 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 ...
user avatar
  • 33
0 votes
0 answers
44 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 ...
user avatar
3 votes
0 answers
210 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 ...
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 ...
user avatar
6 votes
0 answers
112 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 ...
user avatar
5 votes
1 answer
179 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 ...
user avatar
  • 3,920
-1 votes
1 answer
106 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\...
user avatar
0 votes
0 answers
45 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 ...
user avatar
-1 votes
1 answer
61 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 (...
user avatar
  • 131
3 votes
1 answer
158 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 ...
user avatar
  • 10.4k
11 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 ...
user avatar
4 votes
0 answers
89 views

Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience. So, Iet $X = (X,d)$ be a Polish space, ...
user avatar
  • 217
1 vote
0 answers
102 views

Weighted circular balls into bins

I would like to ask you for a help about modified balls into bins problem. Consider $n$ weighted balls such that each ball has a weight $w_i$ that is at most $W$. Furthermore, each of $m$ bins has a ...
user avatar
  • 303
5 votes
0 answers
116 views

Majority function stability under deletion and addition of entries

It is well known that the majority function is stable under random flipping of bits. That is, if $v$ is a random binary vector, and then we re-sample each bit of $v$ with probability $\delta$ and get $...
user avatar
4 votes
1 answer
410 views

Maximization of Mutual Information

Let $X\in\{0,1\}^d$ be a Boolean vector and $Y, Z\in\{0,1\}$ are Boolean variables. Assume that there is a joint distribution $\mathcal{D}$ over $Y, Z$ and we'd like to find a joint distribution $\...
user avatar
4 votes
1 answer
258 views

How tight is the XOR lemma?

The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
user avatar
  • 235
3 votes
1 answer
111 views

Reconstruction of a sequence generated by a Markov chain - reference request

Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols ...
user avatar
4 votes
1 answer
200 views

Why is differential privacy defined over the exponential function?

For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies $$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ ...
user avatar
6 votes
1 answer
287 views

Big-O bounds on the k-th largest element of iid Gaussians

I'm interested in the following problem. Let $X_1, \dots, X_n$ be iid samples with a $N(0,1)$ distribution. Let $X_{[k]}$ be the $k$-th largest element of $\{X_1, \dots, X_n\}$, so e.g. $X_{[1]} = \...
user avatar
1 vote
1 answer
99 views

How to play the following game? (placing balls into bins)

Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$. The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\...
user avatar
  • 9,378
1 vote
0 answers
66 views

Mapping of entire balls using Locality Sensitive Hashing (LSH)

LSH functions are useful for approximate nearest neighbor search. They are usually defined, for distance metric $d$ and $c>1$ as follows: A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
user avatar
  • 9,378
4 votes
2 answers
176 views

If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including ...
user avatar
3 votes
0 answers
59 views

Probability of detecting small bias of a die in the low confidence regime / balls and bins

We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which ...
user avatar
  • 881
5 votes
2 answers
146 views

Statistical Distance Growth Given K Independent Copies

Let $X$ and $Y$ be distributions with statistical distance (total variation distance) at most $d$. What is the best upper bound you can give on the statistical distance between $k$ independent copies ...
user avatar
  • 117

1
2 3 4 5