Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
6
votes
2answers
203 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
votes
0answers
41 views

Probability distribution and information theory [closed]

In the study of statistics, a given family of probability densities depending smoothly upon a parameter $\theta$ can be expressed in the form $p(x,\theta)=exp\left[c(x)+\sum_{r}\theta^{r}S_{r}(x)-\psi(...
1
vote
1answer
118 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
32 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 ...
4
votes
0answers
139 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
128 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 ...
33
votes
6answers
5k views

Reverse Chernoff bound

Is there an reverse Chernoff bound which bounds that the tail probability is at least so much. i.e if $X_1,X_2,\ldots,X_n$ are independent binomial random variables and $\mu=\mathbb{E}[\sum_{i=1}^n ...
5
votes
0answers
88 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 ...
13
votes
2answers
821 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 ...
-1
votes
1answer
100 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
140 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 ...
6
votes
2answers
292 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 ...
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
80 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, ...
2
votes
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 ...
2
votes
1answer
2k views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will ...
12
votes
2answers
3k views

Sum of Independent Exponential Random Variables

Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - e^{-x/\...
4
votes
1answer
386 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 $\...
5
votes
1answer
112 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
242 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
81 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
2answers
1k views

An upper bound for chi-square divergence in terms of KL divergence for general alphabets

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
4
votes
1answer
170 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
223 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]} = \...
23
votes
2answers
600 views

Which graph parameters are NOT concentrated on random graphs?

It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, ...
1
vote
1answer
82 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
62 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 ...
26
votes
2answers
488 views

Current tightest bounds for critical 3-SAT density

I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or ...
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
122 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 ...
5
votes
3answers
261 views

Probability for an element to appear in at least one set

Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct. What is the ...
29
votes
1answer
1k views

Finding a biased coin using a few coin tosses

The following problem came up during research, and it's surprisingly clean: You have a source of coins. Each coin has a bias, namely a probability that it falls on "head". For each coin ...
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
229 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
113 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

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 ...
15
votes
1answer
272 views

What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
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
2answers
139 views

Multiple independent random number streams

Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel. In other words, one thread will have a full-...
2
votes
1answer
136 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{ ...
19
votes
3answers
1k views

What is the expected depth of a randomly generated tree?

I thought about this problem a long time ago, but have no ideas about it. The generating algorithm is as follows. We assume there are $n$ discrete nodes numbered from $0$ to $n - 1$. Then for each $i$...
4
votes
1answer
274 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,...
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
37 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 ...
3
votes
2answers
716 views

Sampling distinct values with probability proportional to their frequency

This is a variant of my previous question (Reservoir sampling of distinct values) I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass ...

1
2 3 4 5