Questions tagged [pr.probability]
Questions in probability theory
211
questions
-1
votes
0answers
47 views
Concentration bounds for hypergeometric distribution
I asked a similar question a while back. I have reformulated the question. My original intention was to ask this question.
Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are ...
-1
votes
0answers
61 views
A variant of “hypergeometric” distribution
This is already posted here.
We all are aware of Hypergeometric distribution. Let me first briefly discuss what it is.
Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are blue. ...
2
votes
0answers
142 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 ...
3
votes
1answer
92 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 ...
4
votes
0answers
99 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 ...
1
vote
1answer
134 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 ...
0
votes
0answers
40 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 ...
3
votes
0answers
186 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
0answers
132 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
36 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
...
6
votes
0answers
102 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
176 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
102 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
43 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
52 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
142 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
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
81 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
96 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
0answers
115 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
400 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
251 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
90 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
172 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
239 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
84 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
64 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
170 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
135 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
312 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
234 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
109 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
118 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
109 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
137 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
123 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
39 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 ...
6
votes
2answers
220 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^2/\sum_i (b_i-a_i)^2)$. Question: Are there any ...
1
vote
1answer
99 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
170 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
157 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
189 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
112 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
51 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
148 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
275 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
54 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 ...
