# Tag Info

## Hot answers tagged pr.probability

Accepted

### "Almost all objects have property P" vs. "It is easy to test whether an object has property P"

They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance ...
• 11.1k
Accepted

Accepted

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $... • 3,899 10 votes Accepted ### Why is differential privacy defined over the exponential function? This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties: Composition: If$A(\cdot)$... • 18.1k 9 votes Accepted ### What are bounded-treewidth circuits good for? We now understand that for any fixed bound$k \in \mathbb{N}$on the treewidth, we can convert any Boolean circuit of treewidth less than$k$to a so-called d-SDNNF circuit, in linear time and with ... • 8,223 9 votes Accepted ### Upper and lower bound of binomial summation Let me denote the sum as$S_{n,p}$. It gives the probability that a random sample from the binomial distribution$B(n,p)$exceeds its expected value. For$0<p<1$constant, the central limit ... • 15.4k 9 votes Accepted ### Approximating distributions from samples I think it's a simple application of Hoeffding's inequality. Using your notation, let$Q_i = \frac1m C_i$, i.e.$Q$is the empirical distribution that approximates$P$. The total variation distance ... • 18.1k 9 votes Accepted ### Graph that maximizes minimum hitting time? It is well known that a barbell graph (two cliques of size$n/3$connected by a path of length$n/3$) has average hitting time$\Omega(n^3)$, but I believe the same applies to minimum hitting time (... • 50.5k 9 votes Accepted ### Heterogeneous Hoeffding/McDiarmid Yes. See for example the stronger concentration for the occupancy problem in the following note: http://sarielhp.org/teach/17/b/lec/10_martin_II.pdf Theorems 10.3.1 and 10.3.2. (This is also covered ... • 9,586 8 votes Accepted ### Example of pairwise independent random process with expected max load$\sqrt{n}$Here's how to do it. First, choose a random$k$between 1 and$n$to be the "crowded bin". Next, choose a random permutation$\pi$of$1,2,\ldots, n-1$. Now, for$1 \leq i \leq n-1$, $$\mbox{put ... • 23.9k 8 votes Accepted ### A bounded-independence variant of the Berry-Esseen theorem There are variants of Berry-Esseen for bounded independence, although I have not seen one which is as general as the original theorem. For example Theorem 5.1. in Diakonikolas, Kane, Nelson implies a ... • 18.1k 8 votes ### Can the "mutual independence" condition in the Lovász local lemma be weakened? The Lopsided Lovasz Local Lemma relaxes the mutual independence condition to negative dependence. We assume we have events A_1, \ldots, A_n, with a lopsidependency graph G defined on [n] s.t. ... • 18.1k 7 votes Accepted ### Number of distinct differences of \omega(\sqrt{n}) integers chosen from [n] Assume as given that m=\omega(\sqrt{n}). Fix any \epsilon>0. We will consider r\in[1,n] with r<(1-\epsilon)n. The aim is to show that with high probability as n\to\infty, r is ... • 186 7 votes Accepted ### Which graph parameters are NOT concentrated on random graphs? Many parameters of the largest connected component are not concentrated for G(n,p) if p=1/n and more generally if p is in the critical window. Examples are the diameter and the size of the ... • 441 7 votes ### Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables See Theorem 23 in Section 9.3 of Ryan O'Donnell's book Analysis of Boolean functions. Even though the theorem there is stated for \pm 1 variables, it holds for Gaussians as well (see Chapter 10 of ... • 14.2k 7 votes Accepted ### Statistical distance between uniform and biased coin Denote the random bits by x_1,\dots, x_n. By definition, the statistical distance between U and D is at least \Pr_U\left(\sum x_i \geq t\right) - \Pr_D\left(\sum x_i \geq t\right) for every t... • 3,899 7 votes ### Expected Kolmogorov complexity under Kolmogorov complexity distribution If \alpha is the answer to the 1st question then \alpha=\infty. Namely, for any c there is an n such that all strings w of length at least n have K (w) \ge c. In particular the ... • 4,445 7 votes Accepted ### Reference for the number of samples needed to distinguish two probability distributions So here, you only have two options: either your samples come from p, or from q (and you know explicitly both). By definition of the statistical/total variation distance, we have$$ d_{TV}(p,q) = \... • 4,381 6 votes ### Which graph parameters are NOT concentrated on random graphs? Failure to concentrate happens for some counting ($\#\mathsf{P}$) properties, and maybe for many of them. A simple example is the number of spanning subgraphs ($2^m$). The number of edges of a random ... • 50.5k 6 votes ### Can the "mutual independence" condition in the Lovász local lemma be weakened? The formulation on p.70 of the 4th edition of The Probabilistic Method by Alon and Spencer is along the lines you state. • 2,039 6 votes Accepted ### Statistical Distance Growth Given K Independent Copies See the "inclusion-exclusion" Lemma 2.2 here https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf . For distributions$p,q,p',q', we have $$||p\otimes q-p'\otimes q'|| \le ||p-p'|| + ||q-q'|| - ||p-p'|| ... • 10.2k 6 votes Accepted ### Isolation Lemma over finite fields Here is an alternative (and, hopefully, simpler) proof of Neal Young’s argument. To simplify the presentation, I take the set \def\S{\mathcal S}\S of all 2^n-1 nonempty subsets of [n], and a ... • 15.4k 5 votes Accepted ### Reservoir sampling of distinct values This is something that min-wise independent hashing is good for. (See a wikipedia explanation here. The idea is to use a family \mathcal{H} of hash functions so that when you pick a random function ... 5 votes Accepted ### Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p) Write$$\begin{align} h^2(B(n,p), B(n+1,p))& = 2 \left(1 - \sum_{i=0}^{n+1}\sqrt{{n \choose i}p^i(1-p)^{n-i}{n+1 \choose i} p^i (1-p)^{n+1-i}}\right)\\ &=2\left(1 - \sum_{i=0}^{n+1}\sqrt{\left(... 5 votes ### Reverse Chernoff bound The Generalized Littlewood-Offord Theorem isn't exactly what you want, but it gives what I think of as a "reverse Chernoff" bound by showing that the sum of random variables is unlikely to fall within ... • 11.9k 5 votes ### An upper bound for chi-square divergence in terms of KL divergence for general alphabets Your definition of\chi^2$divergence is missing a term; namely, $$\chi^2(P\|Q) = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ} - 1\right)^2 = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1$$ (... • 4,381 5 votes ### Statistical distance between uniform and biased coin A somewhat more elementary, and slightly messier proof (or at least it feels so to me). For convenience, write$\varepsilon = \frac{\gamma}{\sqrt{n}}$, with$\gamma\in [0,1)$by assumption. We ... • 4,381 5 votes ### What is the connection between moments of Gaussians and perfect matchings of graphs? Here is a different proof, adapted from the monograph The semicircle law, free random variables and entropy. Let$X_i$be an infinite sequence of i.i.d. variables with distribution$\Pr[X_i = 1] = \Pr[...
• 14.2k
Lemma. In the unbounded case, the expected number of flips is at most $\sqrt t + 3/2$. Proof. Let r.v. $F$ be the number of flips until a head. Then the expected number of flips is \begin{align} E[F]...