Questions tagged [pr.probability]
Questions in probability theory
205
questions
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 ...
32
votes
14answers
6k views
Book on Probability
While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability.
It seems that the authors of ...
32
votes
4answers
4k views
Does a noisy version of Conway's game of life support universal computation?
Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life."
Do such ...
30
votes
2answers
1k views
Drunken birds vs drunken ants: random walks between two and three dimensions
It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly ...
29
votes
3answers
1k views
What does one mean by heuristic statistical physics arguments?
I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a ...
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 ...
26
votes
2answers
485 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 ...
24
votes
2answers
2k views
Balls and Bins analysis in the $m \gg n$ regime: gaps
Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and $X_{\mathrm{sec-...
23
votes
2answers
592 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, ...
22
votes
2answers
2k views
Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?
If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave. Clearly in the worst case you cannot upper bound $\...
22
votes
3answers
2k views
Number of distinct nodes in a random walk
Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically ...
21
votes
6answers
1k views
What is the best way to get a close-to-fair coin toss from identical biased coins?
(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many ...
21
votes
1answer
667 views
A flowchart for concentration bounds
When I teach tail bounds, I use the usual progression:
If your r.v is positive, you can apply Markov's inequality
If you have independence and also bounded variance, you can apply Chebyshev's ...
21
votes
1answer
534 views
Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$
I encountered the following result during my research.
$$\lim\limits_{n\to \infty} \mathbb{E}\left[
\frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}
\right] = 1$$
where $m=\omega(\sqrt n)$ and $a_1,\...
20
votes
1answer
477 views
Are there efficient general Bonferroni-style bounds known?
A classic problem in probability theory is to express the probability of an event in terms of more specific events. In the simplest case, one can say $P[A \cup B] = P[A] + P[B] - P[A \cap B]$. Let's ...
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$...
18
votes
0answers
498 views
Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?
Question 1: Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function on $n$ variables that can be expressed by a Boolean ...
17
votes
1answer
1k views
The complexity of sampling (approximately) the Fourier transform of a Boolean function
One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.
Here and ...
17
votes
1answer
581 views
Balls and Bins analysis in the m >> n regime.
It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have $O(\log n)$ balls in it. In general, one can ask about $m > n$ balls in $n$ bins. A paper from ...
16
votes
2answers
531 views
Avalanche like stochastic process
Consider the following process:
There are $n$ bins arranged from top to bottom. Initially, each bin contains one ball. In every step, we
pick a ball $b$ uniformly at random and
move all the balls ...
16
votes
0answers
261 views
When does adding edges decrease the cover time of a graph?
When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $...
14
votes
4answers
1k views
Throwing Balls into Bins, estimate a lowerbound of its probability
This is not a homework, though it looks like. Any reference is welcome. :-)
Scenario: There are $n$ different balls and $n$ different bins (labled from 1 to $n$, from left to right). Each ball is ...
14
votes
1answer
264 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 ...
14
votes
1answer
426 views
Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$
For a Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$, the influence of the $i$th variable is defined as
$$
\operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus ...
14
votes
2answers
551 views
Pairwise independent gaussians
Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that
$Y_i$'s are pairwise independent gaussians with ...
13
votes
3answers
2k views
Chernoff-type Inequality for pair-wise independent random variables
Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value ...
13
votes
3answers
3k views
An extension of Chernoff bound
I am looking for a reference (not a proof, that I can do) to the following extension of Chernoff.
Let $X_1,..,X_n$ be Boolean random variables, not necessarily independent.
Instead, it is guaranteed ...
13
votes
2answers
813 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 ...
13
votes
2answers
399 views
What's the bias of random polynomials with low degree over GF(2)?
I have a question concerning low-degree polynomials and probability:
What is the (assyptotic behavior of the) probability that a
random* polynomial, $p$, over GF(2), with degree $\le d$ and n ...
12
votes
6answers
782 views
Computing the approximate population of a bloom filter
Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.
Is it possible to approximate the number of elements inserted into the bloom filter?
...
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/\...
12
votes
1answer
1k views
Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance
We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
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 ...
11
votes
1answer
455 views
Borel-Cantelli Lemma and Derandomization
I was reading a paper titled Random Oracles with(out) Programmability. The last paragraph of section 2.3 reads:
[Using our novel approach] there is no
need to apply well-known classical ...
11
votes
0answers
414 views
Cheeger's inequality for directed graphs?
Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
11
votes
0answers
355 views
Is Bayesian updating computationally unfeasible?
Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be ...
10
votes
4answers
486 views
Constructions better than a random one.
I am interested in examples of constructions in the complexity theory which are better than a random constructions.
The only one example of such construction which I know is in the field of error-...
10
votes
3answers
538 views
Is there any known CCC closed under a probabilistic powerdomain operation?
Equivalently, is there a known denotational semantics for probabilistic higher-order functional programming languages? Specifically, is there a domain model of pure untyped $\lambda$-calculus extended ...
9
votes
2answers
299 views
Guessing a low entropy value in multiple attempts
Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice ...
9
votes
2answers
274 views
Can the “mutual independence” condition in the Lovász local lemma be weakened?
The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows.
Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is ...
9
votes
2answers
723 views
Statistical distance between uniform and biased coin
Let $U$ be the uniform distribution over $n$ bits, and let $D$ be the distribution over $n$ bits where the bits are independent and each bit is $1$ with probability $1/2-\epsilon$. Is it true that ...
9
votes
2answers
629 views
High probability events without low probability coordinates
Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small ...
9
votes
2answers
574 views
Chernoff-type inequality for random variable with 3 outcomes
Suppose we have a random variable which takes non-numeric values a,b,c and want to quantify how empirical distribution of $n$ samples of this variable deviates from true distribution. The following ...
9
votes
3answers
554 views
Technical question about random walks
(My original question still has not been answered. I have added further clarifications.)
When analyzing random walks (on undirected graphs) by viewing the random walk as a Markov chain, we require ...
9
votes
1answer
328 views
Cover time and spectral gap for reversible random walks
I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, ...
9
votes
0answers
165 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 ...
9
votes
0answers
299 views
Beating Nonuniformity by Oracle Access
Informally, we say that a Turing machine $M(\cdot)$ approximates a function $f(\cdot)$ if their outputs on a series of inputs are indistinguishable.
More formally, let $L$ be a language, $M(\cdot)$ ...
8
votes
1answer
158 views
A bounded-independence variant of the Berry-Esseen theorem
I came across a presentation by Ryan O'Donnell regarding invariance principles. After proving the Berry-Esseen theorem, there is a slide that discusses extensions of the theorem and one that is ...
8
votes
1answer
679 views
Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables
Let $X_1,\ldots, X_n$ be $n$ i.i.d. copies of Gaussian random variable $X \sim N(0, \sigma^2)$. It is known that
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n X_j \Bigl| >t\Bigr) &...
8
votes
1answer
311 views
$k$-wise independent probability spaces
I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following:
Suppose we have $n$ random variables $Y_1, \dots, Y_n$, each of $...
