Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
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 ...
31
votes
6answers
4k 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 ...
30
votes
4answers
3k 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
475 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 ...
23
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
519 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
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
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 $\...
21
votes
1answer
645 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
529 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
476 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
995 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$...
19
votes
0answers
492 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
576 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
520 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 ...
16
votes
0answers
254 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
233 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 ...
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
2answers
367 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 ...
13
votes
1answer
393 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 ...
12
votes
3answers
2k 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 ...
12
votes
6answers
694 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
1answer
661 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 ...
12
votes
2answers
2k 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
971 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 ...
12
votes
2answers
510 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 ...
11
votes
1answer
429 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
370 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
349 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
462 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
512 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
263 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
242 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
608 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
607 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
536 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
511 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
302 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
154 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
296 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
151 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
580 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
232 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 $...
8
votes
1answer
178 views

Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is ...