Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
5
votes
2answers
1k views

Multiplication of normal distributions

Suppose X_1, ..., X_k are iid standard Gaussian variables, for some k > 1. Then, what is the distribution of X := X_1 * ... * X_k ? Can it be approximated by a Gaussian, maybe for large k ?
7
votes
1answer
615 views

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 through the data is possible. In my case, the stream contains many duplicate values, ...
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)$ ...
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 ...
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 $...
3
votes
2answers
757 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$ ...
2
votes
1answer
100 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 ...
5
votes
1answer
543 views

Example of pairwise independent random process with expected max load $\sqrt{n}$

This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now ...
4
votes
3answers
206 views

Approximating distributions from samples

One claim I find in many papers about identity testing, and closeness testing is that any distribution over $[n]$ can be approximated to within $\ell_1$ distance $\epsilon$ in $O\left(\frac{n}{\...