23
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 of 3SAT. It's clear that testing whether $x$ satisfies $P$ is NP-hard, yet almost all strings satisfy it: the density $\to 1$ as $n \to \infty$.
15
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 comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ k!}$....
15
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 of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword.
One can see this by constructing a ...
15
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 each possible complete chain of $d$ nonzero ancestors $(a_1,a_2,...,a_d)$, the probability of that chain is $(\frac{1}{a_1})(\frac{1}{a_2})\cdots (\frac{1}{a_d}...
15
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 \in \{1,\cdots,n\}$ and all $(x_1,\cdots,x_{i-1})$ in the support of $(X_1, \cdots, X_{i-1})$, we have
$\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \...
11
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.
10
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 the past few years there has been a very active line of research around so-called quantitative denotational semantics of linear logic, based on the idea (...
10
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 $200n$ (just some big enough constant times $n$). We maintain a candidate set of coins, $C$. Initially, we put $N$ coins in $C$.
Now for $i=1,\dots,\log N$, do ...
10
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 $c_{ij} = {\mathbb E}[\gamma_i \gamma_j]$ be the covariance of $\gamma_i$ and $\gamma_j$. Consider the complete graph on $\{1, \dots, 2n\}$; assign weight $c_{...
10
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)$ is an $\varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(\cdot, a)$ is an $\varepsilon'$-DP algorithm, then the composed algorithm $A' \circ ...
9
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 random λ-terms. Our main results show that asymptotically, almost all terms are strongly normalizing and that any fixed closed term almost never appears in a ...
9
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 the dependency on $k$ being singly exponential.
The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), ...
9
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 theorem tells you that $B(n,p)$ looks like the normal distribution $N(pn,p(1-p)n)$ for large $n$. Since this is symmetric, $S_{n,p}$ will be approximately $1/2$ as ...
9
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 ball } i \mbox{ into bin }
\begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\
k + \pi(i) \mbox{ with probability }1 - \frac{...
9
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 between $P$ and $Q$, i.e. half the $\ell_1$ distance, is
$$
\max_{S \subseteq [n]} \left| \sum_{i \in S}{P_i} - \sum_{i \in S}{Q_i}\right|.
$$
Let $P(S):= \sum_{...
9
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 (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the ...
9
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 in the Randomized Algorithm book by Motwani and Raghavan).
The version stated here is the martingale version, but it is the same thing...
8
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 Berry-Esseen theorem for weighted sums of Bernoulli random variables with bounded independence, as long as none of the weights is too large. If you want error $\...
8
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. for every event $A_i$ and every $S \subseteq [n] \setminus \Gamma^+(i)$,
$$
\Pr\left(A_i \mid \bigwedge_{j \in S}{\bar{A_j}}\right) \le \Pr(A_i).
$$
As you (sort ...
8
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) = \sup_S( p(S)-q(S))
$$
where the supremum is taken over all measurable sets $S$. I haven't looked at the paper, but assuming all is nice (finite), the $\sup$ is ...
7
In general, it seems that you cannot get the concentration you want without more constraints on the probabilities.
Consider the following graph on $n$ vertices. Let vertices $C = \{2,\ldots,n\}$ form a clique such that for all $i,j \in C$, $p_{ij} = 1$. Let vertex $1$ be connected to this clique via only one edge, with $p_{1,2} = 1/\log(n)$, and $p_{1,j} =...
7
If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions. If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then ...
7
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 probability the graph is 0-regular or 1-regular, so $P$ holds with high probability. Also $P$ is preserved by removing edges. But it is certainly not the case that $...
7
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 included in the set of differences.
First consider the set $A=\{a_i:i<m/2\}\cap[1,\epsilon n]$. The number of $i$ with $i<m/2$ such that $a_i<\epsilon n$ ...
7
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 largest component, the size of the second largest component, the number of leaves the component has, etc.
See e.g.
Aldous, David. "Brownian excursions, critical ...
7
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 the book for details on that).
For the more general statement, see Exercise 7 in these lecture notes of Terry Tao.
7
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$. We choose $t = n/2 + \sqrt{n}$.
Note that $\Pr_U\left(\sum x_i \geq t\right) \geq c_1$ for some absolute constant $c_1 > 0$. If $\Pr_D\left(\sum x_i \...
7
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 expectation of $K (w) $ with respect to any distribution on strings of length $n $ is $\ge c $.
Similarly if $\beta$ is the answer to the 2nd question then $0\le\...
6
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 graph fluctuates by $\pm \Theta(n)$ so the number of spanning subgraphs fluctuates by a factor of $2^{\Theta(n)}$, well away from the $(1+\epsilon)$ factor you ...
6
The formulation on p.70 of the 4th edition of The Probabilistic Method by Alon and Spencer is along the lines you state.
Only top voted, non community-wiki answers of a minimum length are eligible