23 votes
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 ...
user avatar
  • 10.4k
15 votes

Throwing Balls into Bins, estimate a lowerbound of its probability

The answer is $\Theta(\sqrt{n})$. First, let's compute $E_{n-1}$. Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability ...
user avatar
15 votes
Accepted

Calculate Huffman code length having probability?

The intended answer is probably that the length of the longest codeword is approximately $$-\log_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length ...
user avatar
15 votes
Accepted

What is the expected depth of a randomly generated tree?

I think there is a concentration result about $e \log n$, but I haven't filled in the details yet. We can get an upper bound for the probability that node $n$ has $d$ ancestors not including $0$. For ...
user avatar
15 votes
Accepted

What is the proof of this nonstandard version of Azuma's inequality?

I can't find a reference, so I'll just sketch the proof here. Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i ...
user avatar
  • 2,743
11 votes
Accepted

A flowchart for concentration bounds

Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey available at http://projecteuclid.org/euclid.im/1175266369 or at Fan Chung Graham's web page.
user avatar
10 votes
Accepted

Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic

You probably want to look at David et al's paper, Asymptotically Almost All λ-terms are Strongly Normalizing: We present a quantitative analysis of various (syntactic and behavioral) properties of ...
user avatar
10 votes
Accepted

Is there any known CCC closed under a probabilistic powerdomain operation?

The following is an extended comment, it does not answer your question in the terms you posed it but does give a semantics for higher-order probabilistic calculi which you may find of interest. In ...
user avatar
10 votes

Finding a biased coin using a few coin tosses

The following is a rather straight-forward $O(n \log n)$ toss algorithm. Assume $1-\exp(-n)$ is the error probability we are aiming for. Let $N$ be some power of $2$ that is between say $100n$ and $...
user avatar
10 votes
Accepted

What is the connection between moments of Gaussians and perfect matchings of graphs?

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 $...
user avatar
  • 3,844
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)$...
user avatar
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 ...
user avatar
  • 7,455
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 ...
user avatar
9 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 ...
user avatar
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 ...
user avatar
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 (...
user avatar
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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
8 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) = \...
user avatar
  • 4,341
7 votes

Proving properties of Random Graphs

It doesn't sound hopeful in general. For example, let $P$ be the statement "all vertices have degree 0 or 1". Let $p=1/n$ and $n$ even. Then conditioned on the event of being regular, with high ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 14.1k
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$...
user avatar
  • 3,844
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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 1,986
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'|| ...
user avatar
  • 10k
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible