Questions tagged [pr.probability]
Questions in probability theory
204
questions
2
votes
0answers
117 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 ...
0
votes
0answers
34 views
Expected value in case of Langevin dynamics
Let $U(\beta) = \exp(-f(\beta))$ where $f$ is $m$ strongly convex and $L$ Lipschitz smooth. I am trying to find an upper bound on $E[\|\beta_t \|^2]$ where $\beta_t \in \mathcal{R}^p$ is defined below
...
5
votes
0answers
82 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 ...
5
votes
1answer
172 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 ...
-1
votes
1answer
98 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\...
0
votes
0answers
42 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 ...
-1
votes
1answer
48 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 (...
3
votes
1answer
136 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 ...
0
votes
0answers
36 views
Delaunay Triangulaition (or Voronoi) for a specific distribution of points
I found a paper about Delaunay triangulation for a set of points that are distributed by the Poisson distribution (https://pdfs.semanticscholar.org/9693/4b7e8e5483893f4874d7ba6afd812bbfe0ba.pdf). The ...
11
votes
3answers
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 ...
4
votes
0answers
77 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, ...
1
vote
0answers
92 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 ...
5
votes
1answer
111 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 $...
4
votes
1answer
382 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 $\...
4
votes
1answer
234 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, ...
2
votes
1answer
78 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 ...
4
votes
1answer
168 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$ ...
6
votes
1answer
216 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]} = \...
1
vote
1answer
77 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}\...
1
vote
0answers
60 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 ...
4
votes
2answers
168 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 ...
3
votes
0answers
58 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 ...
5
votes
2answers
121 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 ...
6
votes
2answers
284 views
Infinite process balls in bins problem
Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
1
vote
0answers
44 views
Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time? [closed]
In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also ...
7
votes
2answers
228 views
Is uniform convergence faster for low-entropy distributions?
Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$. Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\...
2
votes
1answer
106 views
Empirical Rademacher averages versus Hoeffdings bound
Let $M$ be finite set with $n$ distinct elements. I want to probalistically approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$.
An upper-bound for ...
2
votes
1answer
107 views
Sample Complexity for Order Statistics
I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.
Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $...
2
votes
1answer
107 views
A coupon collector type problem with changing probabilities
Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\...
2
votes
1answer
134 views
Recovering a rank-one matrix from its eigendecomposition after randomized rounding
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
4
votes
1answer
113 views
Probability of a $k$-path in a random graph
Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$,
the following fact is well known:
\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\...
0
votes
0answers
35 views
Expected size of the min-cut, under edge perturbations
Suppose we have a graph $G(V, E)$.
Assume that the min-cut of this graph is given $C=(A/B)$ and denote the size of the cut with $|C|$.
Create a random modification of the graph:
Drop each ...
5
votes
2answers
179 views
Heterogeneous Hoeffding/McDiarmid
Hoeffding's inequality for independent random variables $a_i\le X_i\le b_i$ states that their sum has sub-Gaussian tails, decaying as $\exp(-2t/\sum_i (b_i-a_i)^2)$. Question: Are there any ...
1
vote
1answer
94 views
Using a probability distribution in the fooling set technique for communication complexity
I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition:
Let $\mu$ be a probability distribution of $X\...
3
votes
1answer
159 views
Tighter Probability Bounds
Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
-1
votes
1answer
151 views
Application of the inequality with expectations
Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
4
votes
1answer
187 views
Support size lower bound for $k$-wise uniform distribution
So I have this question which I can't seem to find a solution to:
Prove that if $X = (X_1, ... X_n)$ is $k$-wise uniform* and each $X_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \...
2
votes
1answer
107 views
Other Uniform Bound
In theoretical machine learning, VC-dimension (VCD) and Rademacher average (RA) are two frequently used uniform bounds, providing better sample complexity than bounds such as Chernoff bound and ...
2
votes
0answers
45 views
Is there a complete and finite axiom scheme for conditional independence? (Graphoids)
Note: This is a better-written version of an unanswered question asked before on MathOverflow.
Question: Is there a complete and finite axiom scheme for conditional probability?
If so, is there a ...
0
votes
1answer
81 views
Does this pairwise independent random process have expected max load $\sqrt{n}$?
This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ . There the following question is asked and answered in ...
7
votes
1answer
137 views
Random Deterministic Automata
I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)...
4
votes
1answer
273 views
Janson-type inequality, limited dependence
So I am trying to figure out an upper bound on the probability of the following...
This is a question related to a problem I am working on (not for a class, just for fun)
Let $\Omega=\{X_{1},\dots,...
1
vote
0answers
52 views
Problem dependent lower bound for stochastic bandits with full information
Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
13
votes
2answers
806 views
What is the proof of this nonstandard version of Azuma's inequality?
In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:
Let $C_1, \dots, C_k$ be real-valued ...
3
votes
2answers
213 views
Hardness of exact binomial tail bounds
Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. ...
6
votes
1answer
221 views
A random walk that moves to less-visited nodes
Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least ...
4
votes
1answer
485 views
Relation between variance and mutual information
Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$
This bound may be ...
6
votes
1answer
127 views
Directed graph with bounded in-deg can be partitioned in a balanced way
I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two ...
9
votes
0answers
163 views
Fourth(?) moment method for minimum value
I would like to lower bound the quantity $\Pr[X\ge t, Y\ge t]=\Pr[\min(X,Y)\ge t]$ using the small moments of $X$, $Y$ and $XY$.
In particular I am interested in the case where $E[X]=E[Y]=0$, but $E[X ...
3
votes
1answer
165 views
Lower bound on probability of getting two close points in a sample of $n$ points
Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors.
$S\subseteq D$ is obtained by sampling $n$ ...
