# Questions tagged [pr.probability]

Questions in probability theory

17 questions
Filter by
Sorted by
Tagged with
5k views

486 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 ...
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 ...
2k 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 ?
796 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, ...
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$ ...
107 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 ...
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 ...
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)$ ...
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 $... 1answer 626 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 ... 3answers 215 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}{\...
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 ...